Der Kartenmisch-Algorithmus des Windows-FreeCell-Spiels
(solitairelaboratory.com)FreeCell unter Windows, das viele von Ihnen wahrscheinlich schon gespielt haben, ordnet die Karten zufällig an, und jede Kartenanordnung hat eine zugeordnete Nummer. Wenn man dieselbe Nummer auswählt, wird die Kartenanordnung identisch erzeugt.
Bis vor Windows 2000 gab es die Nummern 1 bis 32.000, ab XP wurde das auf 1.000.000 erweitert.
Der Algorithmus, der beim Eingeben einer Nummer die Kartenanordnung erzeugt, ist veröffentlicht und wird auch in anderen FreeCell-Programmen verwendet.
Dieser Algorithmus wurde in kurzem C-Code implementiert und hängt von den von MS-Compilern implementierten Funktionen rand() und srand() ab.
8 Kommentare
Tag-Bruder, Sie spielen wirklich gut.
Der eigentliche Zufallszahlengenerator verwendet eine Rekursionsformel, die eine Folge von Pseudozufallszahlen erzeugt, die zwar zufällig aussieht, es in Wirklichkeit aber nicht ist. Jede Implementierung von
rand()funktioniert etwas anders, aber dass bei gleichem ersten Seed auch die danach folgende Folge von Zufallszahlen identisch ist, ist eine Eigenschaft, die fast allen Algorithmen gemeinsam ist. Wenn also der Kartenmischalgorithmus deterministisch ist, dann wird letztlich jede Kartenanordnung durch den Seed deterministisch festgelegt.Das weicht zwar leicht vom Thema ab, aber wie stark sich Pseudozufallszahlen erzeugen lassen, die wirklich zufällig wirken, ist ebenfalls seit Langem ein Forschungsthema. Auch in TAOCP Vol.2 wird das kurz behandelt.
Tatsächlich gibt es im Computer kein echtes Zufallskonzept.
Deshalb misst man üblicherweise menschliches Verhalten im Millisekundenbereich und verwendet das als Zufalls-Seed.
Ich dachte, dass der Zufallswert den aktuellen Zeitstempel verwendet, aber da lag ich wohl falsch, haha. Danke fürs Teilen.
Beim Initialisieren verwendet man als Seed oft die Zeit. Die Zeit ändert sich ja ständig.
Zur Referenz: In der Windows-Hilfe steht: „Es ist nicht bewiesen, aber für alle hier gespielten Partien gibt es eine Lösung.“ Verschiedenen Versuchen zufolge gilt jedoch Spiel Nr. 11982 bis heute als nicht lösbar.
Auch jenseits von Nr. 32.000 gibt es Kartenanordnungen, die als nicht lösbar gelten, darunter die Nummern 146692, 186216, 455889, 495505, 512118, 517776 und 781948.
Wie hat man nur herausgefunden, dass man sich das notieren und trotzdem nicht lösen kann? Ganz schön hartgesottene Leute!
Unheimliche Leute ...!