Morpion Solitaire - Grilles Records (jeu 5T)

Grilles de Rosin de 177 et 178 coups : les nouveaux records mondiaux

Christopher D. Rosin (Milwaukee, Wisconsin, USA 1971 - ) en 2009 et 2010
(2ème photo par R. Brenson, Aurora, pour Science & Vie, 2010)

12 août 2011: nouveau record avec 178 coups ! Et à nouveau de Chris Rosin, un coup de mieux que son précédent record annoncé seulement trois mois plus tôt, en utilisant une version améliorée de la méthode décrite dans son article IJCAI. Nouveau record immédiatement annoncé par le site de Pour La Science, aussi par Tangente N°143 de nov-déc 2011 (article p.44). Chris vit à San Diego, Californie depuis 1992, et est un des cofondateurs de Parity Computing où il est Chief Algorithmist. Sa page personnelle est www.chrisrosin.com

  
Août 2011 : grille de 178 coups de Chris Rosin
Juillet 2011 : Toby Walsh, Program Chair de IJCAI 2011, donnant l'award à Chris Rosin pour son article décrivant son record de 177 coups

19 mai 2011 : date de son record de 177 coups, cinq coups de mieux que son précédent record de 2010. A ce niveau, autant de coups supplémentaires est un exploit vraiment extraordinaire ! Chris indique avoir trouvé son nouveau record dès le 16 janvier 2011, mais l'a gardé secret pour cause de soumission de son article à l'IJCAI 2011, International Joint Conferences on Artificial Intelligence, Barcelone, Espagne, juillet 2011. En utilisant plusieurs microordinateurs, il a fait 28 exécutions de son programme C++, chaque exécution prenant une semaine. Deux exécutions sur les 28 ont donné deux grilles différentes de 177 coups. Sciences et Avenir a annoncé ce record dans son numéro de juillet 2011, page 23.

   
Mai 2011: grilles A et B de 177 coups de Chris Rosin
Quand réorientées, ces grilles sont proches. Voir la partie comparaison.
(cliquer sur les images pour les agrandir)

• Télécharger le fichier texte de 178 coups ou (A) de 177 coups ou (B) de 177 coups, que vous pouvez directement utiliser dans Pentasol, un logiciel Windows gratuitement téléchargeable
• Télécharger d'autres gilles de 178 coups, aussi au format Pentasol, et très proches de la grille de Rosin, à http://koozdra.wordpress.com/2013/12/21/a-collection-of-high-scoring-grids-in-pentasol-format/, où Dimitri Tishchenko, déjà auteur en 2011 de grilles de 171 et 172 coups, a réuni en décembre 2013 ses meilleurs résultats de 157 à 178 coups.

Grille de Rosin de 172 coups : le record mondial de 2010 à 2011

16 août 2010 : date du précédent record de Chris Rosin avec 172 coups. Avec sa grille obtenue avec ordinateur, il est le premier à avoir réussi à battre le vieux record de 170 coups obtenu 34 ans avant par C.-H. Bruneau sans ordinateur! Et c'est une énorme avancée avec son nouvel algorithme, le précédent record par ordinateur ayant seulement 146 coups. Cinq jours plus tard, il bat aussi le record 5D.

Août 2010: grille de 172 coups de Chris Rosin

Je remarque que le chemin de ses 172 coups est très étroit : pour les coups 132, 134, 135, 136, 144, 145, 150, 168, 170, 171 et 172, il n'y a pas d'autre choix. C'est à l'opposé du sens commun : on pourrait penser qu'un record devrait offrir plusieurs coups possibles à chaque étape. Dans la grille de Bruneau, seuls les derniers coups 169 et 170 étaient uniques. Deux fichiers intéressants détaillant la grille de Rosin :

• Voir le fichier GIF animé (7,5Mo, créé par C. Rosin) montrant la partie, coup par coup
• Télécharger le fichier texte des 172 coups, que vous pouvez directement utiliser dans Pentasol, un logiciel Windows gratuitement téléchargeable

Voici quelques détails de la recherche que Chris Rosin m'a envoyé (traduit ici en français) :

La recherche Monte-Carlo a eu quelques succès récents dans le jeu de Go (par exemple : www.lri.fr/~teytaud/mogo.html), et aussi dans d'autres domaines (incluant quelques-uns des résultats récents au Morpion Solitaire par d'autres). Les méthodes de recherche Monte-Carlo opèrent en produisant des "simulations" ("playouts") aléatoires, puis en jouant des coups qui fonctionnent bien dans ces simulations. Au Morpion Solitaire, une simulation consiste en une séquence aléatoire de coups légaux qui s'enchaînent jusqu'à ce que plus aucun coup légal ne soit possible. Un facteur important de la recherche Monte-Carlo est le choix de la stratégie de simulation, pour influer sur les choix des coups aléatoires pendant la simulation. J'ai passé plusieurs mois à développer et affiner une stratégie de simulation pour le Morpion Solitaire, en combinant quelques techniques de recherche Monte-Carlo modifiées. Cela m'a permis d'aller jusqu'à 166 au jeu 5T, mais je ne pouvais aller au-delà. Du coup j'ai alors jeté ma belle stratégie affûtée de simulation, et essayé d'appliquer des techniques d'apprentissage automatique pour apprendre des stratégies de simulation à partir de zéro. Cette idée générale a aussi été essayée au Go (D. Silver & G. Tesauro, "Monte-Carlo simulation balancing." ICML 2009). J'ai combiné cette politique d'apprentissage avec de la recherche imbriquée (quelque chose comme : T. Cazenave, "Nested Monte-Carlo Search." IJCAI 2009), et cela a réussi en produisant le résultat avec 172 lignes le 16 août 2010.

Le code a été écrit en C++. Pour la version finale, j'ai fait 10 exécutions (chacune avec un germe aléatoire différent), avec chaque exécution prenant 3 jours sur un simple coeur d'un processeur Intel 3GHz. Deux de ces exécutions ont atteint 170 (pas les mêmes que la grille de Bruneau), et une a atteint le résultat de 172 lignes.

J'ai été très heureux de publier un article sur son record dans Science & Vie, la même revue dans laquelle Pierre Berloquin avait publié le précédent record de Bruneau... 34 ans plus tôt ! Dans mon articles, des témoignages de C. Rosin, C.-H. Bruneau, P. Berloquin. Merci à eux et aussi à Hervé Poirier, le rédacteur en chef.

     
Science & Vie, novembre 2010 : publication de la grille de 172 coups de Rosin, par Christian Boyer
(cliquer sur les images pour les agrandir, ou télécharger le fichier PDF, 856Ko)

Et voici ses deux précédentes grilles de 170 coups, égalant le score obtenu en 1976 par C.-H. Bruneau (mais différentes de la grille de Bruneau) :

Les deux premières images sont les grilles de Rosin A et B de 170 coups. Je remarque que ces deux grilles sont très proches :
la troisième image C a été obtenue après rotation et symétrie de l'image B, ressemblant ainsi à l'image A

• Télécharger le fichier texte (A) des 170 coups, que vous pouvez directement utiliser dans Pentasol, un logiciel Windows gratuitement téléchargeable

Grilles de Tishchenko de 171 et 172 coups, égalant le record mondial de 2010

Dimitri Tishchenko (Gomel, Biélorussie 1982 - ) en 2011, et une de ses structures

11 avril 2011 : Dimitri Tishchenko égale le record mondial de Chris Rosin avec une grille différente de 172 coups, avant le nouveau record de Rosin de 177 coups annoncé un mois plus tard. Et construit aussi une bonne grille de 171 coups. Il utilise ce qu'il appelle un "encodage ADN" spécifique des coups. Voir sa page http://koozdra.wordpress.com avec http://koozdra.wordpress.com/2011/05/21/morpion-dna-encoding/

Dimitri Tishchenko vit à Victoria, British Columbia, Canada. Il travaille pour le Réseau canadien de renseignements sur la santé publique (CNPHI - Canadian Network for Public Health Intelligence) en tant que développeur senior d'applications internet. Il a un "bachelors degree of computer science honors program" de l'Université de Manitoba. Il aime fabriquer des structures géométriques avec des petites sphères magnétiques de néodyme, et est fasciné par la photographie. Voir www.flickr.com/photos/38565795@N05/sets/ et www.trendhunter.com/trends/dimitri-tishchenko

   
Avril 2011 : grilles de 171 et 172 coups de Dimitri Tishchenko
Quand réorientées, ces grilles sont proches. Voir la partie comparaison.

• Télécharger le fichier texte des 171 coups, et des 172 coups, que vous pouvez directement utiliser dans Pentasol, un logiciel Windows gratuitement téléchargeable

Au sujet de sa grille 172, après le coup 80, on peut remarquer qu'il y a un seul coup 81 possible ! Il est rare que ce premier coup imposé se produise aussi tôt, donc ici coup 81, on a l'impression que la partie va s'arrêter bientôt. Pour les autres bonnes grilles, ces premiers coups imposés sont 151 (Tishchenko 171), 157 (Rosin 177A), 146 (Rosin 177B), 169 (Bruneau 170), 132 (Rosin 172). Voici quelques détails sur sa recherche que Dimitri m'a envoyé :

J'ai initialement entendu parler du Morpion Solitaire par Reddit en mai 2010. J'ai travaillé sur différents algorithmes et ait été capable de générer 158 coups fin juillet. Je suis allé en vacances en Europe et quand je suis revenu, j'ai vu que Chris Rosin avait battu le record. Ca signifiait que mon meilleur résultat par ordinateur était devenu caduque. J'ai continué à travailler sur le problème, refaisant mon code d'évaluation et essayant différents types d'algorithmes pour obtenir un meilleur score. J'ai essayé différents types d'algorithmes, incluant des algorithmes génétiques, de recuit simulé, de recherche taboo et Monte Carlo. Aucune n'était plus efficace qu'un algorithme que j'ai créé basé sur une chaîne "ADN" qui représente une configuration Morpion Solitaire. En utilisant cette représentation, des modifications peuvent être faites à une configuration et encore maintenir des structures sans rapport entre elles. J'ai développé d'autres encodages mais ce n'était pas très favorable à la modification parce que les coups suivants pouvaient dépendre du coup modifié. Les autres parties de l'algorithme sont la stratégie de modification et l'évitement de pic. J'ai passé du temps à ajuster la stratégie de modification et me suis arrêté à un réglage qui, je pense, peut encore être amélioré. Le Morpion Solitaire a des pics très intéressants. Je considère un pic comme une configuration où des modifications impactent seulement un petit nombre de configurations aux scores similaires. La structure interne de la configuration s'est solidifiée. De façon intéressante, ces pics n'apparaissent pas seulement aux configurations à haut score. Du coup l'algorithme doit être capable de reconnaître ces pics et de revenir à une configuration de plus bas score où la structure interne est plus lâche et où plus de configurations peuvent être générées.

Je suis encore en train de régler différents paramètres de l'algorithme pour essayer de battre le record...

Comparaison des grilles record

(Ce paragraphe et ses fichiers téléchargeables ont été écrits avant la grille 178 de Rosin, mais tout est toujours correct. Sa nouvelle grille, ici réorientée , a encore beaucoup de similitudes avec ses précédentes grilles 177A et 177B)

Je remarque beaucoup de similitudes dans les nouvelles grilles de 2011. Afin de mieux comparer les grilles record (incluant Bruneau), je les ai toutes réorientées, en utilisant rotations et symétries, dans le même sens, grossissant dans la même direction.

Bruneau 170,    Rosin 172,    Tishchenko 171,    Rosin 177B,    Tishchenko 172,    Rosin 177A

Avec la présentation Powerpoint (618Ko), ou son fichier PDF (811Ko) équivalent, montrant clairement les similitudes et différences, on peut voir que :

• Bruneau 170 est différent des autres,
• Rosin 172 est différent des autres,
• mais Rosin 177A + Rosin 177B + Tishchenko 171 + Tishchenko 172 sont de la même “famille”, étant similaires pendant le début du jeu, une large partie basse des grilles ayant la même forme. Et Tishchenko 172 + Rosin 177A ont une ligne (mais pas la même) dépassant de la partie gauche? A la fin des jeux, partie haute des quatre grilles, les grilles sont différentes.

Tishchenko et Rosin n'ont pas collaboré, et leurs programmes sont différents. Cela signifie peut-être que leurs méthodes sont plus proches que ce que l'on pourrait penser, et/ou que leurs grilles en résultant sont maintenant proches de "la" grille optimum ?

En leur envoyant ces remarques, voilà leurs réactions, Dimitri :

Quand j'ai initialement envoyé les grilles 171 et 172, j'ai remarqué la similarité entre elles. Les deux résultats ont été créés par deux ordinateurs indépendants exécutant le même algorithme pendant un week-end. Chacun a démarré avec une grille complètement aléatoire. J'ai vraiment été surpris que les deux aient atteint un résultat si similaire.
Je pense que nos techniques sont similaires. Ma technique ADN permet des modifications dans la structure interne tout en maintenant un chemin vers la grille courante de plus haut score. Les modifications qui créent une grille de score nettement plus bas sont ignorées. La technique de Chris (telle que je la comprend) est de trouver des chemins alternés dans la structure interne qui guideront à la meilleure grille courante. Sa technique est beaucoup plus méthodique que mes modifications effectuées au hasard.

Et Chris:

Christian, ton analyse est intéressante. Chacune des grilles que je t'ai envoyé est le résultat d'une exécution indépendante de mon application, et les exécutions démarrent d'un état complètement aléatoire sans aucune forme préétablie.
La technique de Dimitri semble prometteuse et il peut y avoir des similitudes avec ce que j'utilise. Ma méthode NRPA maintient une distribution des solutions, et met à jour graduellement cette distribution pour accroître les chances de sélectionner des éléments qui font partie de la meilleure grille courante. La description de Dimitri "trouver des chemins alternés dans la structure interne qui guideront à la meilleure grille courante" est assez vraie avec NRPA.

Premières grilles 5T obtenues par ordinateur, avant Rosin

Avant la grille de 172 coups de Rosin obtenue en 2010, les ordinateurs ont été incapables d'atteindre de gros scores à ce jeu 5T et de battre le record de Bruneau obtenu en 1976 à la main. Les premières grosses grilles, 117 puis 122 coups, ont été publiées par Hugues Juillé dans ses articles de 1995 puis 1999, pour sa thèse PhD à la Brandeis University, USA. Plus tard, en janvier 2003, Pascal Zimmer a atteint 143 coups. Puis en décembre 2007, Tristan Cazenave, LIASD, Université de Paris 8, a atteint 144 coups :

Décembre 2007 : Grille de 144 coups obtenue par ordinateur par Tristan Cazenave

Haruhiko Akiyama (Tokyo, Japon 1987 - ) en 2010

Le record obtenu par ordinateur est ensuite passé à 145 coups, atteint le 4 février 2010 par Haruhiko Akiyama, un étudiant du TUAT (Tokyo University of Agriculture and Technology). En utilisant une "recherche Monte-Carlo imbriquée" modifiée (voir les deux articles de Cazenave de 2009), il a fait tourner pendant 21 jours son propre programme écrit en C sur un PC, Intel Core2Duo E8400 à 3,00GHz.

Je peux remarquer, en regardant la grille, que ce record par ordinateur peut être amélioré à la main. Par exemple (d'autres améliorations étant peut-être possibles), il est facile d'obtenir 149 coups :

• coup 23, au lieu de X-20-X-X-23, il faudrait jouer X-X-23-X-8, car il y a alors un nouveau coup possible avec 48-146-X-20-X.
• coup 18, au lieu de 5-6-18-X-10, il faudrait jouer 16-5-6-18-X (ou X-16-5-6-18), car il y a alors un second nouveau coup possible avec X-10-90-110-147.
• coup 108, au lieu de 65-108-57-107-81, il faudrait jouer 82-65-108-57-107, car il y a alors un troisième nouveau coup possible avec 107-81-99-148-147.
• renuméroter le coup 44 par un nouveau coup 32 (toujours obtenu par 32-9-X-25-26), puis au lieu de l'ancien coup 32 avec X-32-20-X-27, jouer un nouveau coup 33 avec 32(=ancien 44)-22-X-33-20, renuméroter les anciens coups 33 à 43 par des nouveaux coups 34 à 44, ne pas modifier les coups 45 à 148, et il y a alors un quatrième nouveau coup possible avec 20-X-27-51-149.

Zbigniew Galias, Pologne, a calculé fin février 2010 que les 71 derniers coups de cette grille améliorée à 149 coups sont optimum.

16 février 2010, Haruhiko Akiyama atteint 146 coups : son programme a finalement vu ma dernière remarque ci-dessus et a fini après 33 jours de calculs. A la numérotation des coups près, mes trois autres remarques s'appliquent encore et permettent d'obtenir 149 coups. Avec son professeur Yoshiyuki Kotani, il a publié un article en japonais, présentant sa grille de 145 coups (papier soumis avant sa nouvelle grille de 146 coups).

• Télécharger le fichier texte des 145 coups, et des 146 coups, que vous pouvez directement utiliser dans Pentasol, un logiciel Windows gratuitement téléchargeable

Février 2010 : Grilles de 145 et 146 coups obtenues par ordinateur par Haruhiko Akiyama

Analysant par ordinateur les grilles symétriques, Michael Quist, USA, a trouvé cette excellente et très belle grille de 136 coups, donc seulement 10 coups de moins que le record ci-dessus ! Il pense que cela devrait être le score maximum de toutes les grilles 5T symétriques (symétriques par rapport au centre comme celle-ci, mais aussi diagonalement symétriques, horizontalement symétriques, rotation de 90°, ...)

Avril 2008 : grille symétrique de 136 coups obtenue par ordinateur par Michael Quist

Jean-Jacques Sibilla, IPGP (Institut de Physique du Globe de Paris), http://www.ipgp.fr/~sibilla, effectue une intéressante recherche: depuis 2007, son ordinateur a généré deux milliards de grilles (statut en octobre 2013), où les coups sont joués au hasard. Ses principaux résultats :

extrêmement difficile d'obtenir des grilles de plus de 100 coups, sa meilleure grille ayant 102 coups
deux pics à 21 et 64 coups
impossible d'obtenir moins de 20 coups, comme mentionné dans les pires grilles possibles

Scores après 34,300,000 grilles aléatoires, calculé par Jean-Jacques Sibilla

© Christian Boyer, www.morpionsolitaire.com