The micro world of games provides an ideal testing environment for search techniques and algorithms. Combinatorial Game Theory (CGT) is a promising, relatively new approach to the analysis of games. By decomposing a game into a sum of independent local games, CGT enables the application of divide and conquer to game tree search. This fundamental paradigm of algorithm design promises to lead to efficient search techniques. Whereas CGT has been subject to mathematical research for more than two decades, this thesis aims to progress in the yet little explored field of computational CGT.
In two case studies we apply the powerful methods of CGT in the field of algorithmic game theory. In the first application we investigate a class of games where a local move can lead to an overall win in a sum of games. We present a new computation model that deals with such global threats and use it to analyze Zugzwang positions in king and pawn chess endgames. In the second case study we analyze zero-sum games without Zugzwang. With applications to the game Regio, we demonstrate that the use of heuristic evaluation functions in local game search combined with algorithms for sum game play is a promising divide and conquer approach to heuristic game playing.
With the Game Bench we present an application framework for combinatorial game programming. Its main focus is an extensible search engine that provides game independent algorithms and data structures for combinatorial game tree search and sum game play. The choice of an object-oriented design and of the programming language Java makes the Game Bench extensible to the programmer's needs and portable to virtually any computer platform. Several applications and student programming projects have demonstrated its value as a tool for rapid prototyping of game playing programs.