7 000 zombies paralysent le moteur : Une victoire humaine évidente devenue impasse informatique

7 000 zombies paralysent le moteur : Une victoire humaine évidente devenue impasse informatique

Développement de JeuxRustAlgorithmesArchitecture Système

Sources:HN + web research

La partie à l’écran s’est figée au 58e tour. D’un côté de la table s’entassent 7 258 zombies, tandis que le défenseur ne dispose plus que de 31 points de vie. Il suffirait de lancer 16 zombies à l’attaque pour clore l’affrontement sur-le-champ. Au lieu de cela, le moteur de règles se fige pendant 35 secondes pour résoudre une seule étape, pour finalement n’envoyer timidement qu’un unique zombie effleurer l’adversaire.

Cette scène insolite a été rencontrée par le développeur Levi Neuwirth lors des tests d’Arcana, un moteur de règles pour Magic: The Gathering (MTG) codé en Rust afin d’évaluer des algorithmes d’IA de cartes. Après avoir lancé 64 decks d’archétypes dans 403 200 parties automatisées, neuf affrontements ont heurté la limite des deux heures avant d’être interrompus par le système.

Le code ne contenait aucune boucle infinie. Ce qui a mis le système à genoux, c’est l’explosion exponentielle déclenchée par les mécaniques intrinsèques des cartes. Quand des milliers de créatures s’accumulent sur le champ de bataille, le parcours exhaustif microscopique dévore instantanément toute la puissance de calcul disponible.

L’équivalence de Magic avec une machine de Turing a été prouvée mathématiquement il y a plusieurs années. Mais la mise en œuvre logicielle relève d’un tout autre défi d’ingénierie. Un humain identifie la victoire d’un seul coup d’œil, alors qu’un programme doit réexaminer l’ensemble de la table pour chaque créature. L’ordre d’un joueur criant « attaque générale » se traduit dans le code par des millions de ramifications combinatoires.

Huit arrivées de terrains créent 6 000 insectes : L’emballement exponentiel

Magic: The Gathering est né en 1993. Chaque carte porte des règles spécifiques capables de redéfinir les règles de base du jeu à tout moment. Lorsque plusieurs cartes aux effets en cascade se rencontrent, les grandeurs numériques s’affolent sans attendre.

La carte « Essaim de scutes » (Scute Swarm) en est l’illustration parfaite. Chaque fois qu’un terrain arrive sur le champ de bataille sous votre contrôle, elle crée un jeton copie d’elle-même. Un devient deux, deux deviennent quatre, doublant à chaque action.

Lors des simulations, elle s’est combinée à des cartes de gain de points de vie et des artefacts démultiplicateurs de jetons. Après huit poses de terrains consécutives, 6 561 insectes grouillaient sur le terrain. Le total de points de vie du joueur a grimpé jusqu’à 26 240. Une partie normale débute avec 20 points de vie ; ce chiffre pulvérise les hypothèses de n’importe quel jeu de société sur table.

Comparaison des courbes de croissance Figure : Comparaison de la croissance exponentielle entre Scute Swarm et l’emblème de Liliana ; chaque graduation verticale principale représente une multiplication par dix. Source : Levi Neuwirth

Autour d’une table physique, deux joueurs posent simplement une paire de dés sur une carte pour matérialiser des milliers de créatures et poursuivre la partie. Un logiciel, en revanche, doit allouer scrupuleusement en mémoire une structure de données dédiée pour chacune des 6 561 entités.

35 secondes par étape : La duplication sature la mémoire

Un essaim d’insectes, aussi terrifiant soit-il, s’élimine d’un seul sort de nettoyage de table. Ce qui a réellement terrassé le moteur, c’est la capacité ultime de l’arpenteuse Liliana. Cette aptitude laisse en dehors de la table un emblème permanent impossible à détruire.

La règle de l’emblème est d’une grande concision : au début de votre étape de fin, créez X jetons de créature Zombie, X étant égal à deux plus le nombre de zombies que vous contrôlez. À chaque tour suivant, le nombre de zombies équivaut au double du tour précédent plus deux. Après seulement huit déclenchements, 510 zombies s’entassaient sur le champ de bataille.

Même si l’adversaire rase le champ de bataille avec un sortilège, l’emblème logé dans la zone de commandement demeure indemne. Au tour suivant, deux nouveaux zombies font leur entrée et relancent la chaîne de duplication. Cette boucle d’auto-multiplication indestructible est devenue le cauchemar du moteur de règles.

Neuwirth a analysé la partie bloquée pas à pas. Au 52e tour, la résolution d’un seul déclenchement de l’emblème a requis 1,72 seconde. Au 54e tour, ce délai grimpait à 7,78 secondes. Au 56e tour, le temps de calcul bondissait directement à 35,15 secondes.

Courbe du temps de résolution Figure : Chaque fois que la population de zombies double sur le plateau, le temps de résolution d’état est multiplié par environ 4,5. Source : Levi Neuwirth

La population de zombies doublant, le temps de calcul unitaire a été multiplié par environ 4,5, illustrant une dégradation superlinéaire de la complexité algorithmique. Dès qu’une nouvelle créature arrive, le moteur doit reparcourir la table entière et réévaluer toutes les capacités passives et déclenchées. Des milliers d’objets interagissant par paires ont enlisé la vérification des règles dans un bourbier informatique.

7 000 zombies sous la main, un budget de recherche suffisant pour un seul

Au 58e tour, la horde a culminé à 7 258 zombies. Le joueur défenseur n’avait plus que 31 points de vie et manquait de bloqueurs. Envoyer seulement 16 zombies pour infliger 32 blessures suffisait amplement à remporter la victoire.

C’est à cet instant précis qu’une situation absurde s’est produite : après une longue réflexion, l’IA n’a envoyé au combat qu’un unique petit zombie de force 2. Il a frappé sans grand effet une créature ennemie. Disposant d’une armée de plus de sept mille combattants, le camp archi-dominant a délibérément manqué l’occasion d’achever la partie.

Interface de rediffusion de la partie Figure : Vue de la rediffusion au 58e tour montrant 7 234 zombies dans une seule pile face à un adversaire n’ayant plus que 31 points de vie. Source : Levi Neuwirth

L’origine du blocage se situait dans la logique de sauvegarde du générateur de coups. Quand des milliers de créatures attaquent plusieurs cibles potentielles, l’espace combinatoire explose de façon astronomique. Pour parer aux dépassements de délai, le développeur avait fixé dans le code un plafond strict de 1 024 coups candidats.

Le générateur évaluait en priorité les manœuvres d’attaque solitaire. Avec 7 258 zombies sur le terrain, les simples combinaisons d’envoi d’un seul attaquant ont saturé l’intégralité des 1 024 places disponibles. Les stratégies d’assaut collectif et d’attaque générale, reléguées en queue de file d’attente, n’ont tout simplement jamais pu être générées.

Au 44e tour, avec 58 créatures, 229 coups avaient été produits, dont quatre impliquant plusieurs attaquants coordonnés. Au 50e tour, le plafond a été atteint et les options d’attaques groupées sont tombées à zéro. Le garde-fou conçu pour éviter les gels a paradoxalement masqué la combinaison victorieuse.

Intuition humaine contre millions de ramifications informatiques

Un joueur humain appréhende ce contexte sous un angle radicalement différent. Même face à dix mille zombies, personne ne calcule le positionnement précis de chaque unité. Dès lors que la force totale excède largement les points de vie adverses, lancer une attaque générale permet de conclure la partie en temps constant O(1).

Les logiciels ne possèdent pas cette capacité d’abstraction globale. Le moteur s’est conformé scrupuleusement à une approche microscopique, découpant méticuleusement chaque entité en structures de données. Quand seules quelques créatures s’affrontent, ce parcours exhaustif garantit une justesse absolue des règles.

Mais dès que l’échelle franchit un seuil critique, la rigueur microscopique devient un fardeau écrasant. L’accumulation de minuscules boucles conformes absorbe l’intégralité de la puissance processeur. L’ordinateur n’est pas devenu stupide ; il s’est simplement retrouvé piégé dans d’insignifiants micro-détails.

Entre complétude théorique et faisabilité d’ingénierie subsiste un fossé béant. Magic autorise les cartes à modifier librement le comportement fondamental des règles, conférant au jeu une richesse infinie. Mais lorsque cette liberté rencontre une prolifération exponentielle, la simulation de règles bascule au bord du gouffre.

Un disjoncteur à 500 permanents pour relancer l’expérience

Pour permettre aux séries de tests automatisés d’aboutir, Neuwirth a mis en place une parade technique : il a instauré une règle coupe-circuit décrétant qu’au-delà de 500 permanents sur le champ de bataille, la situation est jugée incontrôlable et se solde par un match nul.

Dès l’application de ce disjoncteur, les simulations ont immédiatement repris leur cours. Des parties qui restaient bloquées pendant deux heures se sont terminées sans encombre en 0,16 seconde dès l’apparition du 576e permanent. Poser des limites matérielles à l’expansion infinie s’est imposé comme le moyen premier de préserver l’avancement global du projet.

Des refontes d’architecture plus profondes ont également été amorcées. Le moteur met désormais en cache les états fréquemment sollicités afin d’éviter de reparcourir l’intégralité du champ de bataille à chaque création de jeton. De même, l’algorithme de génération de coups réserve dorénavant des créneaux prioritaires pour les heuristiques macroscopiques comme l’attaque générale.

L’incident des 7 258 zombies trace nettement la frontière entre la simulation mécanique de règles et la véritable intelligence. Tandis que l’ordinateur explore les micro-ramifications à une vitesse vertigineuse, l’humain tranche dans le vif grâce à son intuition globale. Quand les règles autorisent une croissance exponentielle sans entraves, un code dépourvu de vision d’ensemble est condamné à l’impasse : il analyse chaque ramification microscopique avec brio, mais finit irrémédiablement englouti par la marée de chiffres qu’il a lui-même produite.

Liens de référence :

  • Article original du blog technique de Levi Neuwirth
  • Dépôt open source du moteur de règles Arcana
  • Discussion technique sur Hacker News