D'où vient le Same Game ? De Chain Shot! (1985) aux chercheurs en IA
Le Same Game a porté beaucoup de noms : Chain Shot!, SameGame, Clickomania, Jawbreaker, Same GNOME, KSame... Derrière ces étiquettes, c'est presque toujours la même règle : on retire un groupe de blocs de même couleur, ceux du dessus tombent, les colonnes vides se resserrent. Cette règle a une date de naissance et un auteur connus, au Japon, en 1985. Elle a ensuite circulé de micro-ordinateur en micro-ordinateur, souvent sans le nom de son inventeur, au point qu'en 2001 des mathématiciens qui l'étudiaient écrivaient que ses origines semblaient inconnues. Voici ce parcours, puis ce que la recherche en a fait.
1985 : une règle trouvée à force d'en retirer
L'inventeur s'appelle Kuniaki Moribe, surnommé « Morisuke ». En 2003, il a raconté sur son site personnel comment le jeu est né. Il n'a pas appris la programmation à l'université : il la découvre au travail, dans une entreprise industrielle, d'abord en préparant les données de machines-outils à commande numérique, puis en BASIC quand on y installe un ordinateur FM-8 de Fujitsu. Il s'achète ensuite un FM-7, que Fujitsu vend à un prix très bas pour l'époque, et passe ses samedis soir à écrire des jeux. Un premier programme est publié dans le magazine Micom BASIC Magazine ; il ose ensuite envoyer trois programmes au mensuel ASCII (Gekkan ASCII), qui les publie tous les trois. L'un d'eux s'appelle Chain Shot!.
Le détail le plus intéressant de son récit concerne la règle elle-même. Selon Moribe, la première version qui tourna sur son écran avait des règles extrêmement compliquées, peu claires, et n'était pas amusante. Il dit avoir ensuite essayé plus de dix variantes de règles et de calcul des points, en jouant lui-même pour juger chacune, avant de retenir celle qu'il publia. La règle épurée que tu connais est donc le résultat d'un tri, pas une idée tombée toute faite.
Le numéro d'ASCII qui la publie est celui de novembre 1985 : c'est la date que donnent les articles de recherche qui citent le jeu, et elle concorde avec le récit de Moribe, qui situe une reprise commerciale de 1995 « exactement dix ans » après la parution dans ASCII.
1992 : SameGame, puis « Samegame » sur PC-9801
Le nom actuel arrive sept ans plus tard. D'après l'historique tenu par l'auteur de MaciGame, une version Macintosh du jeu, Eiji Fukumoto écrit en 1992, sous l'influence de Chain Shot!, un jeu appelé SameGame pour les stations Unix, en mode texte (les blocs sont des caractères). L'équipe de recherche de Maastricht citée plus bas donne elle aussi Fukumoto et 1992.
Fin 1992, toujours selon cet historique, Wataru Yoshioka joue à la version de Fukumoto et l'adapte au PC-9801 de NEC, l'ordinateur personnel le plus répandu au Japon à l'époque, avec de vrais graphismes et un jeu à la souris. Diffusé gratuitement sur le service télématique Nifty-Serve, il devient très populaire. Moribe raconte la même chose de son côté : un logiciel gratuit pour PC-9800 intitulé « SAME GAME », publié sur NiftyServe, connaît un succès immédiat. Les Japonais l'écrivent さめがめ (samegame). Il engendre à son tour des variantes aux noms en écho, citées par l'auteur de MaciGame : TumeGame, KomeGame, MameGame, DebaGame.
Hors du Japon : un jeu sans auteur
En traversant les frontières, le jeu perd le nom de son inventeur. Il réapparaît ailleurs sous d'autres titres, par exemple :
- Clickomania!, logiciel gratuit pour Windows écrit par Matthias Schüssler, avec des versions Macintosh, Java et Palm Pilot ;
- BreakThru!, sorti sur PC en 1994 puis sur Saturn au Japon en 1995, dont la boîte affichait le nom et le visage du créateur de Tetris, Alexeï Pajitnov, qui l'a recommandé sans en être l'auteur. Moribe y reconnaît la règle de Chain Shot! et écrit qu'il n'a appris l'existence de ce jeu qu'après sa sortie ;
- Jawbreaker, installé avec Windows Mobile, le système des assistants personnels Pocket PC de Microsoft ;
- Same GNOME, dans les jeux du bureau libre GNOME, aujourd'hui rebaptisé Swell Foop (sa documentation précise « previously known as Same GNOME ») ;
- KSame, dans les jeux du bureau KDE, repris fin 2010 comme mode d'un autre jeu, Klickety, appelé à le remplacer.
Résultat : quand le mathématicien Erik Demaine et ses collègues découvrent le jeu, c'est par un courriel de Bernie Cosell envoyé le 2 juin 2000 à la liste de discussion math-fun, sous le nom de Clickomania. C'est un autre membre de la liste, Michael Kleber, qui leur signale qu'il existe aussi sous le nom de « Same Game ». Et leur article écrit tranquillement : « The origins of Clickomania seem unknown » (les origines de Clickomania semblent inconnues). Seize ans après Chain Shot!, le lien avec Moribe s'était perdu de ce côté du monde.
| Année | Étape |
|---|---|
| 1985 | Chain Shot! de Kuniaki Moribe, publié dans le mensuel ASCII (numéro de novembre), pour les ordinateurs FM-8 et FM-7 de Fujitsu |
| 1992 | SameGame d'Eiji Fukumoto pour Unix, en mode texte |
| fin 1992 | Version PC-9801 de Wataru Yoshioka, diffusée sur Nifty-Serve |
| 1994-1995 | BreakThru! sur PC, puis sur Saturn au Japon |
| 2000 | Le jeu arrive sur la liste math-fun sous le nom de Clickomania |
| 2001-2002 | Biedl, Demaine et leurs coauteurs : vider la grille est NP-complet |
| 2008 | Schadd et ses coauteurs en font un banc d'essai de la recherche Monte-Carlo |
| 2017 | Adler, Demaine et leurs coauteurs : NP-complet même avec deux couleurs et deux colonnes |
Peut-on vider la grille ? Quinze ans pour finir la réponse
Comme l'explique notre article sur le barème, l'article de Therese Biedl, Erik Demaine, Martin Demaine, Rudolf Fleischer, Lars Jacobsen et Ian Munro, diffusé en 2001 et publié en 2002 dans le recueil More Games of No Chance, montre que savoir si une grille peut être entièrement vidée est un problème NP-complet, dès deux colonnes et cinq couleurs, ou cinq colonnes et trois couleurs. Deux points de cet article méritent qu'on s'y arrête.
D'abord, le cas facile est traité de façon élégante. Avec une seule colonne, les auteurs ramènent le jeu à la reconnaissance d'un langage par une grammaire, comme celles qui servent à analyser les langages de programmation : la question se règle alors en temps polynomial quel que soit le nombre de couleurs, et en temps linéaire avec deux couleurs.
Ensuite, l'article laissait une question ouverte : que se passe-t-il avec deux couleurs seulement ? La réponse est venue d'Aviv Adler, Erik Demaine, Adam Hesterberg, Quanquan Liu et Mikhail Rudoy, dans un article publié en 2017 dont le titre résume le résultat : « Clickomania is Hard, Even with Two Colors and Columns ». Même avec deux couleurs et deux colonnes, le problème est NP-complet. Les auteurs notent que ce résultat est le meilleur possible, puisqu'une seule couleur se règle en un clic et qu'une seule colonne est facile, et qu'il clôt une quête commencée quinze ans plus tôt.
Pour te faire une idée concrète, nous avons énuméré toutes les petites grilles possibles et cherché, pour chacune, s'il existe une suite de clics qui la vide, avec les règles exactes du jeu du site :
| Grille (lignes × colonnes) | Couleurs | Grilles possibles | Part qu'on peut vider |
|---|---|---|---|
| 3 × 3 | 2 | 512 | 77,3 % |
| 4 × 4 | 2 | 65 536 | 86,6 % |
| 4 × 5 | 2 | 1 048 576 | 90,6 % |
| 3 × 3 | 3 | 19 683 | 31,9 % |
| 3 × 4 | 3 | 531 441 | 38,4 % |
| 3 × 3 | 4 | 262 144 | 11,7 % |
L'exemple le plus simple de grille impossible est un damier de deux sur deux : aucun bloc n'a de voisin de sa couleur, on ne peut même pas commencer. Mais ces chiffres valent pour des grilles minuscules et ne se transposent pas aux vraies parties. Surtout, la méthode ne passe pas à l'échelle : la grille Facile du site, 9 × 9 avec 3 couleurs, admet plus de 1038 remplissages différents (381), et pour chacun l'arbre des parties possibles est immense. C'est exactement ce que dit la NP-complétude : on ne connaît pas de méthode générale qui évite, dans le pire des cas, une explosion de ce genre.
Un banc d'essai pour l'intelligence artificielle
Puisqu'on ne sait pas trouver la meilleure partie à coup sûr, le Same Game est devenu un terrain d'entraînement pour les méthodes de recherche. En 2008, Maarten Schadd, Mark Winands, Jaap van den Herik, Guillaume Chaslot et Jos Uiterwijk, de l'université de Maastricht, présentent à la conférence Computers and Games de Pékin une adaptation aux jeux à un seul joueur de la recherche arborescente Monte-Carlo, la famille de méthodes qui réussissait alors au jeu de go. Ils la testent sur le SameGame.
Leur version de référence se joue sur une grille de 15 × 15 à 5 couleurs, qu'ils décrivent comme le standard admis. Un groupe de n blocs y rapporte (n - 2)² points, vider la grille donne 1 000 points de bonus, et les blocs restants coûtent des points. Ils estiment qu'une partie au hasard dure en moyenne 64,4 coups, avec 20,7 coups possibles en moyenne à chaque étape. Les méthodes classiques de recherche de chemin, A* et IDA*, échouent faute d'une bonne façon d'estimer une position : sur 20 grilles de test, IDA* totalise 22 354 points, un niveau que les auteurs comparent à celui d'un joueur débutant.
Leur programme, SP-MCTS, joue des milliers de fins de partie au hasard depuis chaque position et concentre ses efforts sur les coups les plus prometteurs. Sur la même série de 20 grilles, avec 2 à 3 heures de calcul par grille, il obtient 73 998 points, contre 72 816 pour le meilleur programme connu jusque-là, écrit par D. Billings à l'université de l'Alberta. Il vide entièrement les 20 grilles.
Un détail fait écho à nos propres essais. Pour rendre leurs parties au hasard moins naïves, les chercheurs ont mis au point une règle qu'ils appellent « TabuColorRandom » : on repère la couleur la plus fréquente et on s'interdit d'y toucher tant qu'il reste d'autres coups. C'est, à peu de chose près, la méthode de la couleur réservée que nous avons testée dans l'article sur le barème. Dans leurs essais, elle augmente d'environ 50 % le score moyen des parties au hasard.
Le jeu est resté un banc d'essai après eux : en 2009, Tristan Cazenave présente à la conférence IJCAI la « recherche Monte-Carlo imbriquée » et l'applique à trois jeux, dont le SameGame.
Ce qu'il faut retenir, et le lien avec le jeu du site
- Le Same Game est né en 1985 sous le nom de Chain Shot!, inventé par Kuniaki Moribe et publié dans le mensuel japonais ASCII, après plus de dix versions de règles écartées.
- Le nom SameGame vient de la version Unix d'Eiji Fukumoto (1992), popularisée au Japon par une version PC-9801.
- Savoir si une grille se vide est un problème NP-complet, même avec deux couleurs et deux colonnes : la dernière pièce date de 2017.
- Depuis 2008, le jeu sert de terrain d'essai à la recherche Monte-Carlo, et l'une des astuces des chercheurs revient à réserver une couleur.
Le Same Game du site suit la règle de Chain Shot! et de SameGame : groupes d'au moins deux blocs qui se touchent par un côté, chute des blocs, colonnes vides resserrées vers la gauche. Il se distingue de la version des chercheurs sur trois points : trois tailles de grille (9 × 9 à 3 couleurs, 11 × 11 à 4 couleurs, 13 × 13 à 5 couleurs) au lieu du 15 × 15 à 5 couleurs, un barème de (n - 1)² au lieu de (n - 2)², si bien qu'une simple paire rapporte 1 point au lieu de 0, et aucune pénalité pour les blocs qui restent ; le bonus de 1 000 points pour une grille vidée est le même. Toutes les règles du jeu du site, avec des exemples de grilles, sont réunies dans notre guide Règles du Same Game. Pour te mesurer aux autres sur une même grille, le défi du jour propose chaque jour trois grilles identiques pour tous (un compte gratuit est nécessaire), et le classement garde les résultats. Et si tu veux simplement jouer, tout commence sur la page du jeu.
Sources
- Kuniaki Moribe, « 「CHAINSHOT」誕生まで » (La naissance de CHAINSHOT), 22 novembre 2003, site personnel, copie archivée : web.archive.org.
- « Original history of MaciGame », site de l'auteur de MaciGame, copie archivée : web.archive.org.
- T. C. Biedl, E. D. Demaine, M. L. Demaine, R. Fleischer, L. Jacobsen, J. I. Munro, « The Complexity of Clickomania », More Games of No Chance, MSRI Publications 42, Cambridge University Press, 2002, p. 389-404 ; prépublication arXiv cs/0107031 (2001) ; texte du recueil sur library.slmath.org.
- Erik Demaine, page « Clickomania » (origine du problème, courriel de Bernie Cosell) : erikdemaine.org.
- A. Adler, E. D. Demaine, A. Hesterberg, Q. Liu, M. Rudoy, « Clickomania is Hard, Even with Two Colors and Columns », The Mathematics of Various Entertaining Subjects, vol. 2, Princeton University Press, 2017, p. 325-363 : erikdemaine.org.
- M. P. D. Schadd, M. H. M. Winands, H. J. van den Herik, G. M. J.-B. Chaslot, J. W. H. M. Uiterwijk, « Single-Player Monte-Carlo Tree Search », Computers and Games 2008, Lecture Notes in Computer Science 5131, Springer, p. 1-12 : texte des auteurs.
- T. Cazenave, « Nested Monte-Carlo Search », IJCAI 2009 : ijcai.org.
- Documentation de Swell Foop (GNOME) : help.gnome.org ; liste kde-games-devel, 31 octobre 2010 (KSame intégré à Klickety) : mail.kde.org.
- BreakThru! : Wikipédia (en) ; Jawbreaker : Wikipédia (en).