Magic : The Gathering est l'un des jeux les plus complexes du monde selon des chercheurs en intelligence artificielle !

De Dan Auteur - Posté le 9 mai 2019 à 11h09 dans Science

Vous aimez nos articles ? Suivez nous sur facebook

Vous aimez nos articles ? Suivez nous sur twitter

Une récente étude menée par une équipe de chercheurs en intelligence artificielle vient de conclure que Magic : The Gathering (ou Magic : L'Assemblée, en français) était l'un des jeux les plus complexes du monde.

Pour ceux qui ne connaissent pas ce jeu créé en 1993, des joueurs s'affrontent avec 60 cartes au minimum dans les mains. Chaque joueur doit composer son propre deck. Il existe plus de 18 000 cartes différentes et régulièrement, de nouvelles éditions ainsi que de nouvelles règles voient le jour. Si le principe du jeu reste le même, il est en revanche, en perpétuelle évolution.

L'étude en question a été menée par Alex Churchill, un chercheur et concepteur de jeux de société britannique, Austin Herric de l'Université de Pennsylvanie et Stella Biderman du Georgia Institute of Technology. L'équipe a commencé par déterminer la complexité informatique du jeu à l'aide d'une machine de Turing.

Si le jeu avait déjà fait l'objet de précédentes études du genre, celle-ci tend à montrer qu'il est possible de créer un scénario dans le jeu, dans lequel il n'y a aucun moyen de calculer la stratégie gagnante. De ce fait, ce jeu est qualifié de "non calculable" ce qui signifie qu'il est impossible, quelque soit la puissance et la vitesse de l'ordinateur, de trouver une solution gagnante en fonction des différents coups joués.

Si d'autres jeux reposent sur le même principe que Magic : The Gathering comme Hearthstone ou Eternal pour des versions en ligne ou encore sous format papier tels que Star Wars : The Card Game ou encore Call of Cthulhu LCG, aucun d'eux n'atteignent une complexité aussi forte que le jeu étudié ici. En effet, l'une des raisons qui peut expliquer cette difficulté réside dans l'énorme volume de cartes disponibles, le nombre de phases au cours d'un tour pour un joueur et bien entendu, des règles qui n'ont cessé d'évoluer tout au long des 26 ans au cours desquels sont sorties les extensions !

Une erreur ?

Mots-Clés : Magic : The Gatheringcomplexitédifficultécartesintelligence artificielleEtude

Source(s) : kotaku.com

Cliquez sur une phrase de l'article pour proposer une correction.

J'ai compris !

Commentaires (24)

Par Frak, il y a 2 mois :

Et c'est ça qui est intéressant du coup si le jeu ne permet pas de déterminer la clé pour gagner à tous les coups !

Répondre à ce commentaire

Par Comprendre Interstellar en 4 leçons, il y a 2 mois :

Mouai, ça part du principe que à partir de chaque carte jouée est il y a une possibilité infinie de coup derrière, ce qui est déja faux,puisque le principe d'un deck c'est d'avoir un plan de jeu, et que les coups sont limités en fonction du meme plan de jeu de l'adversaire.

Répondre à ce commentaire

Par Wasteak, il y a 2 mois (en réponse à Comprendre Interstellar en 4 leçons):

Je pense qu'ils ont un peu plus travaillé la question que cela tkt pas.

Répondre à ce commentaire

Par Comprendre Interstellar en 4 leçons, il y a 2 mois (en réponse à Wasteak):

En meme temps ce que tu penses n'est pas gage que ce qu'ils affirment est vrai...

Répondre à ce commentaire

Par Seak, il y a 2 mois (en réponse à Comprendre Interstellar en 4 leçons):

il faut pas avoir lu l'article pour dire que ca part du principe que tu cites. Relis bien cette parti :

l'une des raisons qui peut expliquer cette difficulté réside dans l'énorme volume de cartes disponibles, le nombre de phases au cours d'un tour pour un joueur et bien entendu, des règles qui n'ont cessé d'évoluer tout au long des 26 ans au cours desquels sont sorties les extensions !

Et pour rebondir sur le "plan", toi seul joueurs du deck connais le plan quand tu joue une parti, pas ton adversaire, donc l'IA qui joue contre toi, ne connais pas ton plan ni ton deck (comme toi tu ne connais pas celui de ton adversaire), ni les X possibilité de cartes qu'il y'a dedans. Et même si tu joue la carte, elle ne sait pas ce que tu va combiner avec car une carte peut être jouer dans X plan (X qui ne fait que grandir plus les années passe).

Répondre à ce commentaire

Par Comprendre Interstellar en 4 leçons, il y a 2 mois (en réponse à Seak):

"Our result appliesto how realMagicis played, can be achieved using standard-size tournament-legal decks, and does not rely on stochasticityor hidden information"
C'est dans l'abstract de l'article, donc ce que j'ai dit plus haut est bien valable, leur raisonnement est éronné.

Répondre à ce commentaire

Par TheFireNight, il y a 2 mois (en réponse à Seak):

En réalité, même si on ne peut pas connaitre le deck de l'adversaire, il est assez simple d'en deviner le contenu au bout de 3 ou 4 tours.
Ce que dit l'article est vrai, il y a un très grand nombre de cartes. Toutefois, ce nombre descend très vite si on retire les cartes injouables car mauvaises, les cartes qui ne correspondent pas aux couleurs jouées par l'adversaire, et les terrains (40% du deck en moyenne). De plus les joueurs jouent en général plusieurs fois les même cartes dans leur deck, et ils ne jouent que des cartes qui ont une synergie entre elles : on obtient dont un deck qui doit respecter un archetype parmi n, et ce n est loin d'être énorme en tournois compétitif.

On se retrouve finalement un métagame d'une cinquantaine de deck jouables en tournois moderne (parmi 12k cartes), et d'une centaine en vintage (toutes les cartes) d'après le site mtg goldfish...

Répondre à ce commentaire

Par Anonymous, il y a 2 mois :

Oui ce jeu à une certaine complexité mais comme cela a déjà été dit le déroulement du jeu est extrêmement limité par le principe du deck. Les possibilités d'un joueur à chaque tour sont déterminé par ce dernier et par l'ordre dans lequel les cartes se retrouve dans celui-ci. Un joueur n'a au final plus grand chose d'autre à faire que de jouer son plan en fonction d'une pioche.
Un jeu qui fait appel au "hasard", parfois au bluff, ne devrai pas être considéré comme complexe. Il suffit de prendre un exemple très simple qui parlera à tous : La bataille avec un jeu de carte classique.. C'est aussi considéré comme complexe je suppose vu qu'aucun ordinateur ne peut calculer la manière de gagner à coup sûr..
Je joue à Magic depuis longtemps et j'aime bien ce jeu mais étant aussi joueur passionné d'échecs, il m’apparait très clair que ce jeu de carte est en comparaison bien moins complexe et nécessite bien moins de réflexion.

Répondre à ce commentaire

Par Seak, il y a 2 mois (en réponse à Anonymous):

La complexité pour une IA ne vient pas d'avoir "un deck" mais de devoir géré toute les situations possible qu'amène 18000 potentiel cartes "adverse" dans un duel de Magic, il n'y a pas qu'un seul deck mais deux et sur un premier duel dans un jeu avec 18000 cartes il est absolument impossible d'anticiper ce que fera ton adversaire et la structure de son deck, le tout sur plusieurs phases : Upkick, Draw, mainphase 1, Combat phase : Déclaration des attaquant, déclaration des bloqueurs, Résolution, mainphase 2, fin de tour. Et avec plusieurs type de sort jouable a des moments différent (rituel / ephèmere) qui complexifie le tout.

Réduire la complexité de magic a un deck de 60 cartes c'est ridicule. Les possibilité sont évidement réduite en fonction de la pioche, mais le deck building lui doit prendre en compte cette aspect là, le manascrew, et pouvoir contré le maximum de situation possible (merci le side de 15 cartes). Et une fois en jeu, tu ne jouera pas la même mains de la même manière en fonction du deck adverse (ou de la meta). Bref. Il ne faut pas confondre complexe et compliqué.

Répondre à ce commentaire

Par alala, il y a 2 mois (en réponse à Seak):

du coup yuhiog plus dur que magic :o '-'

Répondre à ce commentaire

Par Seak, il y a 2 mois (en réponse à alala):

A partir du moment ou tu ne peux pas interagir pendant le tour de ton adversaire le jeu est déjà bien moins complexe. Donc clairement non. Le jeu a moins de cartes, moins de phases de jeu pendant un tour. YuGi'oh c'est du niveau Hearthstone avec des cartes en plus.

Répondre à ce commentaire

Par Comprendre Interstellar en 4 leçons, il y a 2 mois (en réponse à Seak):

On a pas dit que Magic était prévisible ni le moins complexe. On dit simplement que leur étude est biaisée, puisque les decks ont des archétypes avec des plans de jeu, ça n'empêche que certaines parties peuvent se montrer spectaculaire en rebondissements. Mais le plan d'un deck est lui prévisible , aggro, midrange, controle, meule, etc... qui se reposent sur un certain nombres de "win condition", d'autant plus que les decks sont construits suivant une courbe de mana, donc l'aléatoire n'est pas total au niveau de la pioche.
En plus, les phases de jeu Magic et Yugioh sont exactement les mêmes, avec des noms différents.

Répondre à ce commentaire

Par Seak, il y a 2 mois (en réponse à Comprendre Interstellar en 4 leçons):

Je vois pas en quoi c'est biaisé car les decks ont des plan de jeux ... Une même carte peut être jouer dans différents plan de jeu (que ce soit midrange ou aggro ou whatever) et quand je parle de carte je parle pas d'un land ou d'un sort de contrôle mais bien d'une carte clé/maitresse.

D'ailleurs je vois même pas le rapport entre ce que tu dis et ce que tu cites en anglais dans l'étude. L'étude cite même des cas concret. Et comme tu l'a cité sur des

Ensuite les phases entre YuGi Oh ont beau être similaire (juste le nom en fait), elle ne sont pas comparable par le simple fait que ton adversaire ne peut pas agir pendant tes phases sur YuGiOh, donc malgré leurs nom commun les actions offertes au deux joueurs ne sont pas identique. Ce qui complexifie le truc. Ma réponse sur la complexité via de la
Je cite "il m’apparait très clair que ce jeu de carte est en comparaison bien moins complexe et nécessite bien moins de réflexion."

L'étude te dis que c'est plus complexe que d'autre jeux pour plein de raison et que le nombre de cartes en fait parti mais n'est qu'un facteur "aggravant".

L'IA a du être codé pour fonctionner et tenter des choses pour gagner. lisez donc la parti sur comment faire comprendre a l'IA la légalité d'un coups dans magique, c'est intéressant. Le coté "Cartes et plan de jeu c'est trivial" vous ne faite qu'effleurez le fond du problème soulevez par l'étude.

Répondre à ce commentaire

Par Comprendre Interstellar en 4 leçons, il y a 2 mois (en réponse à Seak):

Ils disent dans leur introduction que leur expérience s'applique au tournoi en mode standard ( le tounoi officiel) , hors c'est faux pour les raisons que j'ai cité.
En plsu,ça se voit que tu ne joues pas à Yugiho, puisque le principe d'une carte piège/magie rapide c'est d'agir pendant le tour de l'adversaire, et il existe aussi les "Hand Trap" qui sont utilisables n'importe quand.

Répondre à ce commentaire

Par Seak, il y a 2 mois (en réponse à Comprendre Interstellar en 4 leçons):

Le format n'est pas le standard mais bien les tournoi legacy, quand tu regarde les cartes cité et la composition du deck utilisé, il n'y a aucune carte standard dans le tas.

Pour YuGi'Oh si t'as jouer un peu a Magic, tu ne devrais vraiment pas comparé les deux. Tu compare vraiment les pièges de YuGiOh en termes de possibilité sur des tours adverse avec ce qu'on peut faire dans Magic ? Capacité de créature (ou d'enchant, artef), de mana, les éphémères, les flash etc? Ne serait-ce que garder des terrain untap pendant le tour de ton adversaire met une pression psychologique. faut oser comparé la profondeurs de certaines actions de magic avec YuGi'Oh (pourtant j'aime bien les deux).

Répondre à ce commentaire

Par Bolas, il y a 2 mois (en réponse à Anonymous):

Joue commander tu verras sur 100 cartes si tu as la chance de faire tourner ton deck exactement dans la situation que tu veux ;) c'est déjà beaucoup plus dur.

Répondre à ce commentaire

Par Comprendre Interstellar en 4 leçons, il y a 2 mois (en réponse à Bolas):

Ils ne parlent pas des modes de jeu annexes, pas la peine d'essayer de justifier avec des arguments hors sujet.

Répondre à ce commentaire

Par Zirak, il y a 2 mois (en réponse à Comprendre Interstellar en 4 leçons):

Ah mon avis, même en mode standard, la difficulté peut venir du fait que même si il y a des listes "optimisées" pour chaque archetype / plan de jeu, au final, des listes peuvent différer de plusieurs cartes, donc même si tu "reconnais" l'archetype de ton adversaire, tu ne peux jamais être sûr à 100% de ce que va contenir ta liste.

De même qu'il y a le fait que suivant les archetypes, en fonction de ton ordre de pioche, tu n'as pas du tout le même pourcentage de victoire, voir même aucune chance même avec la pioche parfaite. Il ne faut pas oublier non plus le fait que tu ne pioche pas (ou trop) de land, pas les bonnes couleurs, etc. etc. Ce qui peut énormément remettre en cause ton plan de jeu ou celui de ton adversaire. Cela induit le fait qu'il n' s'agît pas simplement de jouer des coups parfaits pour gagner, il y a toujours l'aléatoire de la pioche.

Sans parler de la réserve, qui peut renverser complètement la situation et changer complètement de plan de jeu, réserve qui peut se retrouver bien différente dans un même archetype d'une meta locale à une autre. Il ne faut pas oublier que Magic est un jeu prévu pour être joué en BO3 et non en une seule manche, il faut donc prendre en plus la complexité des différentes adaptations possibles au cours des autres manches pour l'IA.

Il y a également les histoires de couches au niveau des effets avec les priorités des uns sur les autres qui peut / doit jouer sur la complexité du truc.

Pour ma part, je ne m'y connais pas assez (ce n'est pas mon domaine de développement) pour dire si leur étude est biaisée ou non, et si Magic peut être assimilé par une IA ou non (après ce n'est peut-être juste qu'une question de temps / matériel / connaissances), mais en soit, je comprends tout à fait, à la fois en tant que développeur et joueur de Magic, que la chose ne soit pas aisée à faire... :D

Répondre à ce commentaire

Par Zirak, il y a 2 mois (en réponse à Zirak):

D'ailleurs j'ai survolé rapidement l'étude, je pense qu'il y a une petite confusion, il s'agît de tournoi au format Legacy (qui est un format standard de Magic, comme le moderne, le vintage, le standard et le limité), et non pas au format "Standard" limité aux dernières éditions. :)

Répondre à ce commentaire

Par Avatar of woe, il y a 2 mois :

Et les cartes a voix multiple, counter spell ou les cartes qui joue directement tes cartes a partir de ta bibliothèque ? Quand on sait que ce ne sont que des cartes seuls qui son déjà complexe a intégrer alors les combos...

Répondre à ce commentaire

Par Avatar of woe, il y a 2 mois :

A noter que les cartes cité offre de multiples choix non orchestrés par le plans de deck

Répondre à ce commentaire

Par Avatar of woe, il y a 2 mois :

Enfin le but est de vaincre le plus large panel de decks, donc avoir la possibilité de s'adapter selon la situation, sinon un même deck n'aurait pas beaucoup d'utilité.

Répondre à ce commentaire

Par RTS_Gamer, il y a 2 mois :

"il est possible de créer un scénario dans le jeu, dans lequel il n'y a aucun moyen de calculer la stratégie gagnante."

A moins d'être un puits de connaissance de toutes les cartes et de toutes les strat existantes, il est souvent difficile de prévoir une stratégie parfaite de A à Z conduisant à la victoire, sans adapter sa stratégie face à la stratégie de l'adversaire.


"aucun d'eux n'atteignent une complexité aussi forte que le jeu étudié ici. En effet, l'une des raisons qui peut expliquer cette difficulté réside dans l'énorme volume de cartes disponibles, le nombre de phases au cours d'un tour pour un joueur et bien entendu, des règles qui n'ont cessé d'évoluer tout au long des 26 ans au cours desquels sont sorties les extensions !"

L'existence d'un pool de cartes énormissime et la longue durée du jeu et son évolution sont effectivement des arguments, mais je me pose quand même la question de la comparaison en termes de complexité sur ces seuls aspects : considèrent-ils que plus l'on à de paramètres à tenir compte lors d'un building de decks dans une perspective de métagaming, plus le jeu est complexe ?

Répondre à ce commentaire

Par Seak, il y a 2 mois (en réponse à RTS_Gamer):

En realité c'est complexe car dans la milliers de cartes utilisable en legacy, il y'a enormement de wording (comprendre les effets des cartes) et donc plus il y'a d'effet différents, plus les interactions entre les effets sont complexe (et donnes des situations complètement folles). Il y'a tellement d’interaction possible entre les cartes que l'IA doit comprendre la légalité des actions, lors dans lequel celle-ci s'effectue (la pile ou la priorité, cas qui nécessite souvent l’intervention d'un juge en tournoi) ce qui n'est de base pas déjà donner a tout le monde, et donc pour que cette IA comprennent les actions, il faut déjà que les gens qui développe cette IA comprennent les actions et interactions possible entre les cartes. Pour ce faire une idée de la complexité que peu atteindre magic, il faut voir les questions poser au juges dans le cadre de leurs monté en niveau dans les examens, et mon dieu... souvent ca pique.

Répondre à ce commentaire

Laisser un commentaire

Votre adresse e-mail ne sera pas visible. Pour avoir une image de profil, utilisez le service gravatar.

Tu es membre premium car tu as commandé une HITEKBOX. Tu peux donc ajouter des smileys et des images.

Derniers tests
Test Huawei Mate 20 Pro, un capteur de 40 mégapixels et un grand écran OLED : fiche technique, prix et date de sortie

Huawei Mate 20 Pro

Il y a 2 semaines

Note : 9,4
Test Samsung Galaxy S10+, un processeur plus puissant, une nouvelle interface et 4 capteurs photos : fiche technique, prix et date de sortie.

Samsung Galaxy S10+

Il y a 2 semaines

Note : 8,6
Test OnePlus 7 Pro, le tout nouveau haut de gamme de la marque : fiche technique, prix et date de sortie

OnePlus 7 pro

Il y a 2 semaines

Note : 9