Combinatorial game theory provides an exciting approach to the analysis of games: It allows the decomposition of a game into a sum of local games. In contrast to classical game theory, few applications to computer game playing have been demonstrated.
Game programming has enjoyed the continuous interest of computer science research. Progress has been impressive: several games have been solved by computer, typically by a combination of mathematical analysis and exhaustive search. Programs for many other popular games give their human opponents strong opposition. The notable exception is the ancient oriental game of Go.
This thesis claims that combinatorial game theory applies to computer Go. We develop a sum game model for heuristic Go programming and a program for perfect play in late stage endgames. As a case study in Knowledge Engineering, the `Explorer' program presents new approaches to modeling Go knowledge. We adapt a string matching algorithm for Go pattern matching, develop algorithms for board partition, and create a framework for identifying, searching and evaluating local games.
We extend the Smart Game Board, a workbench for game programmers, with tools for displaying and editing Go-specific data. For measuring the performance of Go programs, we introduce the Computer Go Test Collection containing thousands of annotated positions.
Die kombinatorische Spieltheorie liefert einen interessanten neuen Ansatz zur Analyse von Go: sie erlaubt die Zerlegung eines Spiels in eine Summe von lokalen Teilspielen. Im Gegensatz zur klassischen Spieltheorie wurde sie jedoch kaum in Computerspielprogrammen eingesetzt.
Die Entwicklung von Spielprogrammen ist ein aktives Forschungsgebiet der Informatik. Dabei wurden eindrucksvolle Fortschritte erzielt: mehrere Spiele wurden vollständig gelöst, typischerweise durch eine Kombination von mathematischer Analyse und erschöpfender Suche. In vielen anderen bekannten Spielen sind Programme ein starken Spielpartner für ihre menschlichen Gegner. Die bemerkenswerte Ausnahme ist das alte asiatische Brettspiel Go.
Diese Dissertation stellt die These auf, dass die kombinatorische Spieltheorie auf Computer-Go anwendbar ist. Wir entwickeln ein Summenspiel-Modell für die heuristische Goprogrammierung und ein Programm für perfektes Spiel im späten Endspiel. Als Fallstudie im `Knowledge Engineering' enthält das Programm `Explorer' neue Ansätze zur Modellierung von Go-Wissen. Wir adaptieren einen Zeichenkettenvergleichsalgorithmus für den Mustervergleich im Go und entwickeln Methoden zur Brettaufteilung sowie zur Identifikation, Suche und Bewertung von lokalen Spielen.
Wir erweitern das Smart Game Board, eine Entwicklungsumgebung für Spielprogramme, mit Werkzeugen zur Anzeige und Bearbeitung Go-spezifischer Daten. Um die Leistung von Goprogrammen zu messen, erstellen wir die Computer Go Test Collection mit tausenden von kommentierten Positionen.
Martin Müller