Vier gewinnt – mit C++ und ClanLib

Vier gewinnt ist ein simples Spiel, dass wohl jeder kennt. Eine künstliche Intelligenz dafür sollte doch recht einfach implementiert werden können. Ich zeige euch, dass man mit heutiger Rechenleistung ohne Optimierung keine perfekte KI schreiben kann.

Vier gewinnt – mit C++ und ClanLib

Eine perfekte KI kennt alle möglichen Lösungen und kann zu jedem Zustand die optimale Aktion setzen. In meinem 6*7 (42 Felder) großen Spielfeld kann jeder Spieler pro Zug aus 7 Spalten wählen. Berechnet man mit der KI zum Beispiel nur die nächsten 3 Züge, dann sind das 7 + 7*7 + 7*7*7 = 399 mögliche Zustände. Bei 4 Zügen sind das schon 2800 mögliche Zustände – ein Spiel hat 42 Züge! Das berechnen der Züge und die Bewertung der Lösung dauert. Damit man nicht ewig auf den Zug des Gegners warten muss darf man maximal 6-8 Züge voraus berechnen.

Source Code

Das Programm wurde mit der ClanLib Engine in C++ implementiert. Der Aufbau entspricht meinen anderen Beispielen (Sanduhr, Waldbrand, L-System oder Damenproblem). Der Source Code ist auf meiner GitHub Seite zur Verwendung freigegeben.

Beginnen wir bei den Konstanten aus der globals.h. Dort findet man Variablen die das Board definieren und Größen zum Zeichnen der Images festlegen:

// board dimension
#define LEVEL_WIDTH 7
#define LEVEL_HEIGHT 6

// cursor
#define CURSOR_SCALE_FACTOR 2
#define CURSOR_SIZE 80
#define CURSOR_OFFSET 17 // cursor position middle

// map
#define TILES_SCALE_FACTOR 2
#define TILES_SIZE 80
#define MAP_OFFSET 20 // render map below cursor

Im Anschluss daran werden zahlreiche Konstanten für die KI Berechnung festgelegt, dazu später mehr. Das Programm hat folgenden Ablauf:

• Board und Cursor mit aktuellem Zustand zeichnen
• Benutzereingabe, man muss den eigenen Zug machen (mit Pfeiltasten Cursor bewegen, mit Enter oder der Leertaste den Stein legen)
• KI Reaktion berechnen und ausgeben
• Prüfen ob jemand das Spiel gewonnen hat

Der Spielzustand wird über ein Array definiert in dem jedes Element einen der folgenden Zustände haben kann:

enum Fieldvalue { EMPTY = 0, RED = 1, YELLOW = 2 };

In der render() Methode wird dieser Zustand gezeichnet. Das Grid wird über map.h und field.h definiert. In der compute() Methode in app.cpp wird die KI Routine aufgerufen.

Künstliche Intelligenz

Für die Berechnung des nächsten Zugs der KI wird über die Klassen GameTree und GameNode ein Baum erstellt. Jede Ebene des Baums enthält alle möglichen Züge. Der Baum wird für eine maximale Tiefe von:

#define TREE_DEEP 6 // max deep of precomputed gametree

jedesmal neu erstellt. Das bedeutet die KI hat 6 Züge in die Zukunft gerechnet. Dieses Wissen hilft der KI aber noch nichts. Sie muss nun noch den besten Zug herausfinden, das geht wie folgt:

• auf der untersten Ebene wird jeweils die Variable cost durch eine Kostenfunktion errechnet. Siehe dazu evaluate() in der GameNode Klasse. Es wird ein numerischer Wert ermittelt, anhand der Info ob die KI 2, 3, oder schon 4 Steine in der Reihe hat. 4 Steine sind dabei höher gewichtet als 3 und 3 höher als 2. Je höher der Wert, desto näher ist man am Sieg.
• über den Minimax Algorithmus wird jeweils entweder der schlechteste, oder der beste Wert eine Ebene höher übernommen. Der beste Wert wird für den eigenen Zug übernommen, der schlechteste für den Zug des Gegners.
• der cost Wert wird bis auf die höchste Ebene übernommen. Jede der 7 Spalten hat nun einen numerischen Wert zugeordnet, die KI setzt den Stein dort, wo der niedrigste Wert steht (bester Zug für den aktuellen Zustand).

in der runAI() Methode sieht das wie folgt aus:

GameTree gametree(_map->_field.getcopy(), _player, TREE_DEEP);
gametree.evaluateLeafes();
gametree.minimax();
int turn = gametree.getTurn();

In turn steht nun der Index der Spalte in der nun der KI Stein gesetzt wird.

Experimentieren

Mit aktuellen Einstellungen ist die KI schon sehr stark und macht fast keine Fehler. Man muss schon gut Vier Gewinnt spielen können um sie zu besiegen. Ihr könnt nun gerne mit den KI Konstanten experimentieren. Da kann man zum einen die berechnete maximale Tiefe des Spielbaums einstellen (ist der Wert zu hoch rechnet der Computer ewig!). Außerdem kann man über die WEIGHTFACTORS in den Konstanten definieren wie stark eine 2er, 3er und 4rer Reihe sich auf den cost Wert für den Minimax Algorithmus auswirkt. Ändert man diese Werte merkt man, dass die KI andere Züge durchführt. Ob diese dann besser oder schlechter ist stellt man meist erst nach mehreren Partien fest.

Fazit

Diese Vier Gewinnt künstliche Intelligenz war meine erste ausprogrammierte Spiele AI. Es hat viel Spaß gemacht diese zu entwickeln und über zahlreiche Parameter zu kalibrieren. Der Computer als Gegner ist zwar noch nicht perfekt, er ist aber trotzdem sehr herausfordernd. Auf jeden Fall würde eine unschlagbare KI sowieso das Spiel schon nach wenigen Partien langweilig machen. Ich denke ich habe für ein Spiel einen recht guten Gegner entwickelt.

Welche Anpassungen würdet ihr bei der KI machen? Wie viele Züge benötigt ihr für den Sieg?