Magic: the Gathering Turing est-il terminé?

Une question très spécifique, je le sais, et je doute qu'elle soit répondue par quiconque ne connaît pas déjà les règles de Magic. Transféré à Draw3Cards . Voici les règles complètes du jeu Magic: the Gathering . Voir cette question pour une liste de toutes les cartes magiques. Ma question est - le jeu Turing est-il complet?

Pour plus de détails, veuillez consulter l'article sur Draw3Cards .

Alex Churchill (@AlexC) a publié une solution qui ne nécessite pas de coopération entre les joueurs, mais modélise plutôt l'exécution complète d'une machine de Turing universelle avec deux états et 18 symboles de bande. Pour plus de détails, voir https://www.toothycat.net/~hologram/Turing/ [ archive ].

Ok, j'ai une solution qui évite le problème de brûlure de mana que j'ai rencontré. C'est une sorte de piratage, car je dois faire l'hypothèse que les joueurs peuvent identifier des terrains spécifiques, ce qui, je pense, n'est pas traité dans les règles. En pratique, c'est le cas, car ils peuvent être organisés en ligne en fonction de l'ordre dans lequel ils sont joués.

Tout d'abord, la description complète du problème sur le site Draw3Cards:

Une réponse positive serait composée de ces éléments:

1. Une fonction calculable fM de Turing Machines aux decks Magic commandés (où l'ordre de la bibliothèque compte)
2. Deux stratégies déterministes et calculables bien définies pour jouer à Magic (qui ne dépendent pas du deck). Appelons-les Strategy TS (Turing Strategy) et Strategy IS (Input Strategy).
3. Un moyen calculable fI pour encoder n'importe quelle chaîne de zéros et de uns comme un deck Magic Input. Une telle façon serait de prendre le numéro de Gödel de la chaîne et de mettre autant d'îles dans le deck Input.

La condition supplémentaire qui doit être remplie est la suivante: étant donné un Turing Machines TM, considérons le résultat du jeu Magic entre la stratégie TS jouant avec le deck fM (TM) contre la stratégie TI jouant avec le deck fI (I), lorsque les bibliothèques sont pas mélangé avant le début du jeu. Cette partie doit être gagnée par le premier joueur si et seulement si TM (I) = true.

Voici donc l'idée. Nous avons 2 joueurs, A et B. B fournira l'entrée, tandis que A implémentera directement une machine de Turing. Les decks seront composés presque entièrement de terrain, mais aussi de la carte Gemstone Array pour annuler la brûlure de mana. A aura 3 types de terres: îles, montagnes et forêts. L'idée de base est d'utiliser des terres exploitées pour représenter un 1 et des terres inexploitées pour représenter un 0. Les îles seront utilisées pour représenter l'état de la bande, les montagnes pour indexer la position actuelle le long de la bande et les forêts pour représenter l'état interne de 24 état 2 symbole Machine de Turing (je crois qu'il y en a une universelle à cause de Rogozhin).

$2^5 = 32 > 24$$2^{m+1}$

$2^5 = 32 > 24$$2^{m+1}$

Stratégie: A et B jouent tous les deux un terrain par tour dans l'ordre dans lequel ils sont tirés. Lorsque chacun a dessiné 4 forêts, il joue un artefact de pierre gemme. Remarque A va en premier, donc a déjà une île lorsque B pioche joue sa première carte d'entrée.

A et B continuent simplement de mettre leurs cartes en ordre jusqu'à ce que B ait épuisé leurs plaines et marais et joue sa première île. Sur son prochain coup, A pour tout ce que je tape sur sa ième île ssi B avec Input Land était un marécage. A initialise sa machine de turing en tapant sur sa première forêt et montagne. S'il a engagé un nombre impair de cartes, il utilise sa forrest supplémentaire et utilise tout ce mana pour ajouter des jetons à Gemstone Array. À partir de là, le jeu se déroule comme suit: B utilise son tour pour simplement refléter l'état du mana de A. B tape son ième Terrain d'entrée si A la ième île de A est engagée. De la même façon, B tape sa ième Forêt (Montagne) si la I e Forêt (Montagne) de A est engagée. Comme A engage toujours un nombre pair de cartes, B fait de même, et le mana est utilisé pour ajouter des jetons à Gemstone Array.

Au tour de A, tout le mana de A devient inexploité, donc A regarde l'état du mana de B, représente l'état du mana de A au tour précédent. A applique la règle de transition selon la machine universelle (24,2) à l'état de B pour obtenir son nouvel état.

Le jeu se déroule de cette manière jusqu'à ce que la machine à turing s'arrête. À ce stade, A met ses montagnes dans l'état «fini» réservé (l'état tout inexploité). Si la machine Turing s'est arrêtée dans un état d'acceptation, B copie l'état des montagnes de A, mais exploite toutes leurs terres restantes en négligeant d'utiliser le réseau de pierres précieuses, commençant ainsi le processus de suicide par brûlure de mana. Au tour de A, si les montagnes de B sont à l'état "fini" et que toutes les autres terres de B sont exploitées, A ne fait simplement rien (notez que ses montagnes sont automatiquement à l'état "fini"). Si les montagnes de A sont à l'état fini, mais que rien d'autre n'est exploité, B continue de se suicider par brûlure de mana. Ceci est répété jusqu'à ce que B soit mort.

Si toutefois, la machine termine à l'état de rejet, B laisse toutes ses cartes inexploitées. Si toutes les cartes de B sont dégagées, A engage toutes ses cartes, commençant le même processus de suicide par brûlure de mana. Si les cartes non-montagne de A sont toutes engagées et les montagnes inexploitées, B laisse toutes leurs cartes inexploitées. Cela conduira A à continuer le suicide par brûlure de mana jusqu'à ce qu'il perde la partie.

Cela devrait répondre aux critères demandés dans la question, et donc lorsque cette commande est autorisée, je pense que le jeu est Turing complet dans le sens décrit dans la question.

Alex Churchill, Stella Biderman et Austin Herrick ont ​​publié cet article montrant que Magic is Turing Complete

Résumé — Magic: The Gathering est un jeu de cartes à collectionner populaire et célèbre sur le combat magique. Dans cet article, nous montrons qu'un jeu optimal dans la magie du monde réel est au moins aussi difficile que le problème de l'arrêt, résolvant un problème ouvert depuis une décennie [1], [10]. Pour ce faire, nous présentons une méthodologie pour intégrer une machine de Turing arbitraire dans un jeu de magie de telle sorte que le premier joueur est assuré de gagner le jeu si et seulement si la machine de Turing s'arrête. Notre résultat s'applique à la façon dont la vraie magie est jouée, peut être obtenue en utilisant des decks de taille standard pour les tournois, et ne dépend pas de la stochasticité ou des informations cachées. Notre résultat est également très inhabituel dans la mesure où tous les mouvements des deux joueurs sont forcés dans la construction. Cela montre que même reconnaître qui va gagner un match dans lequel aucun joueur n'a une décision non triviale à prendre pour le reste du match est indécidable. Nous concluons par une discussion sur les implications pour une théorie de calcul unifiée des jeux et des remarques sur la jouabilité d'une telle planche dans un contexte de tournoi.