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 - 170 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


fed-Code einblenden

fed-Code einblenden
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 170
 
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]