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 - 169 x read [Outline] Printer-friendly version -  Choose languageDE EN

\(\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. [Edit] [To the bottom] 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. \ \big\etwas zur Vorgeschichte von Isola hier auf dem Matheplaneten: MP-Diskussion: Wer gewinnt beim Spiel Isola Wer gewinnt beim Spiel Isola MP-Diskussion: Endspiele König Turm gegen König - wieviele Matt in 0,1,2 Zügen Stellungen Endspiele König Turm gegen König - wieviele Matt in 0,1,2 Zügen Stellungen MP-Artikel von Delstelle: Endspieldatenbanken im Schach Endspieldatenbanken im Schach Ich möchte mich bei allen bedanken, die bei den 2 Diskussionen mitgewirkt haben. [Edit] 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. [Edit] Ergebnisse der Betaversion \ \big\Für 2 Zeilen und 3 Spalten erhalte ich: Hinweis: ich habe hier immer Stellungen betrachtet, bei denen alle Brettfelder gedrückt werden dürfen. Brett ------------ x R x x . B ------------ stelle Mattwert 159 2 dran 2 Brett ------------ . R B x . x ------------ stelle Mattwert 102 1 dran 1 Brett ------------ . . B x . R ------------ stelle Mattwert 435 0 dran 2 Legende: . -> leeres Feld, x -> belegtes Feld (auch Felder von Rot und Blau sind belegt), R -> Rot, B -> Blau \ \big\Für das 3x3 Brett erhalte ich: Brett ------------ x R x x . B x x x ------------ stelle Mattwert 1656 4 dran 2 Brett ------------ . R x x . x x B x ------------ stelle Mattwert 1848 3 dran 1 Brett ------------ . x x R . . x B x ------------ stelle Mattwert 3892 2 dran 2 Brett ------------ . . x R . . B x x ------------ stelle Mattwert 3732 1 dran 1 Brett ------------ . . x . . . B R x ------------ stelle Mattwert 7954 0 dran 2 \ \big\Für das 3x4 Brett erhalte ich: Brett ------------ R x x x x x . B x x x x ------------ stelle Mattwert 7152 6 dran 2 Brett ------------ R x B . x x . x x x x x ------------ stelle Mattwert 1760 5 dran 1 Brett ------------ x R B . x . . x x x x x ------------ stelle Mattwert 12960 4 dran 2 Brett ------------ . R x . x . . B x x x x ------------ stelle Mattwert 17744 3 dran 1 Brett ------------ . x R . x . . B x . x x ------------ stelle Mattwert 29004 2 dran 2 Brett ------------ . . R . x . . x x . B x ------------ stelle Mattwert 31822 1 dran 1 Brett ------------ . . x . x . . R x . B . ------------ stelle Mattwert 88229 0 dran 2 \ \big\Für das 4x4 Brett erhalte ich: Brett ------------ x x x x x x x x R x . B x x x x ------------ stelle Mattwert 2146288 10 dran 2 Brett ------------ . x x x x x B x R x . x x x x x ------------ stelle Mattwert 2072544 9 dran 1 Brett ------------ . . x x x x B x x R . x x x x x ------------ stelle Mattwert 2314208 8 dran 2 Brett ------------ . . x x x B x x x R . . x x x x ------------ stelle Mattwert 2297808 7 dran 1 Brett ------------ . . x x R B . x x x . . x x x x ------------ stelle Mattwert 1052112 6 dran 2 Brett ------------ . . . x R x . x B x . . x x x x ------------ stelle Mattwert 1099472 5 dran 1 Brett ------------ . . . x x x . x B R . . x x . x ------------ stelle Mattwert 2344782 4 dran 2 Brett ------------ . . . . B x . x x R . . x x . x ------------ stelle Mattwert 2278094 3 dran 1 Brett ------------ . . . . B x . x R . . . x x . x ------------ stelle Mattwert 2032270 2 dran 2 Brett ------------ . . . . . B . x R . . . x x . x ------------ stelle Mattwert 2048142 1 dran 1 Brett ------------ . . . . . B . x . . . . R x . x ------------ stelle Mattwert 3031174 0 dran 2 \ \big\Für das 4 Zeilen x 5 Spalten Brett mit allen Feldern wegdrückbar erhalte ich folgende Mattstellungen: Matt (blau): 0 2507776 Matt (blau): 1 13126816 Matt (blau): 2 2442236 Matt (blau): 3 10736548 Matt (blau): 4 3458184 Matt (blau): 5 8302960 Matt (blau): 6 1844414 Matt (blau): 7 3275294 Matt (blau): 8 566648 Matt (blau): 9 694208 Matt (blau): 10 64032 Matt (blau): 11 67148 Matt (blau): 12 3714 Matt (blau): 13 1678 Matt (blau): 14 88 Matt (rot): 0 2507776 Matt (rot): 1 13126816 Matt (rot): 2 2442188 Matt (rot): 3 10737786 Matt (rot): 4 3462382 Matt (rot): 5 8347752 Matt (rot): 6 1980294 Matt (rot): 7 3574788 Matt (rot): 8 1118470 Matt (rot): 9 1509070 Matt (rot): 10 1048720 Matt (rot): 11 1050074 Matt (rot): 12 788960 Matt (rot): 13 489870 Matt (rot): 14 235604 Matt (rot): 15 81680 Matt (rot): 16 18184 Matt (rot): 17 2432 Matt (rot): 18 129 Lesart: für ein Matt von Blau (Blau matt gesetzt) in 14 Zügen findet das Programm 88 Stellungen. Stellungen mit dem Startwert -100 treten am Ende des Programmlaufs nicht mehr auf. Der beste (siegreiche) Verlauf für Rot kann so aussehen (Gegenwehr von Blau): Brett ------------ x x x x x x R x . x x x x x B x x x x x ------------ stelle Mattwert 33553408 10 dran 2 Brett ------------ . x x x x x R x . x x x x B x x x x x x ------------ stelle Mattwert 33160192 9 dran 1 Brett ------------ . x x x x x x R . x x x . B x x x x x x ------------ stelle Mattwert 38140864 8 dran 2 Brett ------------ . . x x x x x R . x x x . x B x x x x x ------------ stelle Mattwert 38337472 7 dran 1 Brett ------------ . . x x x x x x . x x R . . B x x x x x ------------ stelle Mattwert 58260896 6 dran 2 Brett ------------ . . . x x x x x . B x R . . x x x x x x ------------ stelle Mattwert 57179456 5 dran 1 Brett ------------ . . . x x x R x . B x x . . . x x x x x ------------ stelle Mattwert 32013088 4 dran 2 Brett ------------ . . . B x . R x . x x x . . . x x x x x ------------ stelle Mattwert 30693152 3 dran 1 Brett ------------ . . . B . . x R . x x x . . . x x x x x ------------ stelle Mattwert 35657504 2 dran 2 Brett ------------ . . . . . . x R . B x x . . . x x x x x ------------ stelle Mattwert 36965152 1 dran 1 Brett ------------ . . . . . . R . . B x x . . . x x x x x ------------ stelle Mattwert 31982368 0 dran 2 Legende: . -> leeres Feld, x -> belegtes Feld (auch Felder von Rot und Blau sind belegt), R -> Rot, B -> Blau Fazit: mein Programm (Betaversion) findet einen Gewinn von Rot in 11 Zügen aus der Startstellung heraus. Eine Verluststellung von Rot nach Startzug ist folgende (Wert -6 = Matt in 5 Zügen, Blau am Zug): Brett ------------ R x x x x . x x x x x x x x B x x x x x ------------ stelle Mattwert 3661824 -6 zwi3 1040383 Eine langsame Verluststellung von Rot ist folgende: Brett ------------ x R x x x x x x . x x x x x B x x x x x ------------ stelle Mattwert 8649728 -18 dran 2 Brett ------------ x R x x x . x x . x x x x x x x x x B x ------------ stelle Mattwert 9690112 -17 dran 1 Brett ------------ . x x x x . R x . x x x x x x x x x B x ------------ stelle Mattwert 34466816 -16 dran 2 Brett ------------ . . x x x . R x . x x x B x x x x x x x ------------ stelle Mattwert 32828416 -15 dran 1 Brett ------------ . . . x x . x x . x x R B x x x x x x x ------------ stelle Mattwert 57699840 -14 dran 2 Brett ------------ . . . x . . x B . x x R x x x x x x x x ------------ stelle Mattwert 56642560 -13 dran 1 Brett ------------ . . . x . . R B . x x x . x x x x x x x ------------ stelle Mattwert 31475584 -12 dran 2 Brett ------------ . . . x . . R . . x x B . x x x x x x x ------------ stelle Mattwert 32523136 -11 dran 1 Brett ------------ . . . x . . x . . x R B . x x x x . x x ------------ stelle Mattwert 52447612 -10 dran 2 Brett ------------ . . . x . . . . . x R x . x x B x . x x ------------ stelle Mattwert 53494204 -9 dran 1 Brett ------------ . . . . . . . . . x x R . x x B x . x x ------------ stelle Mattwert 58458556 -8 dran 2 Brett ------------ . . . . . . . . . . B R . x x x x . x x ------------ stelle Mattwert 57409660 -7 dran 1 Brett ------------ . . . . . . . . . . B x . . x R x . x x ------------ stelle Mattwert 77332636 -6 dran 2 Brett ------------ . . . . . . . . . . x B . . . R x . x x ------------ stelle Mattwert 77594764 -5 dran 1 Brett ------------ . . . . . . . . . . R B . . . x x . . x ------------ stelle Mattwert 52428826 -4 dran 2 Brett ------------ . . . . . . . . . . R x . . . B x . . . ------------ stelle Mattwert 53477513 -3 dran 1 Brett ------------ . . . . . . . . . . . R . . . B x . . . ------------ stelle Mattwert 58458121 -2 dran 2 Brett ------------ . . . . . . . . . . . R . . . . B . . . ------------ stelle Mattwert 58720257 -1 dran 1 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. [Edit] 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 [Edit] \(\endgroup\) [Show outline only]

Get link to this article   Printer-friendly version -  Choose languageDE EN     Comments   Für diesen Artikel gibt es keine pdf-Datei

Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:

: Spiele+Rätsel :: automatisch eingefügt und unbearbeitet :: Spiele : ein Beitrag zur Lösung des Isola-Spiels für kleinere Bretter als 6x8 [von Delastelle]

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 [Edit]

[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

Domain	Anzahl	Proz
https://duckduckgo.com	3	75%
https://google.com	1	25%

[Top of page]