Solitaire (oder: Wofür hat man einen CPU-Server?)
www.dominique-petersen.com  >  Solitaire


Inhaltsverzeichnis:
  Beschreibung
  1. Programm (naiv)
  2. Programm (naiv rekursiv)
  3. Programm (rekursiv)
  Download
  Bewegungsliste (Lösungen)
  Fazit und Laufzeitanalyse
  Copyright


Beschreibung:

Das Spiel bzw. Problem Solitaire (auch: Solitair, Solitär) mit 45 Feldern hat Prof. Dr. W. Rehm an der TU-Chemnitz in dem Fach Maschinenorientieren Programmierung in der ersten Vorlesung Mitte Oktober 2002 kurz vorgestellt und eigentlich nicht damit gerechnet, dass sich jemand weitergehend damit beschäftigt. Da man im 3. Semester sicherlich noch nebenbei genug freie Zeit hat, habe ich mal versucht, Wege für das Lösen des Problems mit Hilfe des Computers zu finden, denn zu der Zeit fand ich im Internet zwar manuelle Spiele dazu, aber keine Lösungsalgorithmen. Dabei sind drei Programme entstanden.



1. Programm (naiv):

Das erste Programm, "sol_bf", ist ein zufallsgesteuertes BruteForce-Anwendung. Es wählt zufällig eine sprungfähige Koordinate aus und führt diesen Schritt aus. So macht es weiter, bis sich kein Stein mehr rücken lässt. Danach initialisiert es das Feld komplett neu und versucht es weiter.
 
Hierbei ist mein Dual-PIII 450 bis zu 3 übrig gebliebenen Steinen gekommen; mein Athlon 1000 hat nach cirka 10 Stunden einen Bewegungsablauf gefunden, wo "nur" noch 2 Steine übrig geblieben sind. Ausserdem ist es ziemlich langsam wegen der ganzen Random-Befehle. Das muss auf jeden Fall besser gehen!



2. Programm (naiv rekursiv):

Das zweite Programm "sol_rek" ist ein Gemisch aus Zufallsoptionen und einer rekursiven Vorgehensweise. Es sucht solange Zufallszahlen, bis es alle möglichen Züge bei einem Zug herausgefunden hat, und geht diese rekursiv durch. Findet es keinen bewegbaren Stein, löst es die Rekursion von hinten wieder auf.
 
Prinzipiell genauso schnell wie das 3. Programm, nur durch die Zufallsgeschichte wieder enorm langsamer. Das Gute hieran ist, dass man wirklich fast alle Züge rekursiv durchgeht, es sei denn, der Zufallsgenerator hat nicht alle gefunden, was man allerdings vernachlüssigen kann. Nach ca 2000 Minuten (>33 Stunden) hat mein PIII ca 20 Millionen Verschiebungen vorgenommen.



3. Programm (rekursiv):

Das dritte Programm "sol_rek2" ist nun eine reine rekursive Anwendung. Statt per Zufall alle möglichen Sprungsteine zu suchen, sucht es alle, welche es auch rekursiv der Reihe nach durchgeht. Negativ an der Sache ist, dass wenn das Programm neu gestartet wurde, das Programm wieder genau am Anfang beginnnt (dazu könnte man einmal ein save/load-Mechanismus einbauen). Dies ist bei Programm 1 und 2 nicht gegeben. Deshalb habe ich es an einer Stelle modifiziert, und nun geht das geänderte Programm "sol_rek2i" genau von der anderen Seite rekursiv durch.
 
Da nur ein Prozessor je ein Programm verarbeitet, habe ich es so praktisch erreicht, dass jeder Prozessor nur die Hälfte der Arbeit hat, da sie sich zwangsläufig irgendwann einmal begegenen müssen. Also ist die ETA: ewig/2. Mein PIII schaffte nach rund 1300 Minuten (>21 Stunden) knapp 1,2 Milliarden Verschiebungen.



Download:

Alle Programme benötigen die Datei "solitair.mov" im selben Verzeichnis, in welcher sie alle gefundenen Lösungswege auflisten.
 
Bei allen Programmen sind die Tasten "i", "s" (Statusinformation) und "q", "e" und "x" (Beenden) Deine Freunde.
 
     Solitair (SourceCode, Pascal) (12.87 KB)
 
Bei Borland Pascal 7.1 stürzt das dritte Programm immer nach der 8. Bewegung mit einem Stack Error ab. Kompiliert unter FreePascal laufen alle 3 Programme stabil (jedes min. 1500 Stunden). Anbei sind in den jeweiligen Archiven schon bereits die kompilierten Dateien für verschiedene Systeme.
 
     Solitair (Binaries, Linux) (146.39 KB)
     Solitair (Binaries, DOS/Windows) (203.4 KB)



Bewegungsliste (Lösungen):

Nachdem es etwas enttäuschend wurde, dass bei einem Brett von 45 Feldern keine Lösung in Sicht war, beschloss ich, das Feld etwas zu verkleinern, was sich später als richtig heraus gestellt hat. Bei einer Solitaire-Variante von 9+4*6=33 Feldern wies mein alter PC bereits die erste Lösung nach 20 Sekunden auf, und aufgrund der Rekursion die nächsten 150 ein paar Sekunden später. Bereits nach 10 Minuten war die Movelist mit 2000 Lösungen gefüllt, nach 30 Minuten mit 4000. Hierbei wird allerdings nicht auf Symmetrie überprüft, welche man später allerdings mit einem sekundären Programm aus der Move-List Datei rausfiltern könnte (wäre zur Laufzeit zu langsam).
 
Ich habe die Movelist der ersten 140.000 Lösungen hier gezippt zum Download bereit gestellt. Die Datei ist entpackt über 200 MB gross.
 
     Movelist (Bewegungsliste mit 140.000 Lösungen) (3.36 MB)
 
Weiterhin sieht mein Feld und dessen Notation (noch aus dem 45er Solitaire bedingt) so aus:
Legende: [] = Stein, . = kein Feld, <leer> = frei

 Y
 0 ..........................
 1 ..........................
 2 ..........................
 3 ..........[][][]..........
 4 ..........[][][]..........
 5 ......[][][][][][][]......
 6 ......[][][]  [][][]......
 7 ......[][][][][][][]......
 8 ..........[][][]..........
 9 ..........[][][]..........
10 ..........................
11 ..........................
12 ..........................
   0 1 2 3 4 5 6 7 8 9 101112 X

In der Movelist sind die Koordinaten im [x, y]-Format aufgebaut.



Fazit und Laufzeitanalyse:

Inzwischen hat mein Computer in circa 3000 Minuten (50 Stunden) rund 140.000 Lösungen gefunden. Hierbei hat er etwa 2,1 Milliarden Verschiebungen durchgeführt. Wenn ich das nun umrechne, ergibt das alle 15.000 Züge eine Lösung.
 
Nachdem ich mir die Logdatei etwas näher angeschaut und analysiert habe, bin ich zu dem Ergebnis gekommen, dass es im Durchschnitt immer 4,5 Steine gibt, die springen können. Bei einer Steinanzahl von 31 (den letzten zähle ich nicht) sind das also 4,5^31 mögliche Verschiebungen (rund 178 * 10^18). In Verbindung mit dem obigen Ergebnis, dass es alle 15.000 Züge eine Lösung gibt, erhalte ich circa 12 * 10^15 Lösungsmöglichkeiten für ein Solitaire Spiel mit 33 Feldern.
 
Nun wollte ich wissen, wie lange mein Computer daran wohl zu rechnen hätte, bis er wirklich alle Lösungen gefunden hat. In 3000 Minuten wurden 140.000 Lösungen berechnet, was pro Minute in etwa 47 Lösungen ergibt. Gehe ich nun davon aus, dass meine berechneten 12 * 10^15 Lösungen existieren, bräuchte mein Computer schlappe 500 Millionen Jahre und für die Movedatei 18 Exabyte (16,76 Milliarden Gigabyte), welche ich leider nicht habe.
 
Zu diesem Zeitpunkt habe ich mich gefreut, dass ich nicht mit 45 Feldern weiter gerechnet habe. Daher lege ich das Projekt solange auf Eis, bis mein Computer eine Milliarde Mal schneller ist...



Copyright:

Copyright © 2002-2017 Dominique Petersen
Die Programme zum Lösen des Solitaire-Problems sowie die Lösungen selber dürfen unter Berücksichtigung des Copyrights durch den Autor und einem Vermerk auf diesen kopiert und vervielfältigt werden.


Dominique Petersen [email@dominique-petersen.com], 2012/12/30 @ 22:00
Rechtlicher Hinweis: Haftungsausschluss / Disclaimer
document:   show source,   print,   sitemap,   tell a friend,   goto top
script rendered in 1.0999009609222412 seconds