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...
haut de page - Les forums de MV >> MV Gazette >> Discussion : page 1 | 2
Vous devez être identifié pour pouvoir poster sur les forums.