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.

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