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:

• algorithm1 will always return something. The problem is, that something is not always correct - it will output 4 as the sum of 1 and 2, which is incorrect.
• algorithm2 is better in some sense - it never returns an incorrect output. However, it has another problem - it sometimes runs forever, never returning anything. For instance, if you ask for the sum of 0 and 1, it recursively calls itself, which calls itself, etc., going into an infinite loop.
• algorithm3 gets the best of both worlds - it always returns something, and it never returns an incorrect value

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:

• If a game always have a finite number of possible move then it is decidable
• Magic with Swamp, Rat, unlimited deck size and randomness only produce finite possible moves during a full match

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.

@inkfathombiomage That’s like asking, why doesn’t an integer that is theoretically even and odd count? No such thing can exist.

The current MODO will either output an incorrect value on some inputs, or infinite loop on some inputs. Any theoretical modified version of MODO will have the same property.

That’s true, I was thinking more if they fixed the bugs in MODO. It would still enter into an infinite loop if someone played animate dead with worldgorger as the only creature in their graveyard, but only because the gamestate entered a loop. Is this the only place it would run into problems? Was that even addressed by the article?

I think MTGO is protected from infinite loops by the fact that it keeps prompting players when they get priority, and there is a game clock. If you turned off the priority checks and game clock then absolutely you could soft-lock the game within the Rules of Magic alone. I mean, legitimately, not just because MTGO is poorly programmed.

This is, incidentally, why the shortcut rules don't work and certain decks with infinite combos are more difficult or impossible to run on MTGO.

To be clear, just because the game enters an infinite-loop within the rules of Magic doesn't mean that a software program implementing those rules must also enter an infinite-loop. A program like MTGO can, in principle, perform logical deduction on the game state to determine that the game rules yield an infinite-loop, and then output the correct game result (the rules of Magic specify that infinite-loops result in draws). The paper shows that a program like MTGO cannot do this deduction perfectly. Any such attempt will be "buggy" - not due to incompetence of the programmers, but due to the laws of mathematics. But it is certainly plausible that, if well programmed, such a program can do it well-enough to cover all "real-world" situations.

Makes sense, thank you!

This is the same reason a computer compiler can't tell you if your program is going to fall into an infinite loop perfectly.

I feel obliged to point out that there have been significant attempts at creating MtG Turing machines before: https://www.toothycat.net/~hologram/Turing/

The main difference in this preprint is that the Turing machine runs fully automatically, and continued operation does not depend on any player choices including agreeing to play all "may" abilities.