Surprise pour les théoriciens algorithmiques des jeux : jamais ils n'auraient imaginé qu'un jeu puisse être aussi complexe. Pourtant, "Magic" peut parfois mettre les ordinateurs à rude épreuve, comme le montre un travail de recherche récent.
Dans l'intervalle, le jeu de cartes a également séduit de nombreuses personnes d'un point de vue scientifique, car il semble avoir bouleversé des décennies de convictions des théoriciens du jeu : Apparemment, Magic, avec ses nombreuses cartes, ses règles compliquées et ses stratégies sophistiquées, représente un défi plus grand pour les ordinateurs que ce que les informaticiens pensaient possible.
Des experts de la science et de la recherche rendent compte des dernières découvertes dans leur domaine – de manière compétente, authentique et compréhensible.
Si vous étiez à Las Vegas en septembre 2018, vous pouviez facilement vous croire dans la célèbre série télévisée "The Big Bang Theory" : Dans une salle, 24 hommes adultes s'affrontaient à l'aide de cartes de jeu fantastiques colorées représentant des créatures magiques et des sorts. Il s'agissait en fait du championnat du monde annuel "Magic : The Gathering", où les joueurs se disputent des prix d'une valeur totale de 300 000 dollars.
L'intérêt principal des théoriciens algorithmiques des jeux est de calculer des stratégies gagnantes pour les jeux en cours. Plus il est difficile pour un ordinateur de prédire l'issue d'une partie, plus les informaticiens considèrent qu'un jeu est complexe. Magic semble se distinguer des autres jeux d'une manière particulière : Comme le chercheur indépendant Alex Churchill de Cambridge au Royaume-Uni, Stella Biderman du Georgia Institute of Technology à Atlanta et Austin Herrick de l'Université de Pennsylvanie à Philadelphie l'ont démontré dans une [, il n'est pas toujours possible de prédire l'issue d'un duel Magic, ce qui en fait le jeu le plus complexe connu à ce jour. Pour distinguer les différents niveaux de difficulté, les informaticiens théoriques répartissent les problèmes en classes dites de complexité. Le facteur décisif est le temps qu'il faut à un ordinateur - s'il y parvient - pour résoudre un problème. Par exemple, si l'on veut décomposer un nombre en ses facteurs premiers, le temps de calcul nécessaire augmente de manière exponentielle avec sa taille. L'opération inverse, la multiplication de deux facteurs premiers, est beaucoup plus simple : selon les dernières recherches [, le temps de calcul augmente simplement par n log(n), où n est la longueur des deux facteurs. Pour les nombres extrêmement grands, il n'existe donc aucun moyen efficace de les décomposer en leurs facteurs premiers, alors qu'il est très facile de vérifier le résultat. De tels problèmes sont connus en informatique sous le nom de problèmes NP. Ce schéma permet également d'évaluer la complexité d'un jeu. Par exemple, pendant une partie d'échecs proche de la fin, un ordinateur peut calculer si et comment la couleur blanche peut encore gagner. Il lui suffit pour cela de passer en revue tous les coups possibles. Cela semble assez compliqué, mais le plateau de jeu limité permet à l'ordinateur de réaliser cette tâche en peu de temps. Comme la plupart des jeux réels (c'est-à-dire ceux auxquels les gens jouent réellement et qui ne sont pas simplement conçus artificiellement) ne sont pas vraiment complexes, les informaticiens ne s'y sont guère intéressés. En fait, les experts pensaient jusqu'à présent qu'il n'existait aucun jeu réel dont la complexité atteignait la classe NP.
Comme Churchill et ses deux collègues veulent maintenant le démontrer, c'est pourtant le cas de Magic. Ils suggèrent même que le jeu de cartes à collectionner pourrait être encore plus complexe. Pour parvenir à ces conclusions, les chercheurs ont utilisé un concept courant de l'informatique théorique : une machine de Turing. Ce modèle de calcul, introduit en 1936 par le scientifique britannique Alan Turing, simule le fonctionnement des ordinateurs classiques. Il se compose d'une bande divisée en cases individuelles et d'une tête qui lit et éventuellement décrit les cases. La machine peut déplacer le ruban vers la gauche ou vers la droite pour accéder aux champs souhaités. Elle représente ainsi ce que les mathématiciens appellent une fonction : Elle convertit des nombres en d'autres nombres selon une règle précise et univoque. Par exemple, un extrait typique d'un programme pour une machine de Turing est le suivant : "Si la machine est à l'état 3 et que la case contient le nombre 0, remplacez-le par un 1, passez à l'état 5 et déplacez-vous de 4 cases vers la droite". Une question classique dans l'étude des machines de Turing est de savoir si une machine arrive un jour à la fin du calcul d'un problème ou si elle continue à tourner sans fin, les informaticiens parlent de problème d'arrêt. Dès 1936, Turing avait montré qu'il n'y avait aucun moyen de répondre à cette question de manière générale pour tous les algorithmes possibles. Churchill et son équipe ont maintenant réussi à prouver que la question de l'issue d'un duel de Magic correspond au problème d'arrêt : cela signifie qu'il existe des situations de jeu dans lesquelles un ordinateur ne peut pas calculer qui va gagner. Les chercheurs sont parvenus à cette conclusion surprenante en montrant que Magic : The Gathering possède les mêmes fonctions qu'une machine de Turing, c'est-à-dire qu'il est "Turing-complet", comme le disent les experts. En d'autres termes, vous pouvez utiliser Magic pour simuler une machine de Turing et vice versa. Pour ce faire, Churchill, Biderman et Herrick ont construit une situation de départ particulière entre deux joueurs de Magic et ont identifié les coups possibles avec les fonctions essentielles d'une machine de Turing : la lecture, l'écriture et le déplacement de la bande. Le jeu possède ainsi toutes les propriétés du modèle théorique de calcul et peut être étudié avec les outils de l'informatique théorique.
La sélection d'une situation de jeu appropriée pour Magic : The Gathering s'est toutefois avérée difficile. D'une part, elle devait contenir des éléments de jeu suffisamment compliqués pour simuler une machine de Turing, mais d'autre part, elle devait rester suffisamment simple pour que l'on ait une vue d'ensemble des mouvements possibles. Après tout, il existe plus de 20 000 cartes Magic différentes, chacune ayant des fonctions différentes. De plus, certaines d'entre elles contiennent des actions volontaires qui laissent une marge de manœuvre stratégique au joueur, ce qui est difficile à simuler. Churchill et ses collègues n'ont donc utilisé que des cartes ayant un effet clair. Dans leur situation de jeu créée - qui peut tout à fait se produire dans un tournoi réaliste - il n'y a donc que des coups forcés ; les joueurs n'ont aucune liberté de décision. Avant de commencer une partie de Magic, un joueur choisit 60 cartes dans sa collection - ce choix dans l'immense réservoir de cartes disponibles et les possibilités de combinaisons qui en découlent sont à l'origine de l'extraordinaire complexité du jeu. Une fois que le joueur a fait son choix, il mélange soigneusement ses cartes et en prend sept en main. Les autres constituent sa pioche. Parmi les cartes, on trouve des créatures qui attaquent l'adversaire, ou encore des sorts et des artefacts. Au début de chaque tour, vous piochez une carte. Dès qu'un joueur doit prendre une carte d'une pioche vide, il a perdu. Sinon, vous vainquez votre adversaire en réduisant ses points de vie à zéro ou moins grâce à des attaques ciblées. Dans le jeu construit par Churchill et ses collègues, Alice et Bob s'affrontent. Bob se retrouve dans une situation où il n'a aucune carte en main et où sa pioche est vide - il est donc sur le point de perdre. En revanche, il contrôle toutes les créatures présentes sur la table. Alice ne peut donc qu'essayer d'attaquer les créatures de Bob avec les cartes de sa pioche. Cette situation de départ permet aux chercheurs d'identifier le jeu à une machine de Turing. Dans ce modèle, les créatures sur la table correspondent à la bande : sur chaque case se trouve une créature, avec sa valeur de force et de résistance, qui indiquent respectivement les dégâts qu'elle inflige et ce qu'elle peut encaisser. De plus, Magic dispose de cinq couleurs "magiques" différentes pour caractériser une carte. Dans le jeu imaginé par Churchill et ses collègues, des créatures blanches ou vertes apparaissent avec des valeurs de force et de résistance identiques (par exemple 2/2 ou 3/3). La bande est initialement disposée de manière à ce que la tête de lecture repose sur la créature la plus faible (2/2) ; à sa droite se trouvent, par ordre de force, toutes les créatures blanches et, par analogie, à sa gauche, toutes les créatures vertes. Une créature blanche avec une valeur de 5/5 se trouve donc sur la troisième case à droite de la tête. Le type de créature est indiqué par un symbole sur la case.
Turing machine pour Magic : The Gathering | Les cases de la bande correspondent aux créatures vertes (à gauche) et blanches (à droite) de Bob. La distance à la tête de la Turing Machine (en jaune) correspond aux valeurs de force et de résistance de chaque créature (valeurs numériques supérieures). Les lettres symbolisent le type de créature. Source : Spektrum der Wissenschaft
Les différentes fonctions de la machine de Turing sont initiées en jouant les cartes d'Alice : Pour déplacer le ruban vers la droite ou vers la gauche, Alice doit poser une carte qui inflige des dégâts à toutes les créatures d'une couleur donnée. Mais que se passe-t-il si une créature meurt dans le processus ? Churchill et ses collègues ont prévu ce cas de figure : l'une des cartes de Bob est le [Réveil de Modèles](https://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=167754), qui remplace une créature morte par une nouvelle de même puissance. Cela explique aussi comment la tête de la machine de Turing lit et réécrit une case : à savoir en tuant une créature et en la ressuscitant ensuite par Bob. La carte Développement artificiel, qui permet à un joueur de modifier les actions d'autres cartes, est cruciale pour l'ensemble du processus. Par exemple, alors que le ressuscitant des poumons modernes ne fait que ressusciter des clercs sous forme de zombies, l'évolution artificielle permet de remplacer le zombie par n'importe quelle autre créature. Selon Churchill, c'est précisément cette capacité qui caractérise Magic : The Gathering : "Pour qu'un jeu ait la même complexité que Magic, un joueur doit pouvoir le contrôler ou le programmer au cours d'une partie, comme le permet l'évolution artificielle", fait-il savoir. Avec cette sélection de cartes, le jeu entre Alice et Bob a toutes les capacités d'une machine de turing. "Si vous choisissez votre problème de maths préféré, vous pouvez créer une situation de jeu Magic qui calcule ce problème en choisissant les cartes de manière appropriée", explique [Stella Biderman](https://www.reddit.com/r/magicTCG/comments/bgiz6j/magic_the_gathering_is_turing_complete/eln2vbk/), co-auteur des travaux. Mais cela demande beaucoup de travail : Il faut d'abord traduire le problème dans le langage d'une machine de Turing, ce qui est déjà assez compliqué, et ensuite trouver la bonne sélection et la bonne disposition des cartes Magic qui correspondent au problème. Mais une fois la bonne situation de départ trouvée, il suffit de laisser Alice et Bob se lancer ; leurs mouvements forcés correspondent alors aux différentes étapes du calcul. Dès que le jeu entre eux est terminé, la solution du problème peut être lue. Churchill et son équipe ont conçu le jeu de manière à ce que Bob ne puisse pas gagner. Par conséquent, la machine de Turing ne s'arrête que lorsqu'Alice gagne, sinon elle continue indéfiniment. Dans les vrais jeux Magic, de telles situations peuvent effectivement se produire. Il existe même une règle qui stipule qu'en cas de coups répétés, une partie se termine par un match nul
Au total, trois situations peuvent donc se produire dans le jeu entre Alice et Bob : Les cartes correspondent à un problème qu'une machine de Turing peut résoudre, comme calculer "2 + 2". Dans ce cas, Alice gagnera la partie. D'autre part, le jeu pourrait représenter un problème insoluble, tel que "calculer l'entier naturel x pour lequel x2 = 2". Comme un tel nombre n'existe pas, la machine de Turing continuera à fonctionner indéfiniment ; le jeu se terminera donc par un match nul. Il existe cependant une troisième possibilité : les cartes pourraient représenter quelque chose dont on ne sait pas s'il est possible de le résoudre ou non. Un exemple serait "Calculez une paire de nombres premiers jumeaux (c'est-à-dire deux nombres premiers avec une différence de 2) qui sont supérieurs à 10500 000". Comme les mathématiciens ne savent pas encore s'il existe des jumeaux de nombres premiers de cette taille, il n'est pas certain que la machine de Turing tienne un jour.
Problèmes mathématiques dans Magic : The Gathering | Il y a trois types de problèmes mathématiques qui peuvent survenir dans un duel Magic tel que les scientifiques l'ont construit. En haut : Un problème soluble, la machine de Turing s'arrête, ce qui signifie qu'Alice gagne. Au milieu : Le problème est insoluble, la machine de Turing continue indéfiniment et la partie de Magic se termine par un match nul. En bas : On ne sait pas s'il existe une solution, on ne sait pas si la machine de Turing s'arrêtera un jour et donc l'issue de la partie est également incertaine. Source : Spektrum der Wissenschaft
Si un ordinateur doit donc prédire l'issue du jeu entre Alice et Bob, il doit résoudre le problème d'arrêt pour les machines de Turing. Pour de nombreuses situations, comme dans les deux premiers exemples cités précédemment, ce n'est pas un problème. Mais il y a aussi des jeux pour lesquels l'issue n'est pas claire, comme dans le dernier cas. Globalement, aucun algorithme ne peut donc prédire pour n'importe quel duel comment, si et quand le jeu entre Alice et Bob se terminera - et ce, même si chaque coup des deux joueurs est forcé. L'issue d'une partie ne dépend donc que des créatures que Bob maîtrise au départ et de l'ordre dans lequel Alice tire ses cartes. Les chercheurs ont pu démontrer que la situation de jeu qu'ils ont imaginée peut réellement se produire dans un duel réaliste - et n'est pas une simple construction artificielle. Ils estiment également que d'autres situations de jeu peuvent conduire à des impasses similaires. Par conséquent, le jeu atteint au moins le niveau de complexité NP, écrivent les auteurs. Cependant, pour vérifier s'il est peut-être encore plus complexe, il faut adopter une autre approche. Cependant, le résultat reste surprenant du point de vue de la théorie des jeux, même s'il peut moins surprendre les joueurs de Magic : certains d'entre eux se vantent depuis longtemps de maîtriser un jeu extrêmement compliqué. Désormais, ils peuvent officiellement affirmer qu'ils jouent au jeu le plus complexe du monde.
Nous sommes partenaires de [Spektrum der Wissenschaft](https://www.spektrum.de/) et souhaitons rendre les informations scientifiques plus accessibles. Vous aimez les articles de Spektrum ? Alors suivez Spektrum der Wissenschaft ou [abonnez-vous au magazine](https://www.spektrum.de/shop/) et soutenez ainsi le journalisme scientifique.
