05w5048 Combinatorial Game Theory Workshop

Arriving Saturday, June 18 and departing Thursday, June 23, 2005

Organizers: Elwyn Berlekamp (University of California, Berkeley), Martin Mueller (University of Alberta), Richard Nowakowski (Dalhousie University), David Wolfe (Gustavus Adolphus College).

Confirmed Participants

Information for Participants

Tentative Schedule

Final Report (PDF file)

Workshop Videos

Objectives

The recent workshops at MSRI 2000 and Dagstuhl 2002 brought together the two camps, mathematicians working in combinatorial game theory and computer scientists interested in algorithmics and Artificial intelligence, i.e. the heuristics, structures and procedures needed to approximate or find best play. Essentially, the former work from the end of the game and the latter work from the beginning.

Until the MSRI 2000 workshop there was almost no communication between the two groups. The Dagstuhl workshop was a direct consequence of connections made at the MSRI conference. Both resulted in collaborations between the two groups. At Dagstuhl, there were 46 participants from Europe, North America, and Asia.

The field, and the number of practitioners in it, has increased recently. The Journal of Theoretical Computer Science had a Games Section which had few submissions per year in the 1990s. Our call for a special volume of the Journal of Theoretical Computer Science on results from the workshop brought 26 submissions. [The results span combinatorial game theory, complexity theory (i.e., NP-completeness results of games), winning strategies for games, and general game play heuristics. A number of results were produced during the workshop and new papers originating out of the workshop were being submitted a year after the deadline. The game of Clobber was introduced (two papers) `Sliding block puzzles' and their complexity status were also much discussed and solved (4 papers).] INTEGERS (started 2000) has opened a special games section (started 2002) which has had a steady stream of submissions.

Since Dagstuhl, there have been loose connections between local groups working on old and new areas. For example: in the last two years two all-small games, Clobber and Cutthroat (Albert, Demaine, Grossman, McCurdy, Nowakowski, Wolfe) have been developed that are a basis for expanding the atomic weight theory: Partizan Octal games (Albert, Grossman, Nowakowski, Plambeck, Wolfe); Misere games are very difficult, advances in the analysis of misere octal games are suggesting new techniques for misere games in general (Conway, Plambeck, Sibert); hexadecimal games and generalized octal games are showing regularities never reported before and only some of these regularities fall to automatic checking (Horrocks, Nowakowski). Go is a hot topic and its analysis is expanding the theoretical tools (Berlekamp, Fraser, Spight) as well as the algorithmic tools (Mueller). Complexity issues generated by games have been examined by Demaine (MIT) and Fraenkel (Technion) and their groups. The University of Alberta GAMES group does research into artificial intelligence using games as experimental test beds. The games used include combinatorial games (such as Go and Amazons), classical board games (chess, checkers, Othello), cards games (poker), and commercial games. Game-related research includes new high-performance search algorithms and machine-learning techniques. A group lead by Aaron Siegel has developed a new software tool, CGSuite, which is a versatile, graphical Java program for computing and manipulating game positions and their values. This tool puts the analysis of many positions and games within the realm of the ordinary practitioner.

It is time to bring these separate groups together, to exchange ideas, tools and to cement the connections between them.