|COMPUTER SCIENCE/DISCRETE MATH II|
|Topic:||An Invitation to Combinatorial Games|
|Affiliation:||Mathematical Sciences Research Institute and Member, School of Mathematics|
|Date:||Tuesday, October 17|
|Time/Room:||10:30am - 12:30pm/S-101|
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.