Magic: the Unsolved Problems in Mathematics

[Elvish Pillager]

I thought this would be fun, but I don't have enough time to waste spend on it right now. I figured XKCDers might be interested in it though.

Construct a situation in the game Magic: the Gathering where the winner (assuming ideal play) depends on an unsolved problem in mathematics.

For instance, a situation where player A wins if the Collatz Conjecture is true, and player B wins if it's false. (That one suits the M:tG rules rather well, since it only relies on integers, division by two, and multiplication. There's probably a variety of other problems that you could use, but that's the one that came to mind.)

[mike-l]

In order that it can't simply be brute forced, you're going to need play to go on indefinitely, so both players are going to need multiple copies of something like http://magiccards.info/query?q=!Quest+f ... nt+Secrets. You're also going to need a resource that can be accumulated indefinitely, eg counters.

So, something like, each player has a library consisting of one timetwister. They each have a 0/1 monster with N +1/+1 counters, both have a dismember, and then a third 'Collatz' card which does the collatz process on all counters on the board. Then it's a tie for all N except for those which the Collatz fails. They each have enough mana, and the counters got there in the first place via other cards that are now exiled with no return condition.

[undecim]

In order that it can't simply be brute forced, you're going to need play to go on indefinitely, so both players are going to need multiple copies of something like http://magiccards.info/query?q=!Quest+f ... nt+Secrets. You're also going to need a resource that can be accumulated indefinitely, eg counters.

So, something like, each player has a library consisting of one timetwister. They each have a 0/1 monster with N +1/+1 counters, both have a dismember, and then a third 'Collatz' card which does the collatz process on all counters on the board. Then it's a tie for all N except for those which the Collatz fails. They each have enough mana, and the counters got there in the first place via other cards that are now exiled with no return condition.

Not necessarily. There are plenty of permanents with optional actions (i.e., when X you may Y). There are several combinations that result in infinite loops if both players continue this infinitely. This can mean that not only a single turn, but a single stack can continue indefinitely.

Also, for those that don't know about it: http://gatherer.wizards.com/

[mike-l]

Quite true, I didn't think of that.

[Elvish Pillager]

The solution I'm imagining is something like this:

It's Player A's turn. Player A has access to unlimited mana, has Psychic Battle or something (so ze'll win if it gets back to zir turn again), and Dawnglow Infusion. Player B has a weird setup that can't do anything except the Collatz process on Player A's life total (i.e. player B can halve player A's life total at will, but only if it's even, and can *3+1 player A's life total at will, but only if it's odd), and only works on Player B's turn (so ze can't mess up player A's initial life gain.)

Essentially, Player A can set zir life total to any positive integer, and player A wins if that integer is a counterexample to the Collatz conjecture and otherwise loses. You just have to figure out what stuff player B can have that gives that limited set of abilities.

A gamestate that doesn't depend on the players to know the strategies, but simply *forces* the game to end one way or the other based on the result, would be trickier, since an infinite loop is just a draw. I'm pretty sure it's impossible to do an "A wins if Collatz is true, otherwise B wins", because it's a statement about all positive integers, and so you'd have to check all of them, which would take forever. If we knew there weren't divergent trajectories, then you could have a "tie if it's true, win if it isn't" situation, but we don't even know that.

[undecim]

The solution I'm imagining is something like this:

It's Player A's turn. Player A has access to unlimited mana, has Psychic Battle or something (so ze'll win if it gets back to zir turn again), and Dawnglow Infusion. Player B has a weird setup that can't do anything except the Collatz process on Player A's life total (i.e. player B can halve player A's life total at will, but only if it's even, and can *3+1 player A's life total at will, but only if it's odd), and only works on Player B's turn (so ze can't mess up player A's initial life gain.)

Essentially, Player A can set zir life total to any positive integer, and player A wins if that integer is a counterexample to the Collatz conjecture and otherwise loses. You just have to figure out what stuff player B can have that gives that limited set of abilities.

A gamestate that doesn't depend on the players to know the strategies, but simply *forces* the game to end one way or the other based on the result, would be trickier, since an infinite loop is just a draw. I'm pretty sure it's impossible to do an "A wins if Collatz is true, otherwise B wins", because it's a statement about all positive integers, and so you'd have to check all of them, which would take forever. If we knew there weren't divergent trajectories, then you could have a "tie if it's true, win if it isn't" situation, but we don't even know that.

If you're going to try for Collatz, the biggest problem is having different things happen on odd or even life. So you'll probably need some other convoluted process to get that basic mechanism.

[legend]

sounds really difficult, but it might be possible.
I'd say player B needs Chaos moon and an infinite turn combo (using Time Vault or something). Player A has a mox lotus and Goblin Offensive. Now we just need a way to half / triple+1 the goblins depending on their strength...

[Elvish Pillager]

Another possible way to measure even/odd is to use Banshee or Aspect of Wolf and check whether the numbers are equal or not. Or other "rounded down/up" cards if you can also double the value and check if it's equal to the original value.

[skeptical scientist]

Another possible way to measure even/odd is to use Banshee or Aspect of Wolf and check whether the numbers are equal or not. Or other "rounded down/up" cards if you can also double the value and check if it's equal to the original value.

If you want to implement Collatz, measuring whether Z is odd or even is only useful if Z is something you can make arbitrarily large. Counting forests is only useful if there's a card (or combination of cards) which can be used to generate forest tokens (or tokens that count as forests). Measuring the mana in your pool seems potentially more useful, but there's nothing to stop a player from leaving leftover mana in their pool when they use the banshee ability, so it won't check whether their mana pool is even/odd, just whether the mana they spent was even/odd. So that seems problematic.

What we really want is a combo that can perform collatz on the enemy's life total (repeatably), but can't be used to modify their life total in other ways.

[Elvish Pillager]

Counting forests is only useful if there's a card (or combination of cards) which can be used to generate forest tokens (or tokens that count as forests).

There is - either animate a forest and use something that copies creatures, or make lots of Saproling tokens and use Life and Limb.

[Xias]

In order that it can't simply be brute forced, you're going to need play to go on indefinitely, so both players are going to need multiple copies of something like http://magiccards.info/query?q=!Quest+f ... nt+Secrets. You're also going to need a resource that can be accumulated indefinitely, eg counters.

So, something like, each player has a library consisting of one timetwister. They each have a 0/1 monster with N +1/+1 counters, both have a dismember, and then a third 'Collatz' card which does the collatz process on all counters on the board. Then it's a tie for all N except for those which the Collatz fails. They each have enough mana, and the counters got there in the first place via other cards that are now exiled with no return condition.

Not necessarily. There are plenty of permanents with optional actions (i.e., when X you may Y). There are several combinations that result in infinite loops if both players continue this infinitely. This can mean that not only a single turn, but a single stack can continue indefinitely.

Also, for those that don't know about it: http://gatherer.wizards.com/

You cannot have an infinite loop caused by choosing to use "may" actions indefinitely. If an optional action is involved, you must show your opponent the loop and then declare how many times you are going to do it, and they have the chance to interrupt it. So an optional combo can not continue indefinitely, since you must define it.

For example: Say you control a Fiend Hunter, which has exiled another Fiend Hunter you control. If you play another Fiend Hunter, targeting the one on the battlefield, you can create a loop of Fiend Hunters exiling each other. However, since it is a "may" action, the infinity rule requires that you say how many times you are going to do it (say you have a Soul's Attendant on the battlefield, you say "I do this 1,000,000 times and gain 1,000,000 life.")

Even on a must, if you choose a target (such as Oblivion Ring) if there is another valid target that would halt the loop, you are required to break the loop. So if you wanted to do the same thing with Oblivion Ring as you did with Fiend Hunter, you may only loop the exiles a definite number of times before declaring another target, UNLESS there is no other valid non-land permanent to target, in which case the game ends in a draw.

So I don't think any kind of looped combo would work for this, unless you say "I repeat this loop until I reach an integer that violates the Collatz Conjecture," but I don't think that qualifies as declaring a number, nor does it really fit the spirit of the problem.

[Nitrodon]

So I don't think any kind of looped combo would work for this, unless you say "I repeat this loop until I reach an integer that violates the Collatz Conjecture," but I don't think that qualifies as declaring a number, nor does it really fit the spirit of the problem.

I was assuming it was more along the lines of "I repeat this Collatz loop until [whichever number is involved] becomes small enough to allow me to win." For instance, if it's possible to construct this Collatz loops with the number of Saproling tokens player A controls, then player B can use the Collatz loop until the number of Saprolings is small enough that A can't block all of his creatures, so B wins. If A chose a counterexample to the Collatz conjecture, then B will be forced to break the loop, and will be unable to block enough Saprolings on A's turn.

[Yakk]

Not a complete answer, but I like abstracting problems away.

First, start with this:
http://draw3cards.com/questions/2851/is ... /3225#3225
next, set up a turing machine whose answer is a function of an unsolved problem in mathematics.

Finally, figure out a way to map that to win/lose. And set up the tape (or at least describe how). And ensure that the only way to win is to execute the program (or start the situation after the program starts, which would qualify -- everything in the program is apparently triggered).

[skeptical scientist]

Finally, figure out a way to map that to win/lose. And set up the tape (or at least describe how). And ensure that the only way to win is to execute the program (or start the situation after the program starts, which would qualify -- everything in the program is apparently triggered).

Sort of. There are lots of optional triggered abilities, and the M:tG state carries out the computation only when they are all taken. This makes things very problematic, because Bob can mess with the Turing machine configuration by e.g. choosing not to put +1/+1 tokens on creatures when he has the option. Bob can also mess with things by choosing to use non-triggered abilities, like sacrificing creatures to Teysa. It's entirely possible that Bob can get from a configuration representing the start of a non-halting computation to a configuration representing a halt state by carrying out all the steps he is supposed to, but choosing not to place +1/+1 tokens that he has the option of placing, or sacrificing creatures in the tape. So if you managed to add a mechanism so that Bob wins iff he gets to a configuration representing a halt state, or some other way to map that to win/lose, it's possible that Bob could win even if the Turing machine doesn't halt.

I don't suppose there's an unglued card which has the effect of replacing all instances of "may" on all cards with "must", or something to that effect?

[Gwydion]

Sure, but taking back the example of the Collatz card used on your opponent's life total - say B's only cards in play are this Collatz card and an Enchanted Sorceror (or equivalent). The only way for B to win this turn (or at all, given Psychic Battle or equivalent) is to use Collatz a finite number of times, followed by tapping the Tim for A's last life point. A, therefore, has a (potential) winning strategy of choosing a life total for which B is unable to reduce A's life to 1, and assuming perfect play, A wins iff he disproves the Collatz conjecture via counterexample.

[Yakk]

I suppose the goal would be to somehow prevent other options from being winning ones. The may instead of must are somewhat limiting... If we somehow blocked other abilities, and skipping the may just stopped you, and the goal was to reach exactly n creatures - which we arrange as our halting state - then we could imagine a way to turn a Turing process into an effective must.

An easier problem would be to force an NP hard problem instead of an unsolved one. Because I do not see a Collatz operator just falling out of magic...

[skeptical scientist]

Sure, but taking back the example of the Collatz card used on your opponent's life total - say B's only cards in play are this Collatz card and an Enchanted Sorceror (or equivalent). The only way for B to win this turn (or at all, given Psychic Battle or equivalent) is to use Collatz a finite number of times, followed by tapping the Tim for A's last life point. A, therefore, has a (potential) winning strategy of choosing a life total for which B is unable to reduce A's life to 1, and assuming perfect play, A wins iff he disproves the Collatz conjecture via counterexample.

Okay, yes, it's obvious that you can do it if you're allowed to make up your own cards.

[Elvish Pillager]

[Dopefish]

Can I target myself?