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
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.
pour ouvrir les fenêtres correspondantes