Item — HN Reader

I'd claim strongly, that any game with:

- finite number of pieces (eg. cards)

- finite number of actions each round

- clear endgame criteria

is computionally solvable. What comes with randomness is stochasticity, but if that made game unsolvable what about poker (solved for limit heads-up) and even scrabble?

Probably it's kind of semantic problem. I'm not complexity nor game theory expert.

11 comments

Magic The Gathering is different from the games you mentioned in that it is defined by cards that rewrite the rules of the game. There are already at least five known ways to implement Turing machines, for example:

https://www.toothycat.net/~hologram/Turing/

If you then think about the sheer number of existing M:tG cards and the implied number of possible combinations of those cards and changes to the rules (even if "optimized" to combinations that eliminate obviously nonsensical strategies like only having spells that require green mana and no sources of green mana) and the ways those cards can interact, then the computational complexity of the game explodes in ways that no other game can compare to.

And that's not even what these people showed, I think. They showed that beyond this, the complexity is worse than NP-hard.

FWIW that's my old site, showing the 2012 version of the result, which required cooperation between 4 players. The version in the paper on arXiv is the result of my latest research (with Stella and Austin) where we get it down to 2 players and eliminate all choices required by any player.

I am planning to update the toothycat.net site pretty soon with this new result, though.

> I'd claim strongly [...] I'm not complexity nor game theory expert.

Why are you making “strong” claims in a field you admittedly are not an expert in? This is not how polite nor useful conversations happen.

MTG doesn’t have finite number of pieces, or finite number of actions each turn though.

Naturally people have implemented Turing machines in mtg. www.toothycat.net/~hologram/Turing

Also, the endgame criteria of mgt can be changed, but that said there is only a finite number of simple possible endgames in a sense.

It depends. I'm pretty sure it is possible to layer an unlimited number of contrasting win/lose conditions; distinguishing essentially different "endgames" seems slippery.

Actions in Magic: the Gathering let you create "tokens" which are like cards but aren't limited in number. Although you can only have a finite number in any given game, there's no upper bound on how many you can have.

There is indeed no limitation on the number of tokens in a game.

There are many combo wins that involve having (technically) infinite tokens, dealing infinite damage, gaining infinite life, taking infinite turns. You get the idea.

I said technically because in practice, setting this to a very large number is enough for the win. Dealing 1e6 damage is, although possible, already way overkill in most cases when your opponent starts with 20 life.

Though you do need to pick a number. The paper itself describes a game state which devolves into the 'the player who picks a larger number wins', and even gaining a large but finite amount of life can be dangerous if you don't go large enough (I have heard of a specific example of someone gaining arbitrary life, picking a google, and then losing by have their life reduced to zero through a series of losses of half their life).

Combat resolution/targeting can get a wee bit out of hand:

https://i.redd.it/wyn3d22evs011.jpg

This is not the worst I've seen, simply what I was able to turn-up on short notice.

EDIT: To clarify (the UI isn't great), what you see above is a selection of the "cards" (creatures/tokens) in play, more are off screen.

Maybe the UI isn't great in an absolute sense (that situation would be really tedious to play), but I don't see how it could be made substantially better. It wouldn't be better if that situation arose in a physical Magic game either... the problem there is the game state, not the UI.

My point was that for people that have never seen MtG Arena before, it's non-obvious that there's more going on off-screen. A more intuitive UI would make that situation more explicit and not require explanation.

As you've rightly pointed out, a better UI isn't going to solve the UX issue of ridiculous game state; but it could better depict the state itself.

Do you know if there is a video showing a full turing complete game? I can't quite visualize what is going on.

Well some cards can create additional (potentially infinite) game pieces or resources with which to preform more actions per round.

The output of a computer program can be unsolveable, even though the source of the program has finite characters. It's the same thing. (Literally: you're building an interpreter out of cards.)

MTG can have:

an infinite amount of pieces(there are cards that restore your library, generate infinite amount of mana/tokens)

infinite amount of actions each round, by each player too!

Endgame criteria which can be changed by cards themselves.

Some game have more states than there are atoms in the universe. They are solvable in theory but we will need a bigger universe to put this theory in practice...

Actually they are not even solvable in theory even with a bigger universe of insanely powerful computer. Which is what it means to say that mtg is Turing complete.

Add at least one more:

- doesn't let you repeat actions, or patterns of actions (move back and forth in a stalemate like pattern).

Detecting non-trivial stalemates is hard, though.

Here's a game. It has just one card, it says: "repeat this card's action". Is it solvable?