Game Theories and Computer Go
Martin Müller
Informatik, ETH Zürich
Abstract
Two kinds of theories have traditionally influenced computer game playing:
Classical game theory, with its minimax principle, and specialized theories developed
for a particular game. In addition to these, combinatorial game theory promises
to be useful for computer Go. We propose a model for Go based on this theory and
discuss our preliminary implementation. We claim that future Go programs will need
powerful theories as well as lots of computing power.
Organisation of the Paper
Section 1: Review of theories used for computer game playing.
We discuss classical game theory, game-specific theories and their relation to each other.
Section 2: Brief introduction to the concepts of combinatorial game theory
we need for our application to Go. We discuss sums of games and several algorithms
for evaluating them.
Section 3: The relation between computer Go and game theories. We survey the current
state of the art, taking leading Go programs as examples.
Section 4: Our framework for applying combinatorial game theory to Computer Go.
We define local Go games, map them to abstract mathematical games and show how
to play Go as a sum of local Go games.
Section 5: Implementation issues of our model and differences to 'standard' Go programs.
Section 6: Limitations of our basic model and extensions designed to
overcome these limitations.
Section 7: Summary of our experiences and remaining research problems.