The thinking-ahead game
I'm an AI that plays tic-tac-toe by imagining every possible future. You're X, I'm O. Tap a square to start!
Same position, different brains — what each thinking depth would have played. Tap one to use it.
Make a move and the AI will show what each brain would have chosen.
How it works
Imagine my moves
For every empty square, I picture myself playing there. That's the first row of the tree.
Imagine your replies
For each of my moves, I picture every reply you could make, then my answers, all the way to the end.
Score the endings
An ending where I win is good, a draw is okay, and a loss is bad.
Assume you play well
For each of my moves, I assume you'll find your best reply. That's my "worst case".
Pick the best worst-case
I play the move whose worst case is the best. That's called minimax.
What just happened?
- The AI didn't practise or learn. It searched: it imagined the future and picked the safest move.
- Looking only 1 move ahead, it can't see your traps, so it's easy to beat. Looking all the way, it never loses. The best you can do is draw!
- Pruning gave the same answer with far fewer positions. Smart skipping beats brute force.
- This is a different kind of AI from the neural networks earlier in the course. Real game AIs often combine both.
For grown-ups: what's really going on
This is minimax search on the full game tree of tic-tac-toe, classical (symbolic) AI. No data and no training are involved.
- Values: from the AI's side, a win in p plies scores
10 − p, a lossp − 10(so faster wins and slower losses are preferred), and a draw 0. The AI picks the move maximising the minimum guaranteed result, assuming the opponent minimises. - Depth limit: beyond the horizon the search returns 0 ("can't tell"), the simplest evaluation function. With depth 1 it only spots an immediate win; depth 2 also blocks immediate threats; deeper depths see forks. Exhaustive tests: depth 9 lost 0 of 569 games against every possible human line; depth 1 lost 329 of 649.
- Alpha-beta pruning: keeps a window (α, β) of results that could still matter and stops exploring a node once it can't change the parent's choice. It returns the same move as plain minimax, here with roughly 90% fewer positions (about 59,700 down to about 4,000 after a corner opening). Moves are searched in index order; better move ordering would prune even more.
- Ties: equal-valued moves are chosen at random so the AI doesn't play the same game every time. The pruning window is widened by one so tied moves still get exact values.
- Scale: tic-tac-toe has fewer than 550,000 game positions. Chess has around 1044, so real engines add strong evaluation functions, move ordering, and (in AlphaZero and Leela) a learned neural network to guide the search.