5 ms·

Some thoughts about AI: After Chess, Go and StarCraft 1, Magic is definitely an interesting game for AI to tackle next. While there are certain play patterns,

Some thoughts about AI: After Chess, Go and StarCraft 1, Magic is definitely an interesting game for AI to tackle next. While there are certain play patterns, the space of potential actions is extremely large and there is a great number of synergistic interactions between cards that needs to be taken into account. From an AI perspective Magic is also very hard because it is: * Non-deterministic * Partially observable * Antagonistic

shapiro92 7y ago
but those interactions are actually not as large as a real time game such as Dota or even Go. Your deck has an X amount of cards and the synergies can be easily calculated from a machine. The real problem would be, is it smart enough to beat an unknown opponent deck?
- dagw 7y ago
  and the synergies can be easily calculated from a machine This article is all about how those synergies are Turing complete and thus cannot be easily calculated since doing so reduces down to solving the halting problem. edit: that being said I suspect that writing an AI that plays "well enough" to beat human players, as opposed to optimally, is quite doable.
- mratsim 7y ago
  As a Magic player (since 1996) and Go player (since 2004) and also deep learning scientist, the main issue with Magic is modeling the game. The interactions and exceptions are really numerous, I expect Magic Arena and Magic Online are a mess of spaghetti code. For go modeling basically you have in input an image of the go board, and for DOTA an image of your screen and the action you have are "limited" and do not change wildly depending of the state of your screen (except if you're dead on Dota). For Magic, you can't just use deep reinforcement learning with an image input, you need to somehow track the state of your deck, cards, instant effects, what your opponent did ...
  - Endy 7y ago
    I suggest you look at projects like Shandalar 2012 and such - the original game is from the Banding era, but the 'AI' isn't too bad.
  - Qwertystop 7y ago
    Arena at least has the advantage of not including all-cards-ever, only going a few sets back relative to release. That strips out some of the worst of them.
staticautomatic 7y ago
I wonder if the problem of "playing the game" optimally is mostly the same as the problem of "choosing the best deck."
- vaylian 7y ago
  It is definitely a factor, but there is no auto-win for any deck. It definitely matters which cards you play and which ones your opponent plays, because just like rock-paper-scissors some cards are good at eliminating specific other cards. But unlike RPS you cannot always enforce a favorable interaction between specific cards. Your opponent can maneuver around whatever you are playing.
  - staticautomatic 7y ago
    Should we rule out the possibility that there are decks which are unbeatable when played well/"correctly"?
    - moate 7y ago
      Yes. Best case is that there are decks that are unbeatable when played correctly against other decks (even if that deck is played correctly). I can think of a few match ups that are likely "auto-lose" based on deck construction. Most of the games AI has surpassed humans at have several things in common, and one of the biggest is they don't contain a great deal of hidden information. Chess is all in the open, with very set defined options. There are a ton of different game states, but none of them involve "what if my opponent suddenly drew the one card that I cannot in any way do anything about to prevent ruination". TL;dr- robots will never defeat the "heart of the cards" unless you stack the game in their favor.
      - afiori 7y ago
        on this note there was a nice paper [0] proposing a game entirely focused on hidden information (Hanabi) as a benchmark for automated decisions. [0] https://arxiv.org/abs/1902.00506 https://arxiv.org/abs/1902.00506
moate 7y ago
Depends on what you expect the AI to do. If you allow it access to a DB of decklists to compare opponent cards/choices against, it gets "easier" but still complex. There's so many branching option trees though. Could be interesting to see what happened, I just don't think you'd be able to build an "unbeatable" machine that didn't also cheat the RNG elements of the game/have the full decklist of its opponent.
rsync 7y ago
"While there are certain play patterns, the space of potential actions is extremely large and there is a great number of synergistic interactions between cards that needs to be taken into account." Yes, that's certainly the promise of MTG - and is the reason why I was drawn to it originally and continue to be, at least passively, interested in it. The idea is that there are so many different cards and so many potential interactions that every deck could be fantastically unique and every game could produce very unique outcomes. I have found, in 25 years of playing MTG that this is not the case. The reality is that in every release, or set of "legal" cards, there are a few overwhelmingly advantageous cards and card combinations that must either be adhered to or prepared against. Further, "classes" of decks (counter decks, control decks, blast decks, etc.) need to be fairly simple and anti-fragile to work effectively given the random draw, etc. My opinion, circa 1998 or 1999, was that to really open up the playing space, WOTC needed to produce sets of very complex cards that had abilities and interactions that in themselves were as complicated as the game was. Cards whose abilities and interactions we would still be discovering years later. Perhaps even random attributes/abilities For obvious reasons this is not the direction they went and would be a big hurdle for new players. And so every set has, effectively, its own channel+fireball and we all play that or prepare for it and for all the turing-completeness, there's not that many surprises at the game store on Friday night ...
- manifestsilence 7y ago
  Well put! MTG is notorious in the huge gap between the potential complexity and the actual complexity of most games. I've found that deck design is a far more interesting problem than the in-game play strategy, and unfortunately most really interesting decks end up far too fragile or slow to compete with the optimal strategies. Someone really ought to design a format that bans all the straightforward but powerful cards, forcing a bit more creativity into the mix, but I fear the banned list would be prohibitively long and surprisingly difficult to come up with after the first round of obvious bans. There's always some new infinite combo that's a little too easy to pull off once the super fast quick wins are out of the way. Edit: there's always that person (I've occasionally been him) who doesn't play to win and just tries to mess with the game's limits as much as possible. I knew someone with a "Jester Deck" that played cards that so mangled the rules that no one could even figure out how to finish the game any more. That was pretty interesting.
forgot-my-pw 7y ago
One step before that is Hanabi: https://arxiv.org/abs/1902.00506 https://arxiv.org/abs/1902.00506

shapiro92 7y ago

but those interactions are actually not as large as a real time game such as Dota or even Go. Your deck has an X amount of cards and the synergies can be easily calculated from a machine. The real problem would be, is it smart enough to beat an unknown opponent deck?

dagw 7y ago
and the synergies can be easily calculated from a machine This article is all about how those synergies are Turing complete and thus cannot be easily calculated since doing so reduces down to solving the halting problem. edit: that being said I suspect that writing an AI that plays "well enough" to beat human players, as opposed to optimally, is quite doable.
mratsim 7y ago
As a Magic player (since 1996) and Go player (since 2004) and also deep learning scientist, the main issue with Magic is modeling the game. The interactions and exceptions are really numerous, I expect Magic Arena and Magic Online are a mess of spaghetti code. For go modeling basically you have in input an image of the go board, and for DOTA an image of your screen and the action you have are "limited" and do not change wildly depending of the state of your screen (except if you're dead on Dota). For Magic, you can't just use deep reinforcement learning with an image input, you need to somehow track the state of your deck, cards, instant effects, what your opponent did ...
- Endy 7y ago
  I suggest you look at projects like Shandalar 2012 and such - the original game is from the Banding era, but the 'AI' isn't too bad.
- Qwertystop 7y ago
  Arena at least has the advantage of not including all-cards-ever, only going a few sets back relative to release. That strips out some of the worst of them.

staticautomatic 7y ago

I wonder if the problem of "playing the game" optimally is mostly the same as the problem of "choosing the best deck."

vaylian 7y ago
It is definitely a factor, but there is no auto-win for any deck. It definitely matters which cards you play and which ones your opponent plays, because just like rock-paper-scissors some cards are good at eliminating specific other cards. But unlike RPS you cannot always enforce a favorable interaction between specific cards. Your opponent can maneuver around whatever you are playing.
- staticautomatic 7y ago
  Should we rule out the possibility that there are decks which are unbeatable when played well/"correctly"?
  - moate 7y ago
    Yes. Best case is that there are decks that are unbeatable when played correctly against other decks (even if that deck is played correctly). I can think of a few match ups that are likely "auto-lose" based on deck construction. Most of the games AI has surpassed humans at have several things in common, and one of the biggest is they don't contain a great deal of hidden information. Chess is all in the open, with very set defined options. There are a ton of different game states, but none of them involve "what if my opponent suddenly drew the one card that I cannot in any way do anything about to prevent ruination". TL;dr- robots will never defeat the "heart of the cards" unless you stack the game in their favor.
    - afiori 7y ago
      on this note there was a nice paper [0] proposing a game entirely focused on hidden information (Hanabi) as a benchmark for automated decisions. [0] https://arxiv.org/abs/1902.00506 https://arxiv.org/abs/1902.00506

moate 7y ago

Depends on what you expect the AI to do. If you allow it access to a DB of decklists to compare opponent cards/choices against, it gets "easier" but still complex. There's so many branching option trees though. Could be interesting to see what happened, I just don't think you'd be able to build an "unbeatable" machine that didn't also cheat the RNG elements of the game/have the full decklist of its opponent.

rsync 7y ago

"While there are certain play patterns, the space of potential actions is extremely large and there is a great number of synergistic interactions between cards that needs to be taken into account." Yes, that's certainly the promise of MTG - and is the reason why I was drawn to it originally and continue to be, at least passively, interested in it. The idea is that there are so many different cards and so many potential interactions that every deck could be fantastically unique and every game could produce very unique outcomes. I have found, in 25 years of playing MTG that this is not the case. The reality is that in every release, or set of "legal" cards, there are a few overwhelmingly advantageous cards and card combinations that must either be adhered to or prepared against. Further, "classes" of decks (counter decks, control decks, blast decks, etc.) need to be fairly simple and anti-fragile to work effectively given the random draw, etc. My opinion, circa 1998 or 1999, was that to really open up the playing space, WOTC needed to produce sets of very complex cards that had abilities and interactions that in themselves were as complicated as the game was. Cards whose abilities and interactions we would still be discovering years later. Perhaps even random attributes/abilities For obvious reasons this is not the direction they went and would be a big hurdle for new players. And so every set has, effectively, its own channel+fireball and we all play that or prepare for it and for all the turing-completeness, there's not that many surprises at the game store on Friday night ...

manifestsilence 7y ago
Well put! MTG is notorious in the huge gap between the potential complexity and the actual complexity of most games. I've found that deck design is a far more interesting problem than the in-game play strategy, and unfortunately most really interesting decks end up far too fragile or slow to compete with the optimal strategies. Someone really ought to design a format that bans all the straightforward but powerful cards, forcing a bit more creativity into the mix, but I fear the banned list would be prohibitively long and surprisingly difficult to come up with after the first round of obvious bans. There's always some new infinite combo that's a little too easy to pull off once the super fast quick wins are out of the way. Edit: there's always that person (I've occasionally been him) who doesn't play to win and just tries to mess with the game's limits as much as possible. I knew someone with a "Jester Deck" that played cards that so mangled the rules that no one could even figure out how to finish the game any more. That was pretty interesting.

forgot-my-pw 7y ago

One step before that is Hanabi: https://arxiv.org/abs/1902.00506 https://arxiv.org/abs/1902.00506