April 24, 1997 Elwyn Berlekamp, UC Berkeley "Overview of combinatorial game theory"Abstract:
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:
Although Nim was first solved by Bouton in 1902, most of the relevant mathematics has been discovered in the past 25 years, starting with Conway's pioneering theory of "partizan games". This theory postulates that the game ends a player who is unable to make a legal move loses. The theory applies directly to all but the first two games on the above list. Surprisingly, extensions of the results of this theory also often prove decisive in analyzing endgame positions in "Go" and in "Dots and Boxes", even though both of these games are usually viewed as contests in which the players seek to maximize their scores rather than to get the last move.
The talk will include several examples from the game of Domineering, selected to illustrate several more general results.
There is a natural abstract equivalence relation among games, namely that G = H iff for all games X, and for both choices of who moves first, the games G+X and H+X, both optimally played, have the same outcome. Under these notions of equivalence and sum, the set of all "short" games (games which necessarily end after a finite number of plays) forms an infinite abelian group. The "0" in this group is the set of all games which can be won by either player if he plays second. There is a natural partial ordering on this group, according to which G >= H iff the player called Left, going second, can win the game G-H. The "numbers" form an important subgroup of the group of all games. Another important subgroup is a rich group of "infinitesimals".
Two important numerical properties of any position are its "mast value" and its "temperature". The mast value is a measure of the relative advantage the position offers to the player named Left. The temperature is a subtle measure of the relative advantage the position offers to whichever player moves next. When games are added, mast values add, but temperatures maximize. A position can be classified as "hot", "tepid", or "cold", depending on whether its temperature is positive, zero, or negative. Cold games are numbers. Tepid games are infinitesimals.
Extensions of these notions are providing a new paradigm for getting Go-playing computer programs to see their data more like it appears to human Go players rather than as it appears to computer chess players.