08w5075 Combinatorial Game Theory

Arriving Sunday, January 20 and departing Friday, January 25, 2008

Organizers: Michael Albert (University of Otago), Elwyn Berlekamp (University of California, Berkeley), Ezra Miller (University of Minnesota), Martin Mueller (University of Alberta), Richard Nowakowski (Dalhousie University), David Wolfe (Gustavus Adolphus College).

Confirmed Participants

Press Release: Combinatorial Game Theory

Information for Participants

Schedule and Abstracts (PDF file)

Final Report (PDF file)

Objectives

The field is growing and is attracting the interest of more people. There have been major workshops at MSRI in 1994 and 2000, Dagstuhl in 2003, and BIRS in 2005. The MSRI and BIRS Workshops resulted in three books: Games of No Chance, More Games of No Chance, and Games of No Chance III. The latter includes twenty research papers, four top-level surveys, and updated versions of the Unsolved Problems in- and the Bibliography of- Combinatorial Games. The field is new and is growing. Our call for a special volume of the Journal of Theoretical Computer Science on results from the Dagstuhl workshop brought 26 submissions. INTEGERS (started 2000) opened a special games section in 2002 and this has had a steady stream of submissions.

There have been many important developments in the last few years most of which were announced at the last BIRS meeting. The main objectives of the proposed workshop are to air the new results and to introduce new people and techniques to the area. Specifically:

1: Misère games. One major development is Plambeck's breakthrough in the analysis of misère games (announced at BIRS 2005). He showed that the solution to a misère game G can be described by its misère quotient, a commutative monoid that encodes the additive structure of G. Dr. Aaron Siegel has designed algorithms for computing misère quotients, and together Plambeck and Siegel have begun to develop a structure theory. A major thrust of this workshop would be to invite and interact with algebraists. Dr. Ezra Miller has joined the organizing committee for this reason and has already found several interested algebraists.

2: Go is a hot topic and its analysis is expanding the theoretical tools (Berlekamp, Fraser, Spight) as well as the algorithmic tools (Mueller). The recently introduced (2005) game of Woodpush allows for an analysis of ko-like situations without requiring the rest of the structure of Go. At the last BIRS meeting, Dr Nakamura presented his results showing that cooling by 2 points was essential to the analysis of ‘races to capture’. Nakamura's results bear so many resemblances to the atomic weight theory that there may be deeper connections waiting to be discovered.

3: All-small games: recent analyses of Clobber, Cutthroat and Dragover (Albert, Demaine x 2, Fleischer, Grossman, McCurdy, Nowakowski, Wolfe), have suggested ways of expanding the atomic weight theory. In addition, John Conway (2006) has suggested a new representational theory that could greatly simplify the canonical form representation of all-small games. Again, the underlying algebraic structures pose interesting and challenging questions.

4: Complexity issues: This is always an important topic. There are groups at MIT (Demaine et al) and Weizmann Institute (Fraenkel) and the University of Alberta GAMES group.