Solitär

Solitär (weitere deutsche Bezeichnungen: Solitaire, Steckhalma, Solohalma, Springer, Jumper, Nonnenspiel oder Einsiedlerspiel^[1]) ist ein Puzzle für eine Person, das bereits hunderte Jahre alt ist. Die erste belegte Erwähnung war 1697^[2]. Ziel ist es aus der Startposition durch Sprünge, die den übersprungenen Stein entfernen, die Endposition zu erreichen.

Regeln

Spielfeld, Startposition und Zielposition

In der englischen Variante ist das Spielfeld kreuzförmig und symmetrisch, besitzt 33 Felder und wird mit 32 Spielsteinen gespielt. In der Startposition ist jedes Feld außer das mittlere mit Spielsteinen belegt. Die Zielposition ist dabei das genaue Gegenteil, ein einziger verbleibender Spielstein belegt das mittlere Feld.

Züge

In jedem Zug springt ein Spielstein in einer Linie über einen direkt daneben liegenden Spielstein auf ein freies Feld und der übersprungene Spielstein wird vom Spielfeld entfernt. Es muss immer genau ein Stein übersprungen werden und dabei können Sprünge nur horizontal oder vertikal passieren und nicht diagonal.

Spielende

Das Spiel gilt als gewonnen, wenn die Zielposition erreicht wurde. Sind keine gültigen Züge mehr möglich(Beispiele in Abbildung 4) und die Zielposition wurde nicht erreicht, so gilt das Spiel als verloren.

Spielvarianten

Mit den Standard-Regeln lässt sich auf verschiedensten Spielfeldern spielen. Einige Bespiele sind in Abbildung 5 dargestellt. Neben der englischen Variante(4) ist auch die französische(1) sehr verbreitet. Eine Sonderform stellt das dreieckige Spielfeld(6) dar, bei dem Sprünge in sechs Richtungen möglich sind.

Es gibt Variationen des Spiels durch Anpassung der Regeln:

• Fool's Solitaire^[3]: Schnell "verlieren", also mit möglichst wenig Zügen in eine Stellung kommen die keine gültigen Züge mehr zulässt
• Long-hop Solitaire^[3:1]: Sprünge die in direkter Folge mit einem Spielstein durchgeführt werden zählen als ein Zug, das Ziel ist es die Züge bis zur Zielstellung zu minimieren
• Reversals^[3:2]: Invertierung des Spiels, also das Löcher springen und die Start- und Zielposition vertauscht sind^[3:3]
• Unterschiedliche Muster in Start - oder Zielposition

Modellierung im Integer Programming

Durch die sequentielle Spielweise mit eindeutiger Start- sowie Zielposition lässt sich Solitär als ein Planungsproblem einordnen^[3:4]. Ein solches Planungsproblem mithilfe des Integer Programming zu modellieren und zu lösen eröffnet neue Perspektiven auf die Anwendung des Integer Programming.

Integer Programming ist im Deutschen als ganzzahlige lineare Optimierung bekannt und bezeichnet das Lösen von Optimierungsproblemen, die ganzzahlige oder diskrete Variablen enthalten^[4]. Mehr dazu im eigenständigen Artikel zu Integer Programming.

Modellierung

Die Modellierung erfolgt über Variablen und Gleichungen bzw. Ungleichungen.
Es gibt 2 Typen von Variablen:

• M[i, j, t ,d] , eine binäre, ganzzahlige Variable die 1 ist wenn von der Position (i, j) ∈ B ein Zug im Zeitpunkt t = 1, ..., 31 und in Richtung d ∈ \{N, E, S, W\} gemacht wird, ansonsten 0
• bState[i, j, t], eine binäre, ganzzahlige Variable die 1 ist wenn sich in der Position (i, j) ∈ B zum Zeitpunkt t = 1, ..., 32 ein Spielstein befindet, ansonsten 0

Die einzelnen Bestandteile des Gesamtmodells sind nochmal in Abbildung 6 markiert.

Spielfeld B und Zugnotation

Um für die aktuelle Spielposition zu modellieren bekommen die einzelnen Felder Koordinaten, wobei für (x, y) x die Zeile und y die Reihe angibt. Dadurch entsteht die Menge B, die die Menge aller Felder des Spielfelds ist.

Bei einem Zug springt ein Spielstein von (x, y) zu (x', y'), wir verwenden dafür die Schreibweise (x, y) \to (x', y').

Zeitkomponente t

Solitär lässt sich als Planungsproblem betrachten, dabei lassen sich jedoch 2 Vereinfachungen durchführen um die Modellierung im Integer Programming zu erleichtern:

1. In jeder Position ist nur genau ein Sprung gleichzeitig erlaubt.
2. Es ist von vornherein klar wie viele Züge gebraucht werden um die Zielposition zu erreichen.

In der englischen Variante des Solitär starten wir mit 32 Spielsteinen, wobei mit jedem Zug genau einer entfernt wird bis ein einziger verbleibt. Jedem Schritt der Sequenz an Zügen lässt sich dabei einen Zeitpunkt t zuordnen.

Optimierungsziel

Die Optimierungsfunktion \max bState[3, 3, 32] bildet die Zielposition zum Zeitpunkt t=32 ab. Zum Zeitpunkt t=32 befindet sich noch genau ein Spielstein auf dem Spielfeld und wenn sich dieser auf dem Feld (3, 3) befindet, dann erreicht die Optimierungsfunktion ihr Maximum. Das Feld (3, 3) bezieht sich dabei auf das zentrale Feld.

Zugrichtung

Für die Darstellung der Zugrichtung wird sich an den Himmelsrichtungen orientiert. N steht dabei für Norden, E für Osten bzw. East, S für Süden und W für Westen.

Gültige Züge

Die gültigen Züge je Spielposition lassen sich mit einer Reihe von Ungleichungen ermitteln und aufgrund der Beschaffenheit des Spiels sind diese je Zugrichtung symmetrisch.

Beispielhaft werden sie an der Zugrichtung E erklärt:

• M[i, j, t, E] \le bState[i, j, t]
• M[i, j, t, E] \le bState[i + 1, j, t]
• M[i, j, t, E] \le 1 - bState[i + 2, j, t]

M[i, j, t, E] = 1, wenn wir einen Zug in Richtung E zum Zeitpunkt t von Feld (i, j) ausgehend machen. M kann aber nur 1 sein, wenn die Ungleichungen erfüllt werden. Das heißt auf den Feldern (i, j) und (i, i + 1, j) befindet sich jeweils ein Stein und auf dem Feld (i + 2, j) befindet sich keiner. Zudem müssen diese Felder überhaupt existieren.

Die Züge (2, 3) \to (4, 3) in Richtung E und (3, 3) \to (1, 3) in Richtung W sind die einzigen gültigen Züge der in Abbildung 9 gezeigten Spielposition.

Nur ein Sprung pro Zug

Auch wenn zu einem Zeitpunkt mehrere gültige Züge möglich sind, so ist darf nur genau einer durchgeführt werden. Die Summe aller gemachten Züge je Feld und Zugrichtung muss daher 1 sein:

\sum_{(i, j) ∈ B} (M[i, j, t, N]  + M[i, j, t, E]  + M[i, j, t, S]  + M[i, j, t,w] ) = 1

Veränderung des Feldzustands bei einem Zug

Bei jedem Zug verändert sich der Zustand von 3 Feldern. Das Feld (i, j) von dem aus gesprungen wird geht vom belegten zum unbelegten Zustand, das Feld mit dem übersprungenen Spielstein geht ebenfalls vom belegten zum unbelegten Zustand, weil der Spielstein entfernt wird, und das Feld wohin gesprungen wird geht vom unbelegten zum belegten Zustand.

bState[i, j, t] - bState[i, j, t + 1] = \sum_{d ∈ {N, E, S, W}}M[i, j, t ,d] \\
+ M[i, j + 1, t, N] - M[i, j + 2, t, N]
+ M[i - 1, j, t, E] - M[i - 2, j, t, E] \\
+ M[i, j - 1, t, S] - M[i, j - 2, t, S]
+ M[i + 1, j, t, W] - M[i + 2, j, t, W]

Die Gleichung bildet die Differenz der Feldbelegung vom Feld (i, j) zum Zeitpunkt t zur Feldbelegung vom Feld (i, j) zum Zeitpunkt t+1. Ist der Wert:

• -1, dann hat sich die Feldbelegung vom unbelegten zum belegten Zustand geändert, also es ist ein Spielstein dorthin gesprungen
• 0, dann hat sich die Feldbelegung nicht geändert
• 1, dann hat sich die Feldbelegung vom belegten zum unbelegten Zustand geändert, also entweder ist ein Stein von dort gesprungen oder wurde übersprungen

Die Feldbelegung ändert sich also nur für Felder die einen Sprung involviert sind. Das lässt sich am Zug in Abbildung 11 nachvollziehen:

• Für Feld (3, 1) ist das Ergebnis der Gleichung 1 = 1, das heißt ein Stein wird durch den Zug entfernt
• Für Feld (3, 2) ist das Ergebnis der Gleichung 1 = 1, das heißt ein Stein wird durch den Zug entfernt
• Für Feld (3, 3) ist das Ergebnis der Gleichung -1 = -1, das heißt ein Stein wird durch den Zug hinzugefügt
• Für alle anderen Felder das Ergebnis der Gleichung 0 = 0, das heißt die Feldbelegung ändert sich nicht

Solving und Vergleich mit Ai Plannern

2006 wurde das Integer Programming Modell mit gängigen AI Plannern verglichen^[3:5]. Konkret waren das Blackbox 4.22, Fast-forward 2.33, HSP 2.04 und STAN 45. Für das IP Modell wurde der Ilog Solver 5.3 verwendet. Dabei wurde jedoch nicht die Standardvariante genutzt, sondern die komplette Menge an sogenannten Reversals, die bereits im Abschnitt Spielvarianten erwähnt wurde. Für Solitär ist jedes Reversal lösbar, unabhängig von der Position des ersten Spielsteins^[5]:.

Für den Vergleich hatten alle Solver bzw. AI Planner je Reversal jeweils eine Stunde Zeit und einen Pentium III 750Mhz mit 256 Mb RAM zur Verfügung. In Tabelle 1 sind Teile der Ergebnisse zusammengefasst. Zu erkennen ist, dass sich das IP-Modell mit 14 gelösten Reversals als vergleichbar effektiv zu einigen der AI Plannern zeigt. Die durchschnittliche Zeit für gelöste Reversals ist beim IP-Modell am höchsten. Zudem ist es das einzige Verfahren, wo alle ungelösten Reversals auf die Zeitbegrenzung und nicht die Speicherbegrenzung zurückzuführen sind.

Ergebnis

Laut den Autor*innen des Papers hat sich vor allem die Flexibilität des Integer Programming gezeigt. Die Herangehensweise war zwar weniger erfolgreich beim Lösen von Reversals, aber hat sich dafür als flexibler gezeigt wenn es darum ging weitere Spielvarianten wie Fool's Solitaire oder Long-hop Solitaire zu modellieren und zu lösen. Diese Spielvarianten ließen sich mit den zum Vergleich herangezogenen AI Plannern nicht lösen. Zudem wurde gezeigt, dass sich Integer Programming auch für die Modellierung von sequentiellen Planungsproblemen eignet.

Referenzen

Abb. 1 selbst erstellt; keine Vorlage
Abb. 2 selbst erstellt; Vorlage aus "Modelling and solving english peg solitaire"^[3:6], S.2
Abb. 3 selbst erstellt; keine Vorlage
Abb. 4 selbst erstellt; keine Vorlage
Abb. 5 "Peg Solitaire game board shapes" by Júlio Reis is licensed under CC BY-SA 3.0
Abb. 6 selbst erstellt; auf Grundlage von "Modelling and solving english peg solitaire"^[3:7], S.4
Abb. 7 Vorlage aus "Modelling and solving english peg solitaire"^[3:8], S.2
Abb. 8 Vorlage aus "Modelling and solving english peg solitaire"^[3:9], S.2
Abb. 9 selbst erstellt; keine Vorlage
Abb. 10 selbst erstellt; keine Vorlage
Abb. 11 selbst erstellt; keine Vorlage

Tab. 1 - Daten aus "Modelling and solving english peg solitaire"^[3:10]