14 ms·

> I would have thought that a game as complex as MTG would require a lot of overhead in terms of creating an AI opponent. But nope! You can actually check out a

> I would have thought that a game as complex as MTG would require a lot of overhead in terms of creating an AI opponent. But nope! You can actually check out all of the logic for Sparky, including a few places in the debug UI where WOTC developers reached a corner case that they felt was not worth implementing. I don't blame them - MTG is a beast of a game to try to have full coverage for! 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.

Dylan16807 3y ago
Show HN is for projects people can play with, not blog posts. https://news.ycombinator.com/showhn.html https://news.ycombinator.com/showhn.html
- mgdev 3y ago
  The sample code plus walkthrough sounds like "things people can run on their computers". :)
  - Dylan16807 3y ago
    Don't make me regret removing the sentence that explicitly pointed out that the sample code in an appendix is not the point of the linked page.
    - deleted 3y ago
      [deleted]
jncfhnb 3y ago
Is there any practical strategy that approaches this complexity at all? I have never played. But I assume this claim is just that you can technically create some stateful stuff if you’re explicitly not trying to win
- sciolist 3y ago
  Here's a paper on creating a Turing machine in Magic: https://arxiv.org/abs/1904.09828 https://arxiv.org/abs/1904.09828
- x86x87 3y ago
  It's not that easy. There are strategies but they depend on the game format (standard, legacy, modern, etc) and on a deep understanding of the game meta. You cannot devise a strategy that works under any conditions. Lookup the rules + understand that new abilities and cards are introduced all the time.
- saghm 3y ago
  I'm not sure what level of complexity you're looking for, but there are some pretty complex combos that have been viable over the years, even in formats that don't use some of the older "broken" cards. One popular strategy for a while in the "Modern" format, which doesn't allow cards for the first 10 years or so of the game, used a mechanic called "Storm" where a spell would be copied for every spell you previously cast in the same turn. A card called Grapeshot had this ability and did 1 damage, so the deck played creatures that made your spells cost less mana and spells that gave you extra mana or draw cards, and the goal was to cast 19 spells and then grapeshot your opponent for their entire starting life total of 20, often as early as on their fourth turn. It was consistent enough that it was a staple in the format for at least a few years (although I haven't kept up with the meta as much for a few years now). Another higher variance but potentially even faster combo used a creature called Griselbrand, which let you pay 7 life to draw 7 cards, a bunch of mana "rituals" like storm, and used a card called Nourishing Shoal to let you exile certain cards from your hand to gain life. The win condition was typically to draw at least 7 lands and cast a creature that let you discard a land to do 3 damage, and it could potentially do this on the very first turn, although eventually one of the cards that was necessary for it to function got banned in modern, although by then Griselbrand decks weren't really ever played due to there being far more consistent options with better ability to deal with an opponent trying to thwart their game plan. If you include Legacy (which allows cards from any point in the history of the game but still with a custom ban list) or Vintage (where all cards are allowed but some are "restricted" to only one copy instead of the typical 4 per deck), there are even more powerful combos you can take advantage of. 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.
tcbawo 3y ago
The game is constantly changing because new sets are rotating through, but I believe it is possible to create infinite loops with certain dynamics, or at least it has been possible at various points. ie. something like creating/killing token characters with "on entry"/"on exit"/"untap" mechanics, etc. Not all of them result in either player taking damage.
- chmod775 3y ago
  The rules explicitly address infinite loops and forbid players from forever taking actions that create one. If one would occur anyways, the game ends in a draw. https://mtg.fandom.com/wiki/Loop https://mtg.fandom.com/wiki/Loop
  - gpm 3y ago
    Ok, so instead of being turing complete it requires solving the halting problem to properly referee it?
    - chmod775 3y ago
      > Ok, so instead of being turing complete it requires solving the halting problem to properly referee it? 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.).
      - readams 3y ago
fauria 3y ago
It is actually Turing Complete: https://arxiv.org/abs/1904.09828 https://arxiv.org/abs/1904.09828
_cenw 3y ago
Arena's rule engine and AI is based on Duels of the Planeswalkers, so they had several years to develop the AI player.
- ugexe 3y ago
  The AI player just casts the first card it has the mana to cast, regardless of if any normal player would do it. As an example Sparky will gladly cast a kill spell on their own creature if the opponent has none, or cast protection spells on the opponents creatures if it has no creatures itself. This is far different than duels of the planewalkers.
- Ensorceled 3y ago
  14-15 years ...
- apetresc 3y ago
  Arena's rule engine was explicitly not based on Duels; this was a big selling point when it first launched to replace Duels, and they've gone into some detail since then describing how it works. See https://magic.wizards.com/en/news/mtg-arena/on-whiteboards-naps-and-living-breakthrough https://magic.wizards.com/en/news/mtg-arena/on-whiteboards-n... for instance.
dmurray 3y ago
"The game can be used to encode a Turing machine" is not at all the same as "it is difficult to write a program that can play a legal action in every situation". It's the latter that seems to be difficult for the bot authors.
- jprafael 3y ago
  > "it is difficult to write a program that can play a legal action in every situation" 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.
  - dmurray 3y ago
    Oh I completely agree, I'm just shitting on the idea that this has anything to do with the game being "Turing-complete".

Dylan16807 3y ago

Show HN is for projects people can play with, not blog posts. https://news.ycombinator.com/showhn.html https://news.ycombinator.com/showhn.html

mgdev 3y ago
The sample code plus walkthrough sounds like "things people can run on their computers". :)
- Dylan16807 3y ago
  Don't make me regret removing the sentence that explicitly pointed out that the sample code in an appendix is not the point of the linked page.
  - deleted 3y ago
    [deleted]

jncfhnb 3y ago

Is there any practical strategy that approaches this complexity at all? I have never played. But I assume this claim is just that you can technically create some stateful stuff if you’re explicitly not trying to win

sciolist 3y ago
Here's a paper on creating a Turing machine in Magic: https://arxiv.org/abs/1904.09828 https://arxiv.org/abs/1904.09828
x86x87 3y ago
It's not that easy. There are strategies but they depend on the game format (standard, legacy, modern, etc) and on a deep understanding of the game meta. You cannot devise a strategy that works under any conditions. Lookup the rules + understand that new abilities and cards are introduced all the time.
saghm 3y ago
I'm not sure what level of complexity you're looking for, but there are some pretty complex combos that have been viable over the years, even in formats that don't use some of the older "broken" cards. One popular strategy for a while in the "Modern" format, which doesn't allow cards for the first 10 years or so of the game, used a mechanic called "Storm" where a spell would be copied for every spell you previously cast in the same turn. A card called Grapeshot had this ability and did 1 damage, so the deck played creatures that made your spells cost less mana and spells that gave you extra mana or draw cards, and the goal was to cast 19 spells and then grapeshot your opponent for their entire starting life total of 20, often as early as on their fourth turn. It was consistent enough that it was a staple in the format for at least a few years (although I haven't kept up with the meta as much for a few years now). Another higher variance but potentially even faster combo used a creature called Griselbrand, which let you pay 7 life to draw 7 cards, a bunch of mana "rituals" like storm, and used a card called Nourishing Shoal to let you exile certain cards from your hand to gain life. The win condition was typically to draw at least 7 lands and cast a creature that let you discard a land to do 3 damage, and it could potentially do this on the very first turn, although eventually one of the cards that was necessary for it to function got banned in modern, although by then Griselbrand decks weren't really ever played due to there being far more consistent options with better ability to deal with an opponent trying to thwart their game plan. If you include Legacy (which allows cards from any point in the history of the game but still with a custom ban list) or Vintage (where all cards are allowed but some are "restricted" to only one copy instead of the typical 4 per deck), there are even more powerful combos you can take advantage of. 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.

tcbawo 3y ago

The game is constantly changing because new sets are rotating through, but I believe it is possible to create infinite loops with certain dynamics, or at least it has been possible at various points. ie. something like creating/killing token characters with "on entry"/"on exit"/"untap" mechanics, etc. Not all of them result in either player taking damage.

chmod775 3y ago
The rules explicitly address infinite loops and forbid players from forever taking actions that create one. If one would occur anyways, the game ends in a draw. https://mtg.fandom.com/wiki/Loop https://mtg.fandom.com/wiki/Loop
- gpm 3y ago
  Ok, so instead of being turing complete it requires solving the halting problem to properly referee it?
  - chmod775 3y ago
    > Ok, so instead of being turing complete it requires solving the halting problem to properly referee it? 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.).
    - readams 3y ago

fauria 3y ago

It is actually Turing Complete: https://arxiv.org/abs/1904.09828 https://arxiv.org/abs/1904.09828

_cenw 3y ago

Arena's rule engine and AI is based on Duels of the Planeswalkers, so they had several years to develop the AI player.

ugexe 3y ago
The AI player just casts the first card it has the mana to cast, regardless of if any normal player would do it. As an example Sparky will gladly cast a kill spell on their own creature if the opponent has none, or cast protection spells on the opponents creatures if it has no creatures itself. This is far different than duels of the planewalkers.
Ensorceled 3y ago
14-15 years ...
apetresc 3y ago
Arena's rule engine was explicitly not based on Duels; this was a big selling point when it first launched to replace Duels, and they've gone into some detail since then describing how it works. See https://magic.wizards.com/en/news/mtg-arena/on-whiteboards-naps-and-living-breakthrough https://magic.wizards.com/en/news/mtg-arena/on-whiteboards-n... for instance.

dmurray 3y ago

"The game can be used to encode a Turing machine" is not at all the same as "it is difficult to write a program that can play a legal action in every situation". It's the latter that seems to be difficult for the bot authors.

jprafael 3y ago
> "it is difficult to write a program that can play a legal action in every situation" 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.
- dmurray 3y ago
  Oh I completely agree, I'm just shitting on the idea that this has anything to do with the game being "Turing-complete".