Im Laufe der Entwicklung von Sistances Explode! habe ich mir einige Strategien für künstliche Intelligenzen angeschaut, die für Spiele wie dieses häufig vorgeschlagen werden.
Ich stelle einige davon kurz vor und gehe dann auf die Vor- und Nachteile ein, die ich für Sistances EXPLODE! ausgemacht habe.

Anforderungen an die KI

Das Ziel der KI soll sein, aus einer Menge von Zügen denjenigen auszuwählen, durch den sie den größten Vorteil gegenüber dem Gegner erlangt oder den geringsten Nachteil.
Züge, bei denen die KI gewinnt, sind entsprechend mehr wert als alle anderen Züge. Existiert kein Zug, durch den die KI direkt gewinnt, muss sie die daraus resultierende Spielsituation bewerten. Derjenige Zug, der zur für die KI besten Folgesituation führt, wird von der KI gespielt.

Bewertungsfunktion

Um eine Spielsituation als gut oder schlecht einzuschätzen, benutzen typische KI-Algorithmen eine sogenannte Bewertungsfunktion. Die Bewertungsfunktion liefert einen einfachen Wert -üblicherweise eine Zahl-, der beschreibt, wie gut oder wie schlecht die Situation für einen bestimmten Spieler ist.
Abhängig von der Definition bedeuten hohe Werte gute Situationen und niedrige (gegebenenfalls sogar negative) Werte schlechte Situationen.
Eine Spielsituation, in der die KI das Spiel gewonnen hat, wird bestmöglich bewertet, eine Spielsituation, in der die KI verloren hat (oder verlieren wird), wird schlechtestmöglich bewertet.

Um eine Situation zu bewerten, können einfache und komplexe Sachverhalte herangezogen werden. Der Minimax-Algorithmus zieht sogar die Bewertung zukünftiger, erreichbarer Spielsituationen heran.

Eine Bewertungsfunktion für Sistances EXPLODE! könnte einige der folgenden Informationen berücksichtigen.

• Wie viele Felder besitze ich? Wie viele Felder besitzt der Gegner?
• Wie viele gegnerische Felder bedrohe ich? Wie viele meiner Felder bedroht der Gegner?
• Welchen Wert haben meine Felder? Welchen Wert haben die gegnerischen Felder?
• Wie viele Züge kann ich machen, bevor ich den Gegner angreifen muss? Wie viele Züge bleiben dem Gegner?
• Kann ich expandieren, ohne eigene hochwertige Felder zur Explosion zu bringen? Kann es der Gegner?

Wie man sieht, sind diese einfachen Überlegungen auch diejenigen, die man als Spieler selbst recht bald anstellt. Meine aktuelle Bewertungsfunktion verwendet zwar noch einige komplexere Fragestellungen, doch ist es schon mit den genannten Regeln möglich, eine halbwegs vernünftige Anfänger-KI zu schreiben.

Vorausplanen - Tiefensuche, Breitensuche, Minimax-Algorithmus

"Welchen Zug wird der Gegner machen, wenn ich nun diesen Zug mache? Wie wird der Gegner reagieren, wenn ich stattdessen die andere Spielsituation herbeiführe?" - eine vorausplanende KI versucht, alle möglichen Züge oder zumindest die vielversprechendsten Züge vorauszuplanen, um die beste Situation nach einer ganzen Reihe von Spielzügen zu ermitteln - inklusive des Zugs, den sie aktuell machen sollte.

Zwei verbreitete Vorgehensweisen sind die sogenannte Breitensuche und die Tiefensuche, jeweils kombiniert mit dem Minimax-Algorithmus. Beim Minimax-Algorithmus nimmt die KI an, dass beide Spieler (also die KI selbst und ihr Gegenspieler) jeweils denjenigen Zug wählen, der ihnen nach einer Reihe von Zügen die beste Spielsituation garantiert.
Dadurch, dass die KI und ihr Gegenspieler abwechselnd am Zug sind, muss die KI davon ausgehen, dass nach ihrem eigenen Zug der Gegner sich für den Zug entscheidet, der zum (für die KI) schlechtestmöglichen Ergebnis führen wird. Das Ziel des Algorithmus ist es nun, alle relevanten Spielzug-Folgen zu analysieren und zu bestimmen, wie gut beziehungsweise schlecht die KI am Ende dieser Zugfolgen mindestens dastehen wird.
Wenn sie einen Zug findet, bei dem nach N Zügen die KI auf jeden Fall gewinnt, wird sie diesen Zug bestmöglich bewerten. Wenn sie auf jeden Fall verliert, wird der Zug schlechtestmöglich bewertet.

Theoretisch kann eine KI alle Züge "bis in die Unendlichkeit" vorausberechnen und ermitteln, ob es eine Zugfolge gibt, mit der sie auf jeden Fall gewinnt, ob es eine Zugfolge gibt, durch die der Gegner sie auf jeden Fall besiegen wird oder ob es Zugfolgen gibt, die zu Patt-Situationen führen.
Praktisch sind einer KI mehrere Grenzen gesetzt, die es unmöglich machen, in einem komplexen Spiel, wie Sistances EXPLODE! oder gar Schach alle Züge in beliebiger Zugtiefe zu berechnen.

Die erste Grenze ist die Rechenzeit, die ein Computer für "unendlich lange Berechnungen" benötigt. Ein Spieler erwartet, dass eine KI nach relativ kurzer Zeit reagiert.
Je nach verwendetem Algorithmus steigt der Rechenaufwand pro zusätzlicher Zugtiefe exponenziell an.

Die zweite Grenze ist die Speicherkapazität, die der Algorithmus braucht, um alle Spielsituationen zu speichern. Bei Sistances EXPLODE! existieren 25 Felder, die theoretisch fast alle einen von elf verschiedenen Werten annehmen können. Das ergibt theoretisch 11 hoch 25 mögliche Feldbelegungen, von denen mit den bestehenden Zugregeln praktisch aber nur ein Bruchteil tatsächlich erzeugt werden kann. Dennoch ist auch diese Zahl noch weit größer als typischerweise auf einem Android-Gerät in Byte zur Verfügung steht. Ein Byte ist dabei noch sehr großzügig geschätzt, da eine eindeutige ID der Größe 11 hoch 25 (minus X), sowie die Information, welcher Spieler am Zug ist, in dem Datensatz gespeichert werden muss. Will man noch Nutzdaten transportieren (zum Beispiel die Bewertung der Spielsituation oder Verknüpfungen zu Folgezuständen), ist man schnell bei einem Vielfachen davon.

Aus diesem Grund begrenzen KI-Algorithmen die Anzahl untersuchter Züge auf verschiedene Art und Weise. Für Sistances EXPLODE! erachte ich eine Zugtiefe von 10 für sinnvoll. Bleibt die KI wesentlich darunter, kann sie viele taktische Maneuver nicht erkennen, die sie selbst oder der Gegner in Stellung bringen könnte. Geht sie darüber hinaus, wird der Rechenaufwand entsprechend größer.

Zu den beiden Algorithmen habe ich Versuche durchgeführt und auf den entsprechenden Seiten beschrieben.

Menschliches Bewerten

Menschen denken anders als ein Algorithmus. Sie schauen sich das Spielfeld an und erkennen taktische Anordnungen, die der KI zunächst verborgen bleiben. Die Tiefen- und Breitensuche arbeitet im Prinzip stoisch jede Zugfolge ab, bis die Bewertung der Situation eindeutig ist (gewonnen beziehungsweise verloren) oder zumindest mit einer relativ simplen Bewertungsfunktion einigermaßen realistisch eingeschätzt werden kann.

Falls der Speicher für eine Breitensuche oder die Rechenzeit für eine Tiefensuche in der erforderlichen Zugtiefe nicht vorhanden ist, muss eine verbesserte Bewertungsfunktion zum Tragen kommen. Das Ziel dieser Bewertungsfunktion ist es, komplexere Fragestellungen und Sachverhalte zu prüfen. Während eine Tiefen- oder Breitensuche alleine durch das Ergebnis nach N Zügen vorhersagen kann, dass eine bestimmte Zugfolge schlecht ist, muss eine Bewertungsfunktion, die nicht "in die Zukunft schauen" kann, strategische Elemente als solche kennen.
Vereinfacht ausgedrückt erkennen einfache Bewertungsfunktionen für Tiefen- und Breitensuche gefährliche Spielkonstellationen nur daran, dass sie in ihrer Sichtweite (also nach maximal N Zügen) zu einer schlechten Spielsituation führen, ohne dass sie wissen, weshalb das so ist.
Eine komplexe Bewertungsfunktion, die das taktische Denkvermögen eines menschlichen Spielers simuliert, muss Feldkonstellationen einem Muster zuordnen können, das ihr als gefährlich bekannt ist.

Den Versuch, eine solche KI zu schreiben, habe ich unter "PI * Daumen" beschrieben.