Fonds marins

Magic : the Gathering

L’apprenti sorcier

Les ordinateurs ne dominent pas encore le monde, mais c’est pour bientôt, c’est connu. Le monde tremble depuis que des programmes maîtrisent Othello, qu’ils sont devenus les maîtres des échecs après la bataille de Kasparov-Deep Blue en 1996. Les humains rescapés se sont réfugiés dans des jeux aux possibilités plus grandes, comme le go, ou ... les cartes Magic, inventées en 1993 par Richard Garfield, et qui sortent de façon ininterrompue depuis. Pourtant, ce ne sont pas les tentatives qui manquent d’implémenter un joueur artificiel pour le produit phare de Wizards of the Coast. Petit tour d’horizon.

Décrire les règles de Magic rappelle un peu la situation du narrateur du Jeu des perles de verre : on peut en donner une définition grossière, mais impossible d’en résumer simplement toutes les subtilités, les raisons qui en font un jeu de société exceptionnel. Esquissons tout de même les principes ; ceux qui veulent plus de détails iront voir les tutoriaux officiels.

À chaque tour, le joueur a le droit de poser un terrain, qui lui donne un mana d’une certaine couleur (sur cinq en tout). Cette ressource lui permet d’acheter des créatures, qu’il lance à l’attaque contre l’autre joueur. L’adversaire peut bloquer cette attaque avec ses propres créatures grâce à un système simple de force/endurance. On peut également poser d’autres cartes qui ne sont pas des créatures (artefacts, enchantements, planeswalkers), et lancer des sorts ponctuels (rituels et éphémères) au bon moment pour influencer la partie. La complexité tient au fait que chaque carte ajoute généralement une règle ou plus, voire modifie complètement un aspect du jeu. Chaque extension, au rythme de trois par an plus un "core set", apporte son lot de méchanismes nouveaux, comme les cartes recto-verso en 2012. Au total, il y a plus de 9000 cartes autorisées en tournoi [1].

Un terrain, une créature, un sort : c’est parti !

Jeu aux nombreuses règles, univers fantasy : le créneau vidéoludique est tout trouvé, l’ordinateur aidant à gérer toutes les règles — qui se raffinent depuis des années, et changent encore régulièrement ; être juge de Magic n’est pas une sinécure. Le développement n’est toutefois pas si simple. Sans même parler d’une I.A. capable de jouer à Magic, la seule implémentation des règles du jeu est déjà difficile. Pour commencer, il n’existe (à ma connaissance) aucune plate-forme virtuelle proposant toutes les cartes physiques, même sur le logiciel officiel, Magic : the Gathering Online.

Plus grave, aucune n’implémente non plus complètement les règles, notamment celle qui concernent les boucles infinies qui peuvent survenir. Il arrive en effet des cas [2] où un joueur peut répéter une suite d’actions un nombre arbitraire de fois, et les règles spécifient bien qu’il a le droit de donner un nombre aussi grand qu’il veut. Cette notion est difficile à encoder dans une interface déjà chargée. Ce premier problème explique l’apparition de certaines plateformes (Cockatrice, Magic Workstation) qui n’appliquent aucune règle et laissent les joueurs responsables de la partie, se contentant de fournir le réseau social.

Shandalar, l’ancêtre

D’accord, il est raisonnable d’ignorer quelques règles très spécifiques, et de limiter le nombre de cartes. En 1997, alors que la hype de Magic commence à battre son plein, Wizards of the Coast juge encore trop complexe le développement d’une plateforme multijoueur. L’éditeur demande donc à MicroProse de créer un jeu solo, Shandalar (officiellement tout simplement Magic : the Gathering). Cette toute première représentation virtuelle du jeu marque les esprits pour plusieurs raisons. C’est le seul cas qui ne se limite pas au jeu de cartes : le joueur contrôle un personnage qui explore un monde (non sans similarités avec Darklands du même MicroProse), doit régulièrement acheter à manger, explorer des donjons, accomplir des mini-quêtes.

Même la partie jeu de carte a subi des interprétations : les matchs se font en misant une carte (un système originel de Magic abandonné depuis longtemps) ; le nombre de points de vie n’est pas fixé à 20 comme dans les règles officielles, mais varie selon l’ennemi. Et surtout, le jeu contient toutes les cartes les plus puissantes de Magic à l’époque et donc non seulement interdites dans la plupart des compétitions, mais même jamais rééditées et inaccessibles pour la plupart des joueurs.

Shandalar, version rajeunie.

Comme attendu, l’I.A. du jeu est souvent dépassée et elle ne fait jamais le poids à deck égal, à moins d’un coup de chance. Le jeu a cependant une difficulté élevée : les decks de départ sont boiteux et mal fichus, et on ne commence qu’avec très peu de points de vie ; les donjons contiennent des effets continus qui avantagent nettement les adversaires ; le fait que l’on mise à chaque match interdit d’en perdre trop à la suite, surtout lorsque l’on commence à avoir de bonnes cartes. A côté de ça, l’aspect "grosbill" du jeu, avec ses cartes surpuissantes qu’on ne voit jamais d’habitude, est très jouissif et de toute façon nécessaire : le boss final a plusieurs centaines de points de vie et un deck plutôt corsé. Pour finir le jeu, il faut donc mettre au point une combinaison de cartes interdisant pratiquement au boss de jouer. Ce n’est pas là du Magic tel qu’on le joue dans les boutiques de jeu de société.

Quelques années après le succès de Shandalar, de nombreux projets se lancent pour ajouter de nouvelles cartes et améliorer l’I.A.. Abandonnant la partie promenade dans les bois, Manalink (actuellement à la version 3.0) ajoute des cartes et un mode multijoueur. D’autres projets aux noms permutables fleurissent avec l’idée de tout recommencer depuis le début : Wagic, MagMa, Magarena, MAGE, Forge [3]... parmi ceux-ci, Forge — au développement arrêté, même si les nouvelles cartes seront mises à jour — propose un mode "aventure" intéressant où l’on peut faire évoluer son deck.

Forge, version 1.2.13.

L’insurmontable complexité

Dans son blog, le développeur de Forge explique les choix qu’il est amené à faire. Par exemple, la carte Force de sauvagerie est une créature qui a une endurance de zéro. Il est donc inutile de la jouer, puisqu’elle meurt instantanément, sauf s’il y a une autre carte sur la table dont l’effet est de relever son endurance immédiatement, comme une Antienne. Le développeur demande donc à l’I.A. de vérifier d’abord la présence d’une de ces cartes avant de jouer la Force de Sauvagerie. Ce sera effectivement un moyen fréquent de la jouer, mais un joueur un peu expérimenté de Magic pourrait donner dix autres moyens de la jouer efficacement : la solution est donc bancale, compromis entre efficacité et simplicité.

Plutôt que ces solutions ad hoc, on imaginerait donc bien un algorithme plus général. Mais les possibilités sont bien trop grandes. Je peux jouer un éphémère (une Foudre, par exemple) à n’importe quel moment — 10 fois par tour — et peux alors cibler n’importe quoi (joueur, créature, et je peux avoir des raisons de viser dans mon camp). Chaque choix n’a pas les mêmes conséquences selon l’endurance et les particularités de chaque créature ; enfin, il peut déclencher une série de réponses différentes selon les capacités de chaque carte en jeu. Si j’ai maintenant deux sorts, il faut multiplier les possibilités, et même plus, puisque l’ordre dans lequel je les joue — si je les joue tous les deux — change encore une fois le résultat.

Tout ceci sans même considérer le fait que l’information est partielle : l’adversaire a-t-il dans sa main de quoi contrer mon sort ? Va-t-il jouer une créature plus dangereuse dans les prochains tours, auquel cas je ferais mieux d’attendre ? De mon côté, est-ce que j’envisage au prochain tour d’utiliser toute ma réserve de mana, me privant de la possibilité de jouer ma Foudre — il vaudrait donc mieux la jouer maintenant ? Le choix possible d’un seul coup est donc énorme, bien plus grand qu’aux échecs ; et pour simuler une réflexion, l’algorithme devrait explorer l’arbre des coups possibles de part et d’autres — en faisant des suppositions sur l’information inconnue : pioche, main et deck de l’adversaire. L’explosion exponentielle de cet arbre vient alors rapidement à bout des faibles calculateurs de silicium, là où l’humain sait faire un tri instantané.

Duels of the Planeswalkers

Devant l’ampleur de cette difficulté, Wizards choisit en 2009 d’implémenter (via Stainless Games) la stratégie inverse des projets qui précèdent : la simplicité. Dans Duels of the Planeswalkers, les joueurs n’ont pas la possibilité de composer leurs propres decks. Ceux-ci sont pré-établis, les cartes choisies sont simples, et ils pratiquement tous monocouleurs (une seule ressource dans chacun). Les règles sont également largement assouplies. Ces contraintes ont permis de construire une I.A. très correcte, à quelques erreurs près. Le jeu est régulièrement actualisé et remis en vente avec de nouveaux decks, d’où une version 2012 et 2013, auxquelles s’ajoutent quelques extensions (encore de nouveaux decks).

Duels of the Planeswalkers : l’horrible révélation ...

Le choix de Wizards en vaut-il la chandelle ? De leur point de vue, oui : DotP est ouvertement une simple porte vers le jeu physique, un tutoriel pour apprendre à jouer, d’où son prix faible et sa simplicité. En cela, il est effectivement excellent et doit probablement attirer de nombreux joueurs dans les filets du lucratif système Wizards. Pour un addict déjà confirmé, par contre, il est difficile d’y trouver de l’intérêt. La quasi-absence de deckbuilding supprime la moitié de l’exercice et du plaisir. La plupart des matches ne propose pas de vrai choix et se joue sans réfléchir. Parfois même l’adversaire a un deck complètement absurde — comme celui qui propose 20 fois Guet des nuages + Pinacle de l’hélice + une créature pour bloquer (alors que les règles interdisent plus de 4 fois la même carte) — et on réprime alors difficilement un Alt-F4 rageur. Le titre se sauve en proposant des "défis", c’est-à-dire des puzzles, des situations préconstruites où il faut trouver la bonne combinaison d’actions. Contraint à l’extrême, le jeu réagit alors comme il faut.

En matière de joueur artificiel, on se retrouve donc devant un dilemme classique : si l’on soumet le jeu à de fortes contraintes, il est possible de construire des réponses efficaces, mais le joueur ne s’y amuse pas vraiment ; si l’on laisse trop de liberté au joueur, l’ordinateur ne sait plus jouer. Finalement, la seconde possibilité reste la plus viable, si l’on sait s’adapter. Car malgré tous ses défauts, Shandalar reste la référence en matière de jeu vidéo tiré de Magic, parce qu’il propose une expérience alternative à partir du principe de base, expérience que le mode aventure de Forge ravive presque. Malheureusement, la recherche de l’originalité de la part de Wizards n’a produit récemment qu’un l’abominable clone de Heroes of Might and Magic qui n’a de Magic que le nom. Les dernières extensions du jeu de cartes ont initié le retour vers des plans déjà visités précédemment (Mirrodin, Ravnica). N’est-il pas temps de revenir sur Shandalar ?

Ça ne marche pas bien, mais on en veut quand même :

Notes

[1] D’autres chiffres sont parfois avancés : ils prennent en compte les cartes aujourd’hui bannies, les éditions parodiques, les cartes de grande taille pour multijoueur, pour un total supérieur à 11000. Si on compte les éditions séparées, on arrive encore plus haut, bien sûr.

[2] Un exemple : la Druidesse dévouée prend des marqueurs -1/-1 et donne du mana vert. Au bout de 2 marqueurs, son endurance est de 0, donc elle finit par mourir : mais Mikaeus, le maudit la fait revivre en lui rajoutant un compteur +1/+1 (qui s’annule avec les -1/-1). En répétant cette opération X fois, le joueur obtient X mana, de façon illimitée.

[3] Disclaimer : je n’ai pas essayé tous les logiciels cités ici.

Il y a 7 Messages de forum pour "L’apprenti sorcier"
  • Steph Le 22 novembre 2012 à 12:09

    C’est dommage, on ne peut pas poser de questions ou emmerder l’auteur avec ce genre d’articles. C’est clair et instructif. J’ai appris des choses.

    Ah si ! Les caractéristique de ces jeux de cartes font-elles qu’il est plus difficile de créer une IA pour eux que pour un jeu de stratégie type Total War ?

  • Martin Lefebvre Le 22 novembre 2012 à 12:18

    Et l’absence de critique du consumérisme sans limite induit par Magic, vaut-elle résignation ? Steph je te trouve bien mou sur le coup. ;)

    A propos de Total War, je lisais une discussion assez intéressante sur les problèmes de endgame dans les jeux de stratégie 4x comme Rome TW. Donc oui je pense que c’est aussi assez compliqué de faire une IA pour les 4x, même si rien n’empêche dans ce cas les développeurs de construire le jeu autour de ce que l’IA sait faire, luxe que n’ont pas ceux qui adaptent des jeux existants, évidemment.

    Sinon pour ceux qui ne l’ont pas essayé, Richard Garfield a sorti un jeu avec des cartes dans le genre de Magic, mais pensé pour le solo contre l’ordi : Spectromancer, qui est pas mal du tout pour faire une partie de temps à autre, et qui en cette période de soldes de fin d’année doit se trouver pas cher.

  • Laurent Braud Le 22 novembre 2012 à 13:09

    Total War c’est un bon exemple parce qu’il est au tour par tour. La différence c’est qu’on sent qu’il y a des idées globales qui font à peu près le boulot et que c’est pas si grave si t’as fait une unité de trop par ici, un bâtiment par là.

    Magic c’est beaucoup plus sensible à toutes les perturbations : il y a une combinaison d’actions qui gagne, un point c’est tout. Les parties se jouent souvent au coup près, être sous-optimal c’est être complètement à côté de la plaque. Ca tient notamment au fait que les nombres manipulés sont assez petits, que "4 points de vie" c’est vraiment pas "3". C’est pour ça que le mode défi est pas mal dans DotP : les situations proposées ont bien l’air d’être perdantes et on est vraiment surpris quand on trouve la solution.

  • Pierre Corbinais Le 22 novembre 2012 à 22:51

    Je devais avoir quoi...dix ans...quand mon père a un bureau de tabac m’a acheté, sans raison aucune, un magazine Magic auquel était ajouté un CD de jeu vidéo Magic The Gathiring. J’ai passé genre DES MOIS sur ce jeux, c’était vraiment excellent, et peut-être était-ce à cause de mon jeune âge, mais je n’ai pas senti de faiblesse de l’IA, il y avait même un moyen d’importer mes decks physiques que j’avais construit pour les tester, vu que personne dans mon entourage ne jouait...

    ...et puis je me suis réveillé.
    True Story.

    Blague à part (ce n’est pas une blague, c’est tragique, mais bon ^^) je trouve super intéressante l’idée de ce jeu inadaptable. Magic serait un peu au jeu vidéo ce que Don Quichotte est au cinéma. Ce qui est amusant, c’est le parallèle avec le Go, qui est un au contraire jeu simplissime mais sur lequel l’IA n’est jamais parvenu à battre l’humain (l’humain balaise, j’entends). Les ordinateurs craindraient-ils les extrêmes ?

  • Cédric Le 23 novembre 2012 à 00:23

    Ah c’est cette complexité qui m’a toujours fait adorer Magic ! Mais il faut dire qu’avant la règle de la pile (qui date de la 5ème édition environ, si je me souviens bien) c’était encore plus compliqué. Je me souviens, avec nostalgie, avoir joué au 1er logiciel de Magic sur PC (celui que vous avez en capture d’écran), qui était moche, lent, mais malgré tout assez addictif (la possibilité de jouer des decks avec des cartes de 1ère édition complètement bugguées comme Ancestral Recall y était pour quelque chose). Aujourd’hui l’innocence de ma jeunesse a disparu, je bosse pour une boutique de vente en ligne de larimar... Snirf... Magic, je ne t’oublierai pas, tu resteras toujours dans mon coeur ! :)

  • roger Le 23 novembre 2012 à 09:25

    Juste un détail sur l’introduction pour être un peu chiant : Kasparov a vaincu Deep Blue en 1996. L’ordinateur a gagné l’année suivante, mais dans des conditions contestées ;). Je trouve d’ailleurs ça proprement incroyable qu’un être humain résiste aussi bien à un ordinateur capable de calculer des centaines de millions de coups à la seconde...

  • Le 23 novembre 2012 à 10:44

    Oopsie, effectivement, 1997.

    Le truc c’est qu’un humain sait apprécier d’un coup d’oeil si une configuration est favorable ou non (parfois, il se trompe, d’ailleurs), et se concentre sur celles qui l’intéresse. Un ordinateur, lui, doit trouver une mesure précise pour toutes les actions. Ca implique de vrais calculs et non une appréciation plus ou moins floue.

    Cependant il y aurait peut-être moyen de faire en sorte qu’un programme "apprécie" plutôt que "calcule". C’est l’opposition entre un système expert classique, qui applique des règles préétablies, et des trucs genre réseau de neurones, qui commencent par regarder plein de cas et en tirent des règles floues sans "savoir" pourquoi. Mais je n’ai pas rencontré de réseau de neurones qui joue à Magic, et j’ai des doutes sur la faisabilité vue la sensibilité aux perturbations dont je parlais plus haut.

    @Cédric : moi, j’essaie de retrouver l’innocence de ma jeunesse en continuant à jouer, mais mon portefeuille fait un peu la gueule ...

Laisser un commentaire :

Qui êtes-vous ? (optionnel)
Ajoutez votre commentaire ici

Suivre les commentaires : RSS 2.0 | Atom

© Merlanfrit.net | À propos | web design : Abel Poucet