Combinatorial Analysis of Go Endgame Positions Open Access

McMillen, Jacob Aaron (2010)

Permanent URL: https://etd.library.emory.edu/concern/etds/vx021f31v?locale=en
Published

Abstract

Abstract
Combinatorial Analysis of Go Endgame Positions
By Jacob A. McMillen
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.

Combinatorial Analysis of Go Endgame Positions
By
Jacob A. McMillen
B.S., SUNY Fredonia, 2005
Advisor: Ron Gould, Ph.D.
A thesis submitted to the Faculty of the
James T. Laney School of Graduate Studies of Emory University
in partial fulfillment of the requirements for the degree of
Master of Science
in Mathematics
2010

Table of Contents

1 Overview: pg. 1

2 Combinatorial Games: pg. 3

3 Analyzing Go Positions: pg. 8

4 Current and Future Research: pg. 35

A Rules of Go: pg. 38

About this Master's Thesis

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School
Department
Degree
Submission
Language
  • English
Research field
Keyword
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files