There's a ton of fascinating stories coming out in the last decade around hacking/exploits/etc of games of that era; DAoC, UO, Shadowbane (this one was real bad).
I'd highly suggest checking out these two episodes of this podcast - https://darknetdiaries.com/episode/7/
- there were hell levels
- Halflings instead of Humans got the XP bonus (and that there actually WERE race/class XP differences?)
- early Shaman alchemy actually WAS broken
Also wasn't it what lead to eqemulator.org?
If you encrypt it, this is no longer possible. If a cheater wants to decrypt it, he has to get access to the decryption key, which usually is send over an TLS encrypted connection (with certificate pinning in place) [Or in some cases self made encryption :/].
Therefore he has to either reverse the game to get the certificate or has to attempt to read it while the game is running. In the first case the game developers (and the Anti-Cheat providers) will try there best by obfuscating the specific regions. And the 2nd case is basically what AC is all about, and therefore difficult for modern Anti-Cheats.
Versus just reading clean packages from a network.
ShowEQ definitely showed drops at some point. I vividly recall farming lightstones from Willowisp and using ShowEQ to ignore the ones with burned out lightstones.
Is this sort of packet sniffing (to cheat) far more difficult (impossible?) for browser-based games ?
Assume of course a modern browser fairly standard use of the browser itself
I dont get that. Maybe I am missing something.
Lets say, the MTG AI was so intensive to run that it would be unreasonable to run on the customer's machine - then I wouldn't run it on the server either, since it would be quite expensive (and bot games in card games are usually not pay per play).
Also, servers are not magic - most of them run on the same x86 CPUs as the local machine, with a lower clockspeed than their desktop counter parts (but higher than (most) notebooks). Therefore, the only way to archive a lower Bot turn timer compared to running locally would be to use significantly more cores than the customer (usually 4-8, hence 8-16 allocated cores per player?!). Sounds like a nightmare, especially during peak concurrent player hours/days!
If the CPU Player does not support multi-core, running locally should be faster in any case.
> I dont get that. Maybe I am missing something. Lets say, the MTG AI was so intensive to run that it would be unreasonable to run on the customer's machine - then I wouldn't run it on the server either [...]
They said "footprint", not "processing power". The bot's rules engine is small enough to run in the memory footprint on older iPhone or Android devices, a server could have a lot of memory dedicated to holding a state machine or rules engine and still use very little processing power to execute the engine for any particular request.
But to address your point, while that is true, Sparky itself plays with very basic decks, and plays even those very poorly. The goal of Sparky is to introduce players to the rules, not to be a competitive MtG agent; playing badly is intended. I wouldn't be surprised if Sparky's code is actually just a bunch of very simple heuristics (maximize your mana utilization this turn, attack with any creature that can trade evenly or better, etc).
For anyone interested, I'm _inactively_ working on an unofficial client of MTGA which does hardly anything meaningful for now. The vision is to provide some automation for playing ranked games and stronger bot opponents. Sadly I was distracted lately away from the project and am still puzzled how to make a good UI to see things clearly. I can't even estimate when it will be barely useful.
Beside that, I'm still very interested in any game hacking story of Daniel and anyone else! Please tell me more about how to spot such bugs, how not to worry being banned after such hacking, how to `disclosing the bug to them` like @aethros commented, how to structure an unofficial card game client, and other stories. Thank you!
[0] https://github.com/MayerDaniel/mayerdaniel.github.io/issues/...
This is a huge understatement, since the game is nearly (no infinite loops) Turing complete, and people have a lot of fun with that. I assume there's a lot of work already done on AI strategy for it though.
The post title should probably have a "Show HN:" on it too, since you're posting it yourself.
A proxy can be as simple as a basic land with Sharpie writing on it, so this format is by definition as affordable as Magic can ever be.
WoTC as a card distrubtor on the other hand, does not agree with this. Thankfully they have no input on the matter. And is why they push the online avenues as much if not more than paper.
I once developed a small game. Sometimes, for responsiveness, you need to implement game logic on the client. But nothing says you can't redo the logic on the server and that's what I did.
It can be hard on a real time game like FPS or RTS, but there simply is no excuse for a card game.
I think for a card game like this you really want to send no more information to the client than a real player would see. So for example, rather than send the cards that the opponent has in hand, just send the number of cards that he has -- no more and no less than what you would see in a real game situation.
It goes without saying that any actions sent to the server are only speaking for you and not your opponent. So no, you should not be able to declare forfeit for your opponent. You should only be able to say "forfeit!" which the server interprets as your forfeit because you are the only player you have power over.
The exploit was that one was able to set up a second client and connect to the currently ongoing game but in the opponents seat, once this was done they could sene actions as the opponent including the forfeit action.
As the article clearly states, the game play is entirely server side. The author exploited a problem in the authorization and game connection code, not any client side game logic.
> It goes without saying that any actions sent to the server are only speaking for you and not your opponent. So no, you should not be able to declare forfeit for your opponent. You should only be able to say "forfeit!" which the server interprets as your forfeit because you are the only player you have power over.
You are simply repeating how exploit that the author found works.
One thing I don't understand is, in the case where you connect your bot during a real match, 1) why does the game allow someone to join mid-match, and 2) when the bot resigns, why does that count as your opponent resigning? If it's creating a 3-player game, Player 3 conceding shouldn't also make Player 2 concede.
It stays a 2 player game, his code has to figure out which "seat" index his account is, and then has the bot join the other seat index.
The problem is that they're not validating that the joining user is the correct user that should be in that seat.
There's also the thought that you shouldn't allow a player to connect to an already connected seat. But since this game is also available on mobile, you probably want disconnection timeouts to be fairly long, and you don't want to interrupt a player who briefly disconnected and then reconnected before the timeout has recognized their early connection is broken. I've seen this in other games, where you try to reconnect and get a "cannot join game in progress" for about 10 seconds until you're actually able to reconnect.
Basically imagine showing up to an MTG tournament at your local game store, pushing someone out of their seat, sitting in it and shouting "I concede!". And then the judges agree that player B forfeited the game because the person in their chair declared it.
I never wanted to use it to cheat, i really just wish there was a battle log. What matches I won, what I lost, view the battlefied of a finished game, etc...
Gonna check this out, but hopefuly its patched quick.
In terms of viewing your history, you should check out https://untapped.gg/en. I have talked to them a bit and they essentially do what you want. They take most of their info from MTG's debug log, which you can find in MTGA's application directory, so you could also make your own tracker as well if you want. They talk about it on their site: https://help.hearthsim.net/en/articles/3620440-how-do-i-supp...
I have no interest in interacting with a glorified skinnerbox.
All cards available, and full rules engine.
I'm simultaneously surprised something this simple worked, and also not surprised at all. He does make a good point, this is an effective way to provide a practice bot and not need to make many server side modifications. I understand why they did it this way. The problem is they didn't make any server side modifications haha.
Edit: so far 3 of them have given me a lol or laugh emoji. This is excellent writing.
It brought back memories of error handling in VB6, and was rather unpleasant. I presume this is being done for performance reasons?
I believe this only applies in best of 1 matches, but not best of three matches.
Unfortunately I don't have a credible source for this.
Playing = executing
- Decompile C# for Sparky bot [a], rewrite Sparky to be a substitute online opponent, connect Sparky vs you online as if you're connecting a human in a match, have Sparky auto-concede and jack your win rate.
[a] Note I thought was interesting was: "C# is also really nice because it utilizes metadata tokens to associate elements of the compiled code with their human-readable names, which are still stored in the compiled .NET assembly. That means I can see all the function, variable, and class names that the developers wrote when they wrote their code." Which means its super easy to reverse engineer.
That being said, I can totally think of a few ways to get around that. It's like you said, the client doesn't really need to know until the enemy is looted.
[Actually, the one exception that I can think of is that rogues can pickpocket certain loot. And while pinging the server to generate loot once the npc is dead feels like it shouldn't be a major problem, having to ping the server to generate loot while the npc is still alive does make the system architect in me feel a bit more nervous ... at the very least for systems as they were when EQ first came out.]
The reason why they probably did it is because NPCs actually used the items. When the froglok King loaded his two handed sword, he was actually using it. And when he didn't load it, he wasn't.
If they encrypt before the network functions, you can just look at the callstack and trace the variable containing the buffer backwards until it's non encrypted.
Sometimes you will be forced to hack the software, to allow interception or to replace a key. Unless they use a symmetric key that is easily found, but I have never seen that.
And then you have the monsters such as Widevine.
This is categorically false - any WPN/DCI sanctioned tournament forbids proxies except in extremely limited circumstances:
Section 3.4 - Proxy Cards A proxy card is used during competition to represent an otherwise legal Magic card or substitute card that can no longer be included in a deck without the deck being marked. For a proxy to be issued, the card it is replacing must meet at least one of the following criteria: • The card has been accidentally damaged or excessively worn in the current tournament, including damaged or misprinted Limited product. Proxies are not allowed as substitutes for cards that their owner has damaged intentionally or through negligence. • The card is a foil card for which no non-foil printing exists.
Players may not create their own proxies; they may only be created by the Head Judge who has sole discretion as to whether the creation of a proxy is appropriate. When a judge creates a proxy, it is included in the player’s deck and must be denoted as a proxy in a clear and conspicuous manner. The original card is kept nearby during the match and replaces the proxy while in a public zone as long as it is recognizable. A proxy is valid only for the duration of the tournament in which it was originally issued
WOTC, judges, players, do not check for "dupe/clone" cards. How can they? why would they? To prove the player/opponent is poor in this individual set in the middle of a tournament?
When we're taking about proxies in sanctioned tournaments, we are not talking about what WotC is talking about:
No one declares at tournaments "This is my proxy" and presents a hand drawn liliana, that then prompts the inspection you quoted in which the judge has to unsleeve my very valuable card for the judge to inspect, and can only be used for the tournament. What a waste of time and lack of professionalism, for no reason. WotC would stop paper magic tournament support.
Instead they play a "liliana of the veil", in mint condition holo somehow, and we all know what's up.
Players fake/clone cards very easily/well, for obvious reasons. You would not be able to determine my commander deck is entirely "fake". There's no mechanism in tournaments to prove it. I simply don't want to support Hasbro/WotC and TCGPlayer admins.
I assure you, as a frequent bottom 2048 loser of these sanctioned tournaments, every single player is playing with clones, WotC is aware, and they would be foolish to enforce any ruling on that.
It's bad enough that my friend group casually accepts having to "concede" 2 or 3 times just to get a decent match going.
Card advantage is massive in MTGA so people don't mulligan when they should ...
This is trivial (just forfeit).
The hard part is figuring out the best possible action to select from. MTG is particularly hard at this because: * Some actions are only allowed in certain conditions (e.g. in response to, in a specific phase, etc) * Actions vary significantly not only in their effects but also in their inputs (some require targeting a creature, a player, an opponent, a card in hand, a card in exile, a name of a card that could exist). Some have a varying list of inputs (target many creatures). This variance makes it hard to encode the action space. * The state space is huge. It is not only determined by the cards in play, but is also affected by the meta-game (to play optimally players have to play in a specific way to avoid getting countered by a card that could be in play by the opponent, because that card is legal to play and is commonly used by decks that look like what the opponent is playing). * Technically the state space is also infinite because you can create infinite loops that keep creating more and more triggers/creatures/etc.
A common trope is to have a card that allows you to create mana, and then a way to infinitely bring that card back from the discard pile, allowing for infinite mana. Then you play a card that says something like "spend X mana to deal X damage" and you deal a trillion damage.
[0] the above commenter is correct that a true infinite loop is not allowed. But you're allowed to create a scenario where an infinite loop happens according to a repeating choice you can make (essentially a while loop) and repeat as much as you want within the match timer while still allowing time for your damage card. The general etiquette is just to say "I can do this a billion times and so I deal a billion damage".
I've actually been at a local (mostly informal) tournament where someone with an Elf deck managed to pump their life into the thousands (you start with 20 or 40 depending on the ruleset), and his opponent with a Goblin deck got an infinite combo for infinite damage. But the Elf player refused to accept "I can do this infinity times" and made him actually try to perform his card combo over a thousand times before the round timer ran out. Goblin deck did not win.
https://gatherer.wizards.com/pages/card/Discussion.aspx?mult...
Combo decks have always and likely will always be a part of the meta for most formats, although to varying degrees depending on how many cards the format has available and how effective it happens to be in the current meta. It's considered one of the three main deck archetypes along with "control" decks that attempt to shut down what the opponent is trying to do and slowly build an advantage over time and "aggro" which use a more straightforward approach of just attacking the opponent with creatures or spells (or both). Not everything cleanly fits into one of those strategies of course, and even a deck that has a win condition that fits into one archetype might dip into the other as a backup plan (e.g. a combo deck with control elements that help it buy time if it can't get off the combo as quickly as it would prefer, or a control deck with some efficient creatures that it can use for a surprise attack if the circumstance makes sense), but even in a setting like playing a few games at a card shop on a Friday night, seeing a combo deck with the level of complexity described above isn't really uncommon at all.
That said, I've read that a lot of the hardest cards to program tend to be the ones that subvert the basic expectations of the game. One infamous example that comes to mind is a creature that after being cast added an extra turn after yours where you controlled your opponent, after which they took their regular turn and the turn order resumed its previous alternation. Programming that would require adding in the ability to show one player's hidden game state to the other, let them make any sort of decisions using their cards that the player would normally do (short of literally conceding the game) and inserting an extra turn in the order with that weird control mechanism...all just for one card out of tens of thousands! Obviously most cards are not that complex, and Arena specifically doesn't attempt to support literally every card in existence and instead supports cards going back to its initial stable release along with explicitly chosen cards added to special Arena-only sets in order to introduce them, but when its an explicit rule that the text on the card overrides the normal rules of the game when they disagree, it very quickly gets to the point where you need to consider that there will likely be an edge cast for almost any possible state transition.
So the Goblin-deck owner allowed the Elf-deck owner to do a "I give myself 1000 life" with a combo but the Elf-deck owner wouldn't let the Goblin-deck owner do the same with damage? That's kind of a jerk move if so.
If the combos are sequential and the Elf has to commit to a certain number of life before the Goblin commits to a certain number of damage, then the Goblin would win.
There are some other possible intricacies (can they give themselves 1 life infinite times? or infinite life once?) From the mechanics of how the game usually goes, I would assume the first case applies here.
If the elf deck can gain "infinite life" at instant speed, then they'd win over a goblin deck that can deal infinite damage at sorcery speed, because whatever number the goblin player picks, the elf deck can pick that number squared, for instance.
If both players can combo at instant speed then it's an impasse and they have to jockey for who can put their opponent in a position where they're tapped out, etc.
I agree that in formal tournaments this would happen, but the comment I was responding to was about a "casual tournament." I was assuming the 1000 life was with a sorcery (e.g. infinite mana combo + stream of life). In casual play, shortcuts are only when both sides agree, so it would be a jerk move to not agree to one that benefits your opponent after your opponent has agreed to one that benefited you.
So the moral of this story is, uh, always name Graham's number. Or don't because I'm not sure what a Judge is to do if two people name numbers so large that the Judge can't work out which one is bigger on a pocket calculator.
(I think that in a Comp REL game, in your scenario, the Goblin player should have won unless the combo was non-deterministic.)
Is that how it goes now? It used to be infinite loops (e.g. playing a Faceless Butcher when the only creature in play is a Faceless Butcher that exiled another Faceless Butchers) resulted in a draw, not a loss.
I suspect most of the MTG infinite loops are something like "A triggers B, B triggers C, and C triggers A". Asserting that the loop will never resolve is not a violation of the halting problem.
The rule cited is worded to only apply to loops that go on indefinitely (machines that don't halt), so the referee can't even know whether or not they're allowed to apply the rule against a without knowing if it halts. On the particular machine mentioned above that would require solving the halting problem.
And yes, I'm sure the people saying "they'd just kick you out if you tried this in a tournament" are right. That's really not the point. The point is the cited rule doesn't really make things better with respect to turing completeness. If magic the gathering without the cited rule is turing complete, then with it it's both just-shy-of-turing-complete* (you'd be able to run any program that does halt) and uncomputable.
* Depending on the precise definition of "turing complete" it might in fact be turing complete. You can evaluate any program. Either it does halt and you can report the output, or it doesn't halt and you can report that you're in an infinite loop because the referee-oracle said so. That's probably enough to satisfy most definitions - even if it's a strange way to implement it.
It's possible that there's a way to do something turing-challenging or busy-beavery in such a situation, but it's usually pretty difficult to make complex unbendable loops, they're usually very direct cases where taking an action more or less forces you to immediately take the same action again, so the loop has...two steps. Anything much bigger or more complex and you're basically assured to have player choice.
There's probably room to do something where a player is clearly losing unless they do something which might continue a situation that is undecidable.
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.).
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.
Shortcuts are supposed to be used to speed up and smooth play, there should be no information exchange, and so as another person pointed out this is about being able to describe all intermediate game states. If shuffling means you will reveal (seemingly) irrelevant but arbitrary information about your deck (e.g. cards that are no longer in it because they were discarded), you can't describe the intermediate game state beforehand (it is random) and the other player can't make an informed decision about whether or not they'd interrupt. And if you could infer from their refusal that there is a situation they might interrupt, you'd have extracted information you shouldn't have had access to. Hence in tournaments it is not allowed.
Slow play is the phrase explaining why indeterminate combos don't get shortcutted. "An indeterminate-loop combo may take anywhere from fifteen minutes to fifteen hundred years to actually succeed, and we really do not need to be waiting around to see which it's going to be."
The argument is that MtG is Turing complete except for that part, because it cannot compute forever, even in an ideal scenario where time and space are infinitely available, because the rules explicitly forbid it.
An ideal Turing machine with someone to pull the plug is not a Turing machine. Also: just because humans can recognize some infinite loops doesn't mean we can recognize all infinite loops, so the person pulling the plug may be misinterpreting and pulling the plug on a machine that would otherwise eventually halt.
Put another way: you can try to set up a game state in a competitive match where the judge has to solve the Collatz conjecture, but because that would take way too long and clearly be contrary to good sportsmanship, you'd never reach that point.
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?
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 ℵ₀.
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[0].
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.
Neither was I? The proof is trivial - actually doing it is very much not.
> 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 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.
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);
}
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.
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.
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