Tic-Tac-Toe Minimax: the machine that refuses to lose
Play noughts and crosses against a machine that reads every possible future and never loses. Watch it score each move, win, draw, or loss, before it plays.
This week the AI stops guessing and starts calculating. The perceptron learned, the Markov babbler counted; today’s guest does neither. It searches.
The gadget below plays tic-tac-toe with a perfect strategy called minimax. Before every move it looks at the whole game, every move it could make, every reply you could give, all the way to the last empty square, and then picks a move that cannot lose. Go ahead and try to beat it. You can’t. The best you will ever manage is a draw.
How to play:
- Choose whether you play X (you go first) or O (the machine goes first).
- Tap a square. The machine answers at once.
- Watch the panel beside the board: it lists every square the machine weighed this turn and the guaranteed outcome with perfect play, machine wins, draw, or machine loses, and marks the one it chose.
Search, not learning
Minimax is beautifully dumb. It has no experience, no training, no data. It simply assumes both players are perfect, plays out every branch of the game tree, and scores each ending: +1 if the machine wins, −1 if it loses, 0 for a draw. Then it takes the branch with the best guaranteed score. That is the whole trick.
This is the other great family of early AI, the one that had nothing to do with neurons. It runs from Claude Shannon’s 1950 sketch of a chess-playing machine straight to Deep Blue, the IBM computer that beat world champion Garry Kasparov in 1997 by searching millions of positions with hand-tuned rules, brute-force lookahead, not learning.
Why it stops at tic-tac-toe
Tic-tac-toe has only 255,168 possible games, so a laptop reads all of them in a blink. Chess has more positions than there are atoms in the observable universe, so Deep Blue could only peer a few dozen moves ahead and lean on a clever evaluation function. Go is vaster still, which is why beating it needed a different idea altogether: the search-plus-learning hybrid behind AlphaGo in 2016.
So enjoy your unwinnable game. It is the smallest, purest example of good old-fashioned AI: a machine looking brilliant simply by being thorough.
Missed the earlier editions? Train a perceptron in the browser or watch a Markov chain babble.