dans

‘Magic: The Gathering’ est le jeu le plus complexe au monde, à 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é, notamment une série Netflix, il cache également une très grande complexité.

À 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 qui cataloguait ‘Magic: The Gathering’ comme le jeu le plus complexe au monde, en termes de calcul.

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 à former leur intelligence. C’est le cas de DeepMind avec AlphaGo ou OpenAI avec Dota 2, mais les scientifiques nous ont surpris par leur découverte. Ce n’est autre que Magic, le jeu le plus complexe au monde. Et pour le prouver, ils ont créé une machine de Turing, lui ont donné un maillet et l’ont fait jouer à «Magic: The Gathering».

Qu’est-ce qu’une machine de Turing? Fondamentalement, un ordinateur capable d’exécuter les méthodes mathématiques classiques pour résoudre des problèmes. Dans le cas de Magic, les chercheurs ont adapté une machine déjà fabriquée à cet effet en 2011.

Comme l’explique Stella, le programme est capable de jouer à Magic. La machine reçoit une lettre comme «entrée» et renvoie un mouvement. Sur cette base, les investigateurs peuvent prédire combien de mouvements il faudra pour vaincre l’adversaire ou combien de temps il est optimal pour continuer avec cette carte. Ce qui se passe, c’est que tous les problèmes de Magic dans le jeu ne peuvent pas être résolus par un algorithme.

Dans les simulations effectuées avec la machine de Turing jouant à Magic, ils ont constaté qu’il était mathématiquement impossible pour l’ordinateur de jouer à Magic de manière optimale. Autrement dit, il n’y a pas d’algorithme capable, sur la base d’une «entrée», de renvoyer le meilleur mouvement.

Turing

Selon les chercheurs, « Magic est le premier jeu connu et joué dans le monde physique où nous avons un système non calculable. » À quoi ils ajoutent qu ‘«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 une question ouverte, comme beaucoup d’autres aspects informatiques dans «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 en de nombreuses occasions, la machine saura déterminer les meilleurs mouvements. Cependant, l’importance de cette recherche est que c’est le seul jeu où il y a une 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 « n’est pas conforme aux hypothèses que les informaticiens font habituellement lors de la modélisation de jeux. Nous pensons que le jeu le plus optimal dans Magic est beaucoup plus difficile que ce résultat ne l’implique. Nous laissera la vraie complexité de Magic et sa réconciliation avec les théories de jeu existantes pour de futures recherches. « 

‘Magic: The Gathering’ est plein Turing

la magie

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 la force brute nécessaire pour gagner soit énorme. Cependant, il y a des jeux où ce n’est pas une question de force brute, mais plutôt il n’y a toujours pas d’algorithme capable d’établir comment gagner. Ils sont appelés «non calculables» et Magic en ferait partie.

Seuls quelques jeux ont une complexité non triviale, c’est le cas de certains tels que Jenga, Tetris ou d’autres jeux vidéo comme Super Smash Bros.Mais ‘Magic: The Gathering’ serait le premier jeu physique à rentrer dans cette catégorie .

Déjà en 2011, Alex Churchill a expliqué que «Magic: The Gathering» était un jeu de Turing complet. Il l’a fait à travers des simulations mais ce n’est qu’en 2019 que la base mathématique pour prouver qu’elle a été construite.

Qu’est-ce que cela signifie d’être Turing à part entière? C’est une manière 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 en un jeu Magic et l’utiliser théoriquement comme méthode de calcul. Bien sûr, cette tâche serait incroyablement difficile à planifier et prendrait beaucoup de temps.

Le simple fait que «Magic: The Gathering» soit un jeu non calculable représente de nouvelles pistes d’investigation dans la théorie des jeux unifiée. L’article a été initialement publié sur le portail arXiv en mars 2019, la recherche étant ensuite révisée dans une deuxième version lors de la «  IEEE Conference on Games  ».

En Engadget | ‘Magic: The Gathering’ arrive sur Netflix avec un anime basé sur l’univers du jeu de cartes et produit par les frères Russo

45secondes est un nouveau média, n’hésitez pas à partager notre article sur les réseaux sociaux afin de nous donner un solide coup de pouce. 🙂

  • Magic The Gathering Nissa Revane Legacy Action Figure
    From the popular trading card game Magic: The Gathering, comes this Nissa Revane Legacy Action Figure. Magic: The Gathering has spanned for nearly 2 decades and finally receives the Legacy action figure treatment! This Magic The Gathering Nissa Revane Legacy Action Figure stands about 6-inches tall with over 20 points of articulation and comes in a window display box. This Nissa Revane Legacy action figure makes a great addition to any MTG fan's collection!
  • Magic The Gathering Jace Beleren Legacy Action Figure
    From the popular trading card game Magic: The Gathering, comes this Jace Beleren Legacy Action Figure. Magic: The Gathering has spanned for nearly 2 decades and finally receives the Funko Legacy action figure treatment! This Magic The Gathering Jace Beleren Legacy Action Figure stands about 6-inches tall with over 20 points of articulation and comes in a window display box. This Jace Beleren Legacy action figure makes a great addition to any MTG fan's collection
  • Magic The Gathering Legacy Garruk Wildspeaker Legacy Action Figure
    From the popular trading card game Magic: The Gathering, comes this Garruk Wildspeaker Legacy Action Figure. Magic: The Gathering has spanned for nearly 2 decades and finally receives the Funko Legacy action figure treatment! This Magic The Gathering Garruk Wildspeaker Legacy Action Figure stands about 6-inches tall with over 20 points of articulation and comes in a window display box. This Garruk Wildspeaker Legacy action figure makes a great addition to any MTG fan's collection!