Hacker News Reader

Comment by petters | Hacker News Reader

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."

View on HN

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.

> 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.

Can you ELI5 how a game can be Turing complete? I have only heard that in relation to programming languages.

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.

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).

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.

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.

As many as you can shuffle unassisted is the upper limit.

This is an interesting rule, as it seems to provide an advantage to players on the basis on hand size.

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.

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.

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.

It's not, pretty much all decks stick to the minimum required number because the more cards in your deck the less likely you are to see any particular card you want or need. To that end where they're available in the format many decks will run 'fetch lands' which search the deck for a particular type of land in order to thin out the remaining deck.

Does this mean that players with larger hands are allowed more cards? Or is it an idealized "you can shuffle"?

In practice there is no strategic benefit of having more cards. There is one bad deck that uses more than 250 (to win with Battle of Wits). It arguably breaks the rule already.

And at least there is a card that can be insert an unlimited amount of times and it is not a land. So technically, the combinations are infinite.

Presumably there is an optimal Island / Persistant Petitioners only deck ratio against a dumb opponent who does nothing but draw a card a turn and play a land.

I wonder if it's irrational?

Since you want to draw both lands and petitioners, there's an advantage to having a smaller deck, so this probably wouldn't be the case.

Aha, thanks! Then my comment does not apply!

For constructed formats the minimum is 60. For limited formats the minimum is 40. For EDH/Commander it is 100 (including the commander card).

Every card that either has the subtype "basic" or that has a card text that explicitly states so (for example: Relentless Rats), can be included in any number of copies. All other cards can be included at most 4 times or at most 1 time if it is a EDH/Commander deck.

There are 11 cards with subtype basic: https://scryfall.com/search?q=t%3Abasic&unique=cards&as=grid...

And 4 non-basic cards that can be included in any number: https://scryfall.com/search?q=o%3A%22A+deck+can+have+any+num...

> 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.

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.

>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.

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.

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

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

Reply on news.ycombinator.com