You Can Never Lose at Tic-Tac-Toe If You Do the Math
Perfect play at Tic-Tac-Toe takes 255,000 possibilities, but chess and Go quickly run into the billions and quintillions.
CS50 · CS50x 2025 - Artificial IntelligenceYou never have to lose at Tic-Tac-Toe. There is a strategy that guarantees at worst a tie, and computer science teacher David Malan says if you do lose, you played it wrong.
The trick is to turn the playground game into arithmetic. Give every finished board a score. If X gets three in a row, the board is worth plus 1. If O gets three in a row, it is worth minus 1. If nobody wins, it is worth zero. X now wants the biggest number possible, and O wants the smallest.
From there the choice is mechanical. On your turn, ask first whether you can win immediately. If not, ask whether your opponent could win on the next turn, and block that square. When the answer is neither, look ahead.
Malan calls the method minimax, for minimizing and maximizing. Imagine two squares are left and it is O's turn. One move leads, after X's forced reply, to an X win worth 1. The other move leads to a tie worth zero. O wants the minimum, so O picks zero. Work that logic backward, square by square, and an unfinished board inherits the value of the ending it must lead to.
The count of possible games grows fast. Each extra empty square roughly doubles the tree of possibilities. A simple 3-by-3 board, the kind children doodle on napkins, offers 255,000 possible games. That is trivial for a modern laptop, but impossible to hold in a human head.
Scale up slightly and perfect calculation breaks down. Just the opening four turns for each side in chess can be played in more than 85 billion ways. Go, with its much larger board, has 266 quintillion possible games. With today's computers, no machine can draw the whole tree.
So computers stop solving and start approximating. They sample branches, estimate scores, and make their best educated guess. That gap, between a tiny game that math can finish and vast games it cannot, is why researchers needed learning systems rather than rule books.
Questions people ask
If Tic-Tac-Toe can always be tied, why do people still lose?
They miss a block or a forced win. Malan notes the further you rewind toward the start, the less obvious the right move gets. The guarantee holds for the player who follows the method all the way to the end, whatever the opponent does.
How do chess computers play well if they cannot see every move?
They search as many moves ahead as time allows, score the resulting positions with estimates, and pick the move with the best score. Strong programs also prune hopeless branches and remember patterns from past games. That lets them play well without solving the game perfectly.
What makes Go so much harder than chess?
The board is much bigger, with 361 starting points instead of 64 squares, and stones are placed rather than moved. That creates far more legal moves at each turn, so the number of possible games grows much faster. Modern Go programs rely heavily on neural networks to judge positions without searching every branch.