Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

A very specific question, I'm aware, and I doubt it will be answered by anyone that isn't already familiar with the rules of Magic. Cross-posted to Draw3Cards. Here are the comprehensive rules for the game Magic: the Gathering. See this question for a list of all Magic Cards. My question is - is the game Turing Complete?

For more details, please see the post at Draw3Cards.

share|improve this question
1  
(1) What is the input? Do you assume that you know the content and the order of the cards in both players’ decks? (2) To analyze its complexity, a problem must have infinitely many possible inputs. For example, we cannot say that chess is EXP-complete (even if we say so, it means that the generalization of the chess to an n×n board is EXP-complete). How do you generalize the game? (3) The game may be too complicated to analyze its complexity, but I do not know. –  Tsuyoshi Ito Oct 9 '10 at 11:08
1  
@Daniel: Thanks. In fact I checked it too, but I was not sure if anyone wants to analyze the game where each card except for land cards are restricted to at most 4 copies and only the number of land cards can grow. –  Tsuyoshi Ito Oct 9 '10 at 11:13
1  
@Daniel: Not sure if the logic works that way because there are several different types of land cards. After all, the original game itself may be complicated enough to be Turing complete. What I am not sure is whether the asker really wants to analyze the game where almost all cards in a deck are necessarily land cards. I will wait for the asker to reply. –  Tsuyoshi Ito Oct 9 '10 at 11:44
4  
@Daniel: That's not a reasonable objection! Most hardness reductions for games output something that looks more like the reduction than the original game. (Hamiltonian cycles don't naturally arise in draughts, for example.) –  JɛffE Oct 9 '10 at 15:43
1  
@Tsuyoshi - I think that would be asking if Magic is decidable. For this question to be meaningful, you could assume perfect information - all libraries and hands are revealed, and all random coin-tosses and the like are predetermined. Is it possible to determine from every Magic position who the winner is? –  ripper234 Oct 11 '10 at 11:28

2 Answers 2

up vote 13 down vote accepted

@Alextfish has posted a new solution at Draw3Cards, which does not require cooperation between the players, but rather models the complete execution of a universal Turing machine in one turn: http://draw3cards.com/questions/2851/is-magic-turing-complete/3225#3225

(Flagged CW to avoid reputation.)

share|improve this answer
    
The link is dead for me. Should we recreate the solution in the answer to be complete? –  Artem Kaznatcheev Oct 29 '13 at 14:08

Ok, I have a solution that avoids the mana burn issue I ran into. This is kind of a hack, since I need to make the assumption that players can identify specific lands, which I don't think is dealt with in the rules. In practice this is the case, since they can be arranged in a line based on the order in which they are played.

First, the full description of the problem from the Draw3Cards site:

A positive answer would be composed of these components:

  1. A computable function fM from Turing Machines to ordered Magic decks (where the order of the library matters)
  2. Two well defined deterministic & computable strategies to play Magic (that do not depend on the deck). Let's call them Strategy TS (Turing Strategy) and Strategy IS (Input Strategy).
  3. A computable way fI to encode any string of zeros and ones as a Magic Input deck. One such way would be to take the Gödel number of the string and put as many islands in the Input deck.

The additional condition that should be satisfied is this: Given a Turing Machines TM, let us consider the result of the Magic game between strategy TS playing with deck fM(TM) against strategy TI playing with deck fI(I), when the libraries are not shuffled before the game starts. This game should be won by the first player if and only if TM(I) = true.

So here is the idea. We have 2 players, A and B. B will supply the input, while A will directly implement a Turing machine. The decks will be composed almost entirely of land, but also the Gemstone Array card to void mana burn. A will have 3 types of land: Islands, Mountains and Forests. The basic idea is to use tapped land to represent a 1 and untapped land to represent a 0. Islands will be used to represent the state of the tape, Mountains to index the current position along the tape and Forests to represent the internal state of 24 state 2 symbol Turing machine (I believe there is a universal one due to Rogozhin).

The decks are ordered as follows: A's deck: Gemstone Artifact; 6 Forests (since $2^5 = 32 > 24$ plus an additional forest); For m=0 to infinity: $2^{m+1}$ Islands followed by 1 Mountains. Note that the number of mountains (which can be either tapped or untapped) is always the number required to index every island, plus a halting state.

B's deck: Gemstone Artifact; 6 Forests (since $2^5 = 32 > 24$ plus an additional forest); For m=0 to infinity: $2^{m+1}$ Input Lands followed by 1 Mountains. Note again that the number of mountains (which can be either tapped or untapped) is always the number required to index every island held by A, plus a halting state. The Input lands are taken to be Plains (to represent a 0 in the input string), Swamp (to represent a 1 in the input string) and Islands (which are used after the end of the input string has been reached.

Strategy: A and B both play one land a turn in the order in which they are drawn. When each has drawn 4 forests they play Gemstone Artifact. Note A goes first, so already has an Island when B draws plays his first input card.

A and B simply continue to place their cards in order until B has exhausted their Plains and Swamps and plays their first Island. On his next go, A for all i taps his ith Island iff Bs ith Input Land was a swamp. A initialises his turing machine by tapping his first Forest and Mountain. If he has tapped an odd number of cards he taps his extra forrest, and uses all this mana to add tokens to Gemstone Array. From here on the play proceeds as follows: B uses their turn to simply mirror the state of A's mana. B taps his ith Input Land iff A's ith Island is tapped. Similarly B taps his ith Forest(Mountain) iff A's ith Forest(Mountain) is tapped. As A always taps an even number of cards, so does B, and the mana is used to add tokens to Gemstone Array.

On A's turn, all of A's mana becomes untapped, so A looks at the state of B's mana, represents the state of A's mana on the previous turn. A applies the transition rule according to the universal (24,2) machine to B's state to obtain his new state.

Play proceeds in this manner until the turing machine halts. At this point, A puts his mountains into the reserved "finished" state (the all untapped state). If the Turing machine halted in an accepting state, B copies the state of A's mountains, but taps all their remaining land neglecting to use Gemstone array, thus beginning the process of suicide by mana burn. On A's turn, if B's mountains are in the "finished" state, and all B's other land is tapped, A simply does nothing (note that his mountains are automatically in the "finished" state). If A's mountains are in the finished state, but nothing else is tapped, B continues suicide by mana burn. This is repeated until B is dead.

If however, the machine finishes in the reject state, B leaves all their cards untapped. If all B's cards are untapped, A taps all his cards, beginning the same process of suicide by mana burn. If A's non-Mountain cards are all tapped, and the mountains untapped, B leaves all their cards untapped. This will lead A to continue the mana burn suicide until he loses the game.

This should satisfy the criteria asked for in the question, and hence when this ordering is allowed, I believe the game is Turing complete in the sense described in the question.

share|improve this answer
2  
Cool. An extra thought: As long as any player taps more than 1 land per turn, you can use charges on the Gemstone Array to avoid mana burn. For example, if I need to tap 3 lands, I turn two mana into a charge, spend the charge to generate one mana, then spend the two remaining mana to create a new charge. -- of course, you solved this problem already anyway. :) –  Daniel Apon Oct 9 '10 at 15:15
1  
Aewsome! It might also be easier to simulate a 2-counter machine (using different types of mana as the counters) instead of directly simulating a Turing machine: en.wikipedia.org/wiki/… –  JɛffE Oct 9 '10 at 15:54
2  
Your reduction also implies that (cooperative) Magic with a finite number of cards is PSPACE-hard. –  JɛffE Oct 9 '10 at 15:56
1  
@Joe - there is no longer mana burn in Magic. You could use Platinum Angel to avoid losing due to running out of cards in your graveyard. –  ripper234 Oct 9 '10 at 16:42
1  
@Joe - you missed my comment earlier that the concept of mana burn has been completely removed from the rules. You can fix it by having each player have a copy of Fireball in his deck. –  ripper234 Oct 9 '10 at 20:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.