Professor Elwyn Berlekamp, UCB Math Department

``Games of No Chance''

November 29, 1999

Combinatorial game theory is concerned with two-person perfect-information games, especially those classes of positions for which winning strategies can be stated explicitly, or at least proved to exist. The powerful mathematical methods (often requiring only paper and pencil, no computers) are most successful when applied to games whose positions often decompose into "sums". If A and B are games, then A+B is the game in which each player, at his turn, can either choose to play in A, or in B, but not in both. The many examples of such games include:

For combinatorial game positions, like many other mathematical objects (e.g., groups), computer programs, and engineering systems, successful understanding and analysis is often limited primarily by the extent to which objects can be decomposed into "simpler" objects with some limitations on their interactions.

In the first two of the games listed above, the object is to score more points than the opponent. In the other games, like checkers, the object is to attain a position from which the opponent is unable to move. Philosophically, games with continuous score seem more amenable to a von Neumann style approach, where each player's motto is "Don't Lose". Typically, each player has a strategy which ensures that his final score will be, at worst, within epsilon of the optimum. On the other hand, games in which the final move wins have "Winner Take All" characteristics. Recursive, discrete, algebraic techniques yield precise solutions to many positions in such games. Each summand has a definite value, which can be a number, or an infinitesimal, or a more complicated object. The outcome of the total game depends on the sign of the sum of the values of the relevant position. A positive or negative total value implies a win for one player or the other, no matter who moves next. A zero value implies a win for the second player, and a fuzzy value (incomparable with 0 in an appropriately defined partial ordering) implies a win for the first player. In the early 1990s, these techniques were extended to endgames in Go (which have integer-values scores).

In the past two years, a refined paradigm has appeared which superimposes a von Neumann style, linear-programming-like, continuous, real, structure on top of the precise values of game positions. This is achieved by adding a specified, universal set of many more summands into any given position. This yields a precise real value corresponding to the notion of how much the next move is worth. It also supports a unified overview of a structure which includes all of the games listed above, and many others. The ramifications for the game of Go look especially interesting.