Deux jeux de fusion, une question : l'un ou l'autre peut-il se jouer sans faute ? La réponse passe par le coin d'un plateau, un adversaire qui n'arrive jamais, et un nombre haut de dix-sept exposants.
Rédigé et édité en anglais. Cette version française a été produite par traduction automatique ; en cas de doute sur un point précis, l'original anglais fait foi. Lire l'original en anglais →
Commençons par le jeu que tout le monde connaît. 2048 — quatre directions, une grille 4×4, des tuiles qui doublent au contact — est, à strictement parler, non résolu. Personne n'a écrit d'algorithme qui y joue parfaitement. Ce dont nous disposons, ce sont de très bonnes approximations. Une recherche expectimax, scrutant huit coups à l'avance environ et notant chaque plateau selon une poignée d'heuristiques réglées à la main — cellules libres, grosses tuiles plaquées contre un bord, régularité —, atteint la tuile 32768 dans plus d'un tiers de ses parties, 1 et le moteur public le plus fort touche la tuile 65536 quelques pour cent du temps. 2 Généralisé à un plateau m×n, le simple fait de décider si une tuile cible est atteignable est NP-difficile. 3 Fort n'est pas synonyme de résolu.
Jusqu'où une seule tuile peut-elle grimper ? Sur seize cases, la réponse relève d'un petit calcul élégant. Disposez le plateau en escalier descendant : 65536, 32768, 16384, et ainsi de suite jusqu'à un 2 solitaire. Chaque tuile est exactement une puissance de deux en dessous de sa voisine, si bien que les seize puissances distinctes de 21 à 216 remplissent le plateau parfaitement, et 65536 = 216 trône au sommet : un exposant par case. Tel est le plafond si le jeu ne vous donne jamais que des 2. Mais 2048 fait apparaître un 4 une fois sur dix, et un seul 4 bien synchronisé introduit en fraude un dix-septième exposant, portant le vrai maximum à 131072 = 217 : dix-sept tuiles de puissances tassées dans seize cases. 4 Aucun humain ne l'a construit ; quelques IA l'ont frôlé.
Pourquoi ces plateaux récompensent-ils le fait de nicher votre plus grosse tuile dans un coin ? Une tuile au centre peut être poussée dans quatre directions, et elle se retrouve sans cesse séparée des tuiles qu'elle veut épouser. Une tuile de coin touche deux murs ; elle ne bouge que lorsque vous poussez vers des murs qu'elle épouse déjà, si bien qu'elle reste immobile pendant que tout s'organise autour d'elle. Enchaînez le reste en un serpent monotone — la plus haute dans le coin, se repliant d'avant en arrière par ordre décroissant — et un seul balayage peut déclencher une cascade de fusions. 1 C'est l'heuristique qui domine le jeu humain amateur, et c'est presque exactement ce que les IA redécouvrent quand on les laisse régler leurs propres poids.
Un jeu de fusion à apparitions aléatoires n'a pas d'adversaire, seulement de la météo. Le « résoudre », c'est battre les dés en moyenne, non battre un esprit.
Basculez maintenant le plateau dans la troisième dimension. 3927 est le cousin cubique de 2048 : un réseau 3×3×3 de 27 cellules, six directions de poussée au lieu de quatre, et des tuiles qui fusionnent par trois — 3 vers 9 vers 27 vers 81 —, base trois là où 2048 est en base deux. 5 L'empilement dans les coins survit-il à la dimension supplémentaire ? Un cube a huit coins, et une cellule de coin touche désormais trois faces au lieu de deux : elle devrait être plus stable encore, plaquée par trois murs à la fois, même si les six directions donnent au plateau davantage de moyens de défaire votre structure. Le serpent devient un chemin replié qui enfile les trois couches. Autant que je puisse le vérifier, personne n'a établi si l'analogie tient réellement — raisonnement, non mesure.
Et le plafond ? La règle d'un exposant par cellule suggérerait 327 ≈ 7 600 milliards comme borne supérieure lâche. Mais l'analogie s'effiloche gravement. L'exposant supplémentaire de 2048 venait d'un 4 chanceux ; 3927 ne fait jamais apparaître que la plus petite tuile, un simple 3, donc pas de bonus. Pire, une fusion triple exige trois tuiles alignées, et chaque rangée, colonne et pilier d'un cube 3×3×3 mesure exactement trois cellules, si bien que chaque fusion consomme une ligne entière. Cette contrainte mord bien plus fort que tout ce que connaît le jeu plat et tire presque certainement le maximum réel bien en dessous de 327. Ce qu'est ce nombre véritable, je ne l'ai trouvé calculé nulle part. (Raisonnement clairement signalé ; les mécaniques ci-dessus sont mesurées d'après les documents de conception du jeu.)
Voici la subtilité qui rend le « jeu parfait » insaisissable. Un jeu de fusion à apparitions aléatoires est un jeu stochastique à un joueur, une réussite contre un dé, non un duel. Rien ne choisit la pire apparition pour vous ruiner ; il n'y a que le générateur aléatoire, indifférent. La bonne notion de jeu optimal est donc l'expectimax : maximiser le résultat espéré sur la distribution des apparitions. Ce n'est catégoriquement pas le minimax : le minimax présuppose un adversaire, et si vous en laissez effectivement un placer chaque tuile (« evil 2048 »), le jeu devient une chose plus cruelle que l'on peut vous forcer à perdre. Parce que les dés peuvent en principe distribuer n'importe quelle séquence, une stratégie qui garantit une tuile donnée peut tout simplement ne pas exister. La réponse honnête à « existe-t-il une stratégie parfaite ? » est donc que, pour un jeu stochastique, le mieux que l'on puisse même définir est une stratégie optimale en moyenne, et la calculer exactement est hors de portée pour 2048 6 et grand ouvert pour 3927.