Hacker news

  • Top
  • New
  • Past
  • Ask
  • Show
  • Jobs

Exponential Behavior in Magic: The Gathering (https://levineuwirth.org)

71 points by neuwirth 2 days ago | 55 comments | View on ycombinator

khaliostr about 21 hours ago |

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

jcalx about 17 hours ago |

Reminds me of the "deal infinite damage for 4GRU, as long as the twin primes conjecture is true" Reddit post (https://www.reddit.com/r/BadMtgCombos/comments/1feps3y/deal_...)

gravitronic about 19 hours ago |

MTGO biggest drawback is you need to pay real money for the virtual cards, and sometimes they cost more than the paper cards themselves.

Endstep.cc is a newcomer to the field.. it runs the forge engine on the server and allows online play. It is now my favorite place to play my favorite format (pauper)

amluto about 20 hours ago |

Surely this particular problem can theoretically be (mostly) addressed by an engine that tracks the number of copies of a given card or stack of cards (card plus attached tokens, etc).

I say mostly because:

- Surely there are ways to create N token creatures with a range of counters such that there are still exponentially many different stacks.

- A fast-enough growing pile could require exponentially many bits to store (or more than exponential).

But at least the particular problem in the OP could be addressed.

apitman about 18 hours ago |

> The game is remarkably complex, even Turing complete, with intricate keywords and a daunting amount of mechanics

Software engineers can learn a lot from the way complexity exists in MTG. The number of mechanics is huge, but relatively shallow. Once you learn a pretty small set of core rules (tapping, mana, turn phases, the stack, etc), you can add new mechanics to your knowledge easily, usually be reading a small chunk of text.

You normally only have a handful of mechanics interacting with each other, and usually only need to look up one or two you're not familiar with in a game. It's sort of like a plugin system. Reminds me of Unix too.

rappatic about 20 hours ago |

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.

lbo about 19 hours ago |

Does anyone know what the strongest existing AI magic player is considered to be? I’ve made one that has an 85% winrate over Forge, but am looking for any new challengers

eithed about 17 hours ago |

When I read articles like this I find myself agreeing with finitists = accounting for infinities in real scenarios isn't worth it (and should be capped). This worked for Heartstone.

thom about 19 hours ago |

I feel like this is probably my only opportunity on HN to post this classic:

https://www.youtube.com/watch?v=AGXG5rNe_tI

chokma about 22 hours ago |

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 ;)

bob1029 about 20 hours ago |

The problem with MTG is that it's like a computer program that is constantly evolving its own instruction set and business logic.

Building a rule system that can capture MTG means building a rule system that can modify itself.

gpugreg about 21 hours ago |

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.

[1] https://scryfall.com/card/eoe/15/exalted-sunborn

[2] https://scryfall.com/card/cn2/111/followed-footsteps

world2vec about 19 hours ago |

Off-topic: Thought it was gwern's website for a second

deadnomore about 20 hours ago |

It’s a finite state machine, it’s very expressive.

brudgers 1 day ago |

related, Magic the Gathering is Turing Complete.

Which to me suggests that one will encounter the halting problem in theory if not in practice.

hnedeotes about 21 hours ago |

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

learntoplaypitc about 19 hours ago |

[flagged]

Agataproximadev about 22 hours ago |

[flagged]