9

In this paper, the authors prove that it's possible to construct a Legacy-legal combo deck where the comboing player constructs a Turing Machine through mandatory actions, which begins to execute a series of actions that will result in one player either winning or losing the game, but determining which of these actions will occur is as hard as the Halting Problem.

What would occur if a player were to construct and execute this combo in a real Magic: the Gathering tournament?

doppelgreener
  • 24,520
  • 15
  • 96
  • 170
nick012000
  • 742
  • 6
  • 15
  • There is a video where somebody actually built this and also asked a judge what would happen: https://youtu.be/pdmODVYPDLA – CALEB F Mar 18 '20 at 13:28
  • 5
    They would lose to someone that has a deck that is optimized for winning. – Acccumulation Mar 18 '20 at 22:31
  • 3
    "which begins to execute a series of actions that will result in one player either winning or losing the game" - no, either one player wins, or the game is a draw due to an infinite loop. If there was sure to be a winner, then the victor could be determined simply by playing the game to conclusion. – user2357112 Mar 19 '20 at 00:02
  • @user2357112supportsMonica: It doesn't sound like you're familiar with the Halting Problem – Mooing Duck Mar 19 '20 at 00:21
  • 3
    @MooingDuck: I am quite familiar with the halting problem. If you read the paper linked, you'll see that it matches my description and not the question's description. The reason it can't be "one player either wins or loses" is because there's no way to turn an infinite loop into a victory for either player (or if there is some weird card that does that, the paper doesn't use it). – user2357112 Mar 19 '20 at 00:23
  • 2
    The only way to guarantee that one player either wins or loses is to construct the combo in a way that is guaranteed to halt, and if the setup guarantees halting, then you don't have to solve the halting problem. – user2357112 Mar 19 '20 at 00:24
  • 2
    (Particularly, note section IV.F of the paper, where halting is encoded as Alice winning, and non-halting is considered a draw by infinite loop due to rule 104.4b.) – user2357112 Mar 19 '20 at 00:30
  • 1
    "In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever." Applying that here: there's no generic rules you can apply to determine if the deck is infinite, other than playing it out and watching for patterns in board state. – Mooing Duck Mar 19 '20 at 17:59
  • 1
    I understand the halting problem. If the game is a draw, you may not be able to tell. Following the MtG rules may require hypercomputation. That's the point of the paper. My point is simply that the question says the combo results in a win or a loss, but the actual combo results in a win or an infinite loop draw (which may be impossible to determine). – user2357112 Mar 20 '20 at 00:05
  • ok, that paper was a good read :) – ikegami Mar 25 '20 at 06:35

2 Answers2

14

This situation, in which no player knows whether a sequence of mandatory actions will end or loop forever, is so rare and so niche that neither the comprehensive rules nor the tournament rules address it. By a strict reading of the rules, players would need to continue executing the loop until they either know it will end, or that it will loop forever.

Practically speaking, in most situations either the players will eventually agree to end the game in a draw, or one player will just concede.

In a tournament, if neither player wants to end the game, they will keep playing, the game will go to time, and after the 5 overtime turns, the game will end in a draw. Or the "Turing Machine" will halt during that time; that's always a possibility. If someone ever finds a combo like this that never needs to pass the turn, a judge will probably rule that the game ends in a draw after it goes on long enough to start cutting into the next round's time.

If one player wants to end the game with a draw, but the other doesn't, and neither wants to concede, the first player will probably call a judge. There is no guidance for a situation like this in the existing judging documents, so they will have to make a judgement call, which will probably be either that the players have to continue playing it out, or that the sequence of mandatory actions has gone on long enough to qualify as a loop, and the game is a draw.

murgatroid99
  • 81,939
  • 10
  • 218
  • 317
  • 1
    Side note, there are examples of bannings (Second Sunrise) and rules adjustments (treatment of the Four Horsemen combo ) to ensure that tournaments can be played in a timely manner. – Swimmer F Mar 18 '20 at 10:36
  • To go along with @SwimmerF’s comment, the ultimate example is probably Shahrazad, which is banned in every format ever, including casual formats like Commander, because of how preposterously long it takes to execute. – KRyan Mar 18 '20 at 18:02
  • The problem with the Turing deck is that it need a exact hand to even work so most likely it would lose ever match and then draw for time if it got the right hand. – Styxsksu Mar 18 '20 at 20:06
4

According to the rules, the machine would be played out until one of the following occurs:

  • It halts. (A player wins and the other loses)
  • It visits a previously-visited state. (Loop of mandatory actions ⇒ Draw)
  • Time runs out. (Draw)

Of course, tournaments have human judges and human organizers, and these may decide a different outcome is appropriate.

Sometimes, a game of MTG returns to a previously visited state. When this happens, the game is deemed to have looped, and one of two things happens:

  • If non-mandatory actions were taken in between the two identical states, a player must take a different action.[CR 721.3]

  • If only mandatory actions were taken in between the two identical states, the game ends in a draw.[CR 721.3]

It's crucially important that we don't need to determine if a loop will occur; we only need to determine if a loop has occurred.

Determining if a loop will occur requires solving the halting problem.

Determining if a loop has occurred "merely" requires comparing the current game state against the previous game states. While unbounded storage may be required to record every achieved game stats and whether the action that caused the transition to each state was mandatory or not, solving the halting problem isn't required.

In practice, keeping track of each state isn't necessary because each state is assumed to be unique until the assumption has been demonstrated to be false. In other words, people only start paying attention if they suspect a loop is occurring.

721.3. Sometimes a loop can be fragmented, meaning that each player involved in the loop performs an independent action that results in the same game state being reached multiple times. If that happens, the active player (or, if the active player is not involved in the loop, the first player in turn order who is involved) must then make a different game choice so the loop does not continue.

721.4. If a loop contains only mandatory actions, the game is a draw. (See rules 104.4b and 104.4f.)

We've established that it isn't necessary to solve the halting problem to determine if the game has resulted in a draw.

So what are the actual consequences of being able to implement a Turing Machine in M:TG?

Proposing a Shortcut May Require Solving the Halting Problem

When players propose a shortcut, they describe a sequence of game choices which may be a loop that repeats a specified number of times. For a shortcut to be proposed, the resulting game state must be known by the player proposing the shortcut, and it must end with a player gaining priority. As such, the loop only occurs if the loop is already known to halt.

But it does mean that a player may have to solve the halting problem to determine final state of the shortcut he wants to propose. Attempting to do so with result in a Slow Play error. They will be forced to abandon their shortcut.

In short, a timeout is utilized to avoid having to solve the halting problem.

Knowing If a Game Will End May Require Solving the Halting Problem

It's possible for a M:TG game to never end. Trying to determine if they will end (and when) would require solving the halting problem. Rather than trying to do this, tournament games are given a time limit.

In short, a timeout is utilized to avoid having to solve the halting problem.

Community
  • 1
ikegami
  • 47,712
  • 3
  • 83
  • 167
  • Assuming the loop like this exists in a single turn, and doesn't meet the first two conditions, would timeout even ever occur? Is there even an actual timeout rule that doesn't require turns to end? – Andrew Mar 25 '20 at 19:39
  • 3
    @Andrew, That isn't possible with the machine in the paper linked by the OP. But let's say that someone comes up with such a machine. A judge would probably rule that they are failing to "take their turns in a timely fashion" and to "adhere to time limits specified for the tournament". Both are these are Slow Play. It's hard to defend that it's not your fault that your machine is taking too long when you single-handedly constructed the machine. – ikegami Mar 25 '20 at 19:58
  • 1
    Executing a complex combo is not slow play. If you have only mandatory actions available and you are taking those individual actions quickly, you can't actually make the game go faster at that point in the game so it doesn't make sense to penalize you for playing slowly. The slow play rules do not mention the tournament time limit at all, and nothing in the rules addresses what happens if the turns after time is up take an unreasonable amount of time. – murgatroid99 Mar 25 '20 at 22:40
  • @murgatroid99, Re "The slow play rules do not mention the tournament time limit at all", The passage I quoted is a directed quotation from the definition of SP. /// Re "so it doesn't make sense to penalize you for playing slowly", It does make sense to penalize people intentionally creating a situation where a turn takes over an hour. (Not saying they should or they will.) – ikegami Mar 26 '20 at 01:26
  • OK, you're right, I actually missed that part. But there are specified additional turns after the time has ended, and those have no specified time limit. So there's no established standard for penalizing someone for having those turns take too long. In any case, the point of the slow play rules are about penalizing taking actions slowly and taking actions that do not advance the game state, not for simply playing a combo that takes a lot of steps to play out. – murgatroid99 Mar 26 '20 at 03:27
  • @murgatroid99, Re "So there's no established standard for penalizing someone for having those turns take too long.", Also, there's no established standard for handling hour-long turns. But something has to happen. Ultimately, it will be a political decision, not a rule decision. – ikegami Mar 26 '20 at 03:32
  • The usual interpretation of "loop" in rule 104.4b doesn't require revisiting game states. For example, a situation where one player is forced to put more and more +1/+1 counters on a creature forever would be ruled a loop draw. Also, rule 104.4b says that the game is a draw as soon as the loop is entered, not after it revisits a previous state or after the loop executes a complete iteration (however you want to define iterations). – user2357112 Mar 27 '20 at 02:33