Combinatorial Game Theory Workshop (05w5048)

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.