Morpion Solitaire - Grilles Records (jeu 5D)

21 août 2010 : nouveau record 5D avec une grille de 82 coups par Christopher D. Rosin, USA, seulement 5 jours après son record 5T !!! Deux coups de plus que le record 5D précédent par Tristan Cazenave. Chris Rosin a obtenu son résultat après seulement une heure de calcul, en réutilisant le même logiciel qui avait produit son record 5T. Un algorithme et un logiciel très puissants !

Voir sa grille ci-dessous ou voir le fichier GIF animé (2,1Mo, créé par C. Rosin) montrant la partie, coup par coup.


Août 2010 : Grille de 82 coups obtenue par ordinateur par Chris Rosin (cliquer sur l'image pour l'agrandir)

En mai 2011, Chris Rosin a annoncé que la nouvelle version améliorée de son programme, capable de produite un nouveau record 5T, a hélas été incapable de produire un nouveau record 5D. Toutefois, bons résultats puisqu'après 82 exécutions de son application, une heure pour chaque exécution, 25 d'entres elles ont produit des grilles de 82 coups, ce qui égale 25 fois son précédent record !

Voici 19 grilles, Chris n'a pas d'image des 6 grilles manquantes. Après rotations/symétries, j'ai orienté ces grilles dans la même direction que son premier record de 2010, on peut mieux voir qu'elles sont extrêmement proches. Voir la présentation Powerpoint (2,1Mo), ou son fichier PDF (2,3Mo) équivalent. Quasiment les mêmes, incluant le même étrange "trou" dans la croix grecque. Ce que je pensais plus bas sur la grille de 80 coups de Cazenave était faux : finalement pas si rare d'avoir un trou dans une bonne grille...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Mai 2011 : Nouvelles grilles de 82 coups , comparées à la grille de 2010 (cliquer sur les images pour les agrandir)

Deux grilles de 82 coups ont été trouvées en 2012 par Tristan Cazenave grâce à son nouvel algorithme Monte-Carlo nommé recherche "Beam" (en faisceau). Il a aussi, et séparément, réutilisé l'algorithme "NRPA" (Nested Rollout Policy Adaptation ~ apprentissage de politique de parties aléatoires imbriquées), algorithme de Chris Rosin inspiré par ses travaux de 2009, mais amélioré avec cette recherche en faisceau : il n'a pas obtenu de meilleur score, mais cet algorithme amélioré est intéressant pour le problème du voyageur de commerce avec fenêtre de temps, une très difficile version du vieux problème classique du voyageur de commerce. Voir les articles publiés de 2009 à 2012 par Chris Rosin, et par Tristan Cazenave (et Fabien Teytaud).


2012: Deux grilles de 82 coups par Tristan Cazenave.
Pour une meilleure comparaison, les grilles sont ici orientées après rotations/symétries dans la même direction que celles de Rosin.
La première est la même que la 82e de Rosin, et la seconde est très proche des 82d et 82i de Rosin.

Tristan Cazenave (Paris 1968 - ) en 2008

Avant 82 coups, le précédent record était une grille de 80 coups par Tristan Cazenave, obtenue par ordinateur le 1er février 2008. Tristan Cazenave, un spécialiste bien connu du jeu de Go, avait déjà écrit des articles sur le Morpion Solitaire et avait déjà été le tenant du record avec ses grilles de 76 et 78 coups. Il était professeur assistant au LIASD (Laboratoire d'Informatique Avancée de Saint-Denis, Université de Paris 8), http://www.ai.univ-paris8.fr

3 novembre 2008 : une autre grille de 80 coups trouvée par Tristan Cazenave. Il est maintenant professeur au LAMSADE (Laboratoire d'Analyse et Modélisation de Systèmes pour l'Aide à la Décision, Université de Paris-Dauphine). Sa page web est http://www.lamsade.dauphine.fr/~cazenave


 2008 (février à gauche, novembre à droite) : Grilles de 80 coups obtenues par ordinateur par Tristan Cazenave

Mon sentiment personnel est que les records ci-dessus de Cazenave peuvent encore être améliorés. Regardez les potentialités non exploitées de la grille de novembre 2008 : alignements 20-24-26, 38-32-41, 75-67-65 et 77-70-66. Et regardez celles du coin sud-ouest de la grille de février 2008 : alignements 71-76-73, 63-70-79 et 72-68-75. Laisser autant de potentialités inutilisées dans une zone si restreinte offre généralement, après de légères modifications dans les coups, une meilleure solution. Et rare de voir une grille record avec un trou, ici à gauche du coup 18. Mais après mes propres essais, je ne suis pas capable d'améliorer cette grille. J'ai réussi à utiliser sa potentialité 63-70-79 ajoutant donc un coup dans le coin sud-ouest... mais seulement si je supprime un coup dans le coin opposé nord-est. 80 + 1 - 1 = à nouveau 80 coups...

Zbigniew Galias, Pologne, a calculé fin février 2010 que les 47 derniers coups des deux grilles de Cazenave sont optimum.


Février 2008 : Une autre grille de 80 coups par Christian Boyer, après quelques modifications de la grille de Cazenave

Le précédent record a été obtenu 8 mois auparavant, également par ordinateur, par l'équipe finlandaise Heikki Hyyrö et Timo Poranen, University of Tampere. Ils ont utilisé un algorithme de "recuit simulé" ("simulated annealing") décrit dans leur article "New Heuristics for Morpion Solitaire". Pour ce type d'algorithme, voir http://en.wikipedia.org/wiki/Simulated_annealing ou http://mathworld.wolfram.com/SimulatedAnnealing.html.

Juin 2007 : Grille de 79 coups obtenue par ordinateur par Heikki Hyyrö et Timo Poranen

Dans son article "Reflexive Monte-Carlo Search" au CGW 2007 (Computer Games Workshop), Tristan Cazenave a publié cette grille de 78 coups.

Mai 2007 : Grille de 78 coups  obtenue par ordinateur par Tristan Cazenave

Pour les précédents records du jeu 5D, voir la page http://slef.org/jeu de Stefan Langerman. Certains anciens records avaient été obtenus à la main, sans ordinateur.

Analysant par ordinateur les grilles symétriques, Michael Quist, USA, a trouvé cette grille de 68 coups. Il pense que cela devrait être le score maximum de toutes les grilles 5D symétriques (symétriques par rapport au centre comme celui-ci, mais aussi diagonalement symétriques, horizontalement symétriques, rotation de 90°, ...)


Avril 2008 : Grille symétrique de 68 coups obtenur par ordinateur par Michael Quist

© Christian Boyer, www.morpionsolitaire.com