Game Theory

This article records tradition as it has been passed down and reported. Its sources are not yet part of the atlas's verified catalogue.

In 1950, Claude Shannon published a paper with a modest title, Programming a Computer for Playing Chess, that founded computer chess as a field before a single working chess program existed to test it against. Buried in the paper is a calculation Shannon almost certainly meant as an aside: an estimate of how many distinct games of chess are possible, arrived at from roughly 30 legal choices per move and a typical game running 40 moves per side. The number that falls out, on the order of 10 to the 120th power, is now called the Shannon number, and it is not a claim about how many games have been played or ever will be. It is a claim about why a certain kind of solution to chess was never going to work. A player, or a computer, considering the full game tree, every possible sequence of moves from the current position to the end of the game, cannot simply enumerate all of them and pick the best line, because there are more of them than there are atoms usually estimated to exist in the observable universe. Shannon's own point was not that chess is unsolvable in principle; two-player games of perfect information with no chance element are, in a strict mathematical sense established well before Shannon wrote, always solvable by exhaustive search given enough time. His point was that no amount of raw computing power anyone would ever plausibly build could do that exhaustive search directly, which meant a chess-playing program would have to evaluate positions heuristically rather than by looking all the way to the end. Every chess engine built since, from the first primitive programs of the 1950s through the systems that eventually beat human world champions, has been an answer to the problem Shannon's own number stated rather than solved.

This article records tradition as it has been passed down and reported. Its sources are not yet part of the atlas's verified catalogue.

John von Neumann and John Nash built the branch of game theory most people mean by the term: players with defined payoffs, choosing strategies, converging or failing to converge on an equilibrium. John Conway built a different one almost by accident, while trying to understand the endgame of Go. Late-stage Go positions often break into several independent regions of the board where play barely interacts, and Conway, analyzing how the value of each region combines with the others, found that the combining itself obeyed rules that looked exactly like arithmetic on a new and much larger kind of number. He worked out the theory properly and published it in 1976 as On Numbers and Games, and the numbers themselves came to be called surreal numbers: a system vast enough to contain every real number, every ordinal number, and infinitely many infinitesimal and infinite quantities besides, all constructed from nothing but the recursive idea of a game position and its possible moves. This is combinatorial game theory, and it is a genuinely different animal from the von Neumann and Nash tradition. Von Neumann and Nash games typically involve simultaneous choices, incomplete information about the other player's intentions, and payoffs that can require compromise or bluffing to navigate. Conway games are sequential, perfect-information, no-chance contests like Go, chess endings, or Nim, where the entire question is which player, moving optimally, forces a win. The two traditions share a name and a founding motivation, understanding strategic play mathematically, and very little else about their machinery. That a Cambridge mathematician found a new kind of number by staring hard enough at a Go endgame is, on its own terms, one of the stranger origin stories in modern mathematics.