MVarticles
Magic, Complexité et Machine de Turing
le 21/05/2019 9:56
  Cliquez ici pour lire cet article écrit par zombie33
haut de page - Les forums de MV >> MV Gazette >> Discussion : page 1 | 2
ZeSword
Bruxelles, Belgique

AVATAR
Anonyme1
le 24/05/2019 20:23
Seule une partie finie du ruban, au début de la partie, peut avoir des symboles non-blancs, mais la machine effectue bien ses opérations sur un ruban infini. Simplement, pour représenter le fait qu'il y a des "blancs" à gauche et à droite du ruban là où on n'a rien représenté, ça se passe comme ça :

https://arxiv.org/pdf/1904.09828.pdf, Section IV.E. a écrit :
The Turing tape can be initialised to any desired length before starting processing. But it is preferable to allow the machine to run on a simulated infinite tape: in other words, to assume that any uninitialised tape space contains symbol 3 (the blank symbol in the (2, 18) UTM [1]), represented by creature type Cephalid. This is accomplished by having the ends of the currently-initialised tape marked by two special tokens, one green Lhurgoyf and one white Rat. Suppose we’ve exhausted all the initialised tape to the left. This means that the casting of Infest on turn T1 kills the Lhurgoyf rather than one of the normal tape types. This does not directly trigger any of the normal Reanimators/Necromancers. Instead, Bob has another Rotlung Reanimator hacked [2] to read “Whenever Rotlung Reanimator or another Lhurgoyf dies, create a 2/2 green Lhurgoyf creature token”, and Alice has a Rotlung Reanimator hacked to read “Whenever Rotlung Reanimator or another Lhurgoyf dies, create a 2/2 black Cephalid creature token.” Bob’s trigger will resolve first, then Alice’s.

First, Bob’s Reanimator trigger creates a new Lhurgoyf just to the left of the current head. (Alice’s Illusory Gains triggers and gives her control of this new Lhurgoyf, but that will soon change.) We have one copy of Shared Triumph set to Lhurgoyf (“Creatures of the chosen type get +1/+1”) so this token arrives as a 3/3.

Second, Alice’s Reanimator trigger now creates a 2/2 black Cephalid under Alice’s control. The same two copies of Dread of Night as before are giving all black creatures -2/-2, so the black Cephalid will arrive as a 0/0 and immediately die.

The death of this Cephalid triggers one of the regular phasing Reanimators of Bob’s just as if a tape cell containing symbol 3 had been read: a new 2/2 token is created and Illusory Gains moves to that new token. The green Lhurgoyf token serving as an end-of-tape marker has been recreated one step over to the left.

The situation for the white Rat representing the right-hand end of the tape is exactly equivalent. Bob has a Rotlung Reanimator hacked to read “Whenever Rotlung Reanimator or another Rat dies, create a 2/2 white Rat creature token”; Alice has a Rotlung Reanimator hacked to read “Whenever Rotlung Reanimator or another Rat dies, create a 2/2 black Cephalid creature token”; and we have another Shared Triumph set to Rat.


[1] : Yurii Rogozhin, "Small universal Turing machines", https://doi.org/10.1016/S0304-3975(96)00077-1
[2] : Glamerdye, Artificial Evolution

Légende
le 26/05/2019 20:17
wow c'était cool
Samioul
le 28/05/2019 15:41
Très bon article ! J'ai apprécié le lire et comprendre les divers problèmes.
Comme dit plus haut, c'est un peu confus lors de l'explication de la partie à la fin. Il se passe quoi ? ^^

Petit bémol, il y a trois fois des doublons de mots, des coquilles pire sont retrouvées dans les articles du Monde au pire :D
Paco369
Rodez (12), don't forget to put your { on

Elfe
le 04/06/2019 16:56
et pourtant je l'ai corrigé.
(et aussi au passage : c'est une honte toutes ces fautes d'accord pour un matheux !)
tu l'as re-modifié après mon passage ou je suis si mauvais ?

et sinon "déterminer l'issue d'une partie de Magic dans laquelle toutes les actions sont forcées est impossible"
est ce qu'il aurait pas fallu dire : l'issue "de cette partie bien particulière" de magic pour ne pas comprendre l'issue "de n'importe quelle partie" de magic ?
zombie33

Légende
le 04/06/2019 19:01
Je l'ai modifié en effet après ta relecture.

Sinon la phrase "déterminer l'issue d'une partie de Magic dans laquelle toutes les actions sont forcées est impossible", est bien correcte. Il faut comprendre "impossible en général". Pour montrer qu'en général c'est impossible, on donne bien un exemple de cas impossible.

C'est la différence entre "l'issue de n'importe quelle partie est impossible à determiner" et "l'issue d'une partie quelconque est impossible à déterminer". La deuxième est correcte.
Paco369
Rodez (12), don't forget to put your { on

Elfe
le 12/06/2019 14:25
Du coup j ai pas bien compris pourquoi cet exemple permet de conclure pour le cas général (de la partie quelconque).

(t as pas fait tant de boulettes que ça, mais autant l orthographe c est pas inné, autant les accords c est une poignée de règles et une analyse tellement basique qu'il est étonnant que tu y fasses des fautes. Peut être par manque de goût ?)

Tu restes mon idole pour tout ce qui relève des maths, ne t'inquiète pas.
zombie33

Légende
le 12/06/2019 15:13
C'est quelque chose de classique en théorie de la complexité mais je ne l'ai peut-être pas évoqué dans l'article. Quand on parle de complexité d'un algorithme ou d'un système on parle toujours de la complexité du pire cas de figure pouvant se présenter.
Donc montrer qu'une partie spécifique a une certaine complexité, atteste que le jeu dans son ensemble a au moins ce degré de complexité. Après c'est un peu comme la loi de Murphy, quand on parle de la complexité d'une partie quelconque, on imagine toujours le pire qui peut se produire. En revanche il est faut de dire que n'importe quel parti a ce degré de complexité.

(Quand j'écris, je m'intéresse essentiellement au fond et à la forme et j'ai tendance à délaisser l'orthographe. Après je ne me cherche pas d'excuse. Je sais que c'est pas bien et je suis le premier à penser qu'un texte avec des fautes n'est pas plaisant à lire.)
Paco369
Rodez (12), don't forget to put your { on

Elfe
le 12/06/2019 20:26
OK, je comprends bien mieux.

Perso je suis assez mauvais en orthographe pure, sans doute car j'ai très peu lu. Mais comme les accords (pluriel, féminin) et la conjugaison sont une mécanique quasi universelle (exceptions), que j ai certainement eu la chance de connaître au bon moment du développement de mon cerveau, je l'ai toujours en tête quand je lis. :D mais globalement mes yeux me piquent souvent.
Manu34
Montpellier, France

Légende
le 02/07/2019 14:08
Tu m'as perdu après
Citation :

Comment faire pour représenter un ruban avec des cartes Magic ?


Tu pourrais expliquer un cas simple genre un mec qui a 60 îles vs un mec qui a 59 forêts et 1 llanowar elves? Comment tu représentes les cartes en jeu ou non? En quoi le llanowar elves a quelque chose à voir avec tes tokens et ton infest?
zombie33

Légende
le 02/07/2019 14:29
Vu ta question, j'ai l'impression de t'avoir perdu avant :) Le but n'est pas de codé une partie de magic sur une machine de turing mais de créer une machine de turing au sein d'une partie de magic particulière.

Dans un premier temps on se demande quels sont les objets à notre disposition à Magic pour la représenter et ce n'est que dans un second temps que l'on va essayer de mettre ça en place lors d'une partie de magic.
LiuPei
Toulouse
le 10/07/2019 12:40
Super article ! Merci.

Pourquoi ça ne m'étonne pas que MTG soit Turing-complet ?...

Réponse : cf. la page wikipedia de Richard Garfield qui est docteur en maths spécialité analyse combinatoire...
Glatoorian
Lyon, France
le 02/08/2019 15:30
Super article mais y a un truc qui cloche, quand tu pioche toute ta bibliothèque, y a un problème pasque tu peut pas avoir plus de 7 cartes dans ta main. À moins que les cartes soit déjà dans le bon ordre et que tu les pioches petit à petit ?
miniK
Wild Evocation
le 18/08/2019 19:50
Pour répondre à ZeSword sur WildEvocation, il me semble en effet qu'il est indispensable que Bob le contrôle pour une raison de pile. Lorsqu'un token tapped est créé, Alice en prend le contrôle et au début de son tour le dégage. Du coup, la capa de mesmeric orb doit être mise en pile au début de l'upkeep, ainsi que la capa de WildEvocation. Alice étant le joueur actif, elle empile ses capas avant Bob et donc Mesmeric orb se résout après et Coalition Victory file en-dessous du deck après cleansing Beam, ce qui ne modifie pas l'ordre des cartes du deck d'Alice. Si Alice contrôlait WildEvocation, elle pourrait décider de le résoudre après l'orbe et donc de modifier l'ordre des cartes de son deck. La démonstration étant basée sur le fait qu'aucun des deux joueurs n'a de choix dans le déroulement des actions, il est donc nécessaire que ce soit Bob qui controle WildEvocation.
crazyjam
sympa
le 05/09/2019 11:12
Vraiment sympa cet article, et utile ! Comme tu dis, la plupart des médias ont traité la news de manière sensationnelle et avec beaucoup de mauvaises informations.

Il y a un point que tu ne mentionnes pas et que je trouve très intéressant sur la raison de la complexité de MtG, c'est le fait que les éléments du jeu peuvent modifier les règles (il y a des cartes qui disent "à la place de suivre cette règle, fait ceci"). Ça créé une boucle qui complexifie tout, car ça ramène le jeu à un ensemble de règle qui se modifie lui-même.

En fin de compte, c'est peu surprenant de tomber sur des cas analogues aux théorèmes limitatifs des maths, de la logique et de l'info puisqu'ils surviennent dès qu'on introduit du méta (théorie qui veut prouver des trucs sur elle-même, programme qui veut analyser un autre programme, assertion qui parle d'elle-même, etc).
J'aime les carottes

le 02/11/2019 17:21
haut de page - Les forums de MV >> MV Gazette >> Discussion : page 1 | 2
Vous devez être identifié pour pouvoir poster sur les forums.