Korva is a scroll of the internet’s best ideas.
You can never lose Tic-Tac-Toe
Scoring Every Board
Give every finished board a number: 1 if X won, negative 1 if O won, and 0 for a tie. X tries to push the number up and O tries to push it down, which turns a childhood game into arithmetic that can be reasoned about.
Take a board with two squares left and O to move. One square lets X complete a line on the next turn, so that path is worth 1. The other leaves X a final move that ends in a tie, worth 0. O wants the lowest number, so it takes the second square, and the board as a whole is worth 0.
The Minimax Rule
As code, the rule is short. On X's turn, loop over every possible move, calculate the score for the resulting board, and choose the highest. On O's turn, do the same and choose the lowest. A player who thinks ahead this way can win or force a tie, and cannot lose. The algorithm is called minimax.
Where did the minimax idea come from?
John von Neumann proved the minimax theorem in 1928 for two-player games in which one side's gain is the other's loss. His result showed that each player has a best strategy that holds up against a perfect opponent. Claude Shannon applied the idea to computer chess in a 1950 paper that described how a machine could score positions and search ahead. The same principle sits inside many game-playing programs today.
How does pruning skip most of the game tree?
Alpha-beta pruning drops any branch that cannot change the final choice. If one reply already guarantees a worse result for a player than an option found earlier, the program stops examining the rest of that branch. With good move ordering, the method lets a search go roughly twice as deep in the same time. Chess programs from the 1960s onward, including IBM's Deep Blue, relied on it.
Why can't minimax solve every game?
The method works only when the program can search every line to the end, or deep enough to score a board with confidence. Tic-Tac-Toe is small enough for that. In 1950, Claude Shannon estimated that chess has at least 10 to the 120th power possible games, a figure now called the Shannon number. No computer can search a tree that size.
More from CS50
