Magic is Undecidable

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

last edited by dshin

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?

last edited by InkfathomBiomage

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.

• 27
Posts
• 8372
Views