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.
> "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.
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).
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.
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.
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.
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...
I wonder if it's irrational?
No, you can recycle resources and there are cards that remove termination conditions of the game. For example Platinum Angel or Lich's Mastery.
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.
>"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.
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."