Au FreeCell, toutes les cartes sont visibles : c’est un jeu bien adapté à la recherche de solutions par ordinateur. Voyons simplement comment un ordinateur résout le FreeCell. Pour cette page, nous avons écrit un programme qui suit les mêmes règles que l’app FreeCell, et nous l’avons essayé.
La recherche : jouer des coups et regarder ce qui suit
Un ordinateur examine, comme nous, « que se passe-t-il si je joue ce coup ? ». La différence est le nombre de coups examinés.
- Écrire tous les coups possibles dans la position actuelle (poser sur une case libre, empiler dans les colonnes, monter à la fondation, etc.).
- Jouer l’un des coups pour obtenir une nouvelle position.
- Dans cette position, écrire à nouveau tous les coups possibles.
- Quand on trouve une position où les 52 cartes sont montées aux fondations, la suite de coups jusque-là est la solution.
Passer ainsi de position en position, en se ramifiant, s’appelle la recherche.
Astuce 1 : ne pas examiner deux fois la même position
Au FreeCell, en jouant dans un ordre différent, on arrive souvent à la même position. Si l’on déplace une carte vers la droite puis qu’on la ramène à gauche, on retrouve la position de départ. En gardant en mémoire les positions déjà examinées et en ignorant celles qui reviennent, on évite beaucoup de travail inutile.
De plus, les positions qui ne diffèrent que par l’ordre des colonnes, ou par l’ordre des cartes dans les cases libres, se résolvent de la même façon. En les traitant comme une seule position, on réduit encore le nombre de positions à examiner.
Astuce 2 : explorer d’abord les positions prometteuses
Examiner toutes les positions l’une après l’autre prendrait trop de temps. On donne donc des points, par exemple « beaucoup de cartes montées aux fondations », « peu de cartes sur la prochaine carte à monter », « des cases libres vides », et l’on explore d’abord les positions les plus prometteuses.
En lui faisant résoudre la donne n° 1 du FreeCell de Windows, le programme de cette page a trouvé une solution en 110 coups après avoir examiné 843 positions. Ce qui serait pénible pour une personne est instantané pour un ordinateur. La solution trouvée n’est pas forcément la plus courte (Le nombre de coups et la victoire).
Prouver qu’une donne est impossible
Si l’on trouve une solution, la donne est gagnable. Mais comment vérifier qu’elle est « impossible » ?
La réponse : explorer toutes les positions atteignables. Quand, quel que soit le coup joué, plus aucune nouvelle position n’apparaît, et qu’aucune position n’avait les 52 cartes montées, on sait que la donne est impossible.
La donne n° 11982 du FreeCell de Windows est connue pour être impossible. Avec le programme de cette page aussi, même en explorant toutes les positions atteignables (environ 95 000), reprises de cartes de la fondation comprises, il n’y avait aucune solution (Presque toutes les donnes du FreeCell se gagnent).
La règle du déplacement de plusieurs cartes ne change pas ce qui est gagnable
Dans l’app FreeCell, on déplace d’un coup au plus « nombre de cases libres vides + 1 » cartes, et une colonne vide n’augmente pas ce nombre (Combien de cartes déplacer à la fois). Mais un déplacement de plusieurs cartes peut se décomposer en déplacements d’une carte à la fois, avec les cases libres et les colonnes vides. Les positions atteignables sont les mêmes : les donnes gagnables sont donc les mêmes. Seule la façon de compter les coups change.
Le contrôle des donnes de l’app FreeCell
Les donnes de l’app FreeCell sont mélangées au hasard à chaque fois. L’auteur a fait résoudre par ordinateur 100 000 donnes aléatoires, puis a rejoué chaque solution trouvée jusqu’au bout avec le même moteur de jeu que l’app. Les 100 000 donnes avaient une solution.
Cela ne prouve cependant pas que « toutes les donnes sont gagnables » : il reste possible que, parmi les donnes non vérifiées, de rares donnes soient impossibles.
La façon dont l’ordinateur raisonne peut aussi aider les joueurs. Voyez aussi Stratégie et méthode gagnante.
