Bei FreeCell siehst du alle Karten, deshalb eignet es sich gut dafür, dass ein Computer nach Lösungen sucht. Hier erfährst du einfach erklärt, wie ein Computer FreeCell löst. Für diese Seite haben wir ein Programm geschrieben, das nach denselben Regeln wie die App FreeCell arbeitet, und es ausprobiert.
Suche: Züge ausprobieren und vorausschauen
Der Computer prüft wie ein Mensch: „Was passiert, wenn ich diesen Zug mache?“ Der Unterschied ist die Menge.
- In der aktuellen Stellung schreibt er alle möglichen Züge auf (in eine freie Zelle legen, in den Spalten anlegen, in die Zielzelle legen und so weiter).
- Er macht einen Zug und erhält eine neue Stellung.
- In dieser Stellung schreibt er wieder alle möglichen Züge auf.
- Findet er eine Stellung, in der alle 52 Karten in den Zielzellen liegen, ist die Zugfolge bis dahin die Antwort.
Dieses Durchgehen von Stellung zu Stellung mit immer neuen Verzweigungen nennt man Suche.
Trick 1: Dieselbe Stellung nicht zweimal prüfen
Bei FreeCell landest du durch verschiedene Zugfolgen oft in derselben Stellung. Schiebst du eine Karte nach rechts und wieder zurück nach links, ist alles wie vorher. Merkt sich der Computer jede Stellung, die er schon geprüft hat, und überspringt sie, wenn sie wieder auftaucht, spart er viel Arbeit.
Außerdem lassen sich Stellungen, die sich nur in der Reihenfolge der Spalten unterscheiden, oder Stellungen, die sich nur in der Anordnung der freien Zellen unterscheiden, auf dieselbe Weise lösen. Behandelt man sie als gleiche Stellung, muss man noch weniger prüfen.
Trick 2: Zuerst die aussichtsreichen Stellungen
Würde man alle Stellungen der Reihe nach prüfen, dauerte es viel zu lang. Deshalb vergibt man Punkte, etwa dafür, „dass viele Karten in den Zielzellen liegen“, „dass über der nächsten Karte für die Zielzelle wenige Karten liegen“ oder „dass freie Zellen leer sind“. Dann untersucht man zuerst die aussichtsreichen Stellungen.
Als wir das Programm das Windows-Spiel Nr. 1 lösen ließen, fand es nach der Prüfung von 843 Stellungen eine Lösung mit 110 Zügen. Für einen Menschen ist das aufwendig, für den Computer ein Augenblick. Die gefundene Zugfolge ist nicht unbedingt die kürzeste (Züge und Zugzahl beim Sieg).
Beweisen, dass es unlösbar ist
Gibt es eine Lösung, ist die Austeilung lösbar. Wie aber beweist man das Gegenteil?
Die Antwort: indem man alle erreichbaren Stellungen durchgeht. Kommt bei keinem Zug mehr eine neue Stellung heraus und war nie eine dabei, in der alle 52 Karten liegen, ist die Austeilung unlösbar.
Spiel 11982 des Windows-FreeCell ist als unlösbar bekannt. Auch bei unserem Programm gab es für 11982 keine Lösung, nachdem es alle erreichbaren Stellungen (etwa 95.000) durchgegangen war, einschließlich der Züge, bei denen Karten aus den Zielzellen zurückkommen (FreeCell ist fast immer lösbar).
Karten zusammen zu bewegen, ändert nichts an der Lösbarkeit
In der App FreeCell bewegst du auf einmal höchstens „Zahl der leeren freien Zellen plus 1“ Karten, und eine leere Spalte erhöht die Zahl nicht (Wie viele Karten du auf einmal bewegen darfst). Doch einen Zug mit mehreren Karten kann man in einzelne Züge mit freien Zellen und leeren Spalten zerlegen. Die erreichbaren Stellungen sind dieselben, deshalb sind dieselben Austeilungen lösbar. Nur die Zählung der Züge ändert sich.
Die Prüfung der Austeilungen der App FreeCell
Die App FreeCell mischt jedes Mal zufällig. Der Entwickler hat 100.000 zufällige Austeilungen vom Computer lösen lassen und die gefundenen Lösungen mit der Spielmechanik der App tatsächlich bis zum Ende durchgespielt. Alle 100.000 Austeilungen hatten eine Lösung.
Das ist aber kein Beweis dafür, dass jede Austeilung lösbar ist. Unter den Austeilungen, die wir nicht geprüft haben, kann es ganz selten unlösbare geben.
Wie der Computer vorgeht, hilft auch dir beim Spielen. Lies dazu auch Strategie und Gewinnrezepte.
