Combinatorial Game Theory

To get started, the first thing to do is recursively enumerate all possible game positions. In any given position, each of the two players has various possible moves, each leading to another position. If we name the players “left” and “right”, and let L and R be lists of the positions that result from moves by left and right, respectively, then we can use the symbol {L|R} to completely describe the original position.

The recursion begins with the game where neither player has any possible moves, i.e., the game { | }. Whoever moves first in this game loses. Next, consider the game { {|} | }. If left moves first, ve has a move, to { | }, then right is stuck; but if right moves first, ve doesn't have a move. So, right loses, regardless. Similarly, left loses the game { | {|} }.

The amazing thing is that after going through various technicalities, such as imposing an equivalence relation, the set of games can be seen as a superset of the set of real numbers. The game { | } acts as zero, the game { {|} | } or {0|}, which is advantageous to left by one move, acts as one, and so on. There's even a natural operation on games that acts as addition, namely, playing both games at the same time, with a move in the composite game being a move in either one of the component games.

It wasn't an accident that I said “real numbers” above. There are games that represent fractions ({0|1}, for example, is 1/2) and games that represent arbitrary real numbers. In fact, since games are a superset of numbers, there are even more games—for example, games that represent infinite and infinitesimal numbers, and games that aren't even comparable to numbers, such as the game * = {0|0}.

Unfortunately, as far as I know, all the main books on combinatorial game theory are out of print or are otherwise inaccessible. The definitive reference, the first volume of Winning Ways, hasn't been declared to be out of print by the publisher, but it might as well be, because you can't order copies, and it's been that way for years and years. One of the authors, John Conway, also wrote a shorter book On Numbers and Games, but that one is officially out of print. The only thing I do know to be in print is the short book Surreal Numbers, which discusses the use of the {L|R} construction as an axiomatic foundation for real numbers. So, it doesn't get into the interesting game-related aspects, but it does indicate the kind of math that's involved.

Winning Ways is back in print now, in case you were wondering.