Morpion Solitaire - Grilles Records (jeux 4T et 4D)

Morpion Solitaire - Grilles Records (jeux 4T et 4D)

Mars-avril 2008: les jeux 4T et 4D sont résolus ! Grâce à l'énumération de Michael Quist, on sait maintenant que les records 4T et 4D de Heikki Hyyrö et Timo Poranen, qui ont été les premiers à trouver des grilles de 62 et 35 coups, ne seront JAMAIS battus ! Aucune partie 4T ne pourra jamais atteindre 63 coups, et il existe 12 différentes grilles records possibles de 62 coups. Voici ces grilles records, qui ont exactement les mêmes points, seulement leurs lignes sont légèrement différentes. La grille Hyyrö-Poranen est la quatrième :

Mars-avril 2008: les 12 différentes grilles records 4T de 62 coups par Michael Quist. Les différences étant subtiles, cliquer sur les images pour les comparer.

De même, aucune partie 4D ne pourra jamais atteindre 36 coups, et il existe 4 différentes grilles records possibles de 35 coups. La grille Hyyrö-Poranen est la première :

Mars-avril 2008: les 4 différentes grilles records 4D de 35 coups par Michael Quist. Les différences étant subtiles, cliquer sur les images pour les comparer.

Heikki Hyyrö (1976 - ) et Timo Poranen (Tampere 1974 - )

Les deux records de 62 et 35 coups ont été trouvés en octobre 2007 par Heikki Hyyrö et Timo Poranen, Department of Computer Sciences, University of Tampere, Finlande. Il ont donnés ces grilles dans leur article "New Heuristics for Morpion Solitaire". Leurs pages web sont http://www.cs.uta.fi/~helmu/index_e.html et http://www.cs.uta.fi/~tp

Octobre 2007 : Grilles de 62 et 35 coups obtenues par ordinateur par Heikki Hyyrö et Timo Poranen

Il semble que la première étude des jeux 4T et 4D a démarré bien plus tard que les jeux 5T et 5D : c'était avec Erik D. Demaine, Martin L. Demaine (tous deux du MIT, USA), Arthur Langerman et Stefan Langerman (Université de Bruxelles, Belgique) et ces grilles de 56 et 31 coups de leur article "Morpion Solitaire" initialement publiées en 2004, et à nouveau dans la version améliorée de leur article en 2006.

Mai 2004 : Grilles de 56 et 31 coups par Erik D. Demaine, Martin L. Demaine, Arthur Langerman, et Stefan Langerman.
Dans leur article "Morpion Solitaire", Theory of Computing Systems, vol. 39 (2006), ces grilles sont les figures 6 et 5, page 445.

Ces grilles de 60 et 34 coups faites à la main ont une très jolie propriété : elles sont symétriques par rapport au centre. Meilleures que les grilles Demaine et co, et seulement (et respectivement) deux coups en moins et un coup en moins que les records.

Janvier 2008 : Grilles de 60 et 34 coups par Christian Boyer. Observez la symétrie par rapport au centre.

Après son énumeration, Michael Quist a confirmé que ce score de 34 coups est maximal pour les grilles avec symétrie d'inversion au jeu 4D, et qu'il y a exactement 33 grilles maximales distinctes avec cette symétrie. Et Michael a aussi confirmé que 60 coups est maximal pour les grilles avec symétrie d'inversion au jeu 4T, et qu'il y a 5 grilles maximales distinctes avec cette symétrie.