Combinatorial Game Theory: Introduction to Sprague-Grundy Theory

Speaker:          Gerhard Trippen     
                  HKUST   

Title:            Combinatorial Game Theory: Introduction to Sprague-Grundy Theory

Date:             Monday, 17 May 2004 

Time:             2:00pm - 3:00pm 

Venure:           Lecture Theatre H  
                  (near lift nos. 27/28)   


ABSTRACT: 

Strategies and mathematics of one or two-player games of perfect knowledge are studied 
using Combinatorial Game Theory. Chess and Go are games of perfect knowledge but difficult 
to analyze. So Combinatorial Game Theory often either concentrates on simpler games such 
as Nim - a taking game with several heaps of possibly different sizes -, or attempts to 
solve endgames and other special cases.

The class of impartial games allows both players to make any move for all game positions.
In 1930s, Sprague and Grundy developed a theory of impartial games in which Nim played a 
most important role. According to the Sprague-Grundy theory, every position in an impartial 
game can be assigned a Grundy number which makes it equivalent to a Nim heap of that size.

We will illustrate the Sprague-Grundy theory using the game of Kayles as an example.
Kayles was introduced by Dudeney and Loyd. It is played by two persons who move alternately.
All Kayles (pins) are arranged in a row. In one move a player may knock out either one or 
two adjacent pins. The player who can make the last move will win the game.

BIOGRAPHY: 

Gerhard Trippen received his M.Phil. degree in Computer Science from
Universitaet des Saarlandes, Saarbruecken, Germany. He is currently
working towards his Ph.D. degree in Computer Science at HKUST. His
research interests include online algorithms, algorithm animation, graph
theory, experimental algorithms, computational geometry, and combinatorial
game theory.