[chmod775]

> Ok, so instead of being turing complete it requires solving the halting problem to properly referee it?

No - because the referee doesn't have to devise a program to do it. They can decide whatever they want. Also the statement of the halting problem isn't about it being impossible to tell whether a program will terminate, it's about it being impossible to devise a program that can tell whether any other program running on a turing machine (which actual physical computers are not, since they have finite state) will terminate.

For any program running on actual physical computer hardware it is obviously possible to tell whether it will terminate. For an actual game of magic, which has considerably less possible state, it's likely even trivial 99.9% of the time. The remaining 0.01% are up to the judge. In the case of MTGA on a computer, there are hard-coded limits on many things (but a lack of enforcement of the first part of the loop rule. Nexus of Fate wasn't a good time.).

[readams]

It is absolutely not true that for any problem on a real computer it's possible to tell if it terminates, other than fairly trivial observations such as noting that if it runs longer than 2^(size of memory) steps it must be looping.

If you could, then I'd start using your "real computer" halt checker to instantly mine bitcoin or break all cryptography, so let me know when you figure out out.

[aidenn0]

MTG doesn't require solving the halting problem because, if neither player nor the referee can come up with a way to halt a loop, then the match ends (long ago, when I played, it ended in a draw; other comments in this thread suggest that a player intentionally doing this may incur a loss now).

[chmod775]

> It is absolutely not true that for any problem on a real computer it's possible to tell if it terminates

Hmmm. Reading on...

> [..] other than fairly trivial observations such as noting that if it runs longer than 2^(size of memory) steps it must be looping.

So you are saying "You can't do it, even though it's trivially obvious that you can."

Or maybe "If we ignore that it is possible, it is not possible."

What am I supposed to do with your comment?

[ben_w]

2ⁿ > n ∀n ∈ ℕ (n>1), therefore while the test is trivial to define for any finite system, in practice you can't do that many steps even for very small n — n=256 states is 2^256 tests is just shy of 2e26 years if each test takes one Planck time.

For a purely theoretical system (which includes the abstracted rather than physically implemented rules of MtG as used by Churchill, Biderman, & Herrick in their paper), n is effectively ℵ₀.

https://arxiv.org/abs/1904.09828

[chmod775]

We don't actually need to know whether something will result in a loop ahead of time, so there's another approach which is much more doable in the context of MTG: Most digital CCG engines already record every past state through a history of actions (some even have full match replays). Together with engine-limits on recursively triggered actions, it really isn't that much data. You can check for repeated state here.

The most naive implementation would replay the entire previous match every time a new action happens. A better implementation realizes that you don't need to - because once you have one repeat, everything after should be a repeat as well, so you really can just keep running and merely check for repeats at strategic points (such as between turns or on any human input). Store the serialized state at those points in some appropriate Set implementation to make checking easy and fast. Increase the spacing between those checkpoints, deleting old ones, if space becomes an issue - though if you get to this point, the game has run for so long that the humans playing it probably need medical attention.

If you want to get even fancier, store serialized state rarely and just store hashes of state at checkpoints, replay from a serialized state using recorded inputs once you detect a collision.

All of this is possible because of the human element: Human just aren't physically capable of producing enough input to make a computer sweat about recording it.

One downside of this approach is that it requires some programmatic refeering in case of "numbers go up" scenarios if you don't want to wait for some player's health pool or token pile to run into the engine limit and keep the game to a length a human can enjoy (do you cap these for comparison? compare with low precision? only allow a decrease?). There's some other scenarios that will not repeat exact state until a human died of old age too. However in real life magic "Loop" is not such a narrow term - just one number being slightly different will not save you from having to explain yourself to the judge.

It'll stop this guy in any case: https://www.reddit.com/r/MagicArena/comments/amxhnk/is_there...

Since what they did was reportable behavior, I suppose technically human referees would eventually take care of it anyways.

[camgunz]

n.b. I think some of your misunderstandings and invokings of the halting problem are nerd sniping people here. One in particular that got me was:

> For any program running on actual physical computer hardware it is obviously possible to tell whether it will terminate.

You can't tell if this program will terminate:

    import random
    while random.randint(0, 100000) != 4: pass

You can intuit why that's the case (nothing at all says that random.randint ever has to return 4, or that it will never return 4), and from there you can probably also get to why it wouldn't be possible to write a program to tell you if this program would terminate.

> You can check for repeated state here.

> because once you have one repeat, everything after should be a repeat as well

> just one number being slightly different will not save you from having to explain yourself to the judge

Yeah see, I think you're seeing the problem here. Computers are pretty particular about equality: even if your states are only slightly dissimilar they're still unequal. I think you're outlining some various heuristics you might use, but those clearly aren't perfect.

And FWIW, a single repeat doesn't mean infinite repeats. There could be some outside state (an RNG, a counter) that's being updated, or literally an enchantment (function) that says "if the state of the game didn't change at all last iteration, gain 30 life". See you're thinking about states, but you're forgetting about the state machine, which can respond to unchanging states just as easily as it can respond to changes. Your heuristic also fails if you get into a loop that iterates through 2 or more states.

But I think on some level you know this right? That's why you point out that AFK there's a judge and in most game engines there's some kind of execution counter that bails if something takes too long. This stuff is related to the halting problem but they're not solutions to it, they're submissions to it.

[chmod775]

> There could be some outside state

No. Just don't use outside state? Obviously you can just make the state of your PRNG part of your overall state as well. For an actual computer it is: It's sitting somewhere in RAM.

Also remember we're trying to reason about computer programs before you come up with ideas like measuring physical phenomena.

Allowing for dicerolls going different ways is an interesting problem though (from the perspective of trying to make a playable game). Since we know whether any happened between the two states we care about, there are multiple approaches. In the case MTG, which doesn't have many dice mechanics, I'd probably just wait until we have exhausted each possibility, where possiblities means each computed direct outcome, not each possible diceroll. This lets us cut down on "gain X life" outcomes with our heuristic judge (2000 + 3 would be the same as 2000 + 2 to us). Most cards with dicerolls only have 2-3 outcomes, even if they roll a d20.

> or literally an enchantment (function) that says "if the state of the game didn't change at all last iteration, gain 30 life"

There's no problem here if you consider the last iteration part of the state of the current iteration. Attach that previous state (sans recursion) to the state of the enchantment on the field. You'll need it to code that enchantment anyways.

> but you're forgetting about the state machine, which can respond to unchanging states just as easily

It becomes quickly obvious that a FSM itself can't detect that its own state didn't change between the previous two iterations and make that affect the next state.

Simple example:

    function FSM(previousState: number): number {
        if (stateDidntChange(previousState)) {
            return 0;
        }

        return blackbox(previousState);
    }

How would you implement stateDidntChange, so the FSM's state becomes 0 when state was the same for two iterations? You may think you can move the if clause after the blackbox state computation and compare the return value, but then you merely prevent the machine from having the same state twice in a row, and are not responding to it actually having happened.

To illustrate, let's assume blackbox always returns 2. You can never make the return value of FSM be 2, 2, then 0.

You would have to add more state to the FSM to detect this, but then you'd have more state you need to compare!

Now if we just want to compare a subset of the state, that's fine. We can do that by storing a copy of the previous state in the overall state - but doing it like that also causes no issues with my proposed loop detection.

[ben_w]

> The most naive implementation would replay the entire previous match every time a new action happens. A better implementation realizes that you don't need to - because once you have one repeat, everything after should be a repeat as well, so you really can just keep running and merely check for repeats at strategic points (such as between turns or on any human input). Store the serialized state at those points in some appropriate Set implementation to make checking easy and fast. Increase the spacing between those checkpoints, deleting old ones, if space becomes an issue - though if you get to this point, the game has run for so long that the humans playing it probably need medical attention.

Any test of this type only works if there is a repeat, which you can only know about if you have a finite machine, and even with finite steps it takes 2^n steps[0] to be sure you've hit an infinite loop. Even in a computer, even with a fairly small deck to build the state, you'll time out on things like the stars going out before you can rule out any loop.

And there isn't necessarily any repeat at all in the unbounded case. The state is recorded by 18 types of card, where "moving" left or right along the tape modifies the number of hitpoints on each card. At that point, I think you can still kinda decide if it halts or is infinite with the Busy Beaver number, except only "kinda" because now you run into the problem that the Busy Beaver number itself isn't generally computable because of the halting problem.

Also the lower bound S-number for a mere 2-state 6-symbol machine, let alone the 2-state 18-symbol one in the paper, is already 10⇈10⇈(10^(10^115)), which is so much larger than the Poincaré recurrence time of the universe (even when measured in Planck times) as to make those periods themselves to be infinitesimal rounding errors.

> All of this is possible because of the human element: Human just aren't physically capable of producing enough input to make a computer sweat about recording it.

In practice, it's the opposite problem: for both humans and computers, even if you already know what it's going to compute and it's only doing something simple, it takes ages to get through enough states to say either way. It's a very slow Turing machine.

[0] well actually[1] it's something more like min(2^n, BB(2, 18)), but BB numbers grow so much faster that in practice they only matter for infinite tapes

[1] I've probably got this wrong, like getting the m and n switched around because the terminology doesn't seem to be entirely consistent, hence me starting that footnote with the traditional catchphrase for someone about to say something stupid :P

[robertlagrant]

> So you are saying "You can't do it, even though it's trivially obvious that you can."

They're referring to the halting problem. If you believe you can solve it, you will win money[0].

[0] https://www.claymath.org/millennium/p-vs-np

[chmod775]

> They're referring to the halting problem. If you believe you can solve it, you will win money.

Proving that you can programatically determine whether a program halts when you limit the turing machine to finite memory is trivial - which the conversation you interjected was about.

[robertlagrant]

They weren't saying the problem was trivial. They were saying that if you massively reduce the problem to its most trivial form, then its trivial form is doable.

[chmod775]

> They weren't saying the problem was trivial.

Neither was I? The proof is trivial - actually doing it is very much not.

[kbrkbr]

You probably meant 99.99%, or 0.1%.