Computer Science/Discrete Mathematics Seminar II

Combinatorial game theory is the study of combinations of two-player games with no hidden information and no chance elements. The subject has its roots in recreational mathematics, but in its modern form involves a rich interplay of ideas borrowed from algebra, combinatorics, and the theory of computation. The first part of this talk will be a general introduction to the classical theory of partizan games. I will show how a few simple axioms give rise to the group of short games, a partially-ordered Abelian group with enormously rich structure. I will discuss how the theory can be applied to extract useful information about a diverse array of games, including Nim, Domineering, Go, and to a lesser extent Chess. In the second half of the talk, I will briefly discuss three areas of current research in combinatorial games: the theory of misere quotients; the lattice structure of short games; and the temperature theory of Go endgames. There has been significant activity in all three topics in the last five years, but nonetheless I will be able to state some major (and reasonably elementary) open problems in each of them.