Journal Magic: the Gathering, le problème de l'arrêt, et une inférence un peu rapide

Posté par . Licence CC by-sa.
42
10
mai
2019

Slate m'offre, dans un article récent, le moyen de concilier mes trois passions : l'informatique théorique, le jeu de société, et me moquer des journalistes.

Ça commence donc par un article plutôt banal sur arXiv : les auteurs ont, à partir de deux decks très spécifiques (mais légaux selon les règles du jeu de société Magic), réussi à créer une machine de Turing. Machine de Turing un peu particulière puisqu'elle mène à la victoire du joueur A si et seulement si elle s'arrête. Ils appliquent donc à cette machine de Turing le problème de l'arrêt : comme l'arrêt de cette machine de Turing précise est indécidable, il existe au moins un cas de partie de Magic indécidable. Les auteurs en concluent que construire une intelligence artificielle sous forme d'arbre des possibles pour Magic est impossible, ce qui est une maigre avancée, mais une avancée quand même : jusqu'ici, on savait "juste" que c'était une très mauvaise idée.

Le point qui est intéressant et nouveau, c'est que Magic devient ainsi le premier jeu réel (et non seulement théorique) indécidable : que ce soit le go, les échecs, Dominion ou whatever, on ne connaissait pas de jeu réellement pratiqué dont on ne puisse prédire s'il allait s'arrêter (autrement dit : tous les jeux de société autres que Magic finissent nécessairement par atteindre leur condition de fin de partie, du moins jusqu'à de plus amples recherches).

À partir de là, la machine (médiatique, pas de Turing) s'est un peu emballée. Kotaku, site spécialisé dans le jeu vidéo et la culture geek, publie Magic the Gathering est si complexe qu'il pourrait planter un ordinateur. Ce qui est formellement vrai, mais uniquement dans la configuration très particulière décrite par les auteurs. Point amusant : l'article original fait abstraction de la grosse majorité des cartes de Magic (et donc de sa complexité), puisqu'il n'en utilise même pas 200 sur les plus de 20000 publiées à ce jour. Slate va alors reprendre l'info et achever de ruiner la (déjà maigre) crédibilité de sa rubrique sciences avec l'article cité plus haut : «Magic: The Gathering» est le jeu le plus dur au monde. On y trouve quekques phrases magiques comme :

Magic a le plus grand quotient de complexité informatique connu

(J'aimerais bien savoir ce qu'est ce quotient, je n'en ai jamais entendu parler)

L'ordinateur, pensé pour calculer les pièges, les stratégies à adopter et les probabilités de victoire, a été incapable de déterminer qui remporterait la partie.

(Alors… C'est juste sans aucun lien avec l'article en question)

Bref, on part de "nous avons réussi à coder une machine de Turing avec une partie vraiment très spéciale de Magic: the Gathering" pour arriver à "Magic: the Gatherinc est si complexe qu'il pourrait planter un ordinateur" et enfin à "Magic: the Gathering est le jeu le plus dur au monde".
Ça me rappelle une histoire déjà publiée sur linuxfr :

C'est un biologiste, un physicien et un mathématicien qui vont à un congrès à Glasgow, en Écosse. Le biologiste regarde par la fenêtre, voit un mouton noir, et s'étonne :
-- Tiens, je ne savais pas qu'en Écosse, les moutons étaient noirs !
Le physicien le reprend :
-- Votre inférence est un peu rapide. Tout ce que vous pouvez dire, c'est qu'il y a des moutons noirs en Écosse.
Le mathématicien le reprend à son tour :
-- Votre inférence est un peu rapide. Tout ce que vous pouvez dire, c'est qu'il existe en Écosse au moins un champ contenant au moins un mouton, dont au moins un côté est noir !

  • # inférence un peu rapide

    Posté par . Évalué à 10 (+15/-1).

    L'inférence du mathématicien est un peu rapide, tout ce qu'on peut dire c'est qu'il existe en Écosse au moins une fenêtre par laquelle, pour au moins une portée de temps définie, on peut voir au moins un mouton dont un côté apparaît noir, ce dans un champ donné.

    ------> [ ]

  • # C'est pas le seul

    Posté par (page perso) . Évalué à 7 (+5/-0).

    Voici une liste (en anglais) de machins qui se sont avérés être Turing-complet : http://beza1e1.tuxen.de/articles/accidentally_turing_complete.html

    • [^] # Re: C'est pas le seul

      Posté par (page perso) . Évalué à 2 (+0/-0).

      C'est super intéressant ! Ce qui m'impressionne c'est la diversité des système qui peuvent être transformés en machine de Turing.

      Si l'on connait les caractéristiques d'une machine de Turing, est-ce que l'on connait les propriétés qui permettent d'en construire une ? (À première vue, le jeu de la vie ne partage pas grand chose avec Magic…).

      • [^] # Re: C'est pas le seul

        Posté par (page perso) . Évalué à 3 (+1/-0).

        Bon, alors l'info théorique, j'en ai pas fait depuis des années… Je pense tout de même que ta question est "à l'envers". On connaît la définition d'une machine de Turing, donc pour en construire une, tu peux faire ce que tu veux, à condition que ça colle à la définition ! Y'a plein de manières différentes d'y arriver. En ce qui concerne le jeu de la vie et MTG, ce qui est intéressant, c'est qu'on s'est rendu compte qu'on pouvait coder des machines de Turing avec. Ça ne veut pas dire pour autant que le codage de la machine est trivial…

        Des manières de créer une machine de Turing, il doit y en avoir une infinité. Si tu veux en faire une nouvelle, invente des règles qui permettent de coller à la définition. Ou invente des règles qui permettent de coder une autre implémentation existante (comme Magic ou minecraft).

      • [^] # Re: C'est pas le seul

        Posté par . Évalué à 4 (+2/-0).

        Le Brainfuck contient 8 instructions et est Turing-complet. Les 8 instructions sont :
        - + : Incrémente de 1 la case mémoire en cours
        - - : Décrémente de 1 la case mémoire en cours
        - [ : Pas d'effet.
        - ] : Si la case mémoire en cours contient 0, pas d'effet. Si la case mémoire en cours ne contient pas 0, rembobine la bande jusqu'au [ correspondant.
        - > : Passe à la case mémoire précédente
        - < : Passe à la case mémoire précédente
        - . : Affiche le contenu de la case mémoire en cours
        - , : Demande à l'utilisateur d'entrer un nombre, le stocke dans la case mémoire en cours

        La dernière instruction n'entre pas dans la définition d'une machine de Turing puisqu'elle a le droit d'être initialisée avec une mémoire non vide. On peut donc considérer que tout langage qui contient au moins une boucle conditionnelle, un moyen de compter de 1 en 1 dans les deux sens, un moyen de changer de case mémoire et un moyen d'afficher son résultat est Turing-complet.

        Ça, ce sont les sources. Le mouton que tu veux est dedans.

  • # nombre de cartes

    Posté par . Évalué à 3 (+1/-0).

    sur les plus de 20000 publiées à ce jour.

    D'où vient ce chiffre ? Est-ce qu'il comptabilise les rééditions, les versions "shiny", les cartes ayant changé de nom ou d'illustration selon les versions comme étant une seule carte ou comme étant plusieurs cartes différentes ?

    Parce que comme dirait un célèbre joueur de Contre-sirop : « Ce qui compte c'est les valeurs. »

    • [^] # Re: nombre de cartes

      Posté par . Évalué à 2 (+0/-0).

      Autant pour moi, c'est pas plus de 20000, c'est presque 20000.

      Ça, ce sont les sources. Le mouton que tu veux est dedans.

      • [^] # Re: nombre de cartes

        Posté par . Évalué à 2 (+0/-0).

        Quand je vais sur le lien de la note de bas de page 1 j'ai rien qui sort du moteur de recherche officiel vu qu'il a changé de comportement.

        Puis sur la note 2 concernant le total de cartes blanches, le lien me donne un chiffre bien inférieur au résultat antérieur.

        Enfin en testant un peu le moteur, j'ai certaines cartes en français qui n'apparaissent pas avec une recherche en anglais (exemple : "Marais" va me sortir deux terrains de base, "Swamp" ne va m'en donner qu'un seul des deux)

        Donc avec de telles différences et sans reproductibilité possible, difficile de savoir ce qui était comptabilisé dans ces chiffres.

      • [^] # Re: nombre de cartes

        Posté par . Évalué à 2 (+1/-0).

        19 641 si je compte le nombre d’éléments de AllCards.json (récupéré sur MTGJSON, projet fort sympa).

    • [^] # Re: nombre de cartes

      Posté par (page perso) . Évalué à 3 (+1/-0).

      19036 cartes à ce jour.
      18574 cartes quand on exclut les sets "humoristiques" (unglued, unhinged, unstable)
      18466 cartes valides dans le format "legacy", valide en tournoi.
      1764 cartes valides dans le format "standard", valide en tournoi.

      Les nombres ci dessus sont des cartes avec un nom uniques: les variantes "foil" (ce que tu appelles shiny), ainsi que les rééditions d'une même carte sont comptées comme une seul carte. En revanche, certaines cartes assez basiques sont rééditées à l'identique en termes de capacités, mais avec un nom différent pour mieux coller à l'édition dont fait partie la carte. N'ayant pas le même nom, elles sont considérées comme des cates différentes.

      • [^] # Re: nombre de cartes

        Posté par (page perso) . Évalué à 3 (+1/-0).

        Wikipédia me contredit, et effectivement il doit y avoir un soucis avec ma requête pour le nombre total de cartes toutes éditions confondues, mais les autres chiffres doivent être corrects.

        • [^] # Re: nombre de cartes

          Posté par . Évalué à 2 (+0/-0).

          La page anglophone de Wikipedia a le même problème que gamepedia : le moteur de recherche officiel a changé du tout au tout entre temps.

      • [^] # Re: nombre de cartes

        Posté par (page perso) . Évalué à 3 (+1/-0). Dernière modification le 10/05/19 à 18:19.

        Il faut voir aussi que le jeux n'aide pas trop, sachant qu'il y a des cartes à deux faces, à deux sens, avec deux cartes sur une face, ou à construire avec deux cartes.

        • [^] # Re: nombre de cartes

          Posté par . Évalué à 3 (+1/-0).

          oui ils ont testé des trucs en cours de route. Il me semble que c'était moins compliqué il y a un peu plus de vingt ans quand j'y jouais encore.

          • [^] # Re: nombre de cartes

            Posté par . Évalué à 2 (+1/-0).

            Au contraire, les règles et les mécanismes ont été largement simplifiés. Rien que l'apparition de la stack (chaque sort s'empile et se résout avant le précédent pendant une phase) est une simplification énorme par rapport à avant. De la même manière, la formulation des cartes récentes laisse beaucoup de moins de place à l'interprétation (foireuse). En format standard, les règles sont plutôt simples et précises. En modern, c'est un peu plus exotique parfois. Mais ce sont plutôt les vieilles cartes de legacy ou vintage qui ont parfois des fonctionnements et des interactions étranges, mais bien documentées sur Magic Gatherer.

            • [^] # Re: nombre de cartes

              Posté par (page perso) . Évalué à 3 (+1/-0).

              La pile c'est quand même pas nouveau, j'ai commencé à jouer en 1995, et ça existait déjà, alors que le jeu date de 1993. Les règles se sont précisées mais il y a surtout eu un changement de règle avec l'arrivée de la 6ème édition je crois, qui faisait que les blessures de combat passaient par la pile. Cela avait des effets de bord en terme de cohérence. Quelques années plus tard les règles ont à nouveau changé pour revenir comme avant sur cet aspect. Dans les anciennes règles, on pouvait aussi engager un artefact pour le désactiver.

              Pour ce qui est de la formulation, oui ça s'est bien amélioré. Ils ont beaucoup utilisé de mots-clés pour définir des mécaniques existantes, ce qui permet de savoir assez rapidement ce que fait une carte. La contrepartie c'est qu'il y a un paquet de mots-clés.

              Il faut aussi savoir que ce qui est écrit sur la carte ne fait pas forcément foi: c'est le texte Oracle de la carte qui fait foi. Certaines anciennes cartes ont ainsi subi des modifications, notamment au niveau des types. Avec l'apparition récente du type de créature "dinosaure", certaines anciennes cartes ont donc vu leur type mis à jour, parce qu'elles étaient plus conforme à ce qu'elles étaient vraiment. Exemple: Fongosaure, Raptor Putride.

      • [^] # Re: nombre de cartes

        Posté par . Évalué à 3 (+1/-0).

        N'ayant pas le même nom, elles sont considérées comme des cates différentes.

        Ce qui est pas très cohérent vu que peu importe l'édition la carte reste la même.

        Après je suis sûr qu'on peut trouver d'autres créatures de même coût, même force et mêmes compétences, du genre une 2/2 qui coûte deux marais et ayant uniquement Vol (je dis nawak c'est pour l'exemple).
        Pour moi, c'est pareil c'est la même carte avec un nom différent et ça change pas le jeu.

        • [^] # Re: nombre de cartes

          Posté par (page perso) . Évalué à 7 (+4/-0).

          Sauf si d'autres cartes jouent sur le nom des créatures (bonus/malus aux gobelins par exemple).

        • [^] # Re: nombre de cartes

          Posté par (page perso) . Évalué à 7 (+5/-0).

          Si ça change le jeu. Comme il y a une limitation qui empêche d'avoir quatre cartes identiques (hors terrains) dans le jeu, il y a des stratégies pour avoir des cartes similaires, mais pas identiques, et ainsi construire un deck cohérent. (Je pense par exemple à un deck "petites créatures" genre 1/1, 1 mana d'invocation)

          Si l'on part du principe que toutes ces cartes sont les même, cela change la construction du deck, en limitant à 4 créature identiques au lieu d'en avoir 16, 20 ? Ou cela lève cette limite de quatre cartes, et donc change radicalement les possibilités de jeu.

          Je te rejoins que dans la partie, cela revient au même, mais cela change les cartes qui ont été mise dans le jeu en amont de la partie, et donc, la manière dont on joue :)

        • [^] # Re: nombre de cartes

          Posté par (page perso) . Évalué à 3 (+2/-0). Dernière modification le 11/05/19 à 13:56.

          Ce qui est pas très cohérent vu que peu importe l'édition la carte reste la même.

          Mais financièrement intéressant ; seuls les cartes des 2 dernières années (en gros) sont autorisées en tournoi sponsorisé, ce qui incite à les racheter quand même ;).

          • [^] # Re: nombre de cartes

            Posté par . Évalué à 0 (+0/-1).

            C'est faux. On a parfaitement le droit d'utiliser une ancienne édition d'une carte ou une carte étrangère en tournoi. Le texte, l'édition ou la langue de la carte n'a aucune importance, tant que le nom anglais de ta carte est considéré comme valide en standard (ou dans le format de la compétition) tu peux l'amener en compétition.

            • [^] # Re: nombre de cartes

              Posté par . Évalué à 3 (+1/-0).

              Mais pas une carte de même caractéristiques (attaque/défense, type, prix, couleur et texte) mais avec un nom différent. Par exemple s'ils créent un artefact qui pour 0 quand tu le sacrifie te permet d'ajouter 3 manas de la couleur de ton choix à ta réserve1, ça ne t'autorisera pas à jouer le lotus noir, je présume ?


              1. on est d'accord, ils le feront pas :) 

          • [^] # Re: nombre de cartes

            Posté par (page perso) . Évalué à 3 (+1/-0).

            Les cartes rééditées "à l'identique" (i.e. avec exactement les mêmes caractéristiques sauf le nom) sont le plus souvent des communes sans valeur. Les rééditions "similaires" de cartes plus rares ont des modifications fonctionnelles qui font que ce n'est pas la même carte.

            • [^] # Re: nombre de cartes

              Posté par (page perso) . Évalué à 1 (+0/-0). Dernière modification le 15/05/19 à 18:22.

              D'un point de vue technique, tu as raison bien sûr.
              Une carte quasi-identifique, mais avec un mana de plus ou moins, un type étendu, ou un mot-clé additionnel, ce n'est pas strictement la même bien sûr…
              Raison de plus pour la racheter ;).

  • # Et le berger...

    Posté par . Évalué à 10 (+17/-0).

    Et là, le berger arrive et dit: "bande de ***, c'est pas un mouton, c'est mon chien"

  • # Vraiment surprenant ?

    Posté par . Évalué à 3 (+2/-1).

    Je ne comprends pas trop où est la surprise, étant donné qu'on peut écrire à peu près n'importe quoi dans les cartes.

    J'ai l'impression qu'il serait trivial, par exemple, d'écrire un jeu fini de cartes ad hoc permettant (en mettant le nombre suffisant d'instances dans son deck) d'encoder n'importe quelle machine de Mealy à 2 compteurs.

    Je n'ai pas lu l'article, mais peut-être que la vraie découverte c'est que le jeu est Turing-complet avec les cartes déjà existantes ? (cela dit, étant donné toutes les cartes qui existent, ce n'est pas très surprenant non plus… )

    • [^] # Re: Vraiment surprenant ?

      Posté par . Évalué à 3 (+1/-0).

      Je me réponds à moi-même : le journal dit bien que la démonstration utilise 200 cartes parmi les 20000 existantes.

      Le résultat n'était peut-être pas surprenant, mais l'exercice n'était donc pas trivial.

      • [^] # Re: Vraiment surprenant ?

        Posté par (page perso) . Évalué à 3 (+1/-0).

        La publication se lit assez bien, n’hésite pas à y jeter un œil.

        Je ne sais pas s’ils sont surpris mais ce qu’ils expliquent c’est que ça «invalide» des choses existantes sur la modélisation des jeux de stratégie qui partaient du principe que ceux-ci n’étaient pas turing-complet et pas aussi complexes (déterminer l’issue d’une partie de Magic dans la situation décrite dans le papier est NP-Complet, avec uniquement des actions contraintes de la part des joueurs)

        • [^] # Re: Vraiment surprenant ?

          Posté par . Évalué à 2 (+0/-0).

          En même temps, Magic est un peu particulier en tant que jeu.

          En fait, je réfléchis depuis quelque temps à comment l'implémenter mais c'est déjà incroyablement compliqué rien que de s'assurer que tous les mécanismes du jeu sont pris en compte et que l'ajout d'une nouvelle carte ne va pas remettre en question tout le moteur du jeu (i.e. juste écrire la machine qui simule le "programme" décrit par une instance du jeu, on est loin de vouloir vérifier des propriétés dessus).

          De là à vouloir écrire une IA sans faire de grosses hypothèses simplificatrices…

          • [^] # Re: Vraiment surprenant ?

            Posté par . Évalué à 2 (+1/-0).

            Autant que je sache il n'y a d'IA officielle actuellement qu'en format standard actuel ou l'ancienne appli Android et donc l'ancien format standard. Et sur l'appli MTG Arena, les IAs utilisent des decks préconstruits pour simplifier la problématique. J'imagine qu'au delà du format standard, les timings bizarres de certaines cartes doivent vraiment désavantager l'IA.
            Au sujet de l'implem des règles du jeu et des cartes, il paraît que le moteur de MTG Arena est implémenté principalement en analysant le texte des cartes et non pas en implémentant chaque carte une par une. Par contre, j'ai complètement oublié où j'ai lu ça.

            • [^] # Re: Vraiment surprenant ?

              Posté par . Évalué à 3 (+1/-0).

              Je confirme, l'ia à des soucis pour jouer, mais les humains aussi, typiquement une combo pas chère qu'on peut faire avec les deck de base de MTG arena harpie vorace avec act of treason permet de prendre le contrôle d'une créature de l'adversaire, attaquer avec puis la sacrifier aux harpies.

              Je suis tombé plusieurs fois sur des gens prenant le contrôle, puis sacrifiant immédiatement sans attaquer, c'est un peu dommage.

              Par ailleurs, la plupart des capacités sont par mot clé, alors qu'il y'a 20 ans des capacité comme le contact mortel étaient écrite sur la carte :)

              Il ne faut pas décorner les boeufs avant d'avoir semé le vent

    • [^] # Re: Vraiment surprenant ?

      Posté par (page perso) . Évalué à 4 (+2/-0).

      À vrai dire, les articles de vulgarisation semblent s'être embalés, cf la mise à jour en fin de l'article de kotaku:
      https://kotaku.com/magic-the-gathering-is-so-complex-it-could-stump-a-com-1834623872

      Shortly after publication, Alex Churchill, one of the authors of the paper, responded to Kotaku in an email with some further clarifications on the group’s findings.

      “What we’ve proven is that the operation of “finding the best move in a game of Magic,” in the worst case, cannot be computed,” he said. “There are certain circumstances, even though they’re very contrived, where it’s proven that no algorithm can find whether there exists a winning move. In fact, since we eliminate all player choice, we’ve proved something slightly stronger: that it’s impossible in the general case for an algorithm to look at a board state and see whether it’s possible for the game to end at all.”

      He went on:

      “This is what computer scientists care about when they talk about the complexity of an algorithm. The algorithm might be easy to solve in almost all cases, but we’ve shown that the worst case is as hard as it can be.”

      “This has very little implication for playing the game in practice, but it does have takeaways for potential AI designers. Probably anyone who was going to write an AI for Magic would not have made the AI choose its next move by trying to exhaustively compute all possible consequences of the current board state - that’d be crazy. They’d do it using heuristics, rules of thumb that give a best guess about how to play. Our paper just proves that the exhaustive computation approach is definitely not the way to go because it’s actually impossible (in some cases).”

      Il semble que le seul but de l'étude était de dire qu'il y a des cas où on ne sait pas dire qui va gagner ou pas, et si la partie va finir ou pas. Ils ont fait leur test en format legacy, mais rien qu'en standard, qui possède pourtant beaucoup moins de cartes, il y a le deck Wilderness Reclamation où tu peux faire une boucle infinie grâce à l'infâme Nexus of Fate. Cette boucle te permettra de gagner sous certaines conditions, et dans les autres tu peux te retrouver à jouer un nombre de tours infinis. En tournoi papier il y aura sans doute un avertissement pour "slow play" (équivalent des pénalités pour non combativité dans les arts martiaux), mais certains noobs ne maîtrisant pas le deck le jouent sur Magic Arena (où il n'y a pas de pénalités, juste un timer qui se recharge) et se retrouvent donc à attendre que leur adversaire concèdent la partie d'ennui. La riposte trouvée a été de scripter l'intéraction et de juste dérouler le script et partir faire autre chose quand on est face à ce type d'adversaire.

      D'autres decks comme le deck Eggs sont notoirement connus pour être très longs et incertains dans leur manière de partir en combo (combo off), car tu ne sais pas si tu vas converger et réussir à gagner ou pas.

Envoyer un commentaire

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.