MATH Seminar

Title: Combinatorial Analysis of Go Endgame Positions
Defense: Master's Thesis
Speaker: Jacob McMillen of Emory University
Contact: Jake McMillen, jamcmil@emory.edu
Date: 2010-06-10 at 3:00PM
Venue: W302
Download Flyer
Abstract: Go is a two player skill game of Chinese origin. Although Go is praised for having a simple rule set, the game generates tremendous complexity. As such, programmers have been unable to design Go AI programs that exceed the level of intermediate human players. By using techniques of combinatorial theory, mathematicians have recently developed methods of determining optimal play on certain classes of Go positions. It is our goal to present a survey of these analytic methods. We will first provide an introduction on the rules of Go as well as relevant concepts of combinatorial game theory. We will then proceed to solve several categories of small Go positions and finally show how to determine perfect play on a full size Go endgame by way of partitioning into solvable subgames.