Die Mini-Welt der Spiele bietet eine ideale Testumgebung für Such-Techniken und -Algorithmen. Die Kombinatorische Spieltheorie (KST) ist ein relativ neuer, vielversprechender Ansatz in der Analyse von Spielen. Indem sie ein Spiel in eine Summe von unabhängigen Teilspielen zerlegt, wendet die Kombinatorische Spieltheorie ein fundamentales Paradigma der Algorithmik in der Spielbaum-Suche an, "Teile und Herrsche". Seit über zwei Jahrzehnten ist die Kombinatorische Spieltheorie Gegenstand der mathematischen Forschung. Ziel dieser Arbeit ist es, Fortschritte zu erzielen in der algorithmischen KST, einem bisher wenig erforschten Gebiet.
In zwei Fallstudien wenden wir die Methoden der KST auf dem Gebiet der algorithmischen Spieltheorie an. Die erste untersucht eine Klasse von Spielen, in denen ein Zug in einem Teilspiel zu einem Sieg in der ganzen Summe führen kann. Wir stellen ein neues Berechnungsmodell vor, welches mit solchen globalen Drohungen umgehen kann und setzen es ein in der Analyse von Zugzwangstellungen in Bauernendspielen im Schachspiel. In der zweiten Fallstudie analysieren wir Zugzwang-freie Nullsummenspiele. Mit Anwendungen im Spiel Regio zeigen wir, dass der Einsatz von heuristischen Bewertungsfunktionen in der kombinatorischen Spielbaum-Suche in Kombination mit einem Algorithmus für das Summenspiel einen vielversprechenden Ansatz, "Teile und Herrsche" in der Spiel-Analyse anzuwenden, liefert.
Die "Game Bench" ist ein Rahmenprogramm für die Implementierung von kombinatorischen Spielen auf dem Computer. Das Kernstück der Game Bench ist eine erweiterbare "Suchmaschine", welche spielunabhängige Algorithmen und Datenstrukturen für die kombinatorische Spielbaum-Suche und das Spielen von Summen zur Verfügung stellt. Die Wahl einer objekt-orientierten Struktur und der Programmiersprache Java machen die Game Bench erweiterbar für die Bedürfnisse der Spiel-Programmierer und portierbar auf praktisch alle Computer-Plattformen. Den Erfolg der Game Bench als Werkzeug für die Entwicklung von Spielprogrammen dokumentieren verschiedene Anwendungen und Studenten-Projekte.