DEV Community

Devanshu Biswas
Devanshu Biswas

Posted on

I Built a Tic-Tac-Toe AI That Literally Cannot Lose

#javascript #gamedev #beginners #algorithms

Tic-tac-toe feels trivial — until you try to write an opponent that never loses. The trick is an algorithm called minimax, and it's the same idea underneath the engines that beat chess grandmasters.

Games are trees

Any turn-based game is a tree. The current board is the root, each legal move is a branch to a new board, and those branch again for the opponent's replies. A full game is one path from the root down to a leaf where someone has won or the board is full. Tic-tac-toe's tree is tiny — at most nine moves deep — so a computer can walk the entire thing instantly. That completeness is why perfect play is possible.

Scoring the endings

We only truly know the value of finished games. Score them from the AI's point of view: a win for the AI is +10, a win for you is −10, a draw is 0. Every other position's value is figured out by assuming perfect play from there.

Minimax: assume both sides are perfect

The two players want opposite things. On the AI's turn it takes the maximum child score; on your turn it assumes you'll take the minimum (best for you). Recurse to the leaves and bubble those choices back up:

function minimax(board, isAI) {
  const w = winner(board);
  if (w) return w === AI ? 10 : w === HUMAN ? -10 : 0;
  const scores = empties(board).map(i => {
    board[i] = isAI ? AI : HUMAN;
    const s = minimax(board, !isAI);
    board[i] = "";
    return s;
  });
  return isAI ? Math.max(...scores) : Math.min(...scores);
}
Enter fullscreen mode Exit fullscreen mode

Win sooner, lose later

Plain minimax treats all wins as equal, so the AI might toy with you or walk into an instant loss. Fold the search depth into the score — subtract it from a win, add it to a loss — and it prefers fast wins and stalls losses:

if (w === AI)    return  10 - depth;
if (w === HUMAN) return -10 + depth;
Enter fullscreen mode Exit fullscreen mode

Why it's unbeatable

Tic-tac-toe is a solved game: perfect play by both sides always ends in a draw. Minimax plays perfectly, so it takes any win you hand it and steers everything else to at worst a tie. The best you can ever get is a draw.

For bigger games like chess you can't search to the end — you add alpha-beta pruning to skip hopeless branches and a heuristic to estimate positions at a depth limit. But the min/max skeleton is identical.

Play the unbeatable version (and an "easy" random mode) here, with the full walkthrough:
https://dev48v.infy.uk/game/day22-tic-tac-toe.html

Top comments (0)