Heuristiken und andere Tricks

Mit dem Min/Max-Verfahren und der verbesserten Suchbaumgenerierung durch Alpha/Beta-Pruning sind die Grundlagen für eine spielstarke KI gelegt. In diesem Kapitel möchte ich abschließend noch kurz auf verschiedene Möglichkeiten eingehen, die KI noch 'intelligenter' zu machen bzw. ihr den letzten Schliff zu geben.

Die 9. Zug-Katastrophe

Bei einem Spiel wie TicTacToe ist es unter Umständen (in JavaScript jedoch nur mit einigem Rechen- und Zeitaufand, wie man merkt) noch möglich, den kompletten Spielbaum zu generieren. Betrachtet man aber 4-Gewinnt, Othello oder gar Schach wird einem schnell klar, dass das wohl nicht immer so funktionieren wird.
Der einfachste Ansatz besteht darin, eine Maximaltiefe einzuführen ab der die Spielbaumgenerierung abgebrochen wird. Der Haken hierbei ist, dass es unter Umständen passieren kann, dass der Spielverlauf z.B. bis zu einer Tiefe von 8 Zügen berechnet wird und bis zu diesem 8. Zug auch alles ganz gut aussieht, jedoch die Katastrophe im 9. Zug übersehen wird.
Eine Verbesserung besteht darin, dass man am Ende den ausgewählten Zug noch einmal genauer untersucht. Den berüchtigten 9. Zug kann man dabei natürlich eventuell trotzdem übersehen. Pech gehabt!
Ein weiterer Ansatz versucht wiederum das Verhalten des Menschen nachzuahmen. Dabei wird die Spielbaumgenerierung nur an solchen Stellen abgebrochen, die als stabile Spielsituation angesehen werden. Ein Beispiel: Wenn beim Schachspiel ein weißer Springer sowohl die schwarze Dame als auch den schwarzen König bedroht, so hat man es zweifellos mit einer eher spannenden Situation zu tun. In solchen Fällen sollte man sich dann noch ein paar Level mehr an Spielbaum gönnen, um genauer über diese unruhige Situation 'nachzudenken'.

Bewertungsfunktion mit Heuristiken

Wie bereits in Kapitel 2 verdeutlicht ist die Bewertungsfunktion das A und O. Zwar muss sie immer ein Kompromiss zwischen Zeitaufand und Qualität darstellen, jedoch sollte sie möglichst viel Spielwissen in Form von Heuristiken enthalten. Unter einer Heuristik kann man eine Art Faustregel verstehen, die zwar nicht immer hundertprozentig zutrifft, aber eine bessere Einschätzung einer gegebenen Spielsituation ermöglicht.
In Kapitel 2 wurden bereits Beispiele für Heuristiken eines Schachprogramms gegeben. Eine auf Schnelligkeit bedachte Bewertungsfunktion für Othello (auch als Reversi bekannt) könnte vielleicht nur die Anzahl der schwarzen und weißen Steine zählen, jedoch wird die Kurzsichtigkeit dieser Vorgehensweise schnell deutlich, wenn man sich die ständig schwankenden Spielsituation vor Augen führt. Die Bewertungsfunktion könnte z.B. dadurch aufgewertet werden, dass sie Rand- und andere Steine, die nicht mehr vom Gegenspieler 'umgedreht' werden können, bestimmt und mit einer größeren Gewichtung in die Bewertung einfließen läßt.

Othello: Sichere Steine

Flexible Strategie

Eine gute Spielstrategie bleibt nicht über ein ganzes Spiel hinweg gleich, sondern passt sich den unterschiedlichen Anforderungen an. Ein Schachspieler hat nicht bereits bei seinem Eröffnungszug e2-e4 die Mattsetzung seines Gegners im Sinn (jedenfalls nicht so direkt :-), sondern versucht erstmal seine Figuren zu positionieren und später vielleicht die Deckung des Gegners zu durchbrechen. Eine ähnliche 'gestaffelte' Spielstrategie sollte eine (sehr) gute Bewertungsfunktion realisieren.

Schlusswort

Wie alle diese Tricks und Kniffe zeigen, kann ein gutes Spielprogramm nicht nur aus einem Suchverfahren bestehen, sondern erfordert auch Fachwissen - je mehr, desto besser. Wenn dieses Wissen in Form von Heuristiken formuliert werden kann, so sind Spielprogramme in der Lage, so manchen menschlichen Gegner zu schlagen.

Wir hoffen, eine interessante und unterhaltsame Einführung in das Feld der künstlichen Intelligenz von Spielprogrammen geschaffen zu haben und können die ProgrammiererInnen der Leserschaft nur dazu ermutigen, sich selbst mal an einem spielenden Programm zu versuchen. Es macht Spaß gegen seine eigene Kreation zu verlieren!