Combinatorial Game Theory (08w5075)

Arriving in Banff, Alberta Sunday, January 20 and departing Friday January 25, 2008


Michael Albert (University of Otago)

Elwyn Berlekamp (University of California, Berkeley)

(University of Minnesota)

(University of Alberta)

(Dalhousie University)

(Gustavus Adolphus College)


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

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.