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.
@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.
@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.
@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.
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.
there are things other than planeswalkers that can be proliferated, though I'm not sure if pentad prism is vintage playable
Gemstone Mine is a card that benefits from the proliferate mechanic. There could be some weird tech with cards like Tanglewire or Smokestack.
You can also use proliferate on your opponents’ permanents. Mystic Remora and Chalice of the Void are a couple examples of cards against which that option could be relevant.
Nothing terribly exciting, but just some possible interactions to keep in mind if the right proliferate card comes along.
Some other Vintage cards besides dredge cards and Snapcaster Mage for which the third ability can be relevant: JVP, Deathrite Shaman, Yawgmoth’s Will, Dark Petition, Cabal Ritual, Ancient Grudge, Vengevine, Squee, Wonder, Riftstone Portal, Life from the Loam, Goblin Welder, Sun Titan, Auriok Salvagers, Tarmogoyf.
This card is potentially the first main-deckable graveyard disruption that has an element of surprise, which might open up new tactical scenarios. The storm player facing down Deathrite Shaman knows to be careful when firing off Cabal Ritual or Dark Petition; otherwise he knows that he is highly unlikely to run into Ravenous Trap. But with this card the risk of surprise graveyard disruption becomes higher.
I suggested changing the per-deck-limit for Mishra's Workshop to 2 or 3, but it seems this suggestion is not really being taken seriously. I suspect the reason for this is the same reason that the DCI used for maintaining a single B/R list for both Type 1 and Type 1.5 in the past: fear of administrative complexity. I can understand that having a max-1-of list, a max-2-of list, and a max-3-of list, rather than just a single restricted list, seems scary.
As long as we are thinking outside the box, another solution to achieve a similar end is to change the parameters of the game for Vintage. @Smmenen has argued elsewhere that it's not unreasonable for different formats to have different mulligan rules. So why not change the 60-15-7 parameterization of the game for Vintage? (60 cards maindeck, 15 cards sideboard, 7 cards starting hand)
It would be an incredible coincidence if 60-15-7 turns out to be the parameterization that optimizes quality of experience for Vintage. The optimal parameterization is probably something else.
Maybe 80-25-7 would work better for the format. It would drop the Mishra's Workshop % to 4/80 = 5%, which matches what my max-3 proposal would achieve, which is why I say this would be another solution to achieve a similar end.
Rather than blue decks having something like 54 core cards with only room for innovation on the remaining 60-54=6, we might have room for innovation on 80-54=26 cards, leading to more diversity.
By having more room for sideboard, there is more opportunity for innovative transformation strategies, and more space to pack specific answers to threats. These things should ultimately leads to more skillful games.
@brianpk80 feels that 1/60 = 1.66...% is too high a density for Monastery Mentor in a deck, and thus suggests banning it. My suggestion would lower the maximum Monastery Mentor density to 1/80 = 1.25%, which is a meaningful decrease.
Philosophically, as long as the card pool keeps growing, I think an increase beyond 60 must be made at some point. Preordain, Ponder, Brainstorm...more cards like this will inevitable come, and at some point, years from now, even if every one mana cantrip is restricted, you'd be able to pack 30 of them in one deck if you really wanted. A format like Modern is always culling the card pool and so will never face the same kind of pressure to alter its game parameterization.