PUB

MORPION SOLITAIRE MS1 

Le compagnon de ceux qui s'embêtent en cours , pas à se gratter les c..., mais à remplir des feuilles quadrillées de petites croix . Toujours plus loin,  à celui qui en fera le plus. Mais ce sont aussi des machines qui se sont frottées à ce jeu.. Il y a bien longtemps dans un centre de calcul du coté de Cachan, un  UNIVAC 1108 monstre de l'époque avec ses 64 Ko de mémoires de ferrite et son FORTRAN IV, en à chié des heures et des heures pour faire des millions de jeux sans pour autant  mettre fin à cette requête ...

Mais rassurez vous, élèves et étudiants de tout poil , la chasse au score maxi est encore ouverte ! La seule certitude que j'ai obtenue à cette époque c'est de faire un score de 61 dans pratiquement  80% des jeux .si vous n'êtes pas spécialiste. Vous pouvez vérifier vous même avec le micro logiciel DOS suivant  Ms1.exe   

La certitude aussi que le jeu va s'arrêter à un maximum situé vers 780. En réalité 300 est un objectif raisonnable.Le record actuel est de 170 croix.

Le maximum en 1972 était de 144, obtenu à la main par Noël CARION  un collègue qui travaille actuellement au CEA sur le fameux TERAFLOP mais sur d'autres projets un peu plus explosifs.

LIENS

 

 

SOLOMORP

UNIV-PARIS-8

EULER

CROIX2MALTE

CDC

CAML

RECREOMATH

BULTEZ

M.I.T.

PENTASOL

WILKE

 

Un peu de théorie très simplifiée:

Comment montrer simplement que le jeu est limité .

Chaque point du jeu peut s'associer à 8 directions données. On appellera ça une potentialité. Le total des potentialité au départ est 8X36 =  288. A chaque fois que vous rajoutez un point vous rajoutez 8 potentialités mais vous consommez également 8 potentialités retirées aux 5 points du segment. Une à chaque  point extrême du segment, 2 aux 3 autres soit 8 au total. Donc le jeu évolue à potentialité constante et égale à 288. (A condition de ne pas tracer de segment de 5 points sans en avoir rajouté au jeu)

Le jeu va  s'arrêter lorsque les potentialités des points sont situés sur la frontière de la figure obtenue et dirigés à l'extérieure. Tous les tracés possibles à l'intérieur étant alors  fait. Dans ce cas on montre que la potentialité totale des points de la frontière est égale à 3X(nb de points de la frontière)+8.

Soit finalement un nb de points de la frontière = (288-8)/3 ) = 92 ou 93

(J'ai les preuves, j'ai encore mes notes, une cinquantaine de pages couvertes de que j'ai du mal à comprendre ! )

J'ai repris mes notes et transcrit le début . 

 

 

Reste à trouver une figure de polygone ou l'intérieur sera maximal à un périmètre donné. Dans le cas continu c'est un disque. Vous pouvez vous amuser à prendre une chaînette de  93 maillons à placer sur une planche à clous quadrillée et compter les clous à l'intérieur.( Attention les diagonales sont plus longues que les horizontales et verticales)  UNIVAC en avait trouvé 781 ........ Mais j'ai paumé la feuille de résultats mais recomposé le début.

Vous trouverez ci-dessous divers logiciels avec des critères de choix. Ils permettent une expérimentation du jeu. Certains sont paramétrables comme speed3.exe. Comme en général il y a plusieurs cas possibles, le choix final reste aléatoire. Pour Ms13-13.exe  par exemple trouvez au moins 70 croix avec des solutions au delà de 80. Ce qui à la main n'est pas évident !  Vous pourrez vérifier au passage la formule . Avec Ki , connexité du jeu et donné par le logiciel. Par exemple si K5 = 8 cela signifie qu'il y a 8 points avec 5 traits dans le jeu. N0 nb de points de départ soit 36 et K nb de points mis au moment du jeu. On remarquera que K0 diminue rapidement et que K8 augmente. 

Vous trouverez aussi une feuille vierge 30X30  correspondant au modèle des différents logiciels. 

Ces programmes et les futurs sont sous DOS, issus du POWER BASIC compilé (le langage le plus rapide , après l'assembleur). Ils assurent une bonne vitesse d'exécution. et une taille mini. Désolé pour les inconditionnels de Windows ....Normalement ça tourne sur XP et même en fenêtre réduite sous IE

Le code source du logiciel simple aléatoire:  ms1.bas  (5Ko) S'ouvre avec le bloc note ou avec un éditeur de texte . Si vous voulez des infos sur son compilateur POWER BASIC contactez moi.

 
Cliquez sur les  pour ouvrir les fenêtres correspondantes

PROGRAMMES avec arrêt et analyse des paramètres 

Nom prgm Critères Résultats
MS1.exe Aléatoire pur Correspond à la courbe de répartition aléatoire sans maximum intéressant
Ms13-13.exe   Le point mis est le plus proche du point (8,8) si n<20 de (10,10) si 20<n<30 de (12,12) si 30<n<40 et de (13,13) si n>40 Donne de bons résultats, en général + de 60 avec un nombre de solutions énorme et un maxi à 90
MS1plusproche.exe Le point mis est le plus proche de celui d'avant Si le premier point est à l'extérieur de la croix donne les 2 jeux minimums de 21. (curieux) Si à l'intérieur donne en moyenne 60 
MS1prev.exe Donne le jeux qui a une profondeur donnée, permet un maximum de point le coup d'après si 1<pas<20. Si vous prenez pas>20 qui le nombre mini de jeux ce n'est pas sur qu'il le fasse.

 

Surtout pratique pour le jeu manuel, donne les meilleures ouvertures
     
     
     

PROGRAMMES SPEEDY automatiques. 

SPEED0.exe Idem précédent 13-13 mais en automatique. Avec ma vieille bécane je suis loin des 0,01 s/jeu d'UNIVAC. Pour ceux qui ont des machines puissantes c'est pas loin !   Sniff  pas terrible ! J'ai pas fait mieux que 82. Le maxi est atteint assez vite < à 500 jeux
SPEED1.exe Point mis le + proche de (13,13) dès le départ Maxi à 86. (4 de mieux!) Tous les autres points de la diagonale donnent de moins bons résultats !
SPEED3.exe Cherche sur un jeu de 10 par exemple celui qui laisse un maximum de possibilité. Ce maxi est atteint au bout de 250 jeux aléatoires. Il le garde et continue ainsi de suite. La valeur d'une tranche peut être entrée par la valeur du pas;       1<pas<20 ça pouvait être une bonne idée, mais j'ai pas dépassé 80 ! Pour les heureux p(r)ocesseurs de >2Gh essayez tous les pas de 5 à 50 et dites moi si c'est mieux.

 

 

Il reste encore du boulot ...

Pour visiter d'autres sites sur le sujet  utilisez la barre de recherche

Google