10 ms·

MtG is played by choosing 60 cards from 20k. Everything is finite. There must be some generalization in order to make it noncomputable. There are probably many

MtG is played by choosing 60 cards from 20k. Everything is finite. There must be some generalization in order to make it noncomputable. There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large. EDIT: This from the real abstract sounds very strange: "Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable."

lmm 7y ago
> EDIT: This from the real abstract sounds very strange: > "Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable." It's not so strange: the game is Turing complete, so the winner can be undecidable because who wins is the result of some arbitrarily complex computation. Imagine we play a "game" where I win if there's a nontrivial zero of the Riemann zeta function with real part not equal to one half, otherwise you win. Neither of us has any decisions to make in this game. It's still very difficult to determine who's going to win.
- rishav_sharan 7y ago
  Can you ELI5 how a game can be Turing complete? I have only heard that in relation to programming languages.
  - simonh 7y ago
    Magic is played by taking a card from the top of your pile and following the instructions on it, then your opponent does the same. In normal games the decks are shuffled, but for this to work you have to be able to program the order of the cards in both decks. In this paper they program the game by constructing the decks using a subset of cards that all have mandatory effects. I think what they do is set up a sequence of cards that 'initialises' the game state with various creatures and resources. These together with the game rules form the Turing machine. Then they have a sequence of cards that correspond to the 'paper tape' of symbols a Turing machine operates on.
  - yorwba 7y ago
    A Turing machine has a simple loop of reading the current tape cell, and depending on the current value, writing a new value, changing state and moving the read head on the tape. The paper shows that there are cards in MTG which can be used to implement that kind of loop. The tape is represented by tokens whose strength increases with their distance from the read head, such that the current cell is the weakest one. On every loop iteration, it gets killed (read) and triggers different effects depending on its type, such as getting replaced (writing a new value), changing the effects that will be active on the next iteration (changing state) and dealing damage to one side of the tape but not the other (moving the read head).
vaylian 7y ago
> Everything is finite. No, you can recycle resources and there are cards that remove termination conditions of the game. For example Platinum Angel or Lich's Mastery.
badpun 7y ago
You can easily gain infinite amount of mana, life, creatures.
bigcostooge2 7y ago
This is strictly incorrect. 60 is the minimum deck size. There is no maximum. You may have up to 4 copies of a non-basic land per deck. There are then limitations on how many of particular cards can be played at once. In general, the battlefield has no max size. But as others have mentioned, there are mechanics to take creatures from the graveyard and generate infinite mana.
tacone 7y ago
AFAIK 60 the minimum number of cards you have to put in your deck, but (at the least at the times) there was not a maximum number. 20k is the number of unique cards, but you can put as much as 4 copies of the same card in your deck for the vast majority of cards. You can also put as many "normal" lands as you wish in your deck.
- tapland 7y ago
  As many as you can shuffle unassisted is the upper limit.
  - mywittyname 7y ago
    This is an interesting rule, as it seems to provide an advantage to players on the basis on hand size.
    - ivl 7y ago
      More cards is not seen as an advantage. There are a couple cases where you may want more cards, but usually up to about 75. It's about drawing the right cards, not just many, and more cards makes your deck less reliable, simply on the likelihood of drawing the card you want.
    - gpderetta 7y ago
      Unless you really really want a Battle of Wits deck (which is maybe tier 7) there is really no advantage and quite a bit of a disadvantage to running more than the minimum allowed number of cards.
      - stellaathena 7y ago
        For those who don't play Magic, this is on a scale where tier 1 decks are top decks, tier 2 decks are reasonable, tier 3 decks have serious weaknesses but are playable.
    - rtkwe 7y ago
kurtisc 7y ago
In a non-cynical way: are you aware the PDF can be viewed on the right?
Xelbair 7y ago
there are cards that: restore your library, grab cards from exile(out of game, literally), Reverse win conditions, Prevent losing, Generate infinite loops - both deterministic and not(with randomness). Create tokens(sometimes coupled with above) - which provide unlimited resources with a sac outlet. And those aren't fringe cases - for example in EDH format quite a lot of decks win by creating some kind of infinite loop, or by generating infinite resources(or sky high amount of them) So i would argue that resources aren't finite.
AlexTFish 7y ago
As the other repliers have explained, MtG provides various ways to circumvent that. Thus we found ways to encode millions of pieces of state in tokens, and we ensured that the game loops round computing the Turing machine execution one step at a time. Your sentence "There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large" is actually key. You're completely right - there are many. What's unusual about our result here is that we found a way to embed a fully functional Turing machine inside not an arbitrary extension of a board game, but inside a board game exactly the way it's normally played.
CryoLogic 7y ago
Do keep in mind that 60 cards is just one Magic format, one of the most popular official formats is Commander which is 100 card singleton. Beyond that, those are not cards in the sense of poker cards with stats and an effect. Many of these have unique effects specific to that card. There are also 100+ categorical effects. Creature types, color types. Plus Magic is played on both players turns unlike other card games. Divide both turns into phases with pros and cons of casting. It's more complex than it sounds when you just call it a "card game" - it is much more deep than most any other card game and does not truly feel like a card game except the fact that you play with cards. The game has infinite loops, race conditions, etc which come in many unpredictable shapes.
hannasanarion 7y ago
>EDIT: This from the real abstract sounds very strange: >"Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable." It is very straightforward. They are saying that, in the turing machine scenario they've set up, for each player's move, the decision they have to make is obvious, so the players don't have to collaborate in order to produce the scenario, it will arise naturally out of the state of the game with two rational players trying to win.
- manifestsilence 7y ago
  I think they actually engineered it to not just involve obvious or optimal choices by each player, but to give them literally no other choice but to watch the machine do its calculation (or concede the game). They do this by causing all cards other than those needed for the machine to be removed from the game.

lmm 7y ago

> EDIT: This from the real abstract sounds very strange: > "Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable." It's not so strange: the game is Turing complete, so the winner can be undecidable because who wins is the result of some arbitrarily complex computation. Imagine we play a "game" where I win if there's a nontrivial zero of the Riemann zeta function with real part not equal to one half, otherwise you win. Neither of us has any decisions to make in this game. It's still very difficult to determine who's going to win.

rishav_sharan 7y ago
Can you ELI5 how a game can be Turing complete? I have only heard that in relation to programming languages.
- simonh 7y ago
  Magic is played by taking a card from the top of your pile and following the instructions on it, then your opponent does the same. In normal games the decks are shuffled, but for this to work you have to be able to program the order of the cards in both decks. In this paper they program the game by constructing the decks using a subset of cards that all have mandatory effects. I think what they do is set up a sequence of cards that 'initialises' the game state with various creatures and resources. These together with the game rules form the Turing machine. Then they have a sequence of cards that correspond to the 'paper tape' of symbols a Turing machine operates on.
- yorwba 7y ago
  A Turing machine has a simple loop of reading the current tape cell, and depending on the current value, writing a new value, changing state and moving the read head on the tape. The paper shows that there are cards in MTG which can be used to implement that kind of loop. The tape is represented by tokens whose strength increases with their distance from the read head, such that the current cell is the weakest one. On every loop iteration, it gets killed (read) and triggers different effects depending on its type, such as getting replaced (writing a new value), changing the effects that will be active on the next iteration (changing state) and dealing damage to one side of the tape but not the other (moving the read head).

vaylian 7y ago

> Everything is finite. No, you can recycle resources and there are cards that remove termination conditions of the game. For example Platinum Angel or Lich's Mastery.

badpun 7y ago

You can easily gain infinite amount of mana, life, creatures.

bigcostooge2 7y ago

This is strictly incorrect. 60 is the minimum deck size. There is no maximum. You may have up to 4 copies of a non-basic land per deck. There are then limitations on how many of particular cards can be played at once. In general, the battlefield has no max size. But as others have mentioned, there are mechanics to take creatures from the graveyard and generate infinite mana.

tacone 7y ago

AFAIK 60 the minimum number of cards you have to put in your deck, but (at the least at the times) there was not a maximum number. 20k is the number of unique cards, but you can put as much as 4 copies of the same card in your deck for the vast majority of cards. You can also put as many "normal" lands as you wish in your deck.

tapland 7y ago
As many as you can shuffle unassisted is the upper limit.
- mywittyname 7y ago
  This is an interesting rule, as it seems to provide an advantage to players on the basis on hand size.
  - ivl 7y ago
    More cards is not seen as an advantage. There are a couple cases where you may want more cards, but usually up to about 75. It's about drawing the right cards, not just many, and more cards makes your deck less reliable, simply on the likelihood of drawing the card you want.
  - gpderetta 7y ago
    Unless you really really want a Battle of Wits deck (which is maybe tier 7) there is really no advantage and quite a bit of a disadvantage to running more than the minimum allowed number of cards.
    - stellaathena 7y ago
      For those who don't play Magic, this is on a scale where tier 1 decks are top decks, tier 2 decks are reasonable, tier 3 decks have serious weaknesses but are playable.
  - rtkwe 7y ago

kurtisc 7y ago

In a non-cynical way: are you aware the PDF can be viewed on the right?

Xelbair 7y ago

there are cards that: restore your library, grab cards from exile(out of game, literally), Reverse win conditions, Prevent losing, Generate infinite loops - both deterministic and not(with randomness). Create tokens(sometimes coupled with above) - which provide unlimited resources with a sac outlet. And those aren't fringe cases - for example in EDH format quite a lot of decks win by creating some kind of infinite loop, or by generating infinite resources(or sky high amount of them) So i would argue that resources aren't finite.

AlexTFish 7y ago

As the other repliers have explained, MtG provides various ways to circumvent that. Thus we found ways to encode millions of pieces of state in tokens, and we ensured that the game loops round computing the Turing machine execution one step at a time. Your sentence "There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large" is actually key. You're completely right - there are many. What's unusual about our result here is that we found a way to embed a fully functional Turing machine inside not an arbitrary extension of a board game, but inside a board game exactly the way it's normally played.

CryoLogic 7y ago

Do keep in mind that 60 cards is just one Magic format, one of the most popular official formats is Commander which is 100 card singleton. Beyond that, those are not cards in the sense of poker cards with stats and an effect. Many of these have unique effects specific to that card. There are also 100+ categorical effects. Creature types, color types. Plus Magic is played on both players turns unlike other card games. Divide both turns into phases with pros and cons of casting. It's more complex than it sounds when you just call it a "card game" - it is much more deep than most any other card game and does not truly feel like a card game except the fact that you play with cards. The game has infinite loops, race conditions, etc which come in many unpredictable shapes.

hannasanarion 7y ago

>EDIT: This from the real abstract sounds very strange: >"Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable." It is very straightforward. They are saying that, in the turing machine scenario they've set up, for each player's move, the decision they have to make is obvious, so the players don't have to collaborate in order to produce the scenario, it will arise naturally out of the state of the game with two rational players trying to win.

manifestsilence 7y ago
I think they actually engineered it to not just involve obvious or optimal choices by each player, but to give them literally no other choice but to watch the machine do its calculation (or concede the game). They do this by causing all cards other than those needed for the machine to be removed from the game.