¶ Einleitung
von Matěj Baťha CC BY-SA 2.5
Kalah ist ein modernes Brettspiel aus der Familie der Mancala-Spiele, einer der ältesten Spielarten der Welt. Mancala-Spielestammen ursprünglich aus Afrika, dem Nahen Osten und Südostasien und werden dort seit mehreren tausend Jahren gespielt. Sie basieren auf dem Verteilen von Spielsteinen in Reihen von Mulden und dem Einsammeln dieser Steine nach bestimmten Regeln.
Kalah wurde in den 1950er-Jahren in den USA als kommerzielle Variante dieser traditionellen Spiele vom US-Amerikaner William Julius Champion, Jr. entwickelt und ist heute vor allem in westlichen Ländern weit verbreitet. Gespielt wird auf einem Brett mit zwei Reihen von Mulden und je einem großen Sammelfeld pro Spieler, der sogenannten Kalaha. Jeder Spieler kontrolliert eine Seite des Brettes und versucht, durch geschicktes Verteilen der Steine möglichst viele davon in die eigene Kalaha zu bringen.
Das Spiel ist leicht zu erlernen, bietet aber eine große strategische Tiefe. Genau diese Kombination aus einfachen Regeln und komplexem Spielverlauf macht Kalah sowohl bei Freizeitspielern als auch in der Informatik interessant.
¶ Spielregeln und Ablauf von Kalah
Kalah wird von Zwei Spielern auf einem symmetrischen Spielbrett gespielt. Jeder Spieler kontrolliert eine Seite des Bretts, bestehend aus einer Reihe von Mulden (auch Pits genannt) und einer großen Sammelmulde rechts vom Spieler, der sogenannten Kalaha oder Store. Üblicherweise besteht jede Seite aus sechs Mulden, die zu Beginn jeweils mit der gleichen Anzahl an Steinen gefüllt sind (klassisch vier oder sechs). Einer der Spieler wird als South, der andere als North bezeichnet. South beginnt das Spiel. Jeder Spieler darf ausschließlich Mulden auf der eigenen Seite wählen.[1]
¶ Ein Zug
Ein Zug besteht aus folgenden Schritten:
- Der Spieler wählt eine nicht-leere Mulde auf seiner Seite.
- Alle Steine aus dieser Mulde werden aufgenommen.
- Die Steine werden einzeln gegen den Uhrzeigersinn in die folgenden Mulden verteilt, beginnend mit der nächsten Mulde.
- Die eigene Kalaha wird beim Verteilen mitgezählt, die gegnerische Kalaha jedoch übersprungen.
Dieses Verteilen der Steine wird als Sowing (Aussäen) bezeichnet.
¶ Sonderregeln für den letzten Stein
Die Position, in der der letzte ausgesäte Stein landet, bestimmt, was als Nächstes passiert:
1. Extra-Zug:
Landet der letzte Stein in der eigenen Kalaha, darf der Spieler sofort einen weiteren Zug ausführen.
2. Eroberung (Capture)
Landet der letzte Stein in einer zuvor leeren Mulde auf der eigenen Seite, dann werden:
- dieser Stein und
- alle Steine aus der gegenüberliegenden Mulde des Gegners in die eigene Kalaha gelegt.
3. Normaler Zugabschluss
In allen anderen Fällen endet der Zug und der Gegner ist am Zug.
¶ Spielende
Das Spiel endet, sobald ein Spieler keine Steine mehr in seinen Mulden hat. In diesem Fall sammelt der andere Spieler alle noch verbleibenden Steine auf seiner Seite in seine Kalaha ein.
Der Spieler mit den meisten Steinen in seiner Kalaha gewinnt. Bei gleicher Steinanzahl endet das Spiel unentschieden.
¶ Formale Beschreibung des Spiels Kalah
Um Kalah algorithmisch analysieren und lösen zu können, muss das Spiel zunächst formal beschrieben und seine Komplexität untersucht werden.
¶ Komplexität
Das Spiel besitzt eine hohe kombinatorische Komplexität. Bereits für die Standardvariante mit sechs Mulden pro Seite und vier Steinen pro Mulde existiert eine enorme Anzahl möglicher Spielzustände und Zugfolgen. Diese Anzahl wächst exponentiell mit der Anzahl der Mulden und der Steine pro Mulde.
Zur Beschreibung der Schwierigkeit eines Spiels werden üblicherweise zwei Maße betrachtet: die Zustandsraumkomplexität, also die Anzahl aller möglichen Spielstellungen, und die Spielbaumkomplexität, die die Anzahl der möglichen Spielverläufe beschreibt.
Für Kalah() ergeben sich folgende Tabellen[1:1]:
Anzahl der Mulden pro Seite
Anzahl der Steine in jeder Mulde, zu beginn des Spiels
Durchschnittlicher Verweigungsfaktor
Durchschnittliche Spielbaumtiefe
Geschätzte Anzahl der Knoten im Spielbaum
Diese Schätzung wurde errechnet indem 100 Spiele pro Instanz mit normalem Alpha-Beta simuliert wurden.[1:2]
Obwohl Kalah ein vergleichsweise einfaches Regelwerk besitzt, weist das Spiel eine hohe kombinatorische Komplexität auf. Sowohl die Anzahl möglicher Spielzustände als auch die Anzahl möglicher Spielverläufe wachsen mit zunehmender Brettgröße und höherer Anfangssteinzahl exponentiell an. Bereits kleine Variationen der Spielparameter führen zu drastischen Zuwächsen der Komplexität.
Tabelle 2 zeigt beispielsweise, dass die Standardvariante Kalah(6,4) eine Spielbaumkomplexität besitzt, die in ihrer Größenordnung mit der von 4-Gewinnt vergleichbar ist. Kalah(6,6) erreicht eine Spielbaumkomplexität, die am ehesten mit der von Dame vergleichbar ist.
¶ Zustandsmodellierung und Spielgraph von Kalah
Ein Spielzustand in Kalah beschreibt vollständig die aktuelle Spielsituation. Er besteht aus:
- der Anzahl der aktiven Steine in jeder Mulde auf beiden Seiten
- dem Spieler, der am Zug ist
Gefangene Steine kehren in Kalah nie ins aktive Spiel zurück. Deshalb hängt der weitere Spielverlauf ausschließlich von den noch aktiven Steinen ab, also nur den Steinen in den Mulden und nicht in den Kalahas.[1:3]
Durch die Zustandsmodellierung lässt sich Kalah als gerichteter Spielgraph darstellen:
- Kntoten entsprechen Spielzuständen
- Kanten entsprechen legalen Zügen
Da es in Kalah keine Zustandswiederholungen gibt, ist dieser Spielgraph azyklisch.[1:4]
¶ Algorithmische Lösung von Kalah
¶ Lösung kleiner Kalah-Instanzen mittels vollständiger Spielgraphen
Für kleine Kalah-Instanzen wird zunächst der vollständige Spielgraph erzeugt, der alle vom Startzustand aus erreichbaren Spielzustände enthält. Aufgrund der Regeln von Kalah ist dieser Graph endlich und azyklisch.
Die Berechnung der Spielwerte erfolgt durch eine vollständige Auswertung aller Zustände. Endzustände, in denen das Spiel beendet ist, erhalten unmittelbar einen festen Spielwert aus Sicht des South-Spielers also dem Start-Spieler:
- Win
- Loss
- Draw
Diese Spielwerte ergeben sich durch die Differenz der Steine im Besitz am Ende des Spiels:
function endGameValue:
value = scoreSouth - scoreNorth
if value > 0:
return WIN
else if value < 0:
return LOSS
else:
return DRAW
Für alle übrigen Zustände werden sämtliche legalen Züge betrachtet und die daraus entstehenden Nachfolgezustände ausgewertet. Der Spielwert eines Zustands ergibt sich anschließend gemäß dem Minimax-Prinzip aus den Spielwerten seiner Nachfolger.
Beispiel:
Befindet sich South am Zug und besitzt ein Zustand Nachfolgezustände mit den Spielwerten Win, Loss und Draw, so nimmt dieser Zustand den Spielwert Win an. Existieren keine Nachfolger mit dem Spielwert Win, aber mindestens ein Nachfolger mit dem Spielwert Draw, so nimmt der Zustand den Spielwert Draw an. Nur wenn alle Nachfolger den Spielwert Loss besitzen, wird der Zustand als Loss bewertet.
Für Zustände, in denen North am Zug ist, gilt das analoge Prinzip, wobei die Spielwerte aus Sicht von South entsprechend minimiert werden.
Dieser Ansatz liefert eine exakte Lösung des Spiels, ist jedoch aufgrund des exponentiellen Wachstums des Zustandsraums nur für kleine Varianten praktikabel. Die größte praktisch vollständig analysierte Variante ist Kalah(4,3) mit etwa 4,6 Millionen erreichbaren Zuständen. Bis zu dieser Größe konnten große Teile der Berechnung im Hauptspeicher durchgeführt werden. Für größere Varianten wäre aufgrund des stark wachsenden Speicherbedarfs zusätzlicher externer Speicher erforderlich, was die Berechnung erheblich verlangsamt. Dieser Lösungsansatz liefert exakte Spielwerte, ist jedoch aufgrund des exponentiellen Wachstums des Zustandsraums nur für kleine Kalah-Varianten praktikabel.
¶ Resultate
Tabelle 3[1:5] zeigt die Größe der tatsächlich erreichbaren Spielgraphen für verschiedenen Kalah-Varianten sowie den prozentualen Anteil dieser Graphen am gesamten theoretischen Zustandsraum aus Tabelle 1[1:6]. Es wird deutlich, dass nur ein kleiner Teil aller möglichen Zustände in realen Spielen überhaupt erreicht werden kann, da nicht jede theoretisch mögliche Verteilung von Steinen durch legale Spielzüge erreichbar ist. Viele Zustände verstoßen gegen die Spielregeln oder würden voraussetzen, dass das Spiel bereits zu einem früheren Zeitpunkt beendet worden wäre. Dennoch wächst die absolute Anzahl erreichbarer Zustände sehr schnell an. Bereits für Kalah(4,3) umfasst der vollständige Spielgraph mehrere Millionen Knoten, was die praktischen Grenzen vollständiger Spielgraphen verdeutlicht.
W/L/D = Win/Loss/Draw
Tabelle 4[1:7] zeigt die Spielwerte verschiedener Kalah-Varianten sowie die Verteilung von Gewinn-, Verlust- und Remisstellungen im jeweiligen Spielgraphen. Auffällig ist, dass der Spielwert der Startstellung nicht immer mit der Mehrheit der Knotenwerte übereinstimmt, wie zum Beispiel bei Kalah(2,3).
¶ Lösung größerer Kalah-Instanzen mittels MTD(f) Optimierung
Für größere Kalah-Varianten ist eine vollständige Berechnung des gesamten Spielgraphen aufgrund der enormen Zustandsraum- und Spielbaumkomplexität nicht mehr praktikabel. Stattdessen werden Suchalgorithmen eingesetzt, die den Spielbaum selektiv untersuchen und nur einen Bruchteil aller möglichen Zustände explizit betrachten.
Genutzt wird ein stark optimierter Spielbaum-Suchalgorithmus, dessen Kern MTD(f) (Memory-enhanced Test Driver) ist. Dieser Algorithmus wurde von Aske Plaat, Jonathan Schaeffer, Wim Pijls und Arie de Bruin entwickelt[2]
¶ MTD(f) mit iterative Tiefensuche und Bewertungsfunktion
MTD(f) ist ein auf Alpha-Beta-Pruning aufbauender Suchalgorithmus, der ausschließlich sogenannte Zero-Window-Suchen verwendet. Anstatt einen breiten Bewertungsbereich zu durchsuchen, prüft der Algorithmus iterativ, ob der tatsächliche Minimax-Wert eines Zustands größer oder kleiner als ein gegebener Schätzwert ist. Dieser Schätzwert wird nach jeder Suche angepasst, bis der exakte Minimax-Wert bestimmt ist.
Zur Lösung größerer Kalah-Instanzen wird MTD(f) in Kombination mit iterativer Tiefensuche und einer einfachen Bewertungsfunktion eingesetzt. Die Suche wird zunächst bis zu einer begrenzten Tiefe durchgeführt. Nach Abschluss von MTD(f) wird die maximale Suchtiefe schrittweise um drei Ebenen erhöht. Dieses Vorgehen wird bis zu einer Tiefe von 30 fortgesetzt. Die Ergebnisse flacher Suchen dienen dabei als Startwert für tiefere Suchen und ermöglichen eine schnellere Konvergenz, da Alpha-Beta-Cut-offs früher auftreten. Ab der Tiefe wird keine Tiefenbegrenzung vorgenommen und MTD(f) läuft ganz normal weiter.
Als Bewertungsfunktion wird die Differenz der in den Kalaha gesammelten Steine verwendet:
Diese Funktion wird zur Bewertung aller Blattknoten der Suche herangezogen.
Einige Optimierungstechniken werden ergänzt, darunter Transpositionstabellen, gezielte Zugordnung, Endgame-Datenbanken. Diese Techniken dienen ausschließlich der Reduktion von Laufzeit und Speicherbedarf und verändern weder das zugrunde liegende Minimax-Verfahren noch den berechneten Spielwert
Transpositionstabellen werden genutzt um die Berechnungen der Zustände abzuspeichern. Dies vermeidet redundante Berechnungen in MTD(f).
Aussichtsreiche Spielzüge werden zuerst besucht und werden wie folgt priorisiert:
- Züge mit zusätzlichem Zug
- Capture-Züge
- Vorschläge aus der Transpositionstabelle
Endspiel-Datenbanken speichern exakte Spielwerte für Kalah-Stellungen mit wenigen aktiven Steinen. Diese vorab berechneten Werte können während der Spielbaumsuche für größere Kalah-Instanzen abgefragt werden und ersetzen in diesen Fällen eine weitere Tiefensuche, wodurch sich die benötigte Rechenzeit deutlich reduziert.
¶ Resultate
Tabelle 5[1:8] zeigt die Endspielwerte für alle untersuchten Kalah-Varianten bis einschließlich Kalah(6,5). Die Variante Kalah(6,6) wurde darüber hinaus ebenfalls vollständig gelöst und besitzt den Endspielwert W für South[3]. Damit ist die Standardvariante von Kalah mit sechs Mulden pro Seite vollständig analysiert und stellt bei optimalem Spiel stets einen Gewinn für den Startspieler South dar.