|
L'exemple ci-dessus est le
départ de la solution record en 170 coups de Charles-Henri Bruneau. Si vous
vous lancer, vous penserez peut-être que la solution est simple. En effet le coup
suivant pourrait être la place libre à côté du 13; puis la place juste en
dessous- de celle-ci. Cela semble naturel.
Pourtant dépassé la centaine de coups, ça se complique notablement.
Pour connaître la suite se référer aux liens.
Ce jeu fut très en vogue dans
les années 1970. Personne n'a réussi à dépasser le record vite établi de 170
coups.
Évidemment, l'ordinateur a vite été demandé à la
rescousse. Mais le problème est coriace. Il est du type NP-difficile (prouvé en 2006).
L'ordinateur est vite arrivé
à résoudre le problème des dames, plus difficilement les échecs et encore plus
difficile pour le jeu de GO. Le morpion solitaire se situe dans ce haut de
l'échelle.
Il est établi que le maximum
de coup jamais réalisable est de 740. On conjecture qu'il est bien plus bas;
sans doute inférieur à 324.
Le record établi en 2010 à
172 coups par Christopher Rosin, informaticien
californien, utilise un programme qui combine la méthode de Monte-Carlo (production de
séquences aléatoires) et techniques
d'apprentissage (comme pour les circuits de neuroniques).
En juillet 2011, Christopher Rosin bat son propre record avec 178 coups.
|
