Mathematik: ein Beitrag zur Lösung des Isola-Spiels für kleinere Bretter als 6x8
Released by matroid on So. 04. April 2021 13:02:05 [Statistics]
Written by Delastelle - 108 x read [Outline] Printable version Printer-friendly version -  Choose language   
Spiele+Rätsel

\(\begingroup\)
Momentan arbeite ich an einer Betaversion eines Programms zur Erzeugung einer Endspieldatenbank für das Spiel Isola für Bretter bis 4x5 Felder (alle Felder drückbar).
Ich habe Ergebnisse für Bretter der Größe 2x3, 3x3, 3x4, 4x4 und 4x5.
Eine Überprüfung der Richtigkeit der Ergebnisse steht noch aus.


Problembeschreibung und etwas zur Vorgeschichte



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.

fed-Code einblenden
MP-Diskussion: Wer gewinnt beim Spiel Isola
LinkWer gewinnt beim Spiel Isola

MP-Diskussion: Endspiele König Turm gegen König - wieviele Matt in 0,1,2 Zügen Stellungen
LinkEndspiele König Turm gegen König - wieviele Matt in 0,1,2 Zügen Stellungen

MP-Artikel von Delstelle: Endspieldatenbanken im Schach
LinkEndspieldatenbanken im Schach

Ich möchte mich bei allen bedanken, die bei den 2 Diskussionen mitgewirkt haben.


Die Verfahrensweise des Programms ist


Buch "Schach am PC" Seiten 300/301


Mein bisheriges Isola-Programm orientiert sich an dem Programm, das schon beim
Schachendspiel König und Turm gegen König zum Einsatz kam.
Als Neuerung werden sowohl Gewinnstellungen von Rot als auch von Blau gesucht.

Durchführung:
- erzeuge alle legalen Stellungen und speichere sie in einem Feld (Wert = -100 für alle Stellungen)
ein Datensatz enthält die Angaben 1.Position Rot (1 Byte), 2.Position Blau (1 Byte),
3. Brettstellung (gedrückte Felder) (bis zu 8 Byte), 4. Bewertung (1 Byte)
- ermittle alle Stellungen in denen Blau Matt ist (Wert 0)
- ermittle alle Stellungen in denen Rot Matt ist (Wert -1)
- ermittle alle Stellungen in denen Blau in einem Zug mattgesetzt werden kann (Wert 1) // Rot am Zug
- ermittle alle Stellungen in denen Rot in einem Zug mattgesetzt werden kann (Wert -2) // Blau am Zug
- ermittle alle Stellungen in denen Blau in zwei Zügen mattgesetzt werden kann (Wert 2) // Blau am Zug
- ermittle alle Stellungen in denen Rot in zwei Zügen mattgesetzt werden kann (Wert -3) // Rot am Zug
...
Das Programm bricht ab, wenn eine vorgegebene Suchtiefe erreicht ist (bei 4 Zeilen und 5 Spalten, tiefe = 20) oder keine neuen Mattstellungen mehr gefunden werden.

Ergebnisse der Betaversion


fed-Code einblenden
fed-Code einblenden
fed-Code einblenden
fed-Code einblenden
fed-Code einblenden

Aus der Startstellung heraus findet Rot also für 2x3, 3x3, 3x4, 4x4 und 4x5 eine Gewinnfortsetzung.
Es existieren aber immer auch Verluststrategien (schlechter 1. Zug von Rot).
Leider kann ich Programmfehler nicht völlig ausschließen - darum (noch) Betaversion.

Ausblick


Für die Rechnung zum 4x5 Isola benötigte ich auf einem ca. 4 GHz Laptop bei 1 genutzten Prozessor eine Rechenzeit von ca.7666 Sekunden und einen Speicherplatzbedarf von 880 MB-RAM.
Das Ergebnis der Berechnungen brauchte als Ascii gespeichert auf der Festplatte
ca. 2,042 GB Festplattenplatz(ZIP-komprimiert 309 MB).

Ein 4x4 Isola benötigt etwa 169 Sekunden Rechenzeit (1 Prozessor), 36,5 MB RAM und bis zu 80 MB Festplattenplatz(12,3 MB ZIP-komprimiert) für die unkomprimierte Endspieldatei.

Es ist also von 4x4 zu 4x5 eine Steigerung der Rechenzeit um den Faktor 45,4;
des RAM-Bedarfs um den Faktor 24,1 und des Festplattenplatzes um den Faktor 25,5.

Mit Hausmitteln (viel RAM, viel Zeit und großen Festplatten) könnte ich wohl noch Isola 4x6 oder 5x5 lösen - mehr wohl nicht.

Eventuell muss ich noch Ideen entwickeln wie ich die Richtigkeit der Ergebnisse besser überprüfen kann!

Isola ist viel weniger komplex als beispielsweise Schach.
Isola -> vielleicht 10^16 verschiedene Stellungen
Schach -> vielleicht 10^42 verschiedene Stellungen

Eventuell kann man mittels Suchbaumtechniken eine Lösung für Isola 6x8 finden.
D.h. ein Programm das mit Rot oder Blau immer gewinnt.
(Es muss eine Gewinnstrategie von Rot oder von Blau geben - es gibt in dem Spiel kein
unentschieden.)

Ein paar Files zu Isola finden sich in meinem Matheplanet-Notizbuch.
fav.php

Danke fürs Lesen!

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 108


[Top of page]

"Mathematik: ein Beitrag zur Lösung des Isola-Spiels für kleinere Bretter als 6x8" | 0 Comments
The authors of the comments are responsible for the content.

 
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]