Ein Framework für die Entwicklung unseres Ataxx-Klons haben wir bereits im ersten Teil des Artikels kennengelernt. Nun geht es ans Eingemachte: Wir betrachten die zum Einsatz kommenden KI-Routinen.

Sie sind auf der Suche nach einer abwechslungsreichen Brettspieladaption für zwei Personen mit einem überaus dynamischen Spielverlauf und einem einfach zu erlernenden Regelwerk, das lediglich zwei Arten von Spielzügen (Klon- sowie Sprungzüge) kennt? Dann dürfte das Spiel Ataxx ganz nach Ihrem Geschmack sein. Um zu verhindern, dass eine Ataxx-Partie immerzu nach dem gleichen Schema verläuft, können wir eine mehr oder weniger große Anzahl von Spielbrettfeldern für die Dauer eines Spiels mit unüberwindbaren Hindernissen blockieren (Abb. 1).

Abb. 1: Blockierte Spielfelder in Ataxx

Auch sind wir im Unterschied zu Spielen wie Schach oder Dame nicht gezwungen, bei jeder Partie auf die in Abbildung 2 gezeigte klassische Startaufstellung zurückzugreifen, bei der Spieler 1 seine beiden Spielsteine auf dem linken oberen sowie dem rechten unteren Eckfeld und Spieler 2 seine Steine auf dem rechten oberen sowie dem linken unteren Eckfeld platziert. In Kombination sind beide Maßnahmen bestens dazu geeignet, die Spieler stets vor neue und abwechslungsreiche Herausforderungen zu stellen.

Abb. 2: Ataxx-Startaufstellungen sind flexibel

Im Zuge der Implementierung unseres Ataxx-Spieleprototyps greifen wir auf das im letzten Artikel vorgestellte Brettspiel-Framework zurück. In diesem Zusammenhang stehen uns für die Beschreibung und Bewertung der durchzuführenden Spielzüge die drei Klassen C1DimMoveDesc, C2DimMoveDesc sowie C3DimMoveDesc zur Verfügung. Sofern wir eine Liste mit den bislang am besten bewerteten Spielzügen aufstellen bzw. aktualisieren müssen, können wir hierbei auf die nachfolgend genannten Funktionen Generate_ListOfBestMoves_IntegerEvaluation(), Generate_ListOfBestMoves_FloatEvaluation() bzw. Update_ListOfBestMoves_IntegerEvaluation() sowie Update_ListOfBestMoves_FloatEvaluation() zurückgreifen.

Für die Handhabung der zu einer Spielstellung gehörigen Daten bietet sich die Nutzung der CGameStateValues-Klasse an. Beim Umgang mit den während einer laufenden Partie ausgeführten Spielzügen machen wir uns die CGameStateRingBuffer-Klasse zunutze. Dank der Verwendung der besagten Ringbuffer-Klasse benötigen wir für die Implementierung eines der wohl wichtigsten Features rundenbasierter Computerspiele – gemeint ist die Möglichkeit, sämtliche Spielzüge wieder rückgängig machen zu können – lediglich einige wenige Programmzeilen. Im Zuge der Speicherverwaltung greifen wir bei der Verwaltung eines CGameStateValues-Objektpools auf eine Instanz der CSimpleGameStatePool-Klasse zurück. Die CGameStatePool-Klasse gestattet uns zusätzlich zur Speicherverwaltung auch einen effizienten Zugriff auf die im Gebrauch befindlichen CGameStateValues-Instanzen, was mittels einer doppelt verketteten Liste realisiert wird.

Mit Hilfe der CExtendedGameStatePool-Klasse lassen sich die Instanzen eines CGameStateValues-Objektpools in Form eines sogenannten Spielbaums (Game Tree) verwalten. Im Unterschied zur zuvor genannten Klasse erfolgt der Zugriff auf die einzelnen CGameStateValues-Instanzen mittels mehrerer doppelt verketteter Listen, wobei die Anzahl dieser Listen der Anzahl an Spielbaumebenen (Abb. 3) entspricht. Mit anderen Worten: jede verkettete Liste ist einer bestimmten Spielbaumebene zugeordnet und ermöglicht uns einen effizienten Zugriff auf diejenigen Spielstellungen, die sich innerhalb derselben Spielbaumebene befinden.

Abb. 3: Game Tree (Ausschnitt)

Die Minimax-Strategie

Unerfahrene Gelegenheitsspieler gehen bei der Auswahl des nächsten Spielzugs für gewöhnlich wie folgt vor: Man schaut sich an, welche Spielzüge man selbst machen kann und überlegt sich, mit welchen Gegenzügen der Kontrahent auf die eigenen Züge antworten könnte. Es muss wohl nicht extra betont werden, dass die Bewertung eines eigenen Spielzugs anhand der möglichen Gegenzüge nicht sonderlich fundiert ist und dass es durchaus von Vorteil wäre, wenn man bei der Bewertung auch diejenigen Spielzüge berücksichtigen würde, mit denen man seinerseits auf die Gegenzüge reagieren kann. In der Praxis würde man als Spieler eine solche Herausforderung bei einer komplizierten Spielstellung allerdings nur dann vollumfänglichen bewältigen können, wenn man mit einem übermenschlichen Gedächtnis gesegnet worden wäre. Die Vorgehensweise, bei der man die erlaubten Spielzüge und ihre möglichen Gegenzüge – dem gesunden Menschenverstand folgend – gegeneinander abwiegt, wird gemeinhin als Minimax-Strategie bezeichnet:

• Ob ein möglicher Spielzug von Spieler 1 (bzw. Spieler 2) gut oder schlecht ist, hängt selbstverständlich davon ab, mit welchen Gegenzügen Spieler 2 (bzw. Spieler 1) auf den besagten Spielzug antworten kann.

• Unter all den möglichen Gegenzügen ist nur derjenige von Bedeutung, der die Erfolgsaussichten von Spieler 1 (bzw. Spieler 2) auf ein Minimum reduziert (Minimierer-Gegenzug) und die Siegchancen von Spieler 2 (bzw. Spieler 1) entsprechend maximiert.

• Bei unseren Überlegungen gehen wir selbstredend davon aus, dass sich Spieler 2 (bzw. Spieler 1) immer für den aus seiner Sicht bestmöglichen Zug entscheiden wird, da er die Partie schließlich ebenfalls gewinnen möchte.

• Was den eigenen Spielzug betrifft, wird sich Spieler 1 (bzw. Spieler 2) am Ende immer für denjenigen Zug entscheiden, dessen Erfolgsaussichten trotz des zugehörigen Minimierer-Gegenzugs nach wie vor am größten sind (Maximierer-Spielzug).

Spielbäume (Game Trees)

Die Tatsache, dass ein menschlicher Spieler bei einer so breit angelegten Suche (Breitensuche) schnell einmal die Übersicht über den vor dem geistigen Auge erstellten Spielbaumausschnitt – siehe hierzu noch einmal Abbildung 3 – verliert, dürfte in Anbetracht der schieren Anzahl an möglichen Zügen und Gegenzügen wohl niemanden sonderlich überraschen. Unsere einzige Möglichkeit, mit der wir unsere Unzulänglichkeiten zumindest teilweise kompensieren können, besteht nun darin, unsere Suchstrategie ein wenig abzuändern und unsere...