Logo

Sistances EXPLODE!
KI - PI mal Daumen / eine B-Strategie


this site in english

Startseite

Explode! für Spieler
  Spielregeln
  Download
  Credits
  Versionsinfos

Explode! für Entwickler
  KI-Entwicklung
    Tiefensuche
    Breitensuche
    PI * Daumen

Android-Entwicklung
Geld verdienen






Valid HTML 4.01 Transitional
Nachdem die Tiefensuche als zu langsam und die Breitensuche als zu speicherhungrig erschien, entschloss ich mich, doch noch einmal eine KI-Variante zu testen, die nicht auf Vorausplanung beruht. Im Bereich von Computerschach nennt man die beiden zugrundeliegenden Strategien A- und B-Strategie.
Grundsätzlich existieren noch Optimierungsmöglichkeiten bei den beiden bisherigen KI-Methoden (A-Strategien), die ich nutzen könnte, doch wollte ich mir zuerst alle drei Varianten anschauen, bevor ich zuviel Zeit in die Entwicklung einer bestimmten KI investiere.

Das Konzept einer KI beruht im Prinzip immer darauf, die möglichen Züge zu bewerten und dann den besten oder einen der besten auszuwählen. Ein Mensch berechnet ebenfalls Züge voraus, aber er sucht und verwendet auch Muster, von denen er weiß, dass sie gut oder schlecht sind. Die Überlegungen, die ein Mensch dabei durchführt, sind nicht immer sofort erkennbar. Doch kann man schnell, beispielsweise durch wiederholtes Fragen, einige der Regeln in Worte fassen, die man sonst durch "aufs Feld starren" intuitiv anwendet.

Für die KI, die ich in diesem Abschnitt beschreibe, bin ich so vorgegangen.
Zunächst habe ich das Spiel einige Male gespielt, um Situationen herbeizuführen, die ich als taktisch interessant empfand. Die ersten interessanten Situationen sind diejenigen, bei denen die Spieler Felder erobern, die an gegnerische Felder angrenzen. Nun hat man eine direkte Konfrontation, die es zu bewerten gilt.
Um nicht das ganze Feld bewerten zu müssen, ist es notwendig, kleinere Teile des Felds separat zu betrachten. Bei einem Spielfeld mit fünf auf fünf Feldern ist es kaum noch möglich, weiter zu unterteilen, sodass ich schnell zu dem Punkt kam, dass hier eine Einzelfeld-Betrachtung schneller zu Ergebnissen führt.
Im Gegensatz zum Beispiel zu Schach haben alle eigenen und alle gegnerischen Felder erst einmal den gleichen taktischen Wert, der durch ihre Feldstärke und ihre Position auf dem Feld modifiziert werden kann. Zum Beispiel ist ein eigenes Fünfer-Feld, mit dem man gegnerische Felder erobern kann, normalerweise mehr wert als ein eigenes Dreier-Feld, das selbst von einem gegnerischen Fünfer-Feld bedroht wird.

Letztendlich habe ich zum Schluss versucht, jedes Feld einer bestimmten Kategorie zuzuordnen und abhängig davon dasjenige Feld zu ermitteln, bei dem ich mir den größten Vorteil beziehungsweise geringsten Nachteil erhoffe.

Eine erste Feld-Unterteilung

  • Grenzt das Feld ausschließlich an den Rand und an eigene Felder, dann ist das Feld ein Hinterland-Feld.
  • Wenn das Feld kein Hinterland-Feld ist, grenzt das Feld dann auch an gegnerische Felder oder nicht? Ein Feld, das nicht an gegnerische Felder grenzt und auch kein Hinterland-Feld ist, ist ein sogenanntes Siedler-Feld, da es unbesetzte Felder erobern kann, aber keine Gegner bedroht (oder von ihnen bedroht wird).
  • Felder, die weder Hinterland-Felder noch Siedler-Felder sind, sind zwangsläufig Felder mit Feindkontakt. Diese Felder verdienen schon früh ein besonderes Augenmerk, denn diese Felder bedrohen den Gegner oder werden vom Gegner bedroht. Die weitere Kategorisierung der Grenzland-Felder beschreibe ich im nächsten Abschnitt.

Grenzland-Felder

Da diese KI-Variante nur Situationen bewertet, in denen sie selbst am Zug ist, fließt diese Nebenbedingung in die weiteren Überlegungen implizit mit ein.
  • Sehr interessant sind eigene Fünfer-Felder, die andere Gegner bedrohen. Ein eigener Fünfer-, der einen gegnerischen Fünfer bedroht, nenne ich einen unbedingten Eroberer. Das ist deshalb der Fall, da der Gegner im nächsten Zug mit seinem eigenen Fünfer unseren Fünfer und alle von ihm bedrohten eigenen Felder erobern kann. Nur in den wenigsten Fällen ist es sinnvoll, so einen Fünfer nicht zur Expansion zu nutzen.
  • Eigene Grenzfelder, die gegnerische Grenzfelder bedrohen, aber keine unbedingten Eroberer sind, sind normale Eroberer. Sie können, wenn sie weiter zu Fünferfeldern aufgewertet werden (falls sie nicht schon Fünferfelder sind), gegnerische Bereiche angreifen. Bedroht wird ein gegnerisches Feld, wenn jedes angrenzende gegnerische Feld weniger Feldwert besitzt als das eigene Feld. Grundsätzlich ist bei solchen Feldern keine unmittelbare Zugnotwendigkeit vorhanden, um den aktuellen Vorteil zu erhalten. Die nächste Kategorie verdient wesentlich mehr Aufmerksamkeit.
  • Eigene Grenzfelder, deren stärkster gegnerischer Nachbar genau den gleichen Wert hat, wie das Feld selbst, sind potenzielle Eroberer. Falls man den Feldwert erhöht, macht man ihn zu einem Eroberer, der Gegner könnte höchstens gleichziehen. Falls man das Feld aber nicht erhöht, dann kann der Gegner in seinem eigenen Zug den stärksten Nachbarn dieses Felds erhöhen und damit selbst zum bedrohenden Eroberer werden.
    Die Liste der potenziellen Eroberer ist daher wesentlich wichtiger als die der Eroberer, die schon einen echten Vorteil darstellen, nicht nur einen potenziellen.
  • Felder, die selbst einen geringeren Wert haben als den Wert des höchsten (unbedrohten) gegnerischen Nachbarn, werden selbst bedroht. Sie werden Opfer-Felder genannt, da sie sich gegen eine gegnerische Übernahme nicht mehr eigenständig wehren können. Sie zu erhöhen bringt nur selten einen Vorteil, außer wenn man eine sogenannte 5554-Stellung aufbauen kann.

Hinterland-Felder

Weit weniger interessant erscheint im ersten Moment die weitere Unterteilung von Hinterlandfeldern, doch das ist nicht richtig. Denn Hinterlandfelder haben oft einen unterschiedlichen, taktischen Nutzen, da sie unter Umständen schnell zu Grenzfeldern werden können oder als Zugreserve dienen.

Speziell bei der 5554-Stellung ist häufig ein Hinterlandfeld beteiligt, aber auch bei trivialeren Stellungen haben grenznahe Hinterlandfelder Aufgaben, die reine Platzhalterfunktionen übersteigen.
Beispiel:
Ein Grenzfeld wird von einem gegnerischen Feld bedroht, sodass es vom Gegenspieler übernommen werden kann. Es ist also ein Opfer-Feld. Das benachbarte Hinterland-Feld kann dieses Feld nun sichern, wenn es höher ist als das eigene Opfer-Feld.

Bewertung

Die Bewertung anhand von Kategorien macht es um einiges einfacher, die Liste der interessantesten Züge einzugrenzen. Fünfer, die andere Fünfer begrenzen sind regelmäßig die besten Züge, da man sehr große Geländegewinne machen kann oder - falls man den Zug unterlässt - sie dem Gegner schenkt.
Potenzielle Eroberer sind auch sehr weit oben in der Liste, da man einen potenziellen Vorteil zu einem echten Vorteil ausbauen kann, wenn man dieses Feld erhöht - oder dem Gegner einen potenziellen Vorteil überlässt, wenn man nicht erhöht.
Geländegewinne sind von Vorteil, da man mehr Raum für taktische Stellungen einnimmt und mehr Züge hat, die man im später im Hinterland machen kann, ohne eine taktisch gute Stellung zu (zer)stören.

Weiterführende Links
Wikipedia: Spielzug
Wikipedia: Bewertungsfunktion
Wikipedia: A- und B-Strategie


 Impressum