¶ Das Spiel
Peg Solitaire ist ein Puzzle-Spiel, das auf einem Brett gespielt sind, auf dem in Feldern Spielsteine plaziert sind. Das am weitesten verbreitete Spielbrett ist kreuzförmig mit 33 Feldern und 32 Steinen (siehe Abbildung rechts). Diese Variante ist auch als English Peg Solitaire bekannt. [1]
Ziel des Spieles ist es, alle bis auf eine Kugel vom Brett zu nehmen. Dazu werden zuerst alle Steine auf dem Brett verteilt, sodass nur noch das mittlere Feld frei bleibt. Danach können Steine heruntergenommen, indem mit einem direkt benachbarten Stein über sie hinweggesprungen wird. Auf einem Feld kann dabei immer nur ein Stein gleichzeitig liegen. Außerdem können die Spielsteine nur in Zeilen oder Spalten springen, nicht diagonal. Das Spiel ist erfolgreich beendet, wenn nur noch genau ein Stein in der Brettmitte übrig ist, also die Brettsituation genau umgekehrt wurde.
¶ Modellierung als Integer Programming
English Peg Solitaire kann mittels Integer Programming modelliert und gelöst werden. Dabei zeigt sich, dass English Peg Solitaire in genau 31 Zügen gelöst werden kann [1].
Bevor English Peg Solitaire als Integer Programm definiert werden kann, müssen erst einmal Definitionen eingeführt werden, um es computerlesbar zu machen. Zuerst kann man die Position eines Spielsteins als Wertepaar beschrieben werden, wobei die Spalte und die Zeile angibt. Folgende Grafik zeigt, wie das daraus entstehende Koordinatensystem auf dem Spielbrett aussieht:
Ein Zug einer Kugel dann der Wechsel . Ein Zug wird immer zu einem bestimmten Zeitpunkt durchgeführt. Es darf pro Zeitschritt nur ein Zug gemacht werden. Außerdem können wir festhalten, dass und ganzzahlig ist. Als Letztes muss noch die Menge definiert werden. enthält alle möglichen Löcher bzw. Positionen, die ein Stein annehmen kann. Wichtig ist, dass nicht das Kreuzprodukt von mit sich selber ist, da z. B. das Feld kein gültiges Feld ist. Außerdemwird noch eine Richtung benötigt, die ein Stein machen kann. Da ein Stein nur horizontal oder vertikal gehen kann, gibt es 4 Richtungen. Diese werden in der Menge gesammelt. Die Buchstaben stehen hierbei für die verschiedenen Himmelsrichtungen.
Die Definitionen der Variablen sind zwar jetzt alle ganzzahlig, sagen aber noch wenig über den Spielstand aus. Dazu werden noch zwei Formeln benötigt:
- (beschreibt einen möglichen Zug)
- bState[i, j, t] (beschreibt eine Feldbelegung)
Dabei ist eine gültige Position, eine gültige Zeit und eine gültige Zugrichtung. Dabei wertet zu aus, wenn vom angegebenen Feld zum Zeitpunkt ein Sprung in Richtung gemacht wurde und bState, ob ein angegebenes Feld zum Zeitpunkt besetzt ist. Wenn dies jeweils nicht erfüllt ist, geben beide Formeln zurück.
¶ Optimierungsfunktion
Diese beiden Formeln sagen etwas über den Spielstand und können somit in unserem Integer Programm genutzt werden. Außerdem ergibt sich daraus direkt die Optimierungsfunktion. Da nach dem letzten Zeitschritt auf dem mittleren Feld einen Stein platziert sein soll, kann bState genutzt werden:
¶ Nebenbedingungen
Jetzt müssen noch die verschiedenen Spieldynamiken in den Nebenbedingungen modelliert werden. Zuerst werden für alle Richtungen jeweils Formeln modelliert. Diese werden exemplarich für den Sprung nach oben, also Richtung , gezeigt. Die Formeln sind folgende:
Formel modelliert hier, dass auf dem Ausgangsfeld eine Kugel liegen muss. Formel modelliert, dass auf dem Feld oberhalb unsres Ausgangsfeldes ebenfalls eine Kugel liegen muss und Formel modelliert, dass auf dem Feld oberhalb unseres Ausgangsfeldes keine Kugel liegen darf. Wenn eine der Formeln nicht definiert ist, da ein Feld aus dem Spielfeld rennt, wird dies ebenfalls abgefangen, da für jeden Zug alle Formeln definiert sein müssen.
Die Formeln für die anderen Richtungen ergeben sich analog, bloß die Indizierung der Felder ändert sich. Sie sehen wie folgt aus:
Dies modelliert jetzt , dass ein Sprung korrekt von einem besetzten Feld, über ein besetztes Feld, auf ein leeres Feld ausgeführt wird. Allerdings wird noch nicht modelliert, dass nur ein Sprung pro Zeitschritt gemacht werden darf. Dafür benötigen wir folgende Formel bzw. Nebenbedingung:
Die Summe iteriert hier über alle Positionen und deren Zugmöglichkeiten und gibt dabei an, ob ein Zug gemacht wird. Durch die Gleichsetzung mit wird erzwungen, dass pro Zeitschritt nur von genau einem Feld in genau eine Richtung ein Zug gemacht wird.
Als letzte Formel fehlt noch die sogenannte "Lebendigkeit". Die Lebendigkeit beschreibt, dass sich durch einen Zug das Bord auch verändern muss. Dies wird durch folgende letzte Formel verhindert:
Da bState entweder oder ist, kann die Differenz nur die Werte , oder annehmen. entsteht, wenn einen Spielstein auf von diesem zum nächsten Zeitschritt gelöscht wird. Entweder, da sie einen Zug ausführt, oder weil über sie übersprungen wurde. hingegen entsteht, wenn sich die Belegung des Feldes zum nächsten Zeitschritt nicht ändern. Wenn allerdings im nächsten Zeitschritt einen Spielstein draufgezogen wird, ergibt sich .
Im rechten Teil der Formel kann durch die vorigen Formeln immer nur höchstens ein Summand zu werden und alle anderen zu werden müssen. Somit können die einzelnen Teile der Formel seperat betrachtet werden. Außerdem sind alle Summanden Formeln, die angeben, ob sich entweder auf dem aktuellen Feld oder den Feldern waagerecht oder senkrecht 1 oder 2 weiter etwas ändert.
Wenn alle Summanden 0 sind, wird auf dem aktuellen Feld und allen für das Feld relevanten angrenzenden Feldern nichts an der Belegung geändert. Dies deckt sich mit der Beobachtung aus dem linken Teil der Formel, sodass dieser Fall abgeschlossen werden kann.
Im Folgendem sind die Teile der rechten Formel, die zu auswerten können, rot markiert:
Die rechte Formel wertet nur zu aus, wenn eine Kugel auf gelöscht wird. Dies kann enteweder passieren, wenn über sie drübergesprungen wird oder sie selbst einen Zug ausführt. Die Summe in der obigen Formel beschreibt den Fall, dass die Kugel selbst einen Zug ausführt. Die anderen 4 rot markierten Formel drücken aus, dass von einem direkten Nachbarfeld eine Kugel einen Zug über das aktuelle Feld gemacht wird. Da dies alle Möglichkeiten sind, mit denen eine Kugel gelöscht werden kann und keine weiteren Formel rot markiert sind, ist dieser Fall auch fertig.
Der letzte Fall ist, dass der linke Teil der Formel zu auswertet, also auf dieses Feld gesprungen wird. Dies geschieht nur, wenn von einem Feld zwei Felder weiter weg über eine Kugel in Richtung des aktuellen Feldes gesprungen wird. Im Folgenden sind alle Teile des rechten Teiles der Formel markiert, die zu auswerten können:
Hier sieht man, dass die 4 Formeln genau das modellieren. Da es die einzigen markierten Formeln sind, ist dieser Fall auch fertig.
Alle Formeln der rechten Seite wurde jetzt ein äquivalentes Ergebnis der linken Seite zugeordnet. Damit ist diese Formel auch komplett erklärt.
In allen Formeln wird hierbei angenommen, dass über iteriert. Außerdem wird in den Formeln (2) bis (12) und (14) angenommen, dass über alle Elemente aus iteriert. Dies aufzuschreiben hätte allerdings die Lesbarkeit der Formeln erschwert, sodass sie leicht vereinfacht dargestellt wurden.
Mit der Lebendigkeit und den Spielregeln, ist das Modell vollständig. Für eine optimierte Programmierung muss noch die Laufzeit berücksichtigt werden.
¶ Laufzeit
In [1] werden keine konkreten Laufzeitberechnungen vorgenommen, sondern verschiedene Modelle des Integer Programmings getestet. Dabei schnitt CPLEX von allen verglichenen Modellen am besten ab. Dabei wurde die Optimierung nur wenig von der Zielfunktion aber maßgeblich von der Branching Strategie beeinflusst, die Kriterien für Fehlerhafte versuche deklariert.
¶ Modellierung als Graph
Peg Solitaire kann auch als Graph modelliert werden. Dabei wird in [3] die Annahme getroffen, dass sich auf endlichen, ungerichteten Graphen bewegt wird, die nur aus einer Zusammenhangskomponente bestehen.
Um Peg Solitaire als Graph zu modellieren, wird das Spielfeld als Knotenpunkte im Graph und die Züge als Kanten dargestellt. Eine Zeitkomponente ist durch den Belegungsgrad der Knoten gegeben. Die Schwierigkeit bei einer Modellierung als Graph ist die Unterscheidung, welche Züge zulässig sind, das Modell insgesamt statischer als Integer Programming ist.
Das Ziel der Modellierung ist es, aus einer gegebenen Startbelegung eine gegebenen Endbelegung zu finden.
¶ Laufzeit
In [3] wird nicht näher darauf eingegangen, mit welcher Laufzeit diese modellierten Graphen zum lösen brauchen. Das ist auch nicht möglich, da keine Suchalgorithmen angegeben sind, die einen Lösungsweg finden können. Da die typischen Graphalgorithmen Breiten- und Tiefensuche keine Unterscheidung der Belegungszustände treffen können, eignen sie sich nicht, um mit ihnen eine Lösung zu finden.
¶ Fazit
Um Peg Solitaire zu modellieren, kann entweder der Ansatz eines Graphen oder eines Integer Programms genutzt werden.
Der Graph bildet das Spielfeld sehr einfach ab, die Schwierigkeit ist hier der Algorithmus für zulässige Züge, an dem nicht nur die Laufzeit, sondern auch die Lösbarkeit hängt. Allerdings sind Graphen gut erforscht und generell eine schnelle Struktur in der Informatik.
Beim Integer Programming hingegen ist die Lösbarkeit gegeben, allerdings hängt die Laufzeit an den verwendeten Branching-Strategien und ist im Worst-Case NP-schwer.
Ob für Peg Solitair Graphen oder Integer Programming oder Graphen genutzt werden, muss deshalb für jeden Fall neu abgewogen werden.
¶ Quellen
¶ Bilder
Abb 1: Wikimedia Commons, „Peg Solitaire interactive solution guide“,[Online]. Verfügbar unter:
https://upload.wikimedia.org/wikipedia/commons/thumb/9/99/Peg_Solitaire_interactive_solution_guide.svg/960px-Peg_Solitaire_interactive_solution_guide.svg.png. [Zugriff am: 18. Dez. 2025].
Abb 2: Adaptiert nach Figure 1 in [2]
¶ Literatur
[1] Wikipedia, „Solitär (Brettspiel)“, Online-Enzyklopädie. [Online]. Verfügbar unter: https://de.wikipedia.org/wiki/Solitär_(Brettspiel). [Zugriff am: 18. Dez. 2025].
[2] C. Jefferson, A. Miguel, I. Miguel, und S. A. Tarim, „Modelling and solving english peg solitaire“, Computers & Operations Research, Bd. 33, Nr. 10, S. 2935–2959, 2006, doi: 10.1016/j.cor.2005.02.027. Link
[3] R. A. Beeler und D. P. Hoilman, „Peg solitaire on graphs“, Discrete mathematics, Bd. 311, Nr. 20, S. 2198–2202, 2011. Link