In Part 1, I built a tic-tac-toe bot with a layered brain: 7 small strategies, asked one by one. It worked. I couldn’t beat it anymore. But it was hard to scale. A bigger board needs more conditions, and every new condition is one more place for things to break.

It also couldn’t really look ahead. Only two of the strategies, Fork and BlockFork, thought about the next move. The rest just read the board as it is right now.

So this time I threw all 7 rules away to make a single rule.


The idea: play every game

Instead of teaching the bot tic-tac-toe, we let it imagine every possible game from here, and pick the move that leads to the best ending.

Every finished game gets a score:

  • Bot wins → positive
  • Human wins → negative
  • Draw → 0

Then both players take turns inside the bot’s head. On the bot’s turn, it picks the highest score (maximize). On the human’s turn, it assumes the human picks the lowest (minimize). That’s where the name comes from: minimax.

One thing to be clear about: the bot doesn’t play for the “highest chance” of winning. It assumes the human plays perfectly, and picks the best result it can guarantee.

I didn’t come up with this. It’s a classic algorithm, I just happened to read about it and implement it. It also has a few variations that make it even better, more on those at the end.

Tic-tac-toe minimax tree example: the bot tries all 3 moves, the human’s replies keep the lowest score, and the bot picks the win at +10


How the minimax algorithm works

makeMove: try every cell

makeMove is the bot’s turn. We go over the board, and for every empty cell we place the bot there, ask minimax how good that is, and take the move back. The cell with the best score is our move.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
for (int i = 0; i < board.getSize(); i++) {
    for (int j = 0; j < board.getSize(); j++) {
        if (!board.getCell(i, j).isEmpty()) continue;

        // bot just moved here, so it's the human's turn next
        Cell cell = board.getCell(i, j);
        cell.setPlayer(bot);
        int current = minimax(board, 0, false, bot, winCheck);
        cell.clearCell();

        if (score < current) {
            score = current;
            bestMove = cell;
        }
    }
}

Notice the false. The bot has just moved, so minimax starts from the human’s reply.

minimax: base conditions first

minimax uses recursion, and the first thing a recursive approach needs is a base condition. I repeat: don’t forget to add an exit condition to a recursive function.

Before anything else, minimax checks if the game is already over: bot win, human win, or a draw. If it is, it returns the score.

If not, we keep playing. On the bot’s turn we try every empty cell with the bot and keep the highest score. On the human’s turn we do the same with the human and keep the lowest.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
if (winCheck.isWinner(bot))   return 10 - depth;
if (winCheck.isWinner(human)) return depth - 10;
if (winCheck.isDraw())        return 0;

if (isBotTurn) {
    int maxValue = Integer.MIN_VALUE;
    // for every empty cell:
    cell.setPlayer(bot);
    maxValue = Math.max(maxValue, minimax(board, depth + 1, false, bot, winCheck));
    cell.clearCell();
    return maxValue;
} else {
    // same thing with the human, using Math.min
}

(Ignore the depth for now, we’ll get to it.)

Place, try, take it back

This is the part that makes it “imagining”. The bot plays moves on the real board, and takes each one back right after: setPlayer → minimax → clearCell.

If you forget the clearCell, every imagined move stays on the board, and by the end of the search the board is full of pieces nobody really played.

You could make a copy of the board and use that too, so that your real games don’t get affected.


The bugs I hit

My first version had the right idea, but it was full of small mistakes:

  • The win check didn’t say who won. It returned 1 for any winner, so to the bot, the human winning looked just as good as the bot winning.
  • No undo. I set cells but never cleared them, so tried moves piled up on the board.
  • The min branch never returned. It computed minValue, then fell through to return 0. Every human turn looked like a draw, so the bot never saw a threat coming.
  • true instead of false. In makeMove I passed isBotTurn = true right after the bot’s move, so the bot played twice in a row in its own head.

Why makeMove has its own loop

This was my first question. minimax already loops over the cells on the bot’s turn. Why not just call it once from makeMove?

Because minimax only returns a score. It can tell you “the best the bot can get is a draw”, but not which cell gets there. By the time it returns, every cell has been cleared again.

And what if we keep the loop, but don’t set the cell? Then every call sees the exact same board, every cell gets the same score, and the bot always picks the first empty cell. Setting the cell is what makes the score belong to that cell.

(You can make minimax return the cell too, but the cell only matters at the top level. Deeper down, the number is all you need.)


Problem 1: the bot can look silly → depth scoring

With plain 1 / -1, a win right now and a win three moves from now look exactly the same to the bot. So sometimes it skips the obvious win and takes the long route. It still wins, but to a human it looks like a mistake.

The fix: count how deep we are in the search, and use it in the score.

1
2
if (winCheck.isWinner(bot))   return 10 - depth;   // sooner win = higher score
if (winCheck.isWinner(human)) return depth - 10;   // later loss = less bad

Now the bot prefers the fastest win. And if it’s ever losing, it picks the slowest loss and makes the human work for it.


Problem 2: it’s slow on bigger boards → depth limit and alpha-beta pruning

Minimax tries every possible game. On 3×3 that’s fine, the first move on an empty board takes well under a second. On 4×4 the number of games explodes.

Here’s how fast it grows. The first move has every cell to pick from, the next one has one less, and so on. So the number of ways to play out a full board is cells × (cells - 1) × … × 1, or cells!

GridEmpty cellsWays to play out the boardCompared to 3×3
3×39362,8801×
4×416~20.9 trillion~58 million×
5×525~1.55 × 10²⁵~43 billion billion×

This is an upper bound. Real games end early when someone wins, so the bot searches fewer. But the growth is the point: one extra row and column, and 3×3’s “well under a second” turns into millions of times more work.

The usual fix is a depth limit: stop searching after a few moves and estimate how good the board looks. That needs a way to score unfinished boards, which my code doesn’t have yet. Another fix is alpha-beta pruning, which skips branches that can’t change the result.

On 3×3 the bot doesn’t need either, so I’ve left both out.


Seeing it think

I also added one small print to the bot, so every move says which strategy picked it:

BOT is playing 0 0 (by MiniMaxStrategy)

Terminal output of a game where every bot move ends with (by MiniMaxStrategy)


Is it really unbeatable?

Instead of trusting my own games against it, I made two bots play each other: 100 games per match, swapping who moves first every game.

  • Against my Part 1 rule-based bot (win → block → fork → block fork → center → corner): 100 draws. Both sides play almost perfectly, so nobody wins.
  • Against a bot that just makes random moves: 88 wins, 12 draws, 0 losses. Minimax wins when the opponent makes mistakes.
Results after 100 games:        Results after 100 games:
ALICE (rules) wins: 0           RANDY (random) wins: 0
BOB (minimax) wins: 0           CAROL (minimax) wins: 88
Draws: 100                      Draws: 12

200 games, zero losses. The best anyone can do against it is a draw.


Rules vs minimax

My rules (Part 1)Minimax
How it worksHand-written tic-tac-toe knowledgeTries every possible game
SpeedInstantSlower (it searches everything)
Looks aheadOnly Fork and BlockForkEvery move, to the end of the game
Works on3×3 only, reallyAny board (with a depth limit)

Wrapping up

Same unbeatable bot. Zero tic-tac-toe knowledge. Seven rules replaced by one recursive function.

If you want to take it further, alpha-beta pruning and a depth limit are where to start.

The full code is on GitHub: system-design/lld/tic-tac-toe