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 zweite Versuch, den ich nach der Tiefensuche unternommen habe, war eine Breitensuche.
Generell bietet die Breitensuche gegenüber der Tiefensuche einige Vorteile. Der erste Vorteil ist, dass bei einer Zeitgrenze, die man der KI gibt, jeder Zug gleichmäßig gut (bzw. tief) untersucht wird. Der zweite Vorteil besteht darin, dass einige der Nachteile dieses Verfahrens durch Optimierungen abgefedert werden können.
Der größte Nachteil, den ich in der Breitensuche sehe, ist die Notwendigkeit, viele Spielzustände parallel zu speichern. Das ergibt eine immens hohe Speicherbelastung. Erfreulicherweise kann man sowohl die notwendige Speicherkapazität senken als auch die Anzahl der Berechnungen, die zur Zuganalyse erforderlich sind.
Wenn man den Breitensuche-Algorithmus unoptimiert implementiert, entstehen aus diesen 16 Situationen noch einmal 16 * 4, also 64, Folge-Spielsituationen, aus diesen dann wiederum 64 * 4, also 256 Spielsituationen und so weiter.
Natürlich wird es nicht bei jeweils vier Folgesituationen bleiben, denn irgendwann werden die Spieler durch Expansion neue Spielzugmöglichkeiten erschließen, bis ein Spieler vielleicht bis zu 24 Zugmöglichkeiten besitzt.
Glücklicherweise sind ab dem dritten Halbzug bei weitem nicht alle Folgespielsituationen einzigartig. Angenommen, der rote Spieler erhöht zuerst Feld 1, der blaue Spieler danach Feld 25 und der rote Spieler schließlich Feld 2. Dann erreicht er eine Spielsituation, die er auch erreicht hätte, wenn er zuerst Feld 2 erhöht hätte, dann der blaue Spieler Feld 25 und der rote Spieler dann Feld 1.
Wenn man den Spielsituationen nach X Halbzügen beibringt, dass es in einer Liste "Spielsituationen nach X+1 Halbzügen" Spielsituationen gibt, die sie durch einen bestimmten Zug erreichen, dann muss eine einzigartige Spielsituation nach X+1 Halbzügen nur noch ein einziges Mal ihre nachfolgenden Spielsituationen berechnen und bewerten lassen, anstatt sie mehrfach rekursiv bis zur maximalen Zugtiefe zu prüfen.
Ich habe den Algorithmus getestet und festgestellt, dass die Einsparungen an Rechenzeit und Speicherplatz enorm sind. Schließlich machen sich nach X+2, X+3 oder noch weitreichenderen Spielzügen beachtliche Synergieeffekte bemerkbar.
Schlimmer noch: obwohl das P920 der Anwendung 64 MB Platz anbot, kam es schnell zu OutOfMemory-Exceptions.
Natürlich ist es möglich, den Speicherverbrauch zu senken, indem ich die Objekte überarbeite, die die Spielzustände zwischenspeichern. Aber ich muss auch bedenken, dass Smartphones mit anderen Konfigurationen vielleicht noch wesentlich weniger Speicherplatz zur Verfügung stellen. Und von diesem Speicher benötige ich ja auch Teile für die Spielgrafiken.
Letztendlich entschloss ich mich, mich an einem Bewertungsalgorithmus zu versuchen, der sich nicht originär darauf verlässt, Züge stoisch vorauszuberechnen, sondern taktische Elemente erkennt und sinnvolle Bewertungen vornimmt. Dazu mehr kannst Du im nächsten Abschnitt lesen.
Generell bietet die Breitensuche gegenüber der Tiefensuche einige Vorteile. Der erste Vorteil ist, dass bei einer Zeitgrenze, die man der KI gibt, jeder Zug gleichmäßig gut (bzw. tief) untersucht wird. Der zweite Vorteil besteht darin, dass einige der Nachteile dieses Verfahrens durch Optimierungen abgefedert werden können.
Der größte Nachteil, den ich in der Breitensuche sehe, ist die Notwendigkeit, viele Spielzustände parallel zu speichern. Das ergibt eine immens hohe Speicherbelastung. Erfreulicherweise kann man sowohl die notwendige Speicherkapazität senken als auch die Anzahl der Berechnungen, die zur Zuganalyse erforderlich sind.
Eine Optimierung
Zu Beginn eines Spiels ist das Spielfeld immer gleich belegt. Der Spieler und der Gegenspieler verfügen jeweils über vier besetzte Felder. Daraus folgt, dass dem beginnenden Spieler vier verschiedene Halbzüge zur Verfügung stehen, die in vier unterschiedlichen Folgesituationen münden. Ausgehend davon hat der zweite Spieler ebenfalls vier Zugmöglichkeiten, die jeweils in vier unterschiedlichen Spielsituationen aufgehen. Nach zwei Halbzügen existieren damit schon 16 unterschiedliche Spielfeldbelegungen.Wenn man den Breitensuche-Algorithmus unoptimiert implementiert, entstehen aus diesen 16 Situationen noch einmal 16 * 4, also 64, Folge-Spielsituationen, aus diesen dann wiederum 64 * 4, also 256 Spielsituationen und so weiter.
Natürlich wird es nicht bei jeweils vier Folgesituationen bleiben, denn irgendwann werden die Spieler durch Expansion neue Spielzugmöglichkeiten erschließen, bis ein Spieler vielleicht bis zu 24 Zugmöglichkeiten besitzt.
Glücklicherweise sind ab dem dritten Halbzug bei weitem nicht alle Folgespielsituationen einzigartig. Angenommen, der rote Spieler erhöht zuerst Feld 1, der blaue Spieler danach Feld 25 und der rote Spieler schließlich Feld 2. Dann erreicht er eine Spielsituation, die er auch erreicht hätte, wenn er zuerst Feld 2 erhöht hätte, dann der blaue Spieler Feld 25 und der rote Spieler dann Feld 1.
Ein Beispiel, wie unterschiedliche Zugfolgen zur gleichen Folgesituation führen können.
 |  Gemeinsame Ausgangssituation |  |
 Situation 1 nach einem Zug |  Alternative Situation 2 nach einem Zug | |
 Situation nach gegnerischem Zug |  Situation nach gegnerischem Zug | |
 |  Gemeinsame Situation |  |
Wenn man den Spielsituationen nach X Halbzügen beibringt, dass es in einer Liste "Spielsituationen nach X+1 Halbzügen" Spielsituationen gibt, die sie durch einen bestimmten Zug erreichen, dann muss eine einzigartige Spielsituation nach X+1 Halbzügen nur noch ein einziges Mal ihre nachfolgenden Spielsituationen berechnen und bewerten lassen, anstatt sie mehrfach rekursiv bis zur maximalen Zugtiefe zu prüfen.
Ich habe den Algorithmus getestet und festgestellt, dass die Einsparungen an Rechenzeit und Speicherplatz enorm sind. Schließlich machen sich nach X+2, X+3 oder noch weitreichenderen Spielzügen beachtliche Synergieeffekte bemerkbar.
Speicher voll...
Als ich den Algorithmus mit sinnvollen Halbzugtiefen (10 und höher) getestet habe, stellte sich heraus, dass die zu speichernden Spielsituationen schnell sehr viel Speicher verbrauchen. Der Rechenzeitgewinn, den ich durch die Optimierung erhalten habe, verpuffte schnell, als der Garbage Collector anfing zu arbeiten.Schlimmer noch: obwohl das P920 der Anwendung 64 MB Platz anbot, kam es schnell zu OutOfMemory-Exceptions.
Natürlich ist es möglich, den Speicherverbrauch zu senken, indem ich die Objekte überarbeite, die die Spielzustände zwischenspeichern. Aber ich muss auch bedenken, dass Smartphones mit anderen Konfigurationen vielleicht noch wesentlich weniger Speicherplatz zur Verfügung stellen. Und von diesem Speicher benötige ich ja auch Teile für die Spielgrafiken.
Letztendlich entschloss ich mich, mich an einem Bewertungsalgorithmus zu versuchen, der sich nicht originär darauf verlässt, Züge stoisch vorauszuberechnen, sondern taktische Elemente erkennt und sinnvolle Bewertungen vornimmt. Dazu mehr kannst Du im nächsten Abschnitt lesen.