Startseite
Explode! für Spieler
Spielregeln
Download
Credits
Versionsinfos
Explode! für Entwickler
KI-Entwicklung
Tiefensuche
Breitensuche
PI * Daumen
Android-Entwicklung
Geld verdienen
Explode! für Spieler
Spielregeln
Download
Credits
Versionsinfos
Explode! für Entwickler
KI-Entwicklung
Tiefensuche
Breitensuche
PI * Daumen
Android-Entwicklung
Geld verdienen
Der erste Anlauf, für Sistances EXPLODE! einen computergesteuerten Gegenspieler zu entwickeln, führte mich zur Tiefensuche mit Minimax-Algorithmus. Das Vorgehen ist ziemlich simpel und die Bewertungsfunktion kann vergleichsweise einfach gestrickt sein.
Wie ich auf der Einleitungsseite zur KI-Entwicklung schon erwähnt habe, muss eine vorausplanende KI eine Mindestanzahl an Zügen ziehen, um bestimmte Spielsteinkombinationen als gefährlich zu erkennen. Bei Sistances EXPLODE! kann ein Feld einen Wert zwischen 0 und 5 haben und einem der beiden Spieler gehören. (Bei einem Wert von 0 gehört das Feld niemandem. Dieser Wert kann aber nicht wieder erreicht werden, wenn ein Feld erst einmal besetzt wurde.)
Jeder Zug des Spielers kann den Wert eines eigenen Felds um 1 erhöhen. Es braucht also bis zu vier Züge, um ein eigenes Feld auf 5 zu bringen und einen weiteren Zug, um die umliegenden Felder durch Explosion dieses Felds anzugreifen. Da der Spieler und sein Gegner abwechselnd ziehen, muss die KI also mindestens 9 Halbzüge vorausrechnen, um in jedem Fall zu erkennen, ob sie einen Vorteil hat, das Feld zu erhöhen.
Die Tiefensuche versucht, vereinfacht ausgedrückt, jede Zugkombination bis zu einer gewissen Tiefe zu berechnen und dann den Zustand zu bewerten. Dabei berechnet der Algorithmus nacheinander zuerst eine komplette Zugfolge mit der vorher definierten Zahl von Maximalzügen, bevor er danach die nächste komplette Zugfolge berechnet, die er noch nicht bewertet hat.
Der Algorithmus ist so aufgebaut, dass nur sehr wenige Spielzugkombinationen im Speicher vorgehalten werden müssen. Der Minimax-Algorithmus, der bei der Tiefensuche zur Ermittlung des besten Zugs eingesetzt wird, erlaubt es, die bisherigen Spielzugkombinationen zu verwerfen, sobald er die sinnvollste (beste beziehungsweise schlechteste) Bewertung mit der Bewertung der aktuell überprüften Zugkombination verglichen hat.
Im Prinzip prüft der Algorithmus unoptimiert jede Zugkombination. Der Nachteil dabei ist, dass der Rechenzeit-Aufwand mit der Anzahl zu prüfender Halbzüge exponenziell ansteigen kann. Bei 5 Halbzügen ist die KI auf meinem Testsystem schon viele Sekunden beschäftigt. Bei den anvisierten mindestens 10 Halbzügen wäre die Wartezeit für den Spieler inakzeptabel hoch gewesen.
Aus diesem Grund habe ich mir die Breitensuche angeschaut, die einige Optimierungsmöglichkeiten bereithält.
Wie ich auf der Einleitungsseite zur KI-Entwicklung schon erwähnt habe, muss eine vorausplanende KI eine Mindestanzahl an Zügen ziehen, um bestimmte Spielsteinkombinationen als gefährlich zu erkennen. Bei Sistances EXPLODE! kann ein Feld einen Wert zwischen 0 und 5 haben und einem der beiden Spieler gehören. (Bei einem Wert von 0 gehört das Feld niemandem. Dieser Wert kann aber nicht wieder erreicht werden, wenn ein Feld erst einmal besetzt wurde.)
Jeder Zug des Spielers kann den Wert eines eigenen Felds um 1 erhöhen. Es braucht also bis zu vier Züge, um ein eigenes Feld auf 5 zu bringen und einen weiteren Zug, um die umliegenden Felder durch Explosion dieses Felds anzugreifen. Da der Spieler und sein Gegner abwechselnd ziehen, muss die KI also mindestens 9 Halbzüge vorausrechnen, um in jedem Fall zu erkennen, ob sie einen Vorteil hat, das Feld zu erhöhen.
Die Tiefensuche versucht, vereinfacht ausgedrückt, jede Zugkombination bis zu einer gewissen Tiefe zu berechnen und dann den Zustand zu bewerten. Dabei berechnet der Algorithmus nacheinander zuerst eine komplette Zugfolge mit der vorher definierten Zahl von Maximalzügen, bevor er danach die nächste komplette Zugfolge berechnet, die er noch nicht bewertet hat.
Der Algorithmus ist so aufgebaut, dass nur sehr wenige Spielzugkombinationen im Speicher vorgehalten werden müssen. Der Minimax-Algorithmus, der bei der Tiefensuche zur Ermittlung des besten Zugs eingesetzt wird, erlaubt es, die bisherigen Spielzugkombinationen zu verwerfen, sobald er die sinnvollste (beste beziehungsweise schlechteste) Bewertung mit der Bewertung der aktuell überprüften Zugkombination verglichen hat.
Im Prinzip prüft der Algorithmus unoptimiert jede Zugkombination. Der Nachteil dabei ist, dass der Rechenzeit-Aufwand mit der Anzahl zu prüfender Halbzüge exponenziell ansteigen kann. Bei 5 Halbzügen ist die KI auf meinem Testsystem schon viele Sekunden beschäftigt. Bei den anvisierten mindestens 10 Halbzügen wäre die Wartezeit für den Spieler inakzeptabel hoch gewesen.
Aus diesem Grund habe ich mir die Breitensuche angeschaut, die einige Optimierungsmöglichkeiten bereithält.