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 Maclag . Évalué à 10.
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é.
------> [ ]
[^] # Re: inférence un peu rapide
Posté par lejocelyn (site web personnel) . Évalué à 10.
L'inférence de l'informaticien est un peu rapide, tout ce qu'on peut dire, c'est qu'il exi
# C'est pas le seul
Posté par Axioplase ıɥs∀ (site web personnel) . Évalué à 7.
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 chimrod (site web personnel) . Évalué à 2.
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 Axioplase ıɥs∀ (site web personnel) . Évalué à 3.
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 Liorel . Évalué à 4.
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.
[^] # Re: C'est pas le seul
Posté par chimrod (site web personnel) . Évalué à 3.
Merci pour ta piste, à priori, il suffirait d'avoir une complétude fonctionnelle, donc un ensemble (AND, NOT) ou (NOR) ou (NAND), ainsi qu'un accès séquentiel à une "mémoire" en lecture/écriture.
Le reste ne serait que brodage et laissé au créateur :)
# nombre de cartes
Posté par Anonyme . Évalué à 3.
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 Liorel . Évalué à 2.
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 Anonyme . Évalué à 2.
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 grim7reaper . Évalué à 2.
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 liberforce (site web personnel) . Évalué à 3.
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 liberforce (site web personnel) . Évalué à 3.
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 Anonyme . Évalué à 2.
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 liberforce (site web personnel) . Évalué à 3. Dernière modification le 10 mai 2019 à 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 Anonyme . Évalué à 3.
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 damaki . Évalué à 2.
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 liberforce (site web personnel) . Évalué à 3.
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 Anonyme . Évalué à 3.
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 Benoît Sibaud (site web personnel) . Évalué à 7.
Sauf si d'autres cartes jouent sur le nom des créatures (bonus/malus aux gobelins par exemple).
[^] # Re: nombre de cartes
Posté par Anonyme . Évalué à 3.
effectivement, ça m'étais sorti de la tête. Mais de souvenir, ça joue davantage sur le type de créature (clerc, soldat, mort-vivant, orc, etc.) écrit dans la description que sur le nom de la carte.
[^] # Re: nombre de cartes
Posté par liberforce (site web personnel) . Évalué à 4.
Il est important de ne pas confondre le nom de la carte, et le type de la carte. "+1/+1 à tous les gobelins" désigne un type de créature, ce qui est indépendant du nom de la carte.
Les cartes qui font référence au nom complet d'une carte sont par exemple pour lever une limitation comme le nombre maximal de cartes portant ce nom dans un jeu, ou permettent d'aller chercher une carte avec un nom spécifique, donnent un bonus spécial, ou permettent de créer un objet permanent qu'il faut alors nommer (pour ceux que ça intéresse, voici une liste plus exhaustive).
Quand une carte est rééditée sous un autre nom, c'est plus souvent pour des contraintes d'homogénéité. Il y a une histoire derrière chaque extension, avec parfois des livres édités spécifiquement pour raconter cette histoire. Cette histoire décrit un multivers, avec différents plans de réalité, et même si certains personnages (qu'on nomme des planeswalkers, mais j'aime bien le terme français d'« arpenteur »), peuvent passer d'un plan à l'autre (transplaner), d'autres personnages sont ancrés dans un plan particulier. Ainsi il est très fréquent que le nom d'un personnage apparaisse dans le nom d'une carte, et ce nom étant souvent associé à un plan, situer l'action dans un autre plan nécessite de renommer la carte.
Parfois des cartes sont aussi extrêmement similaires avec juste un changement mineur, comme un type de créature: On peut avoir des créatures identiques en tout point, sauf qu'une est un ours, l'autre un grand singe, l'autre un elfe et éclaireur, l'autre un elfe et guerrier. Cela permet d'avoir des synergies dans les jeux qui tirent parti de ces aspects (decks tribaux).
[^] # Re: nombre de cartes
Posté par liberforce (site web personnel) . Évalué à 4.
Je vois d'ailleurs qu'il y a deux cartes de créatures qui ont "goblin" dans leur nom, mais qui ne sont pas de type gobelin.
[^] # Re: nombre de cartes
Posté par chimrod (site web personnel) . Évalué à 7.
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 Tarnyko (site web personnel) . Évalué à 3. Dernière modification le 11 mai 2019 à 13:56.
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 damaki . Évalué à 0.
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 barmic . Évalué à 3.
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 ?
on est d'accord, ils le feront pas :) ↩
[^] # Re: nombre de cartes
Posté par damaki . Évalué à 1.
Tout à fait. D'ailleurs c'est courant d'avoir des rééditions fonctionnelles de cartes. Le premier exemple qui me vienne à l'esprit est Epicure Of Blood qui est une version en créature de Exquisite Blood. Après, le Black Lotus et la Reserved List c'est une autre paire de manches…
[^] # Re: nombre de cartes
Posté par liberforce (site web personnel) . Évalué à 3.
Epicure Of Blood et Exquisite Blood n'ont pas vraiment le même effet… La cause de l'un est la consséquence de l'autre (et inversement).
[^] # Re: nombre de cartes
Posté par damaki . Évalué à 2.
Oui effectivement, j'ai halluciné, au temps pour moi. Mon exemple ne tient pas du tout.
[^] # Re: nombre de cartes
Posté par liberforce (site web personnel) . Évalué à 3.
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 Tarnyko (site web personnel) . Évalué à 1. Dernière modification le 15 mai 2019 à 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 Xx+xX . Évalué à 10.
Et là, le berger arrive et dit: "bande de ***, c'est pas un mouton, c'est mon chien"
# Vraiment surprenant ?
Posté par Aldoo . Évalué à 3.
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 Aldoo . Évalué à 3.
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 MCMic (site web personnel) . Évalué à 3.
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 Aldoo . Évalué à 2.
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 damaki . Évalué à 2.
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 fearan . Évalué à 3.
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 liberforce (site web personnel) . Évalué à 4.
À 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
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.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.