Morpion Solitaire, unter anderem auch bekannt unter den Namen Join Five, Cross 'n Lines[1] oder Petites Croix, ist ein erstmals in 1982 in dem französischen Magazin Jeux & Stratégie (z. Dt. Spiel und Strategie) referenziertes, NP-schweres Papier und Bleistift Spiel[2]. Es gibt Aussagen nach denen es auch zuvor, in 1963 oder 1964, bereits in Schulen gespielt wurde, aber die genaue Herkunft von Morpion Solitaire ist bis heute unbekannt[3].
¶ Spielregeln
Morpion Solitaire wird auf einem Kästchengitter gespielt, dessen Größe als unendlich angenommen wird. Auf die Gitterkreuze werden Punkte gesetzt. In der gängisten Variante wird mit einem leeren Kreuz der Seitenlänge vier gestartet[2:1].
¶ Singleplayer
Das grundlegende Spielprinzip lautet wie folgt: Es muss immer genau ein Punkt neu gesetzt werden, sodass eine gerade Linie aus genau fünf Punkten entsteht. Diese Linie darf horizontal, vertikal oder diagonal sein. In der gängigen touching Variante des Spiels dürfen sich Linien höchstens einen Punkt teilen. In der disjoint Variante dürfen gleich ausgerichtete Linien sich gar nicht berühren, Überschneidungen mit anders orientierten Linien sind aber weiterhin erlaubt. In der nebenstehenden Abbildung sind die diagonale und vertikale Linie immer legal, die zweite horizontale nur in der touching Variante[2:2].
Das Ziel ist es, so viele Linien wie möglich zu zeichnen und das Spiel endet, sobald es nicht mehr möglich ist, einen neuen Punkt hinzuzufügen[3:1][2:3].
Prinzipiell kann beliebig variiert werden, wie viele Anfangspunkte es gibt und wie diese angeordnet werden. Selbst die Länge der zu zeichnenden Linien ist variabel. Es ist nur zu beachten, dass bei manchen Startpositionen und Längen entweder unendliche Muster möglich sind, oder die Anzahl möglicher Züge sehr klein[3:2][2:4].
¶ Multiplayer
Spielen mehrere Spieler*innen gegeneinander, ändern sich die Regeln nicht, nur das Ziel. Es wird jetzt abwechselnd jeweils ein Punkt gesetzt, um eine Linie zu ziehen. Die Spieler*in, die als erstes keinen Zug mehr machen kann, hat verloren[2:5]. Es geht also nicht mehr darum, Highscores aufzustellen sondern stattdessen, der Gegner*in den Zug zu verbauen.
Alle Betrachtungen der algorithmischen Ansätze in diesem Artikel beziehen sich auf die Singleplayervariante.
¶ Lösungsverifikation[2:6]
Bei der Online-Version von Morpion Solitaire (zu finden hier) enthält jeder neue Punkt die Zahl des Zugs, in welchem er gesetzt wurde. Das macht es auch für Menschen nachvollziehbar, in welcher Reihenfolge die Linien einer Spiellösung gezogen wurden. Damit ist die Verifikation hierfür einfach.
Zu der Zeit, in welcher Morpion Solitaire erfunden wurde, war es allerdings noch ein komplett analoges Spiel. Es wurde als Rätsel in Magazinen veröffentlicht und die Autoren bekamen in Folge viele händische Lösungen zugeschickt. In diesen enthielten die gezeichneten Punkte keine Zahlen und die Verifikation einer Lösung war extrem zeitaufwendig.
Demaine, E., Demaine, M., Langerman, A. et al. haben sich mit dieser Problematik beschäftigt und einen Greedy-Algorithmus entworfen, der in linearer Zeit von einer gegebenen gezeichneten Lösung entscheiden kann, ob es eine valide Zugfolge zu diesem Endzustand gibt oder nicht.
Das Prinzip ist simpel: Es soll in jedem Zug eine Linie gefunden werden, die bereits (im Fall der Standardvariante gilt = 4) existierende Punkte enthält und einen, der noch nicht gespielt wurde. Wird keine spielbare Linie mehr gefunden, bevor der vorgegebene Endstand erreicht ist, liefert der Algorithmus eine negative Rückmeldung und es gibt keine gültige Lösung. Andernfalls gilt die Verifikation als gelungen.
¶ Beweis der Funktionalität
Da der Algorithmus den Spielregeln folgt, erschließt sich, dass bei seinem Erfolg eine gültige Lösung existiert. Das schließt eine falsch-positive Rückmeldung aus.
Um auch falsch-negative Ergebnisse auszuschließen, muss der Algorithmus garantiert eine Lösung finden, wenn der gegebene Endstand valide ist. Dies ist gegeben, da „Kollisionen unabhängig von der Reihenfolge, in der die Linien gezeichnet werden, sind“ (übersetzt aus dem Englischen). Das bedeutet:
Angenommen es existieren zwei Linien, und . wird nun von dem Greedy Algorithmus ausgewählt. Wenn es eine gültige Lösung gibt, muss egal sein, in welcher Reihenfolge die Linien gezeichnet werden. darf also nicht verhindern, dass gezeichnet werden kann, und umgekehrt. Ungültig wäre es, wenn sich mehr als zwei Punkte überschneiden in der touching Variante, oder mindestens ein Punkt bei gleich ausgerichteten Linien in der disjoint Version.
Es liegt nun das folgende zu prüfende Bild vor:
Die ursprüngliche Punktanordnung ist:
Es ist zu sehen, dass von dieser Punktkonfiguration aus zwei Linien möglich sind, einmal mit einem neuen Punkt rechts von den bestehenden, und einmal links. Egal, welche nun zuerst gezeichnet wird, sie verhindert ein valides Hinzufügen der zweiten Linie:
Folglich macht es keinen Unterschied, welche Linie der Algorithmus zuerst auswählt. Ist der Endstand ungültig und enthält eine Kollision, wird diese zwangsläufig entdeckt werden.
Ähnliches gilt für das Setzen eines Punkts. Wenn für das Zeichnen der Linie ein Punkt an einer Stelle gesetzt wurde, welcher verhindert, dass Linie gezeichnet werden kann, trifft das Gegenteil ebenfalls zu. Wieder ist die Reihenfolge nicht von Belang für die Feststellung, dass die Endposition nicht valide ist.
Ist beispielsweise das Bild
gegeben, ausgehend von der Punktkonfiguration
entsteht ein Konflikt unabhängig von der Reihenfolge, da für das Zeichnen einer Linie das Setzen eines neuen Punkts zwingend notwendig ist:
Nach dem Zeichnen einer Linie in letzterem Beispiel entstehen zwar neue Zugmöglichkeiten, doch keine führt zu dem selben Ergebnis, wie es das zu prüfende Bild darstellt.
Nach dem selben Prinzip kann der Algorithmus auch Kollisionen in einem gegebenen Bild finden, wenn sie nicht so offensichtlich sind wie in den genannten Beispielen.
¶ Umsetzung des Algorithmus
Nach dem Beweis der Funktionalität bleibt die Umsetzung. Besonders wichtig ist dafür, zeichenbare Linien schnell zu finden. Der gegebene Endstand wird dazu im Vorhinein so verarbeitet, dass jede vorkommende Linie eine doppelt verkettete Liste zugewiesen bekommt, in welcher die Punkte vorhanden sind, aus der sie besteht. Jeder Punkt bekommt Pointer zu seiner jeweiligen Position in den bis zu acht Listen, in welchen er vorkommt.
Immer wenn ein Punkt gezeichnet wird, wird er aus all seinen Listen entfernt. Ist nur noch genau ein Punkt in einer Liste übrig, gilt diese als zeichenbar. Da die Punkte des Startkreuzes am Anfang entfernt (oder gar nicht erst eingetragen) werden, muss es anfangs immer mindestens eine zeichenbare Linie geben.
¶ Lösungsansätze
Morpion Solitaire ist ein schwer zu lösendes Spiel für Computer. Zwar besitzt es keinen besonders hohen Branchingfaktor (etwa 10 bis 28 in der ersten Hälfte, 2 bis 9 in der zweiten[4]), dafür hat der Suchbaum eine sehr große Tiefe, genau genommen ein Level für jeden Punkt der Endpunktzahl[5]. Damit eignet sich zum Beispiel Alphabeta-Suche nicht, da der Horizonteffekt zu einschränkend wäre.
¶ Highscores
Für die touching Variante des Spiels erreichte ein evolutionärer Algorithmus von Hugues Juillé eine Punktzahl von 122[2:7] und eine Nested Monte Carlo Search (NMCS) Variante von Akiyama et al. 146[5:1]. Beide liegen jedoch weit unter dem menschlichen Rekord von Bruneau, welcher 170 beträgt und über dreißig Jahre als Weltrekord stand, bevor ein Nested Rollout Policy Adaptation (NRPA) Algorithmus in 2010 eine Punktzahl von 172 erreichte[4:1]. Inzwischen liegt der Weltrekord bei 178, aufgestellt von Christopher D. Rosin, ebenfalls mit NRPA[4:2].
Bei disjoint Morpion Solitaire wurden Highscores abwechselnd von einem Menschen und mit einem random-sampling Algorithmus mit lokaler Suche aufgestellt. Hier beträgt der menschliche Rekord 68[2:8]. Dieser wurde schließlich gebrochen von Cazenave mit einer Implementierung von NMCS, welche 80 Züge erreichte[6]. Aber auch in der disjoint Variante ist der aktuelle Weltrekordhalter Christopher D. Rosin mit seinem NRPA Algorithmus und einer Punktzahl von 82[5:2].
¶ Nested Monte Carlo Search
Während Monte Carlo Tree Search (MCTS) normalerweise einen Suchbaum aufstellt und sich in jedem Knoten das Verhältnis von Siegen und Besuchen speichert, gibt es in Morpion Solitaire nicht wirklich so etwas wie einen „Sieg“. Interessant ist lediglich die beste gefundene Punktzahl, also ein einziger Pfad durch den Spielbaum. Die Funktionsweise von MCTS müsste also in jedem Fall angepasst werden.
Besser eignet sich NMCS. Bei diesem Ansatz handelt es sich um einen rekursiven Algorithmus, der genau diesen besten Pfad speichert, und ansonsten wie MCTS mit zufälligen Rollouts arbeitet (also einen Pfad durch den Spielbaum sucht und bei jeder Verzweigung einen zufälligen Weg wählt)[6:1]. Eine genauere Beschreibung befindet sich in dem Artikel zu NMCS.
In seinem Paper stellt Cazenave fest, dass die Suche für Morpion Solitaire sehr gut mit steigendem NMCS Level skaliert, vorausgesetzt die beste Sequenz wird gespeichert. Das heißt, dass ein höheres Level deutlich bessere Ergebnisse liefert als das nächst niedrigere. Obwohl eine Suche mit Level l 200 mal länger dauert als eine mit Level l-1, gilt für Level kleiner gleich vier, dass es sich lohnt, mit höherem Level zu suchen, weil ein niedrigeres wahrscheinlich eine deutlich niedrigere Punktzahl findet[6:2].
Cazenave stellte außerdem die zu seiner Zeit beste Punktzahl in disjoint Morpion Solitaire mit NMCS auf. Dafür mussten 32 Computer mit dual cores fünf Stunden rechnen, was auf einer einzigen Maschine circa einer Laufzeit von zehn Tagen entsprochen hätte[6:3]. Der folgende Algorithmus kann diese Zeit deutlich unterbieten[5:3].
¶ Nested Rollout Policy Adaptation[5:4]
NRPA kann als Verfeinerung von NMCS betrachtet werden. Der Algorithmus funktioniert ähnlich, jedoch gibt es zwei bedeutende Änderungen:
Zum einen wird bei NRPA die Anzahl der Iterationen, also wie oft pro Rekursionslevel eine tiefere Rekursion aufgerufen wird, durch einen globalen Parameter begrenzt. NMCS führt diesen Aufruf auf jedes Kind des jeweils aktuellen Knotens durch, was vor dem Ankommen beim Rekurisonsanker zu einer Breitensuche führt. Das erhöht die Laufzeit bedeutend.
Zum anderen sind Rollouts (das Abgehen eines einzelnen Pfads im Suchbaum), anders als bei MCTS und NMCS, nicht mehr zufällig. Sie basieren stattdessen auf einer Policy Tabelle, die die Wahrscheinlichkeit eines Zugs bestimmt. Zudem wird in Rekursionsleveln, die kein Rollout sind, nicht mehr der aktuelle Knoten gespeichert: Jedes Rollout beginnt bei der Baumwurzel. Beide Änderungen begünstigen die Exploration, also das Erkunden neuer Pfade im Suchbaum, und erhöhen so die Wahrscheinlichkeit, eine bessere Lösung zu finden.
Eine genauere Beschreibung der Funktionsweise von NRPA findet sich im entsprechenden Artikel und eine Implementierung von Morpion Solitaire mit NRPA in C auf Github.
¶ Dominierte Züge[5:5]
Eine Verfeinerung des NRPA Algorithmus' für Morpion Solitaire ist das Einführen von dominierten Zügen. Ein dominierter Zug ist ein solcher, der den selben Punkt setzt wie seine Alternative, aber mehr Platz einnimmt.
In der nebenstehenden Abb. 5 kann ein Punkt zwischen 0 und 1 gesetzt werden. Die entstehende Linie kann entweder die Punkte von 0 bis 3 beinhalten (A), oder von dem neuen Punkt bis 4 (B). Linie A blockiert alle übrigen Verbindungen in der Abbildung, auch die zwischen 3&4 und 4&5, da in diese Lücke keine weitere Linie mehr gezeichnet werden kann. Linie B blockiert ebenfalls die Verbindung zwischen 4&5, allerdings kann die Verbindung von 0 zum neuen Punkt potentiell für weitere Linien genutzt werden.
Durch das Ersetzen von A durch B bleiben alle legalen Zugsequenzen legal, aber es können neue Möglichkeiten entstehen. Während also in Rosins NRPA Implementation dominierten Zügen ein eigener Code zugewiesen wird und sie weiterhin im Suchbaum als Knoten vorhanden sind, werden sie in der eigentlichen Darstellung des Spielfelds mit den dominierenden Zügen ersetzt.
Die dominierten Züge zu ersetzen gab in Rosins Experimenten eine kleine Verbesserung gegenüber dem Entfernen solcher Züge.
¶ Laufzeiten und Ergebnisse[5:6]
Um die Effizienz von NMCS und NRPA vergleichen zu können, legte Christopher D. Rosin ein Zeitfenster von beziehungsweise Sekunden fest. Nacheinander auf der gleichen Maschine wurden mit dieser zeitlichen Begrenzung Aufrufe der beiden Algorithmen mit der jeweils gleichen Suchtiefe gestartet. Wurde das Zeitfenster nicht komplett ausgenutzt, wurde ein unabhängiger Aufruf gestartet und alle Ergebnisse gespeichert.
Sowohl NMCS als auch NRPA wurden mit aufsteigenden Tiefen getestet, bis nichtmehr der Großteil des ersten Aufrufs innerhalb der gegebenen Zeit vollendet werden konnte. Hier stellte Rosin bereits fest, dass NRPA teilweise mit einer größeren Tiefe als NMCS in der selben Zeit laufen konnte.
Zusätzlich wurde eine NMCS Variante mit einer manuell eingestellten Policy für touching Morpion Solitaire eingeführt, um eine bessere Vergleichbarkeit mit NRPA zu gewährleisten. Aber auch hier lag die Performance deutlich unter der von NRPA, obwohl letzterer Algorithmus seine Policy von Null starten muss.
In Tabelle 1 sind die Ergebnisse zu sehen. Mit der angepassten, aber immer noch statischen Policy erreicht NMCS im Median deutlich bessere Ergebnisse als die konventionelle Version. Aber beide bleiben hinter NRPA zurück, welche schon auf Level 3 im Median bessere Ergebnisse findet, als vorher je von einem Computer in touching Morpion Solitaire erreicht wurden.
Zudem ist zu sehen, dass NRPA auf dem gleichen Level in 1/100 der Zeit von NMCS im Median ein besseres Ergebnis liefert. Diese Tendenz fand sich auch in anderen von Rosins Experimenten mit anderen Spielen als Morpion Solitaire.
Während Cazenave den damaligen Rekord von 80 in disjointed Morpion Solitaire in zehn Tagen (beziehungsweise mit 32 Computern in fünf Stunden) fand, erreichte NRPA von Rosin den jetzigen Weltrekord von 82 in nur einer Stunde. Für das Finden der Punktzahl 177 in touching Morpion Solitaire brauchte der Algorithmus eine Woche. Der beste Vergleich sind 38 Tage für den früheren Rekord eines Computers von 146 von Akiyama et al. Für den aktuellen Weltrekord von 178 liegen in den referenzierten Papern keine Laufzeitwerte vor.
Damit übertrifft NRPA, zumindest für Morpion Solitaire, alle anderen bisher zur Lösung dieses Spiels verwendeten Algorithmen. Sowohl mit Blick auf die Laufzeit, als auch mit der Höhe der Endpunktzahlen.
¶ Range Query Technik[4:3]
Eine der zeitaufwendigsten Aufgaben in NRPA und anderen Monte Carlo Algorithmen ist das Finden legaler Züge. Obwohl NRPA bereits schneller läuft als beispielsweise NMCS, können beide mit höheren Leveln ausgeführt werden, wenn Rollouts effizienter sind. Je höher das Level, desto wahrscheinlicher das Finden einer guten Lösung.
In der Standardimplementierung von NMCS oder NRPA wird nach jedem Zug die Liste mit möglichen Zügen verworfen und neu erzeugt. Dieses Absuchen der gesamten Spielsituation kostet Zeit. Buzer & Cazenaves Ansatz war, die alte Zugliste zu recyclen, indem nur in einem bestimmten Bereich Züge entfernt und neu hinzugefügt werden.
Für Morpion Solitaire ist bekannt, dass nur Züge um den zuletzt gesetzten Punkt beeinflusst werden. Hier bietet sich ein sternförmiger Suchbereich an, da Linien nur horizontal, vertikal oder diagonal liegen können. Für die Effizienz ist es zudem nützlich die Linien, beziehungsweise Züge, mit gleicher Ausrichtung aufsteigend zu ordnen. Dafür erstellten Buzer & Cazenave ein lokales Koordinatensystem. Mit diesem und einer einzigartigen ID für jeden Zug ist es möglich, aus der Liste legaler Züge alle potentiell nicht mehr möglichen zu entfernen und neue hinzuzufügen. Betrachet werden alle Felder in vier Reichweite von dem neuen Punkt, beziehungsweise der neuen Linie, wie in der nebenstehenden Abbildung zu sehen. Die weißen Felder kennzeichnen den Bereich, der neu untersucht wird.
Es ist davon auszugehen, dass es sich bei dem weißen Feld diagonal über um einen Darstellungfehler handelt, da es nach der Beschreibung des Vorgehens in dem vorliegenden Paper keinen Sinn ergeben würde, dieses Feld für die Range Query Technik zu berücksichtigen.
Hiermit gelang es Buzer & Cazenave, NMCS für disjoint Morpion Solitaire um den Faktor zehn zu beschleunigen. Für NRPA wurden zwei weitere Optimierungen vorgenommen: Anstatt die gesamte Policy Tabelle zu kopieren, wurden in Adapt nur die Werte der gegebenen Sequenz kopiert. Außerdem, anstatt immer wieder den Exponent eines Gewichts zu berechnen, speicherten sie gleich die Exponenten der Gewichte in der Policy Tabelle. Zusammen mit der Range Query Technik brachte das eine Einsparung von 36% der Rechenzeit für disjoint Morpion Solitaire, und 32% für die touching Variante.
Doch trotz der signifikant verbesserten Effizienz gelang es nur, die bereits aufgestellten Weltrekorde zu finden. Die Verteilung der Endpunktzahlen ist in den folgenden Abbildungen zu erkennen:
¶ Ausblick
Trotz der bereits vorgenommenen und hier beschriebenen Verbesserungen, ist es bisher nicht gelungen, Rosins Weltrekorde für touching und disjoint Morpion Solitaire zu schlagen. Gleiche Punktzahlen wurden dagegen schon mehrmals erreicht. In disjoint Morpion Solitaire betrug sogar ein Großteil der von Buzer & Cazenave gefundenen Ergebnisse den aktuellen Weltrekord.
Dieses wiederholte Finden gleicher Punktzahlen könnte darauf hindeuten, dass bereits die Grenze des Möglichen, zumindest mit den typischen Konfigurationen von Morpion Solitaire, erreicht ist. Jedoch liegen berechnete Obere Schranken von Demaine, E., Demaine, M., Langerman, A. et al. mit 141 für disjoint und 704 für touching weit über den aktuellen Highscores[2:9]. Diese Schranken bedeuten nicht, dass Punktzahlen dieser Größenordnungen zwingend möglich sein müssen, aber sie lassen das Potential für bessere Lösungen.
Es ist nicht klar, ob bereits die bestmögliche Punktzahl erreicht wurde, oder es noch leistungsstärkere Algorithmen oder eine bessere Spezielisierung benötigt, um die wirkliche Obergrenze zu erreichen.
Letztendlich ist der größtmögliche Highscore in Morpion Solitaire genauso ungeklärt wie die Herkunft des Spiels selbst.
¶ Bildquellen
Abb. 1: Screenshot von https://joinfive.com/
Abb. 2: Screenshot von https://joinfive.com/
Abb. 3: Screenshot von http://www.morpionsolitaire.com/
Abb. 4: Screenshot von http://www.morpionsolitaire.com/
Abb. 5: Screenshot aus [5:7]
Abb. 6: Screenshot aus [4:4]
Abb. 7: Screenshot aus [4:5]
Abb. 8: Screenshot aus [4:6]
Tab. 1: Screenshot aus [5:8]
Die restlichen Darstellungen sind (ohne Vorbild) selbst erstellt.
¶ Referenzen
https://en.wikipedia.org/wiki/Join_five (Stand vom 08.07.2025) ↩︎
Demaine, E. D., Demaine, M. L., Langerman, A., & Langerman, S. (2006, April). Morpion solitaire. Theory of Computing Systems (Vol. 39, Nr. 3, pp. 439-453). | pdf | DOI ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
http://www.morpionsolitaire.com/ (Stand vom 08.07.2025) ↩︎ ↩︎ ↩︎
Buzer, L., & Cazenave, T. (2021, August). Playout Optimization for Monte-Carlo Search Algorithms. Application to Morpion Solitaire. In 2021 Institute of Electrical and Electronics Engineers' (IEEE) Conference on Games (CoG) (pp. 01-08). IEEE. | pdf | DOI ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Rosin, C. D. (2011, July). Nested rollout policy adaptation for Monte Carlo tree search. Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI) (Vol. 2011, pp. 649-654). DOI ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Cazenave, T. (2009, July). Nested Monte-Carlo Search. Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI) (Vol. 9, pp. 456-461). | pdf ↩︎ ↩︎ ↩︎ ↩︎