I came across a really interesting article and i thought id share.
https://arxiv.org/abs/1904.09828
The author claims that deciding who will win a game of magic is at least as undecidable as the halting problem... which is pretty nutso. I need to delve deeper because I'm curious if the variance at play when cards are randomly shuffled or drawn is critical to the result or not.
Anyway, I guess this shows magic is harder than chess, huh?
@Smmenen this seems right up your ally brah
I feel as if I could have just told you this, didn't need no fancy study paper to do so.
It's because Magic has random elements, and infinite permutability in terms of decks
@smmenen actually there are only a finite number of possible decks in Magic. I think the undecidability stems from the infinite number of possible game states.
I think on a Graham's Number* scale there is nothing infinite about magic. I'd side with you that magic is effectively infinite.
I would love to see a Computer that could generate the best deck for Vintage or even Standard.
Yes, magic is incredibly complex, far more so than Chess. Its not just that there are a lot of different cards, its that a lot of the card break the rules of the game.
On a small scale example, a few years ago, I remember trying to code an AI that could play just game 1 of Dredge with a known deck list and it was quite a few lines of code to do so. On a large scale, you can see all the issues that the MTGO team has programming each individual card.
On some of the other comments:
Candy Land has random elements, but it is a 0-player game and physically playable by a 2 year old. So it doesn't really have to do with the randomness.
Infinity is an artificial concept, not an actual number, but from a practical sense there are far too many potential game states and decks for modern computers to compute.
I read the paper and so can provide a layman’s summary.
The authors considered game states where there are no more decisions left to be made by either player, and no more randomness. There is only a sequence of forced actions and triggered effects left to be resolved.
The authors say: assume for sake of contradiction that there is an algorithm that can take such a game state as input and output who will win the game. They prove that if such an algorithm exists, then the algorithm can be used to solve the halting problem. But the halting problem is provably undecidable (no algorithm can solve it). This implies that the assumption of the existence of an algorithm that can determine the winner from a game state is false.
The sketch of the proof is that they cleverly construct a game state that can represent the internal state of a Turing machine, with the mechanics of the remaining triggered effects mapping to the execution of the Turing machine’s instructions. A Turing machine is basically a representation of any algorithm (or computer program). Here is a snippet of their construction:
Each Rotlung Reanimator needs to trigger from a different state being read – that is, a different creature type dying – and needs to encode a different result. Fortunately, Magic includes cards that can be used to edit the text of other cards. The card Artificial Evolution is uniquely powerful for our purposes, as it reads “Change the text of target spell or permanent by replacing all instances of one creature type with another. The new creature type can’t be Wall. (This effect lasts indefinitely.)” So we create a large number of copies of Rotlung Reanimator and edit each one. A similar card Glamerdye can be used to modify the colour words within card text.
Thus, we edit a Rotlung Reanimator by casting two copies of Artificial Evolution replacing ‘Cleric’ with ‘Aetherborn’ and ‘Zombie’ with ‘Sliver’ and one copy of Glamerdye to replace ‘black’ with ‘white’, so that this Rotlung Reanimator now reads “Whenever Rotlung Reanimator or another Aetherborn dies, create a 2/2 white Sliver creature token”4. This Rotlung Reanimator now encodes the first rule of the q1 program of the (2, 18) UTM: “When reading symbol 1 in state A, write symbol 18 and move left.” The Aetherborn creature token represents symbol 1, the Sliver creature token represents symbol 18, and the fact that the token is white leads to processing that will cause the head to move left.
You can sections III and IV of the paper for full details.
I think it should be coded like a sudoku puzzle and include in it that the closest logical move may not be the best move (think of finding a local max but not the best local max and definitely not the absolute max), so there has to be an element of trying suboptimal moves, even after finding the most logical, in hope of discovering a better over all path.
I’ve never even taken any upper division courses yet. Yesterday I was watching an intro to mathematical modeling on YouTube. He presented code finding the most efficient route through 60 cities and he used a “temperature”, where the higher the temperature the more chance it would take the wrong path in hope of finding s better path. As the temperature cooled, it stopped seeking better paths. I’ll try to post the link then.
@desolutionist
A number of statistical / machine learning algorithms have issues getting caught in local min/maxes.
@Smmenen Yeah, that's not the point of the article. @dshin summarizes it pretty well. What they prove is that rules of Magic and the card printed allow you to actually set up a general purpose Turing machine.
This means the result is not as trivial as showing that Magic includes variance, which is what I was curious about when I saw the article. Instead, it is a more fundamental result. it shows that Magic is just as powerful as arithmetic or a Turing machine, which in turn means that Godel's Incompleteness theorem and the halting problem (proved to be basically the same thing by Chaitin) apply to Magic.
That is to say, Magic is undecidable as a general principle. It's not just hard to perfectly predict a game of Magic; it is, in general, impossible.
@maximumcdawg “predict” is even a stronger word than necessary. The paper shows that even when there are no more decisions left to be made by either player, only forced actions and triggered effects left to resolve, it is impossible to write an algorithm that determines the winner.
@dshin said in Magic is Undecidable:
@smmenen actually there are only a finite number of possible decks in Magic. I think the undecidability stems from the infinite number of possible game states.
There are an infinite number of decks possible in magic if you assume that they will always make new cards for the game over a timeline without an end point, but more pressingly there are an infinite number of decks when you consider that there is no maximum deck size and cards that can be used in any quantity. A 5000 card deck of nothing but basic island is, for the purpose of this equation, a different deck than a 5001 card deck of nothing but basic island.
@protoaddict Pushing this even further, since there is a finite amount of cards in existence, wouldn't we go back to finite possibilities?
@protoaddict Yes, you are absolutely right, I forgot about basic lands when I wrote that.
@wagner said in Magic is Undecidable:
@protoaddict Pushing this even further, since there is a finite amount of cards in existence, wouldn't we go back to finite possibilities?
MTGO is in effect infinite and not limited by physical printings.
@protoaddict MTGO is limited by the memory of player's computers and/or the memory of the MTGO servers.
The claim of the article has nothing to do with the randomness or size of decks.
Take two decks with any number of Swamp and Relentless Rats. You can construct a list of all the possible moves for both players for all the possible starting hands and top-decks. This is a very big (exponential in the size of the deck) but finite and computable list.
The article prove that for any method you could to compute such list there is a stat of the game (using this deck) where the method take an infinite amount of time to finish. The game is called undecidable.
In practice no human player can distinguish between exponential complexity and undecidable complexity. The purpose of the article is only to prove something in game theory.
@cuikui I'm repeating myself a bit, but the result of the paper is not concerned with the number of possible moves or number of possible game states. You are right to note that these numbers are large, but the authors don't care about these numbers at all. They are not considering algorithms that try to compute these numbers.
Rather, they only consider game states where neither player has any more decisions to make. In MTGO terms, both players are essentially in "F6" mode. The question is, if we restrict ourselves to only those types of game states, is it possible to write an algorithm that determines who will win the game after the remaining forced actions and triggered effects are processed? The paper proves that the answer to this question is no.
To be very precise on what this means, consider the problem of adding two numbers, x and y. Here are 3 candidate algorithms (written in python) to solve this problem:
The authors proved that if you consider the universe of all possible algorithms that accept a game state of Magic as input (even if we restrict ourselves to those "F6-mode" states where there are no more decisions left to be made by either player), and outputs a winner as output, then every single algorithm in that universe will be like algorithm1 or algorithm2 in my example. In other words, any such algorithm will either return an incorrect output on some inputs, or go into an infinite loop on some inputs. If someone tells you, "hey, I wrote a computer program that correctly outputs the winner given an F6-mode game state as input, without infinite-looping", that'd be like someone saying, "hey, I discovered an integer that is neither even nor odd!" It's simply a mathematical impossibility, a claim that can be rejected on its face, without even looking at the code.
Why doesn’t a theoretical perfect version of MODO count? Because it enters infinite loops?
@dshin What your are describing is the definition of "undecidable" and I agree with it. I also agree that the article prove that Magic is undecidable.
My points are:
Consequence: Magic with Swamp, Rat, unlimited deck size and randomness is decidable.
So my claim is:
Undecidablility of Magic is not already contained in unlimited deck size and randomness.
We need more than only unlimited deck size and randomness to prove undecidablility and it is done in the article.
