Auf der Suche nach einer guten Strategie für das Spiel Isola auf dem 6x8 Brett
Von: Delastelle
Datum: So. 18. April 2021 21:29:31
Thema: Mathematik

Die nachfolgenden Ideen sind nicht gänzlich neu ich möchte sie aber einmal in einem Artikel zusammenfassen. Ich habe 3 Rot-Isola-Strategien jeweils 10000 mal gegen 3 Blau-Isola-Strategien spielen lassen. Ich sehe Fortschritte in den Strategien, bin aber vom Ziel: "Wer gewinnt Isola Rot oder Blau?" noch einiges entfernt.

Problembeschreibung

Aus der Spielanleitung zum Brettspiel Isola (aus dem Jahr 1980) Das Spielbrett umfasst 6x8 = 48 Felder, von denen die 2 Startfelder nicht gedrückt werden können. Die restlichen 46 Felder werden mit gelben drückbaren Plättchen belegt. Spielverlauf "Wenn ein Spieler an der Reihe ist, zieht er zunächst seine Figur ein Feld weiter auf ein benachbartes Feld, und zwar in jede beliebige Richtung. Danach entfernt er noch einen Spielstein seiner Wahl vom Plan. Dies geschieht indem man den Spielstein durch das Gitter hindurchdrückt. Ziel des Spieles ist es, durch Entfernen der Spielsteine den Gegner so zu behindern, daß dieser auf einem Feld isoliert wird und nicht mehr ziehen kann. Derjenige, dem es zuerst gelingt, seinen Gegenspieler zu isolieren, gewinnt das Spiel. Auf einem Feld darf nur eine Figur stehen. Als Feld gelten die gelben Spielsteine und auch die beiden Ausgangsfelder. Beide Spieler können die Ausgangsfelder (auch das des Gegenspielers) beliebig oft besetzen." Ich habe als Startfeld für Rot immer das Mittlere Feld links (Zeilenzahl ungerade) oder das Feld 1 über der Mitte (Zeilenzahl gerade) gewählt. Das Startfeld von Blau ist gespiegelt. Es wurden wie beim Originalspiel 2 Felder als nicht drückbar angesehen - die Startfelder von Rot und Blau.
 

verwendete Spielstrategien

Stategien: (1) Rot oder Blau - ermittle alle zulässigen Züge (Bewegung und Drückfeld ergeben einen Zug) - wähle zufällig einen der Züge aus (2) Rot oder Blau - ermittle alle zulässigen Züge (Bewegung und Drückfeld ergeben einen Zug) - führe für jeden Zug eine Wertung ein, einer der höchsten Werte wird ausgewählt die Wertung beginnt bei 20000 Punkten (damit auch die negativen Wertungen zu einer Wertung größer als 0 führen) - (a) für ein Matt des Gegners gibt es 1 Mio Punkte (wird also immer ausgewählt) (b) es gibt 100 Punkte für jedes erreichbare Feld des Brettes, falls Rot und Blau nicht zusammenhängend wird für jedes Feld, das der Gegner erreichen kann 100 Punkte abgezogen aktuell gibt es noch 5000 Punkte falls die Felder von Rot und Blau getrennt sind (c) für ein erreichbares Nachbarfeld gibt es 1000 Punkte für ein erreichbares Nachbarfeld des Gegners werden 1000 Punkte abgezogen (3) Rot oder Blau - ermittle alle zulässigen Züge (Bewegung und Drückfeld ergeben einen Zug) - führe für jeden Zug eine Wertung ein, einer der höchsten Werte wird ausgewählt die Wertung beginnt bei 20000 Punkten (damit auch die negativen Wertungen zu einer Wertung größer als 0 führen) - (a) für ein Matt des Gegners gibt es 1 Mio Punkte (wird also immer ausgewählt) (b) für ein erreichbares Nachbarfeld gibt es 1000 Punkte für ein erreichbares Nachbarfeld des Gegners werden 1000 Punkte abgezogen (c) es wird ein Muster im gegnerischen Bereich des Feldes angestrebt. Damit kann der Gegner fast sicher zuerst in seinem Bereich des Feldes gefangen werden und dann sein Bereich immer mehr verkleinert werden Falls Rot beginnt: -> drücke Feld 29 weg, dann drücke die 5 Spalte weg - falls Blau oben erst oben, falls Blau unten zuerst unten -> drücke im Restfeld die rechte 3.Zeile weg -> drücke oben oder unten die 7 Spalte weg -> dann drücke Restfelder weg bis Blau Matt ist Der Wert der zu drückenden Felder wird erhöht. Somit werden sie bevorzugt ausgewählt. Strategie 3 von Blau ergibt sich durch Spiegelung des Musters von Rot.
 

Ergebnisse

\ Strategie Rot vs. Strategie Blau - jeweils 10000 Spiele Blau ........ 1 ...... 2 ...... 3 R 1 ... 5036 .... 107 .... 16 o 2 ... 9886 ... 5046 ... 2140 t 3 ... 9995 ... 7959 ... 7164 Lesart: Strategie 3 von Rot gewinnt 9995 mal gegen Strategie 1 von Blau bei 10000 Spielen. Rechenzeit: ca. weniger als 1 Sekunde bis 170 Sekunden für 10000 Läufe(Fortran). \ Ein Spielverlauf von Strategie 3 Rot (Muster) vs. Strategie 2 Blau (ca. Nachbarfeld wegdrücken). Brett ------------ x x x x x x x x x x x x x x x x X x x x x x x x x R x x . x x B x x x x x x x x x x x x x x x x ------------ dran 2 Brett ------------ x x x x x x x x x x x x x x x x X x x x x x B x x R x x . x x X x . x x x x x x x x x x x x x x ------------ dran 1 Brett ------------ x x x x x x x x x x x x x x x x X x R x . x B x x x x x . x x X x . x x x x x x x x x x x x x x ------------ dran 2 Brett ------------ x x x x x x x x x x x x x x x x X x R x . x x x x x . x . x B X x . x x x x x x x x x x x x x x ------------ dran 1 Brett ------------ x x x x x x x x x x R x x x x x X x x x . x x x x x . x . x B X x . x x . x x x x x x x x x x x ------------ dran 2 Brett ------------ x x x x x x x x x x R x x x x x X x . x . x B x x x . x . x x X x . x x . x x x x x x x x x x x ------------ dran 1 Brett ------------ x x x x x x x x x R x x . x x x X x . x . x B x x x . x . x x X x . x x . x x x x x x x x x x x ------------ dran 2 Brett ------------ . x x x x x x x x R x x . x x x X x . x . x x x x x . x . x B X x . x x . x x x x x x x x x x x ------------ dran 1 Brett ------------ . x x x x x x x x x R x . x x x X x . x . x x x x x . x . x B X x . x x . x x x x x x x . x x x ------------ dran 2 Brett ------------ . x x x x x x x x x R x . x x x X x . . . x x x x x . x . x x X x . x x . x B x x x x x . x x x ------------ dran 1 Brett ------------ . x x x . x x x x x x x . x x x X R . . . x x x x x . x . x x X x . x x . x B x x x x x . x x x ------------ dran 2 Brett ------------ . x x x . x x x x . x x . x x x X R . . . x x x x x . x . x B X x . x x . x x x x x x x . x x x ------------ dran 1 Brett ------------ . x x x . x x x x . x x . x x x X x . . . x . x x R . x . x B X x . x x . x x x x x x x . x x x ------------ dran 2 Brett ------------ . x x x . x x x x . x x . x x x X x . . . x . x x R . x . x x X x . . x . x B x x x x x . x x x ------------ dran 1 Brett ------------ . x x x . x x x x . x x . x x x X R . . . . . x x x . x . x x X x . . x . x B x x x x x . x x x ------------ dran 2 Brett ------------ . x x x . x x x x . . x . x x x X R . . . . . x x x . x . x B X x . . x . x x x x x x x . x x x ------------ dran 1 Brett ------------ . x x x . x x x x . . x . x x x X x . . . . . . R x . x . x B X x . . x . x x x x x x x . x x x ------------ dran 2 Brett ------------ . x x x . x x x x . . x . x x x X x . . . . . . R x . x . x x X . . . x . x B x x x x x . x x x ------------ dran 1 Brett ------------ . x x x . x x x x . . x . x x x X R . . . . . . x x . x . x . X . . . x . x B x x x x x . x x x ------------ dran 2 Brett ------------ . x x x . x x x . . . x . x x x X R . . . . . . x x . x . x . X . . . x . x x x x x x x . x B x ------------ dran 1 Brett ------------ . x x x . x x x . . . x . x x x X x . . . . . . x R . x . x . X . . . x . x . x x x x x . x B x ------------ dran 2 Brett ------------ . x x x . x x x . . . x . x x x X . . . . . . . x R . x . x . X . . . x . x . B x x x x . x x x ------------ dran 1 Brett ------------ . x x x . x x x . . . x . x x x R . . . . . . . x x . x . x . X . . . x . x . B x x x x . x . x ------------ dran 2 Brett ------------ . x x x . x x x . . . x . x x x R . . . . . . . . x . x . x . X . . . x . x . x x x x x . x . B ------------ dran 1 Brett ------------ . x x x . x x x . . . x . x x x X . . . . . . . . R . x . x . X . . . x . x . . x x x x . x . B ------------ dran 2 verloren hat Spieler 2 Legende: R -> Rot B -> Blau x -> belegtes Feld X -> Startfeld (nicht drückbar) . -> gedrücktes Feld
 

Ausblick

Was kann man noch tun? - die Ziehstrategie optimieren - die Drückstrategie optimieren Dazu: - bisher rechne ich mit Tiefe 1 (einen Zug voraus). Für eine gute Gesamtstrategie kann man eventuell auch mit Tiefe 3 oder 5 oder mehr rechnen - im der Schach-Programmierung der 1990er Jahre haben sich u.a. Hashtabellen und Nullmove bewährt Hashtables(Hashtabellen) werden unter anderem im Schach verwendet. Wenn eine Stellung in der Berechnung das 1.Mal auftaucht, wird sie berechnet. Falls die Stellung später wieder auftaucht, kann man in der Tabelle die Bewertung nachschlagen und spart sich eine 2.Berechnung. Bei Nullmove(Nullzug) macht ein Spieler 2 Züge hintereinander - so kann man manchmal eher schlechte Züge erkennen, die keinen/kaum Vorteil(e) bringen. Vielleicht kann man diese Ideen auch bei Isola einsetzen. - man kann von einer Stellung berechnen in wie vielen Zügen man welches Feld vom Brett erreichen kann. Diese Information kann bei Angriff (Drückfeld)/Verteidigung(eigener Zug) eine Rolle spielen - die bisherige Strategie 3 ist zwar schon recht ordentlich, aber trotzdem sicherlich noch nicht ideal - wenn Rot die Spalte 5 wegdrückt könnte Blau versuchen zuerst die linke Zeile 4 wegzudrücken mit anschließender Intervallhalbierung - bisher haben die Rotstrategien (Spieler 1) gegenüber den Blaustrategien (Spieler 2) einen leichten Vorteil. Ob aber Rot oder Blau gewinnen sollte weiß ich bisher nicht. Viele Grüße Ronald
 


Dieser Artikel kommt von Matroids Matheplanet
https://matheplanet.de

Die Url für diesen Artikel ist:
https://matheplanet.de/default3.html?article=1935