← Retour au blog

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.

Jouer au Same Game

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 :

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
1985Chain Shot! de Kuniaki Moribe, publié dans le mensuel ASCII (numéro de novembre), pour les ordinateurs FM-8 et FM-7 de Fujitsu
1992SameGame d'Eiji Fukumoto pour Unix, en mode texte
fin 1992Version PC-9801 de Wataru Yoshioka, diffusée sur Nifty-Serve
1994-1995BreakThru! sur PC, puis sur Saturn au Japon
2000Le jeu arrive sur la liste math-fun sous le nom de Clickomania
2001-2002Biedl, Demaine et leurs coauteurs : vider la grille est NP-complet
2008Schadd et ses coauteurs en font un banc d'essai de la recherche Monte-Carlo
2017Adler, 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)CouleursGrilles possiblesPart qu'on peut vider
3 × 3251277,3 %
4 × 4265 53686,6 %
4 × 521 048 57690,6 %
3 × 3319 68331,9 %
3 × 43531 44138,4 %
3 × 34262 14411,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 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

À lire aussi

← Retour au blog Jouer au Same Game
Nouveautés 1/6
Voir tous nos défis du jour
Tu aimeras aussi
Voir tous les jeux →