‘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é, il cache également une très grande complexité.

À tel point qu’Alex Churchill, concepteur de jeux de société de Cambridge et Stella Biderman, mathématicienne du Georgia Institute of Technology, ont publié une étude sur le portail arxiV, cataloguant ‘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 un jeu Magic

Les jeux sont un écosystème parfait pour enseigner 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 du monde. Et pour le prouver, ils ont créé une machine de Turing, lui ont donné un jeu et l’ont fait jouer « Magic: The Gathering ».

Xiaomi Mi Electric Scooter Pro 2: nouveau système de freinage double et plus de lumières pour améliorer la sécurité

Qu’est-ce qu’une machine de Turing? Fondamentalement, un ordinateur qui peut 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à fabriquée à cet effet en 2011.

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

Des «Apple Killers» à l'assaut de l'App Store, l'épisode de The Applesfera Talks est maintenant disponible

Dans des simulations effectuées avec la machine Turing jouant à Magic, ils ont découvert qu’il était mathématiquement impossible pour l’ordinateur de jouer Magic de manière optimale. En d’autres termes, il n’y a pas d’algorithme capable de renvoyer le meilleur mouvement basé sur 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 qu ‘«en plus de montrer que le jeu stratégique le plus optimal dans Magic n’est pas calculable, nous avons aussi que la simple évaluation des conséquences déterministes des mouvements passés dans Magic n’est pas calculable. Toute la complexité du jeu reste une question ouvertecomme beaucoup d’autres aspects informatiques dans « Magic: The Gathering ». «

Apple arrête de vendre des écouteurs et des haut-parleurs tiers, tout indique l'arrivée imminente des AirPods Studio

Nous devons garder à l’esprit que nous parlons à un niveau général. Tous les jeux Magic ne produiront pas un résultat indénombrable et à de nombreuses occasions, la machine pourra déterminer les meilleurs mouvements. 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, où le jeu n’est 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 que le résultat ne le suggère pas. Nous laisserons la vraie complexité de Magic et sa réconciliation avec les théories de jeu existantes pour de futures recherches. «

La Chine prépare sa liste noire en réponse à celle des États-Unis: Cisco (rival de Huawei) vise à faire partie de ceux inclus

‘Magic: The Gathering’ est terminé Turing

la magie

Les échecs sont plus complexes que les dames, mais ce sont deux jeux calculables. Bien que, dans le cas des premiers, l’exercice de la force brute nécessaire pour gagner soit énorme. Cependant, il y a des jeux où il ne s’agit pas de force brute, mais il n’y a toujours pas d’algorithme capable d’établir comment gagner. Ils sont appelés «non calculables» et Magic en serait un.

Seuls quelques jeux ont une complexité non triviale, comme certains comme Jenga, Tetris ou d’autres jeux vidéo comme Super Smash Bros.Mais «  Magic: The Gathering  » serait le premier jeu physique qui tomberait dans cette catégorie.

La série Nvidia GeForce RTX 3000 saluée par les développeurs de jeux

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 a été construite pour le démontrer.

Que signifie être un 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 pouvaient transférer leurs algorithmes sur un deck Magic et les utiliser théoriquement comme méthode de calcul. Bien sûr, cette tâche serait incroyablement difficile à planifier et consommerait du temps insoutenable.

Le simple fait que « Magic: The Gathering » est un jeu non calculable représente de nouvelles voies de recherche en théorie des jeux unifiée. L’article a été initialement publié sur le portail arXiv en mars 2019, la recherche a ensuite été revue dans une deuxième version lors de la «Conférence IEEE sur les Jeux 2019».

Dans SamaGame | ‘Magic: The Gathering’ arrive sur Netflix avec un anime basé sur le monde des jeux de cartes et produit par les frères Russo

La source : Engadget