Freecell-Solver

Gestelltes Problem
Freecell macht mich immer ganz kirre, da hat man dann mit dem falschen Stapel angefangen und auf einmal ist nichts mehr frei, Statistik: “30%, aktuell 17-mal verloren”. Das ist Stress pur!
Warum kostbare Freizeit verschwenden, wenn man solche Probleme per Programm lösen kann?

Algorithmus
Vor der Frage nach dem Algorithmus stand die nach dem Aussehen der Anwendung. Einfach nur Text “Zug von Stapel drei nach vier.” erschien mir nicht ausreichend. Deswegen habe ich erst einmal alle Karten bei Freecell geklaut und als einzelne .bmp-Dateien abgelegt. Da ich mittlerweile auch ganz gern mal den Borland-C++-Compiler benutze, ging der Teil mit der Anzeige der Karten auf einem grünen Spieltisch relativ schnell. Wie in Freecell aus der ausgewählten Spielnummer die Anfangsstellung entsteht, habe ich noch nicht ergründen können. Deshalb wurde das Spiel 21145 fest im Programm verdrahtet. Jetzt mussten ja nur noch zu einer Stellung alle möglichen Züge ermittelt und dann für jeden Zug rekursiv das Gleiche getan werden, bis man auf eine Stellung stiess, wo alle Karten abgelegt waren. Pustekuchen. Die ersten Läufe dieser Version schafften über 100.000 Stellungen, ohne zu einer Lösung zu kommen. Bei Freecell gibt es nämlich reversible Züge. Deshalb wurde eine Liste der schon besuchten Positionen hinzugefügt. Damit konnten auch andere Formen der Stellungswiederholung ausgeschlossen werden. Trotzdem hatte ich ein Programm welches es schaffte in 10 Sekunden 200-mal zu verlieren, aber trotzdem nicht zur Lösung fand. Das lag daran dass es bei Freecell sehr viele Stellungen gibt. Es war notwendig, dem Programm auf der Ebene der möglichen Züge eine Richtung vorzugeben. Statt alle Zugmöglichkeiten wahllos durchzuprobieren, wurde für jeden Zug eine Bewertung berechnet. Die Züge mit der besten Bewertung wurden dann als erste ausprobiert. Eine gute Stellung hat folgende Eigenschaften: möglichst viele freie Plätze, möglichst gut sortierte Stapel, keine eingeklemmten Karten mit kleinem Wert. Damit gings dann. Hat ja auch immerhin fünf Tage gebraucht.
So sieht das dann aus:

(451 Positionen getestet, Rekursionstiefe 318, gemerkt 450 Stellungen, bis jetzt 38-mal verloren)

Leave a Reply

Your email address will not be published. Required fields are marked *