Home

> urticator.net
  Search

  About This Site
> Domains
  Glue
  Stories

  Computers
  Driving
  Games
  Humor
  Law
> Math
  Numbers
  Science

> Game Theory Section
  A Theorem on Finite Abelian Groups
  Probability
  Miscellaneous

> Combinatorial Game Theory
  Game Theory
  The Prisoner's Dilemma
  Evolutionarily Stable Strategies

  An Outline

Combinatorial Game Theory

Combinatorial game theory, not to be confused with regular game theory, is the kind of mathematics used to describe games in which the goal is to make the last move. Strictly speaking, then, it applies only to games like Nim and Sprouts (see Macroscope for the latter), but it turns out that the same theory can be adapted to other games as well, such as Dots and Boxes and even the endgame in go.

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.

 

  See Also

  Books About Go
  Outline, An

o March (2000)
@ August (2000)
o September (2004)