I imagine we can do better than a flat array to represent the permanents on the battlefield. Lots of cards filter permanents by type, mana cost, etc. Building a consideration for this into the data structure is a natural idea.
Another fun combo with an even higher growth rate is Exalted Sunborn [1] + Followed Footsteps [2].
After one turn, you have 3 creatures. Next turn, you have 11. Then 2059. Then 66185228434044942951864067458396061614989522267577311297802947435570493724401440549267868490798926773634494383968047143923956857140205406402740536087446083831052036848232439995904404992798007514718326043410570379830870463780085260619444417205199197123751210704970352727833755425876102776028267313405809429548880554782040765277562828362884238325465448520348307574943345990309941642666926723379729598185834735054732500415409883868361423159913770812218772711901772249553153402287759789517121744336755350465901655205184917370974202405586941211065395540765567663193297173367254230313612244182941999500402388195450053080385547.
It gets out of hand quickly.
related, Magic the Gathering is Turing Complete.
Which to me suggests that one will encounter the halting problem in theory if not in practice.
A friend implemented his version of MTG with the old expansions (about up to Ice Age + interesting later cards), including single player campaign, online multiplayer & play against the machine. It works quite well, but major issues during play testing was network sync and handling different resolutions for artwork and text over artwork. And the bugs in specific card implementations that could take a game down.
The "AI" will look a couple of moves ahead, but is restricted on time and CPU performance so having a 100 tokens with an ability in play that can be activated in every game phase is a challenge, like the article says.
Now he "just" needs a license from Wizards/Hasbro ;)
I think that for these situations you need to create a model of execution that can understand these interactions so that it can move beyond the linear mode of going through every option. I'm designing Aether Summon (https://aethersummon.com) and currently building the native clients to play (which have the hearthstone/arena like game play).
I haven't yet introduced complex mechanics that can lead to infinite combos or exponential triggering, but for combos my idea is to have the human/AI operator declare itself that it's going to combo, so the game/client register that intention and then "records" the actions that lead to the combo, in doing so, and for a combo to be declared, it has to do a few checks, e.g., on each full cycle of combo (that can be 1 or more sequences of actions) the state of the game had to move irrevocably to an increase in some stats (life increase, aether increase, creature count increase, etc) and the conditions to re-do the cycle are present. If this is true then it should mean that you're in a combo, as the engine is deterministic (except for some random effects, but if they don't target you then it should recognize the combo without issues, for instance if on each cycle you remove 3 scrolls out of your opponent's tome, it doesn't matter for the repeatability of the combo, it will just go down to 0 and future ones won't do any "side-effects" in practice) it means you should be able to play the same cycle as many times as you wish, so when validated the user just needs to choose how many times he wants to repeat the cycle and then things are computed based on that.
This isn't exactly the same problem as your's but it's close, if in this cycle it created X+n (where n is the number of times the cycle runs) creatures then it could calculate that if you chose to play the cycle N times, it would create a set amount of creatures and as such it could jump to the final calculation instead of going through each cycle independently and updating the state in each step.
I think something similar could be applied to the trigger stacking. You still need to take care of the other player's possibility of interactions, but these can use a similar system where you announce to the other player that player 1 entered a combo state that ends on X step, you can ignore this is the player has no meaningful way of interacting with it, but otherwise offer the same thing, let the first cycle play as usual so the player can "break" the combo, or allow him to say, on iteration Y of the X that are going to be played, give me back control.
In your case I think you should try to first derive the mathematical properties and relationships between the triggers and the state - this is easier than for an open problem because you have the state after an interaction to derive them and although almost limitless it's still limited the things that can happen in an MtG board.
#edit and regarding turing completeness or not, I think that the issue is that most of the rules and cool interactions where designed for a human to human play mode, with physical cards, time limited, etc. There's plenty of rules in magic that a toddler understands but are extremely complex to model in a program - more so because the rules, their readings and interactions kept being iterated on throughout the game history and for a long time didn't worry about consistency or its computability - that's why this only happens with older editions, new ones dont suffer from the same issues... I would imagine due to already taking into account its practical computability...
[flagged]
There's a bit of an open source Magic renaissance going on lately, which I find really cool.
Forge has been around forever, but we've managed to get it running in the browser via WASM with Manabrew [1]. I'm one of the maintainers, and we're mostly building it because we wanted a nicer way to play Commander with friends.
Meanwhile, Phase and Ironsmith are working on new engines in Rust, Gorge is building one in Go alongside a bot and cross-engine testing tools, and people are starting to collaborate across projects.
Magic is such a ridiculously difficult game to implement that I think it's pretty amazing how many people are tackling it in their spare time.
If you're into Magic and software engineering, come hang out with us. There's a lot going on and plenty of room for more people to get involved :)
[1] https://github.com/witchesofthehill/manabrew