… À tel point que même les machines ne savent pas comment gagner.
‘Magic: The Gathering’ est le roi des jeux de cartes depuis plus de 25 ans. Sorts, créatures, objets magiques… le jeu de cartes à collectionner Wizard of the Coast rassemble des millions de personnes à travers le monde, mais en plus de sa popularité, dont une série Netflix, il cache aussi un niveau de complexité très élevé.
À tel point qu’Alex Churchill, un concepteur de jeux de société de Cambridge, et Stella Biderman, une mathématicienne du Georgia Institute of Technology, ont publié une étude sur le portail arxiV où ils ont catalogué « Magic : The Gathering » comme le jeu le plus complexe de le monde, informatiquement parlant.
Il n’y a pas d’algorithme infaillible pour gagner une partie de Magic
Les jeux sont un écosystème parfait pour apprendre aux machines à entraîner leur intelligence. C’est le cas de DeepMind avec AlphaGo ou OpenAI avec Dota 2, mais les scientifiques nous ont surpris avec leur découverte. Ce n’est autre qu’avec Magic, le jeu le plus complexe au monde. Et pour le prouver, ils ont créé une machine de Turing, lui ont donné un deck et l’ont fait jouer à « Magic : The Gathering ».
Qu’est-ce qu’une machine de Turing ? Fondamentalement, un ordinateur capable d’exécuter des méthodes mathématiques classiques pour résoudre des problèmes. Dans le cas de Magic, les chercheurs ont adapté une machine déjà construite à cet effet en 2011.
Comme l’explique Stella, le programme est capable de jouer à Magic. La machine reçoit une carte comme « entrée » et renvoie un coup. Sur cette base, les enquêteurs peuvent prédire combien de mouvements il faudra pour vaincre l’adversaire ou combien de temps il est optimal de s’en tenir à cette carte. Le fait est que tous les problèmes du jeu Magic ne peuvent pas être résolus par un algorithme.
Dans des simulations effectuées avec la machine de Turing jouant à Magic, ils ont constaté qu’il est mathématiquement impossible pour l’ordinateur de jouer à Magic de manière optimale. C’est-à-dire qu’il n’existe aucun algorithme capable de renvoyer le meilleur coup en fonction d’une « entrée ».
Selon les chercheurs, « Magic est le premier jeu connu et joué dans le monde physique où nous avons un système non calculable ». A quoi ils ajoutent que « en plus de montrer que le jeu stratégique le plus optimal dans Magic n’est pas calculable, nous avons également que la simple évaluation des conséquences déterministes des mouvements passés dans Magic n’est pas calculable. La complexité totale du jeu reste un question ouverte. » , comme le sont de nombreux autres aspects informatiques de ‘Magic: The Gathering.’ »
Nous devons garder à l’esprit que nous parlons à un niveau général. Tous les jeux Magic ne produiront pas un résultat non calculable et, à de nombreuses reprises, la machine saura déterminer les meilleurs coups. Cependant, l’importance de cette recherche est que c’est le seul jeu où il y a la possibilité, dans le cadre des règles, que le jeu ne soit pas calculable.
Cela ouvre toute une série de portes dans le domaine de la théorie des jeux et de l’intelligence artificielle. Selon les responsables de l’étude : « ‘Magic : The Gathering’ ne correspond pas aux hypothèses que les informaticiens font habituellement lorsqu’ils modélisent des jeux. Nous pensons que le jeu le plus optimal dans Magic est beaucoup plus difficile que ce résultat ne l’implique. Nous laisserons la véritable complexité de Magic et sa réconciliation avec les théories des jeux existantes pour les recherches futures ».
‘Magic: The Gathering’ est terminé pour Turing
Les échecs sont plus complexes que les dames, mais les deux sont des jeux calculables. Bien que, dans le cas du premier, l’exercice de force brute nécessaire pour gagner soit énorme. Cependant, il existe des jeux où il n’est pas question de force brute, mais il n’existe toujours pas d’algorithme capable d’établir comment gagner. On les dit « non calculables » et Magic en ferait partie, avec ses plus de 2 000 règles et plus de 19 000 cartes uniques.
Seuls quelques jeux ont une complexité non négligeable, c’est le cas de certains comme Jenga, Tetris ou d’autres jeux vidéo comme ‘Super Smash Bros’ ou ‘Doom’. Mais « Magic : The Gathering » serait le premier jeu physique à tomber dans cette catégorie. Il n’est pas exclu qu’il existe d’autres jeux physiques plus complexes, mais parmi ceux étudiés, Magic s’est avéré être le plus complexe et le premier de ces caractéristiques.
En 2011, Alex Churchill expliquait que « Magic : The Gathering » était un jeu complet de Turing. Il l’a fait par le biais de simulations, mais ce n’est qu’en 2019 que la base mathématique a été construite pour le démontrer.
Que signifie être Turing complet ? C’est une façon mathématique de dire que le jeu pourrait être utilisé comme une machine de Turing et donc servir de base pour résoudre tout type de problème. Les mathématiciens pourraient traduire leurs algorithmes dans un deck Magic et l’utiliser théoriquement comme méthode de calcul. Bien sûr, cette tâche serait incroyablement difficile à programmer et prendrait énormément de temps.
Le simple fait que ‘Magic: The Gathering’ soit un jeu non calculable représente de nouvelles voies de recherche dans la théorie unifiée des jeux. L’article a été initialement publié sur le portail arXiv en mars 2019, et la recherche a ensuite été examinée dans une deuxième version lors de la « Conférence IEEE sur les jeux ». Fin 2020, son travail a été annoncé lors de la conférence « Fun with Algorithms« . Depuis, Alex Churchill, Stella Biderman et Austin Herrick ont donné des conférences expliquant leurs recherches.