Combinatorial Game Theory (11w5073)

Arriving in Banff, Alberta Sunday, January 9 and departing Friday January 14, 2011


Elwyn Berlekamp (University of California, Berkeley)

(Paris-Dauphine University)

(Weizmann Institute)

(University of Alberta)

(Dalhousie University)


A 'Games of No Chance' workshop will be a welcome opportunity to host special sessions on: Temperature Theory; misere-play games; and complexity of impartial games. There have been recent strides forward in all three areas of the subject, many directly attributable to collaborations started in previous 'Games of No Chance' workshops at MSRI and BIRS.

1: Temperature theory: how to play when large gains can be made, is a direction of research that has played a central role in combinatorial game theory for many decades. Over the past fifteen years there have been several major advances in temperature theory, and many promising directions for further research have emerged see [2,6,8-11,13-15] for a small selection. A special session will be an excellent opportunity to take stock of these advances; to evaluate the state of the subject and trace the history of its development; to bring the theory to the attention of a broader audience; and to present opportunities for collaboration on a variety of problems.

Mean and temperature are fundamental invariants of partizan games that quantify the value and urgency of a position. They were studied in the 1950s by Milnor and Hanner, but in the context of modern combinatorial game theory the first rigorous construction was given by Berlekamp, Conway and Guy in the late 1970s [4]. The Berlekamp-Conway-Guy construction applied only to short games, in which repetition is prohibited and play must end after a finite number of moves.

In the ensuing years there has been increasing interest in extending this theory to a wide class of loopy games, those in which repetition is permitted. One such extension was introduced by Elwyn Berlekamp [2] at the first 'Games of No Chance' conference in 1994, and several more recent advances have dramatically increased the scope and sophistication of the theory. These include Fraser's [6] extension of temperature to games with long cycles, and the dogmatic theory of hyperactive positions due to Berlekamp and Spight [15].

These advances suggest numerous possibilities for further research, including a better understanding of cold loopy games; generalizations of heating and cooling to the loopy context; and ultimately, a unified temperature theory that applies to all loopy games.

One of the most exciting elements of this theory is its application to the Asian board game GO, which has been a motivating influence in the development of combinatorial game theory. This connection has attracted attention from numerous mathematicians and GO players from Japan and Korea, several of whom have attended previous 'Games of No Chance' conferences (see [12] for example). Although abstract temperature theory remains the principal focus of this proposed session, we look forward to further collaboration with professional GO players, and to further insights and connections between mathematics and GO.

A further interplay comes from a new heuristic that has been so effective in GO, that of Monte Carlo Tree Search (MCTS) methods (see [5,7] for example). These are sample-based search approaches using Monte-Carlo simulations and selective tree search. They have recently lead to a breakthrough, and have considerably closed the gap to the best human players. A goal for the workshop would be to find connections between MCTS methods and combinatorial game theory, e.g. to utilize local subgame analysis within a global MCTS search.

2: Misere-play Impartial Games: this was a major topic of the 2008 BIRS Games workshop. Recent work (July 2009) by Guo and Miller with Plambeck, Siegel and Weiemerskirsh looking on, suggest a radical change in the mathematical setting and tools. Instead of regarding the games as quotient monoids with a bi-partition they are now encoded as lattice points in rational convex polyhedra. Encodings provided by these lattice games can be made particularly efficient for octal games. The setting of lattice games naturally allows for misere play, where 0 is declared a losing position. Lattice games also allow situations where larger finite sets of positions are declared losing. Generating functions for sets of winning positions provide data structures for strategies of lattice games. The main conjecture is that every lattice game has a rational strategy: a rational generating function for its winning positions. Another conjecture is that every lattice game has an affine stratification: a partition of its set of winning positions into a finite disjoint union of finitely generated modules for affine semigroups. If true, this would give an effective algorithm for solving the games and would represent a great step forward.

In 2009, Meghan Allen [1] extended to misere partizan games the monoid approach of Plambeck and Seigel that has worked well in impartial games. This involves a tetra-partition of the misere quotient as opposed to a bipartition in the impartial case. Her techniques worked well in characterizing all misere quotients that are isomorphic to that generated by *={0|0}. Two important questions that are central to furthering the techniques are: if the monoids for S and T are isomorphic when are they isomorphic to that of S union T ? For which class of games is *+*=0 (mod g) for all g in the class?

3: Normal-play Impartial Games: The lattice game approach of Guo and Miller for misere-play games also provides a framework for normal-play impartial games. It provides an algorithm to compute strategies for many heap games in a natural setting. How effective this is for all impartial games is yet to be seen.

At the same time Fraenkel and Peled [3] found another computationally effective approach for many impartial games. A pair of integer sequences that split the positive integers I is often---especially in the context of impartial games---defined recursively by $A_n=mex{A_i, B_i : 0<= i= 0)$, where mex(S) is the smallest nonnegative integer not in S, and $C:I ->I$. Given x, y in I, a typical problem is to decide whether $x=A_n$, $y=B_n$. For general functions $C_n$, the best algorithm for this decision problem was until now exponential in the input size $omega(log x+log y)$. Very recently it was proved constructively that the problem is actually polynomial for the wide class of approximately linear functions $C_n$. This solves constructively and efficiently the complexity question of a number of previously analyzed take-away games of various authors. It is of interest to extend this result i new directions, such as: (i) relax the requirement of $C_n$ being "approximately linear"; (ii) consider the case where $A_n$ and $C_n$ are not necessarily additively related. These extensions may lead to classes of new games not yet imagined.

[1] Allen, M. R. An Investigation of Misere Partizan Games, PhD., Dalhousie University, 2009.

[2] E. R. Berlekamp: The economist's view of combinatorial games. In: R. J. Nowakowski (ed.): Games of No Chance. Cambridge University Press, NYC (1996).

[3] A. S. Fraenkelhttp U. Peled,

[4] E. R. Berlekamp, Conway, J. H. & Guy, R. K. Winning ways for your mathematical plays. Vol. 1 A K Peters Ltd., 2001.

[5] R. Coulom, Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search Computers and Games, 2006, 4630, 72-83.

[6] Fraser, W. E.Computer-Assisted Thermographic Analysis of Go Endgames, University of California at Berkeley, 2002.

[7] Gelly, S. & Silver, D. Combining online and offline knowledge
in UCT, ICML, ACM, 2007, 227, 273-280.

[8] M. Mueller, Conditional combinatorial games and their application to analyzing capturing races in Go, Information Sciences, 2003, 1[3]54, 189-202..

[9] M. Mueller, E. R. Berlekamp & B. Spight, Generalized Thermography:
Algorithms, Implementations and Application to Go Endgames Technical Report, University of California at Berkeley, 1996.

[10] M. Mueller, M. Enzenberger, and J. Schaeffer. Temperature discovery search. In Nineteenth National Conference on Artificial Intelligence (AAAI 2004), pages 658-663, San Jose, CA, 2004.

[11] K. Kao, Mean and temperature search for Go endgames, Info. Science, 2000, 122, 77-90.

[12] T. Nakamura, Counting Liberties in Capturing Races, Games of No Chance 3 (Albert, Nowakowski,ed.) Cambridge University Press, Cambridge, 2009.

[13] W. L. Spight, Extended thermography for multiple kos in go, Theoret. Comput. Sci., 2001, 252, 23-43.

[14] W. L. Spight, Go thermography: the 4/2/98 Jiang-Rui endgame, More Games of No Chance, (Nowakowski, R. J. ed.) Cambridge University Press, Cambridge, 2002, 42, 89-105.

[15] W. L. Spight, Evaluating Kos in a Neutral Threat Environment: Preliminary Results, Lecture Notes in Computer Science, Springer, 2003, LCNS 883, 413-428.