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

[camgunz]

> No. Just don't use outside state? Obviously you can just make the state of your PRNG part of your overall state as well.

You can't write a program to analyze any given PRNG (or whatever) to know what it will return when without executing it. You could do this for some PRNGs, but that... probably doesn't meet the definition of pseudorandom.

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

Oh I think if anyone's doing this it's you: one of your argument's main legs is that you can analyze RAM usage.

> In the case MTG, which doesn't have many dice mechanics

Yeah the last I played was Homelands so I'm very out of date. If we restrict ourselves to MtG then yeah, I think dice probably aren't insurmountable. For instance, dice are pretty limited RNGs, so you can easily interpret them as ranges to limit the scope of states you'd need to track, and you can do even better if they're just numeric values (i.e. it's always like "add N health" or "add N * 2 health") instead of branches (N <= 2 you lose, N >= 4 you win). This is modelable in finite space, and as you point out the space in general is pretty small. So, yeah sometimes the domain can allow you to avoid theoretical pitfalls.

> Attach that previous state (sans recursion) to the state of the enchantment on the field. You'll need it to code that enchantment anyways.

I'm not super sure what you mean here. I've been thinking of state as like, what cards are in play/hands/graveyard/etc, (tapped) lands, counters, turn, life, phase, and so on--basically whatever you would save in a game save to restore it later. I guess maybe you're thinking you can save something like a triggered or didn't trigger flag on every enchantment as part of your state, but this only works for the "check last state" enchantment, not a "check the last 10 (or N) states". Again I'd be very surprised if there were ever a card like this, so we're purely in the wider realm of the halting problem. My only point here is that there's, as Wikipedia puts it, always a theoretical pathological program (enchantment) to do the opposite of what your heuristic analysis program expects it to do, such that it's not possible to write a general analysis program to see if a Turing complete program will halt. I think the answer re: MtG is: don't print that card lol.

> How would you implement stateDidntChange

Nah let's not get confused here. States are successive, not recursive, i.e. they can refer to each other ("last turn", "after untap") but they can't contain each other. Re: implementation, generally the execution engine has some container of states it can access in various ways (previous, first, current, etc) and things in the program/game can access them. In this way you can then check for changes, because you now have access to more than 1 thing.

But, yeah you can get around this by just limiting the number of states you'll store that haven't changed, and not printing cards (writing expressions) that refer to states outside that limit. This is what a lot of in-game scripting engines do: if you've run N bytecode ops or for M seconds without finishing, you're looping infinitely (even if you might not be) and you're killed. Hardware watchdog timers do a similar thing. So, I think overall you're right that in practice we deal with the halting problem in arbitrary ways all the time and it's very OK, you just kind of have to outline the kinds of valid programs you're disallowing.