Morpion solitaire

                                                                                                                                                                                        page 1/2
(jeu de grille)

Pour un premier synopsis du problème voir l'article de wkipedia sur le sujet :

Nous ne considérons que la version touching model du jeu où les segments dans la même direction peuvent avoir un point extrême commun. Dans leur article [1] "Morpion Solitaire" Theory of Computing Systems, volume 39, number 3, June 2006, pages 439-453. Special issue of selected papers from the 3rd International Conference on Fun with Algorithms, 2004. ici accessible (au format ps et au format pdf icone pdf ) Erik D. Demaine, Martin L. Demaine, Arthur Langerman, Stefan Langerman étudient le cas général pour un set S d'épaiseur k=1,2,3 k>=4. Il est alors utile de définir une fonction potentiel phi(D) qui somme l'ensemble des slots libres de chaque point (dans les 8 directions) au cours du jeu. Pour k=1 et k=2 les grilles s'auto-engendrent à l'infini . Pour le cas de la "croix de Malte" d'épaiseur k=3 on peut démontrer que le nombre maximum de points possibles est plus petit ou égal à 192 (et plus grand que 56). Pour le cas k=4 , (qui est le jeu de grille original- set S de 36 points),qui est en fait un cas où un mouvement conserve le potentiel phi(D) = 288 (=8*36) inchangé, des considérations combinatoires et d'accroissement périphérique géométrique du set de points (du graphe) démontrent que le maximun de points que l'on peut atteindre est inférieur ou égal à 704 points possibles. Une solution (un record) de 170 coups a été décrite par JB Bonté et publiée en 1982, elle n'a jamais été surpassée depuis lors (le nombre de coups possibles est alors plus grand ou égal à ce nombre de 170). Pour k>=5 la progression de la grille s'eteint après 12 mouvements.

P.S.(au 10/2008)
- 1. Les jeux pour k=3 (i.e. jeux référencés 4T et 4D) sont maintenant résolus : Leurs scores maximum sont de 62 (4T) et 35 coups (4D)
- 2. Il existe une antériorité dans le record de 170 coups !! : Avril 1976: publication dans Science & Vie d'une grille de Morpion Solitaire
      faite par Charles-Henri Bruneau, sans aucun ordinateur. Avec ses 170 coups , c'est toujours aujourd'hui le record.

Pour tout savoir et faire le point sur l'état actuel de la recherche sur ce sujet, il faut consulter le beau site fédérateur de Christian Boyer dedié à ce jeu :

http://www.morpionsolitaire.com de Christian Boyer

Solution de JB BONTE (1982)
solution de JB Bonte 170 crois

Algorithmique

Pour k>=3, les auteurs[1] montrent que le problème est NP-hard (Nondeterministic Polynomial-time hard) .
Pour diminuer la complexité du problème, les auteurs proposent de caractériser des "fils", propageant par réaction en chaîne la possibilité d'ajouter des points et ainsi d'étendre le graphe.


Mon Programme de recherche

Ce programme :   cps_autogrille_continuous.c   est écrit en C :
(partie ACTUALISÉE)
Il effectue une recherche en choisisant aléatoirement un mouvement parmi tous ceux possibles à chaque étape du jeu, la grille en cours étant complète quand il n'y a plus de possibilités de jouer (i.e. placer une croix). Le programme teste à chaque exécution 500000 grilles (paramètre du source) pour éviter une inflation de la mémoire (que je n'ai pas pu résoudre) ; et stocke la grille comportant le maximum de nombre de croix à tout instant du run dans le fichier : Fichier_Grille.dat exploitable avec la procédure IDL :   grille_potentielle.pro   lancée par le shell vois ou avec la procédure Runtime IDL (compilée) : rt_grille_potentielle.sav lancée par le shell vois.rt ; qui génèrent toutes deux un fichier postscript : autogrille.ps de la grille obtenue. Un fichier log : rapport_grille.txt est aussi généré, il fournit la trace de l'exécution du programme : nombre de grilles testées et obtention de la grille maximale des grilles déjà testées. Une variante pour une recherche "en continue" par un process permanent a été développée (11/2007).  C'est elle que l'on utilisera dès lors.
Elle met à jour automatiquement en background du run; toutes les 50000 grilles (paramètre du source) par des appels système et des runtime IDL, les statistiques (distribution) et les résultats dès que ceux-ci sont obtenus par le calcul et sont édités : résultats visualisables ici (en page 2/2) du WEB dédié.

Le développement actuel (08/2008) du programme de recherche automatique des Grilles   cps_autogrille_continuous.c   et son environnement :

  • - intégre la correction d'une erreur de type probabiliste dans le programme précédent.
  • - Il intégre aussi la variante pour une recherche "en continue" par un process permanent qui a été développée (cf. partie historique).
  • - Il intégre des statistiques : distributions du rang des Grilles (par le nombre maximun de noeuds atteint) brutes et normalisées.
Le lancement de la recherche s'exécute en batch à l'aide du shell auto_launch & . Un autre shell (tcsh) "infini" :   clmail   teste toutes les heures si la grille optimale sous sa forme "fichier" (Fichier_Grille.dat) a été mise à jour et dans ce cas envoie des mails pour avertir de la découverte d'une nouvelle grille optimale puis s'endort (se met en mode sleep). Ce shell(tcsh) est lancé actuelement (10/2008) sur une machine différente de celle du process auto_launch pour des raisons factuelles système (deamon mail).
(partie HISTORIQUE)
Il effectue une recherche en choisisant aléatoirement un mouvement parmi tous ceux possibles à chaque étape du jeux , la grille en cours étant complète quand il n'y a plus de possibilités de jouer (i.e. placer une croix). Le programme teste à chaque exécution 1 million de grilles et stocke la grille comportant le maximum de nombre de croix à tout instant du run dans le fichier : Fichier_Grille.dat exploitable avec la procédure IDL :   grille_potentielle.pro   lancée par le shell vois ou avec la procédure Runtime IDL (compilée) : rt_grille_potentielle.sav lancée par le shell vois.rt ; qui génèrent toutes deux un fichier postscript : autogrille.ps de la grille obtenue. Un fichier log : rapport_grille.txt est aussi généré, il fournit la trace de l'exécution du programme : nombre de grilles testées et obtention de la grille maximale des grilles déjà testées. Une variante pour une recherche "en continue" par un process permanent a été développée (11/2007).  C'est elle que l'on utilisera dès lors. Cette variante :   autogrille_continuous.c   s'exécute en batch à l'aide du shell auto-lanceur : auto_launch &

Résultats obtenus avec le programme

-Sur 85 millions de grilles testées (03/07/2007) le meilleur score obtenu est une grille de 96 croix
-Sur 11 millions de grilles testées (11/12/2007) "en continue" le meilleur score obtenu est une grille de 97 croix
-Sur 69 millions de grilles testées (16/01/2008) "en continue" le meilleur score obtenu est une grille de 102 croix :
  le fichier log (rapport_grille.txt)


                  Meilleure Grille obtenue nb=102 croix :

Numérotation non-standard (maintenant corrigé)
meilleur grille obtenue : nb=102


Sommaire
page precedente home page page suivante