• About
    • About
    • News
  • STM Publishing
  • Healthcare
  • Careers
Home > News > Morpion solitaire: nouveau record en 178 coups

News

Morpion solitaire: nouveau record en 178 coups

July 22, 2011

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.

Get More Information

  • This field is for validation purposes and should be left unchanged.

Contact

Corporate Headquarters
6160 Lusk Boulevard, Suite C205
San Diego, CA 92121
+1 (858) 535-0516
info@paritycomputing.com

© 2021 Parity Computing. All rights reserved. Privacy Policy.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Cookie settingsACCEPT
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these cookies, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may have an effect on your browsing experience.
Necessary
Always Enabled

Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.

Non-necessary

Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.

SAVE & ACCEPT