Mathematik: Auf der Suche nach einer guten Strategie für das Spiel Isola auf dem 6x8 Brett
Released by matroid on So. 18. April 2021 21:29:31 [Statistics]
Written by Delastelle - 185 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\) 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
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 185
 
Aufrufstatistik des Artikels
Insgesamt 1 externer Seitenaufruf zwischen 2021.05 und 2021.05 [Anzeigen]
DomainAnzahlProz
https://google.com1100%100 %

[Top of page]

"Mathematik: Auf der Suche nach einer guten Strategie für das Spiel Isola auf dem 6x8 Brett" | 2 Comments
The authors of the comments are responsible for the content.

Re: Auf der Suche nach einer guten Strategie für das Spiel Isola auf dem 6x8 Brett
von: Asrael am: Di. 20. April 2021 11:07:14
\(\begingroup\)Minimax-Algorithmus wäre der nächste Schritt! Bei Spielen wie Go und Hex, die hohen Verzweigungsfaktor haben, wurden auch Monte-Carlo-Rollouts (zuende Spielen mit Zufallszügen) zur Zugevaluation angewandt, die dann zu Monte-Carlo-Trees mit ucb wurden und noch später von google deepmind mit neuronalen Netzen ausgestattet wurden (um durch KI sowohl eine Vorwahl von günstigen Zügen zu bekommen wie auch eine Evaluation von Positionen)\(\endgroup\)
 

Re: Auf der Suche nach einer guten Strategie für das Spiel Isola auf dem 6x8 Brett
von: Delastelle am: Di. 20. April 2021 21:12:25
\(\begingroup\)Hallo Asrael und die Anderen! Mit den neusten Entwicklungen bezüglich Schach und Go Programmierung kenne ich mich nicht so aus. Aber Suchbaumtechniken könnten helfen Lösungen zu finden. Ein Nachteil: bei 8 Zügen (Bewegungen) und 40 Drückfeldern hat ein Zug schon 320 Varianten. Ich denke aktuell nach, wie lange eine Einmauerung des Blauen in der rechten Bretthälfte durch teilweises Drücken der 5.Spalte und 4 Zeile braucht (eventuell über eine Endspieldatenbank). Und dies im Vergleich zum Einmauern des Roten auf der linken Seite bzw. ggf. eine Flucht des Roten über die Mittellinie. Falls das Einmauern von Blau schneller geht als der Verlust von Rot links, wäre das ein Hinweis auf einen Sieg von Rot. Viele Grüße Ronald\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]