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.

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.
| |
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.
| |
(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
1for 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 toreturn 0. Every human turn looked like a draw, so the bot never saw a threat coming. trueinstead offalse. InmakeMoveI passedisBotTurn = trueright 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.
| |
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!
| Grid | Empty cells | Ways to play out the board | Compared to 3×3 |
|---|---|---|---|
| 3×3 | 9 | 362,880 | 1× |
| 4×4 | 16 | ~20.9 trillion | ~58 million× |
| 5×5 | 25 | ~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)

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 works | Hand-written tic-tac-toe knowledge | Tries every possible game |
| Speed | Instant | Slower (it searches everything) |
| Looks ahead | Only Fork and BlockFork | Every move, to the end of the game |
| Works on | 3×3 only, really | Any 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
