Softwareentwicklung: Tic-Tac-Toe

Eines der Probleme, die ATARI nie los wurde, war das Image als Spielecomputer. Eine ordentliche Textverarbeitung auf einem ATARI konnte sich so mancher schlichtweg nicht vorstellen. Dass eine solche Abwertung aber sicherlich unberechtigt ist, möchte ich an einem Beispiel zeigen.

Spiele Computer

Ich würde sogar, ganz im Gegenteil, sagen, dass es Office-Anwendungen, Bildbearbeitung, etc. „lediglich" mit Problemstellungen zu tun haben, die schon aus Konzepten oder Überlegungen hervorgegangen sind. Spiele dagegen werden mit dem „echten Leben" konfrontiert. Beim Schach z.B. muss sich das Programm mit dem Menschen messen. Solche Anforderungen sind nicht nur wesentlich höher, sie lassen sich auch nur mit permanenten Innovationen angehen.

Tic-Tac-Toe

Nehmen wir als Beispiel Tic-Tac-Toe. Nicht die Girlies - leider -, sondern das Spiel. In einem Filmklassiker hat es einen Supercomputer zur Verzweiflung getrieben. Das Problem ist zum einen, den momentan günstigsten Zug zu bewerten, andererseits sollten aber auch die folgenden Züge bedacht werden. Im Film kam der Rechner zwar zu der Erkenntnis, dass es keine Sieger geben kann - aber nichts desto trotz soll es hier als Beispiel dienen.

Gametree

Zur Lösung bietet sich ein Gametree an. Die Idee ist, bei einer gegebenen Spielposition die Möglichkeiten für den nächsten Zug durchzuspielen und den gleichen Prozeß mit jeder dieser Möglichkeiten zu wiederholen, bis eine bestimmte Tiefe (Vorausschau) erreicht ist. So lässt sich der günstigste Zug ermitteln. Weil Zug und Gegenzug sich abwechseln, kann man die Bewertung für eine Möglichkeit mit plus und minus gestalten. Was für den Gegner günstig ist, mindert die eigene Chance.
Zunächst wird also ein Rootnode angelegt, von dem aus die Möglichkeiten als Son verbunden werden. Untereinander sind diese Sons über Next verknüpft. So kann man immer alle Sons auf einer Ebene ansprechen, z.B. beim Auswerten und über ptr->son jeweils zur nächsten Ebene fortschreiten. Um herauszufinden, welcher Zug den größten Vorteil verspricht, werden nur die Leafs bewertet, also jeweils die Positionen auf einer Ebene verglichen, und der optimale Node wird über die Son-Ebenen immer durchgereicht. Der erste Schritt (Son) zu dem besten End-Leaf ist dann der gesuchte Zug.

Rekursion

Die Funktionen im Listing sind rekursiv geschrieben. Das ist zwar schön zum Lesen und in dem Beispiel auch gefahrlos, aber wenn Sie das beim Schach versuchen, wird der Stack sicher streiken und Sie die Antwort nie erfahren. Eine optimale Suchtiefe von 9 beschäftigt den Rechner hier schon ganz hübsch. Der Schwachpunkt bei diesem Verfahren ist, dass man zukünftige Züge nur vermuten kann. Deshalb ist eine große Tiefe auch nur bedingt sinnvoll.

Bewertung

Das Beispiel demonstriert aber den Umgang mit Trees und wie man sich durch die Zweige hangeln kann; und der Code ist schön kompakt. Ähnlich, wie bei den Ouicksort-Funktionen noch eine Vergleichsfunktion benötigt wird, sind die Funktionen zum Bewerten der Position und zum Erstellen der möglichen neuen Züge austauschbar gehalten. Sinnlose Möglichkeiten kann man sich dadurch ersparen und den Tree in Grenzen halten. Für die Bewertung einer Position von Tic-Tac-Toe kann man die Anzahl der Linien und Diagonalen, die einem selber noch offen bleiben, von denen für den Gegner abziehen und einfach diese Zahl als Bewertung benutzen. Bei der Suche nach dem Weg zum besten Leaf kümmert sich die Funktion select_move() dann automatisch darum, dass die Benotungen der gegnerischen Möglichkeiten zeichenverkehrt behandelt, also praktisch abgezogen werden. Dafür ist der Parameterturn in der Struktur gamenode zuständig.
Ansonsten enthält die Struktur noch das Spielbrett (board) und die Verzweigungen für Son (zur nächsten Ebene) und für Next (die Ebene untereinander).

Der Code

Die Funktion make_move() kann aus einem Programm heraus aufgerufen werden und liefert das Board mit dem besten Zug zurück. Als Übergabeparameter verlagert sie das alte Board, die Suchtiefe und den Spieler. Zunächst baut sie einen Baum auf, wozu die Funktion build_Ieafs() benötigt wird. build_Ieafs() ist die Routine, in der neue Positionen erstellt werden, und wie gesagt, ist es nicht immer sinnvoll, alle Möglichkeiten durchzutesten. Die Funktionen game_tree() und build_branches(), in der build_Ieafs() benötigt wird, bauen den Suchbaum vollständig auf. Danach verzweigt select_move() jeweils zu den Leafs und liefert letztendlich einen Pointer auf den Son des Rootnodes, der zu dem besten Leaf geführt hat. Zusätzlich wird im Parameter value die Bewertung, die der Node für sein Board erhalten hat, noch mitgeteilt. Das Board aus dem so ermittelten Node wird dann in das Feld newboard übertragen. Und nach Beendigung von make_move() steht mit newbrd also das Spielfeld für den nächsten Gegenzug bereit.

Vorausschau

Sie brauchen sich eigentlich nur um build_leafs() und um test_board() für die Bewertung zu kümmern. Um für eine andere Situation als ein Tic-Tac-Toe Spiel Voraussagen zu machen, müsste man das Board in der Struktur gamenode austauschen und die geeigneten Funktionen für build_leafs() und test_board() schreiben. Sofern der Stack mitmacht, kann man so generell einen Blick in eine virtuelle Zukunft werfen und dann den optimalen nächsten Schritt wagen.
Die Listings zu diesem Artikel sowie das kompilierte Programm erhalten Sie auch über die Spezial-Diskette 7/8 1998.