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.