L’algorithme de mélange des cartes du jeu Freecell de Windows
(solitairelaboratory.com)Freecell de Windows, auquel beaucoup ont sans doute déjà joué, dispose les cartes de manière aléatoire, et chaque disposition reçoit un numéro. En choisissant le même numéro, on obtient exactement la même disposition des cartes.
Jusqu’à Windows 2000, les numéros allaient de 1 à 32 000, mais depuis XP, ils ont été étendus jusqu’à 1 000 000.
L’algorithme qui génère une disposition de cartes à partir d’un numéro est public, et il est donc aussi utilisé par d’autres programmes Freecell.
Cet algorithme a été implémenté en un court code C et dépend des fonctions rand() et srand() telles qu’implémentées par le compilateur de Microsoft.
8 commentaires
Tag-hyung, vous êtes vraiment doué.
L’algorithme original de génération de nombres aléatoires utilise en apparence du random, mais en réalité une relation de récurrence qui produit une suite de nombres pseudo-aléatoires. Chaque implémentation de
rand()diffère, mais presque tous les algorithmes partagent une propriété commune : si le seed initial est le même, la suite de nombres générée ensuite est identique. Donc, si l’algorithme de distribution des cartes est déterministe, alors chaque disposition des cartes est elle aussi déterminée de façon déterministe par le seed.C’est un peu hors sujet, mais la question de savoir jusqu’à quel point on peut générer des nombres pseudo-aléatoires qui paraissent vraiment aléatoires a aussi été un sujet de recherche de longue date. TAOCP Vol.2 aborde aussi brièvement ce point.
En réalité, la notion de véritable hasard n’existe pas sur un ordinateur.
On utilise donc généralement le comportement humain mesuré à la milliseconde comme seed aléatoire.
Je pensais que les nombres aléatoires utilisaient l’horodatage actuel comme timestamp, mais je m’étais trompé haha. Merci pour le partage.
On utilise souvent l’heure comme
seedlors de l’initialisation. Comme le temps change en permanence.À titre indicatif, l’aide de Windows indique que « bien que cela n’ait pas été prouvé, toutes les parties jouées ici ont une solution », mais d’après les tentatives de plusieurs personnes, la donne n° 11982 est à ce jour considérée comme impossible à gagner.
Au-delà de la n° 32 000, il existe aussi des dispositions de cartes réputées impossibles à gagner, comme les n° 146692, 186216, 455889, 495505, 512118, 517776 et 781948.
Mais comment ont-ils réussi à comprendre ça sans même l’avoir noté quelque part ? Il y a vraiment des gens sacrément tenaces !
Des gens terrifiants... !