Grâce à un nouvel algorithme de recherche arborescente, un jeune informaticien américain a battu le record mondial du nombre de coups au morpion solitaire.

Connaissez-vous le morpion solitaire, qui a fait fureur dans les années 1970 et 1980 ? Ce jeu qui se pratique seul avec simplement un stylo et une feuille de papier quadrillé consiste à ajouter tour à tour des points à une configuration initiale en forme de croix suisse de façon à former des segments de cinq points alignés, verticalement, horizontalement ou en diagonale (voir la figure). L’informaticien américain Christopher Rosin, qui travaille chez Parity Computing à San Diego en Californie, a réussi à faire une grille à 178 coups. Il bat ainsi son précédent record (177 coups), qui datait… de trois mois seulement.

Chr. Rosin travaille sur des algorithmes de recherche arborescente, qui explorent des chemins sur un arbre représentant le déroulement des possibilités dans des jeux, des problèmes de planification ou des problèmes d’optimisation. Il a développé un algorithme amélioré où le choix de la branche à chaque ramification est fait au hasard, mais selon une loi qui est adaptée dynamiquement, c’est-à-dire qui est modifiée à mesure que l’on progresse vers les « feuilles » de l’arbre. Chr. Rosin a mis à l’épreuve son algorithme sur deux problèmes : la construction de grilles de mots croisés, et le morpion solitaire. Dans les deux cas, l’informaticien américain trouve que son algorithme a des performances meilleures que les autres. Et, en bonus, il améliore le record du nombre de coups au morpion solitaire. Il l’avait battu une première fois en 2010 avec 172 coups, soit deux coups de plus que le record de 1976. Cette année là, il y a 35 ans, l’étudiant Charles-Henri Bruneau, aujourd’hui professeur de mathématiques à l’Université de Bordeaux, avait réalisé une étonnante prouesse en faisant 170 coups, sans aucune aide informatique. Aujourd’hui, le record est en 178 coups. Qui dit mieux ?

Christopher Rosin se voit remettre un prix pour son article présenté lors de la 22ème International Joint Conference on Artificial Intelligence, qui s’est tenu à Barcelone, du 16 au 22 juillet 2011.

La configuration initiale du jeu de morpion solitaire. Il s’agit d’ajouter un point pour former un segment de 5 points consécutifs horizontalement, verticalement ou en diagonale, puis de recommencer dans le but de former le maximum de segments (ou, ce qui revient au même, d’ajouter le maximum de points).

 

 

La grille à 178 coups obtenue par Christopher Rosin. Chaque coup (ou point ajouté) est numéroté dans l’ordre chronologique.