In my last post I showed my robot arm playing a full game of tic-tac-toe. A minimax search works out the best moves, Gemini picks one of them, and the arm places the piece. I skimmed over the minimax part there. This post digs into it properly, with worked examples and the real code from the GitHub repo.
To keep myself honest, I wrote a small Python version of the same algorithm, using the same scoring as the arm’s code, and ran it to produce every number in this post.
Numbering the board
The arm’s code numbers the squares 1 to 9, left to right, top to bottom. I’ll use the same layout throughout:
1 | 2 | 3
---+---+---
4 | 5 | 6
---+---+---
7 | 8 | 9The arm always plays X and I play O. Either of us can go first.
The game tree
Minimax starts from a simple idea. From any position, list every legal move. For each of those moves, list every reply. Keep going until every line ends in a win, a loss or a draw. What you get is a game tree: the current position at the root, every possible future spreading out below it, and finished games at the leaves.
Once you have the tree, you can work backwards from the leaves to the root and find the best move, provided you assume both players always play their best.
The maximiser and the minimiser
Every finished game gets a score from X’s point of view. Positive is good for X, negative is good for O and zero is a draw.
X is the maximiser. On X’s turn, it picks the move with the highest score. O is the minimiser. On O’s turn, it picks the move with the lowest score, because the lowest score for X is the best result for O.
That’s the whole trick. A position’s score is the best score the player to move can guarantee, assuming the opponent also plays perfectly. Scores flow up the tree, alternating between max and min at each level.
Scoring finished games, with a depth twist
If every win scored the same, the search wouldn’t care whether it wins now or in five moves. It would also see no difference between losing next turn and losing much later. So the arm’s code in tic_tac_toe_rules.h adjusts each score by depth, the number of moves played in the search so far:
inline int minimax(Board &board, char player, int depth, int alpha, int beta) { char winner = board.winner(); if (winner == 'X') return 10 - depth; if (winner == 'O') return depth - 10; if (board.full()) return 0;
An X win scores 10 minus the depth, so a faster win scores higher. An O win scores the depth minus 10, so a slower loss is less bad. A full board with no winner scores 0.
The candidate X move itself counts as depth 1. So an immediate win scores 10 − 1 = 9. If O wins straight after, that’s depth 2 and scores 2 − 10 = −8. A loss two moves further away scores −6, and so on. Keep those numbers in mind for the examples.
The algorithm in pseudocode
function minimax(board, player, depth): if X has won: return 10 - depth if O has won: return depth - 10 if board is full: return 0 if player is X: best = -infinity for each empty square: play X there best = max(best, minimax(board, O, depth + 1)) undo the move else: best = +infinity for each empty square: play O there best = min(best, minimax(board, X, depth + 1)) undo the move return best
To pick X’s move, you try each empty square, score it by calling minimax for O’s reply at depth 1, and keep the highest score. The real code also uses alpha-beta pruning, which I’ll come to shortly, but it returns the same answers.
Example 1: the immediate win
X has squares 1 and 2. O has 4 and 5. It’s X’s turn:
X | X | 3
---+---+---
O | O | 6
---+---+---
7 | 8 | 9Here’s what minimax gives each empty square:
| X plays | Score | Why |
|---|---|---|
| 3 | 9 | Completes the top row. X wins at depth 1. |
| 6 | 0 | Blocks O’s middle row, but X misses its own win. Perfect play from there is a draw. |
| 7 | −8 | O plays 6 and wins straight away at depth 2. |
| 8 | −8 | Same: O plays 6 and wins. |
| 9 | −8 | Same again. |
Square 3 scores highest, so X takes the win. This is one of the cases the code’s own self-test checks: the score must be 9, and square 3 must be the only best move.
Look at square 6 too. Without minimax you might call it a “safe” move. Minimax shows it throws away a win.
Example 2: the forced block
O has squares 1 and 2. X has the centre. It’s X’s turn:
O | O | 3
---+---+---
4 | X | 6
---+---+---
7 | 8 | 9| X plays | Score | Why |
|---|---|---|
| 3 | 0 | Blocks the top row. Perfect play from there is a draw. |
| 4, 6, 7, 8 or 9 | −8 | O plays 3 and wins at depth 2. |
X has no winning threat of its own, so every move except 3 loses immediately. Minimax doesn’t need a special rule for blocking. It simply sees that every other line ends in a loss.
Example 3: the fork trap
This one surprised me the first time. O has taken opposite corners, 1 and 9. X has the centre. It’s X’s turn:
O | 2 | 3
---+---+---
4 | X | 6
---+---+---
7 | 8 | OThe natural instinct is to grab another corner. Minimax says otherwise:
| X plays | Score | Why |
|---|---|---|
| 2, 4, 6 or 8 (an edge) | 0 | Creates an X threat O must answer. Perfect play draws. |
| 3 or 7 (a corner) | −6 | X threatens the diagonal, so O must block in the other corner. That block gives O two winning lines at once (a fork). X can only block one, and O wins at depth 4. |
A −6 rather than −8 tells you the loss isn’t immediate. It’s two moves further away, but just as certain. The code’s self-test checks this position too, expecting the four edge squares and only those.
Openings, and why perfect play draws
On an empty board, all nine squares score 0. Whatever X does first, a perfect O can force a draw, and a perfect X can always avoid losing. That’s why the game is famously a draw between two good players.
The replies to an opening are less even. Here are the results for X’s reply when O opens:
| O opens on | X replies that draw (score 0) | X replies that lose |
|---|---|---|
| 5 (centre) | 1, 3, 7, 9 (corners) | 2, 4, 6, 8 (edges), each −4 |
| 1 (corner) | 5 (centre) only | every other square, each −4 |
A −4 means O can force a win at depth 6, three moves deep for each side. Those are exactly the traps that catch casual players. Minimax sees them because it looks all the way to the end of every line.
How big is the tree?
I counted the full tree from an empty board with the Python script:
- 255,168 possible complete games, if play stops as soon as someone wins.
- Of those, 131,184 are won by the player who moves first, 77,904 by the second player, and 46,080 are draws.
- 549,946 positions visited in total, counting the empty board, if you walk every branch without shortcuts.
- But only 5,478 distinct legal positions, because many move orders reach the same board.
- For comparison, 9! = 362,880 is the number of ways to fill all nine squares in order. The real game count is lower because many games end early.
Half a million positions is nothing for a PC. On a microcontroller it’s worth trimming, which brings us to pruning.
Alpha-beta pruning, briefly
Alpha-beta pruning gives the same answer as plain minimax while skipping branches that can’t change the result. It tracks two numbers as it searches. Alpha is the best score X can already guarantee, and beta is the best score O can already guarantee. If a branch can’t beat what a player already has elsewhere, there’s no point exploring it. Here’s how the arm’s code does it:
if (player == 'X') {
if (score > best) best = score;
if (best > alpha) alpha = best;
} else {
if (score < best) best = score;
if (best < beta) beta = best;
}
// The opponent already has a better line elsewhere. Stop exploring.
if (alpha >= beta) break;When I ran the same pruned search in Python, scoring every opening move from the empty board, it visited about 34,000 positions instead of roughly 550,000. Each candidate move still gets its exact score, because the code starts each one with a fresh window of −100 to 100.
Returning every equally good square
This is where the arm’s code differs from most textbook versions. Instead of returning a single best move, bestMovesForX() returns every square that ties for the top score, packed into a bitmask:
int score = minimax(board, 'O', 1, -100, 100);
board.cells[square] = 0;
if (score > result.score) {
result.score = score;
result.squares = 0; // a strictly better score drops the previous ties
}
if (score == result.score) result.squares |= uint16_t(1) << square;Some examples from above:
- Empty board: all nine squares, mask 0x1FF.
- Example 1: square 3 only.
- Example 3: squares 2, 4, 6 and 8.
- O opens in the centre: squares 1, 3, 7 and 9.
In robotMove() in main.cpp, that list goes to Gemini in the prompt with an instruction to choose only from it. Then the reply is checked: if Gemini names a square that isn’t in the set, the move is rejected and the arm doesn’t budge. When there’s only one right answer, Gemini has nothing to decide. When there are several, it gets some freedom, but it can never pick a losing move.
Wrapping up
Minimax is one of those ideas that looks almost too simple: score the endings, then take turns choosing the max or the min on the way back up. Tic-tac-toe is small enough to search completely, which makes it a great way to see the idea working end to end. The depth adjustment makes the arm win quickly and fight on when it’s behind, and alpha-beta pruning makes it practical on a small board.
If you want to experiment, the code is in the repo. Try changing the scoring, or set up the fork position on your own board and see if you can beat it.
