Magic : L’Assemblée et la machine de Turing
Après le scandale de Yuuya Watanabe – ce grand joueur professionnel de Magic expulsé lors de la compétition des Mythic Championship II de Londres après qu’un contrôle ait révélé que certaines de ses cartes étaient marquées – le jeu de cartes Magic: the Gathering revient sous les feux de la rampe pour de plus glorieuses raisons.
En effet, il s’avère que selon un groupe de chercheurs, le célèbre titre de Richard Garefield serait peut-être le jeu le plus complexe et imprévisible qu’il soit. L’intelligence artificielle n’est en effet pas capable de prédire les coups à jouer pour l’emporter, à cause du trop grand nombre de possibilités disponibles et des effets imprévisibles de certaines cartes.
Pendant longtemps on pensait qu’aucune IA ne pourrait jamais gagner aux échecs. Désormais, après avoir battu les humains aux échecs, au go, et même à Starcraft II, les ordinateurs s’attaquent désormais à Hanabi comme nous vous le disions dernièrement.
Mais Magic pourrait bien ne jamais pouvoir être résolu par une IA, les chercheurs disent actuellement que sa difficulté non calculable pourrait être l’exemple ultime de la complexité des jeux.
Illustration de Shiny Blue Robot – crédits BGG
À lire aussi : Magic fête ses 25 ans – retour aux sources avec Dominaria ?
L’équipe de scientifiques a en effet révélé dans son étude que Magic était semble-t-il plus complexe et plus imprévisible que les tous jeux traditionnels testés jusqu’alors. L’équipe de chercheurs en question est menée par la mathématicienne de l’université de Géorgie, Stella Biderman, secondée par Alex Churchill, chercheur indépendant et auteur de jeux de société à Cambridge, et Austin Herrick, analyste de données de l’université de Pennsylvanie.
« La question de savoir s’il est possible ou non qu’il y ait un jeu du monde réel dont la complexité de calcul est strictement plus difficile que Magic est une question philosophique intéressante « , ont-ils conclu.
Parmi les cartes citées dans l’étude se trouve « Menacing Ogre » de Planechase. Avec cette carte, les deux joueurs doivent secrètement choisir un nombre avant de le révéler en même temps. Celui qui a choisi la valeur la plus élevée gagne plus de force et de défense au prix de points de vie. Rien que cette règle peut rendre impossible la prédiction de l’issue d’une partie.
D’autres jeux de cartes reposent sur le même concept que Magic, on pense bien sûr à Hearthstone par exemple, mais aucun n’a autant de cartes et d’effets disponibles. Faut dire que les règles de Magic ont continué d’évoluer perpétuellement depuis sa création, en 1993, et compte désormais dans les 20 000 cartes environ.
LUDOVOX est un site indépendant !
Vous pouvez nous soutenir en faisant un don sur :
Et également en cliquant sur le lien de nos partenaires pour faire vos achats :
Daniel 13/05/2019
Deep Blue ou Deep Mind ? C’est pas tout à fait pareil!
Shanouillette 13/05/2019
Bonjour Daniel,
L’équipe qui a testé Magic a fait appel à Deep blue. Désolée si ce n’était pas clair.
Chercheur 13/05/2019
Je ne trouve aucun lien avec Deep blue Dan’s l’article scientifique qui en parle. D’où vient cette information ?
Jahz 13/05/2019
Oui je crois qu’il y a un soucis 🙂
Deep Blue c’est beaucoup trop vieux pour que quoi que ce soit d’actuel ne soit basé dessus, il est au musée maintenant 🙂
Deep Mind aurait été plus probable, mais ils ne s’intéressent pas à Magic à ma connaissance.
Shanouillette 13/05/2019
Oui ça me semblait étonnant également pour tout dire bon ce n’est pas mon domaine de compétence mais j’ai compris « basé sur l’algorithme de » comme une ancienne filiation ; et c’est bien ce que j’ai lu à plusieurs endroits plus spécialisés, mais en effet sur le document de l’étude original ce n’est pas spécifié, j’ai donc édité la news pour corriger cette mention.
Merci pour votre vigilance.
Liorel 13/05/2019
J’avais vu l’article sur Slate, et je crains que la machine médiatique se soit considérablement emballée à ce sujet. La publication originale (l’article de recherche dont tout est parti) n’a utilisé ni Deep Blue ni Deep Mind ni aucun logiciel d’IA. Elle s’est contentée de démontrer qu’on ne pouvait pas construire d’IA parfaite à Magic dans une configuration très particulière. En fait, le résultat est encore plus modeste : elle a « juste » démontré qu’il existait au moins une partie de Magic où on ne peut pas prédire le vainqueur (sans même essayer de gagner). Et elle a pris un chemin très tordu et très matheux pour ça.
J’en ai fait un journal sur linuxfr : https://linuxfr.org/users/liorel/journaux/magic-the-gathering-le-probleme-de-l-arret-et-une-inference-un-peu-rapide
Attention : ça convient au public d’informaticiens et de matheux de linuxfr, mais c’est technique 😉
Shanouillette 13/05/2019
Merci pour ces précisions ! Il nous faudrait un expert sur l’informatique théorique pour nos articles j2s qui traitent de ces sujets, car mine de rien les expériences se multiplient. je n’ai pas le bagage (c’est peu dire) pour éviter les errements et inexactitudes. et manifestement les sites plus spécialisés se fourvoient facilement ce qui n’en fait pas une source de vulgarisation fiable… :/
Daniel 13/05/2019
Shanouillette accepte mes excuses pour avoir mis en cause ton papier.
j’ai été voir l’étude et ils précisent qu’ils ont utilisé une Turing machine. C’est à dire un algorithme qui ne doit sa force qu’à sa puissance de calcul.
DeepBlue (d’IBM) est une Turing machine.
donc en ce sens le texte est correct.
Toutefois ces machines n’ont rien à voir avec celles qui font de l’IA aujourd’hui qui ont délaissé l’étude de l’arbre de tous les coups possibles (gigantesque au Go) pour du deep learning. Le deep learning recouvre notament l’analyse d’une base de données énorme de parties jouées ainsi que l’amélioration de son expérience de jeux en jouant un nombre tout aussi énorme de parties contre un adversaire virtuel Conçu comme lui.
Alphago et deepmind (de Google) sont des machines qui font du deep learning et qui ont battu les joueurs de Go et de Starcraft.
je me réjouis d’avance de voir quels progrès Deepmind fera sur Magic et ses 20000 cartes mais d’abord sur Hanabi
Shanouillette 13/05/2019
Merci pour ton commentaire ! Tu es tout excusé, comme je le disais ci-dessus (à peine une seconde avant que tu ne postes ce msg ^^), j’ai préféré éditer pour éviter toute confusion.
J’avoue ne pas franchement maîtriser (alerte euphémisme) ce sujet qu’est le deep learning.
Merci pour toutes ces précisions.
trode 15/05/2019
L’article démontre que Magic est un système Turing Complet (sous une configuration très particulière). Ils décrivent une configuration dans laquelle toutes les conditions sont requises pour disposer d’une machine de turing (c’est à dire, en gros, un ordinateur [plus être plus précis un ordinateur est une machine de turing à mémoire finie). Il devient théoriquement possible – en acceptant l’en codage très particulier à base de jetons de créature d’un type et d’une force donnée – de coder tout ce qui est encodable sur un ordinateur au sein d’une partie de Magic : faire des calculs mathématiques, du traitement de texte, un jeu de la vie, faire tourner une simulation d’une partie de Magic qui elle même fait tourner une simulation de Magic qui elle même …
En soit, ça n’a aucun intérêt autre que philosophique. Par contre, ça permet d’arriver à la conclusion qu’il existe au moins une configuration d’une partie de Magic dans laquelle l’issue de la partie n’est pas mathématiquement calculable, et même que la possibilité de la fin de cette partie ne soit pas démontrable (sans être un combo infini comme il en existe plein déjà, dans lesquels c’est le joueurs qui décide de répéter une action un nombre de fois infini, là c’est le jeu qui boucle tout seul sans plus aucune décision des joueurs 😛 ). Du coup, Magic est un jeu compliqué, oui. Mais trancher en « Magic a vaincu l’IA » c’est un peu se mélanger les pinceaux (merci d’avoir corrigé l’article ici, d’autres ne l’ont pas fait et sont resté dans le titre racoleur).
C’est dommage que les articles soient passés à côté de l’essentiel : on peut simuler une partie de Magic dans une partie de Magic ! Par contre faire les manipulations à la main est pas possible en une vie humaine, et il faut une table de taille théoriquement infinie ou presque, mais sur un logiciel approprié c’est faisable, laborieux, mais faisable. (pour d’autres exemples de jeu Turing complet : Minecraft par exemple, dans lequel plein plein de choses ont été implémentées).
praxis 09/01/2020
Merci pour l’article et aussi pour les commentaires, en particulier le message de trode. Je ne comprenais pas en effet comment Magic pouvait permettre la simulation de circuits logiques jusqu’à la mention de l’encodage de jetons de créatures.