4 ms·

As far as I know, in Magic: the Gathering, the best bots are far worse than most players. Part of the difficulty is that the rules are so complicated that there

by isaacg 5y ago

As far as I know, in Magic: the Gathering, the best bots are far worse than most players. Part of the difficulty is that the rules are so complicated that there are only a couple of complete rules implementations. Beyond that, it's an imperfect information game with far more actions per game than poker, so optimal-solver techniques haven't seen success.

golergka 5y ago
Have people tried using GPT-3 for this?
dwohnitmok 5y ago
I think this is purely a resource issue, e.g. if Google Brain decided to make an MtG bot I would be fairly confident it would be superhuman. Even real time strategy games like Starcraft are looking like they're on the cusp of superhuman bots (Alphastar was competitive as Protoss against elite players, but did not consistently beat them).
- jdmoreira 5y ago
  The search tree is huge in mtg. It has to be the largest of any game. You can take actions all the time. There are triggers all the time, you can stack your actions on top of your opponent actions. Huge space really. And then of course it's also imperfect information both in the sense of your opponent hand but also his deck. The cardpool is also very large for some formats. I actually don't think it's solvable just by throwing MCTS at it with todays hardware but would love to know more about this, if someone else has more insight please reply. EDIT: Oh and there is also the meta-game / deck building aspect. If you are going to win a tournament you have to have favorable matchups against most players in the room.
  - ogogmad 5y ago
    MCTS is usually paired up with Deep Learning. This doesn't appear to have any problems with games with even larger branching factors. Look up AlphaZero and AlphaStar.
  - karpierz 5y ago
    The search tree size isn't an insurmountable issue. For exple OpenAI 5 managed to play DotA (though admittedly relied heavily on perfect timing and the ability to look at every enemy on the minimap at the same time, and lost a lot when people learned to play around the only strategy it knew).I think it'd be feasible to get an AI to play a modern deck. I think it'd be much harder for the AI to do deck building in a vacuum. You could model it as every game starting with you building your deck, but I can't see that converging stably.
  - dwohnitmok 5y ago
    Search space size is no longer a great heuristic of how difficult a game is for the latest in AI approaches. For example, an RTS game has an absolutely enormous search space as well (effectively every unit of several hundred can move in every direction for every single tick of the game clock, many units have spells and many spells are meant to stack with other spells) and Alphastar is a convincing demonstration that this is not out of the reach of current AIs. And you similarly have imperfect information where you don't know what your opponent is doing unless they are sufficiently close to your current units. Even the meta-game/deck building aspect doesn't seem all that insurmountable as it doesn't seem fundamentally different from say a build order other than that it cannot change dynamically on the fly.
- archontes 5y ago
  I doubt very highly it would be able to sit at a game of commander. Four players with 100 card singleton decks would be an absolutely enormous space to operate in.
  - dwohnitmok 5y ago
    Many players sounds like it's still a hard nut to crack for AI approaches (although as poker demonstrates its getting easier), but the deck size doesn't sound like it'd be the main issue.
- runnerup 5y ago
  Alphastar also didn't play with the same limitations that a human has. Even after removing its ability to see the entire map and finally forcing it to scroll around, alphastar never misclicks (so its APM==EPM) and can still blast nearly unlimited APM for short bursts as long as its "average APM" over an x-second period matched human's APM. I believe Alphastar would generate more interesting strategies if we limited alphastar to a bit below human APM and forced it to emulate USB K+M to click (instead of using an API, which it currently does) and adding a progressively increasing random fuzzing layer against its inputs so that as it clicks faster the precision/accuracy goes down. By "interesting strategies" I mean strategies that humans could learn to adopt. Currently its main strategy is "perfectly juggle stalkers" which is a neat party trick, but that particular strategy is about as interesting to me as 2011-era SC AI[0]. Obviously how it arrived at that strategy is quite interesting, but the style of play is not relevant to humans, and may in fact even get beaten by hardcoded AI's. I'm also very curious what Alphastar could come up with if it were truly unsupervised learning. AIUI, the first many rounds of training were supervised based on high level human replays -- so it would have gotten stuck in a local minima near what has already been invented by humans. This may be relevant if Microsoft reboots Blizzard's IP. I would love to have an alphastar in SC3 to play against off-line, or have as a teammate, archon mode, etc. I think all RTS' are kind of "archon mode with AI teammate" already. The AI currently handles unit pathing, selection of units to attack, etc. With an alphastar powering the internal AI instead, more tactics/micro can be offloaded to AI and allow humans to focus more on strategy. That seems like it would be super cool. Examples: "Here AI, I made two drop ships of marines. Take these to the main base and find an optimal place to drop them. If you encounter strong resistance or lots of static defense, just leave and come back home" "Here AI, use these two drop ships of marines to distract while I use the main army to push the left flank. Take them into the main, natural, or 4th base -- goal is to keep them alive for as long as possible. Focus on critical infrastructure/workers where possible but mostly just keep them alive and moving around to distract the opponent." 0: Automaton 2000 AI perfectly controls 50-supply zerglings (2.5k mineral) vs. 60-supply (3k mineral, 2.5k gas) siege tanks: https://www.youtube.com/watch?v=IKVFZ28ybQs https://www.youtube.com/watch?v=IKVFZ28ybQs
  - dwohnitmok 5y ago
    > Alphastar also didn't play with the same limitations that a human has. Even after removing its ability to see the entire map and finally forcing it to scroll around, alphastar never misclicks (so its APM==EPM) and can still blast nearly unlimited APM for short bursts as long as its "average APM" over an x-second period matched human's APM. > I believe Alphastar would generate more interesting strategies if we limited alphastar to a bit below human APM... No Alphastar definitely had misclicks, and it had a maximum cap on APM regardless of average that was far lower than the max burst of APM (or even EPM) of top players. When I have the time I can go dig up some games where Alphastar definitely has misclicks, and I believe the Deep Mind team has said before that it will misclick. Its APM limits are already lower than pros both on average and in bursts (and are reflected in its play, Alphastar will often mis-micro units in larger, more frantic battles such as allowing disruptor shots to destroy its own units, but it will never make the same mistake with much smaller numbers of units). > Currently its main strategy is "perfectly juggle stalkers" Definitely not. That was its strategy in its early iterations against MaNa and is no longer feasible with the stricter limitations in place. Its Protoss strategy is significantly more advanced than that now (see its impressive series of games against Serral with an amazing comeback here: https://www.youtube.com/watch?v=jELuQ6XEtEc https://www.youtube.com/watch?v=jELuQ6XEtEc and a powerful defense against multi-pronged aggression here: https://www.youtube.com/watch?v=C6qmPNyKRGw https://www.youtube.com/watch?v=C6qmPNyKRGw) (and of course by "now" I mean when Deep Mind took it off the ladder). Both of these involve an eclectic mix of units with Alphastar effectively using each type of unit and varying it in response to what Serral puts out and its own resource constraints. A lot of commentators have difficulty distinguishing Alphastar from humans when the former plays as Protoss (its Terran and Zerg play is weaker and often more mechanical). > I mean strategies that humans could learn to adopt. My main takeaways from watching Alphastar were "pros undervalue static defense and often have a less than optimal number of workers (where Alphastar's seeming overproduction of workers lets it shrug off aggressive harassment)," but I don't know if those have picked up in the meta.
cortesoft 5y ago
Wouldn’t the fact that the game is constantly changing, with new cards being added and old ones being removed, also make it harder to solve?
- jdmoreira 5y ago
  That's harder on humans than on computers. Computers have perfect information on what the legal cardpool is at game they are playing
perfect_wave 5y ago
An MTG limited player named Ryan Saxe created an AI that drafts and builds deck to a highly successfully degree: https://github.com/RyanSaxe/mtg https://github.com/RyanSaxe/mtg He was able to reach Mythic, the highest ranking tier on Magic Arena. Of course this is a different problem to actually playing the game (and probably significantly easier). That being said, this is one guy doing it as a side project with restricted resources. I imagine that MTG could played quite successfully by an AI if someone where to dedicate the resources. Imo much of the difficulty is in laying the groundwork. Large amounts of data don't exist publicly and laying the framework for a bot to play itself would be quite difficult (and then the computation costs would be extremely expensive).

by isaacg 5y ago

golergka 5y ago

Have people tried using GPT-3 for this?

dwohnitmok 5y ago

I think this is purely a resource issue, e.g. if Google Brain decided to make an MtG bot I would be fairly confident it would be superhuman. Even real time strategy games like Starcraft are looking like they're on the cusp of superhuman bots (Alphastar was competitive as Protoss against elite players, but did not consistently beat them).

jdmoreira 5y ago
The search tree is huge in mtg. It has to be the largest of any game. You can take actions all the time. There are triggers all the time, you can stack your actions on top of your opponent actions. Huge space really. And then of course it's also imperfect information both in the sense of your opponent hand but also his deck. The cardpool is also very large for some formats. I actually don't think it's solvable just by throwing MCTS at it with todays hardware but would love to know more about this, if someone else has more insight please reply. EDIT: Oh and there is also the meta-game / deck building aspect. If you are going to win a tournament you have to have favorable matchups against most players in the room.
- ogogmad 5y ago
  MCTS is usually paired up with Deep Learning. This doesn't appear to have any problems with games with even larger branching factors. Look up AlphaZero and AlphaStar.
- karpierz 5y ago
  The search tree size isn't an insurmountable issue. For exple OpenAI 5 managed to play DotA (though admittedly relied heavily on perfect timing and the ability to look at every enemy on the minimap at the same time, and lost a lot when people learned to play around the only strategy it knew).I think it'd be feasible to get an AI to play a modern deck. I think it'd be much harder for the AI to do deck building in a vacuum. You could model it as every game starting with you building your deck, but I can't see that converging stably.
- dwohnitmok 5y ago
  Search space size is no longer a great heuristic of how difficult a game is for the latest in AI approaches. For example, an RTS game has an absolutely enormous search space as well (effectively every unit of several hundred can move in every direction for every single tick of the game clock, many units have spells and many spells are meant to stack with other spells) and Alphastar is a convincing demonstration that this is not out of the reach of current AIs. And you similarly have imperfect information where you don't know what your opponent is doing unless they are sufficiently close to your current units. Even the meta-game/deck building aspect doesn't seem all that insurmountable as it doesn't seem fundamentally different from say a build order other than that it cannot change dynamically on the fly.
archontes 5y ago
I doubt very highly it would be able to sit at a game of commander. Four players with 100 card singleton decks would be an absolutely enormous space to operate in.
- dwohnitmok 5y ago
  Many players sounds like it's still a hard nut to crack for AI approaches (although as poker demonstrates its getting easier), but the deck size doesn't sound like it'd be the main issue.
runnerup 5y ago
Alphastar also didn't play with the same limitations that a human has. Even after removing its ability to see the entire map and finally forcing it to scroll around, alphastar never misclicks (so its APM==EPM) and can still blast nearly unlimited APM for short bursts as long as its "average APM" over an x-second period matched human's APM. I believe Alphastar would generate more interesting strategies if we limited alphastar to a bit below human APM and forced it to emulate USB K+M to click (instead of using an API, which it currently does) and adding a progressively increasing random fuzzing layer against its inputs so that as it clicks faster the precision/accuracy goes down. By "interesting strategies" I mean strategies that humans could learn to adopt. Currently its main strategy is "perfectly juggle stalkers" which is a neat party trick, but that particular strategy is about as interesting to me as 2011-era SC AI[0]. Obviously how it arrived at that strategy is quite interesting, but the style of play is not relevant to humans, and may in fact even get beaten by hardcoded AI's. I'm also very curious what Alphastar could come up with if it were truly unsupervised learning. AIUI, the first many rounds of training were supervised based on high level human replays -- so it would have gotten stuck in a local minima near what has already been invented by humans. This may be relevant if Microsoft reboots Blizzard's IP. I would love to have an alphastar in SC3 to play against off-line, or have as a teammate, archon mode, etc. I think all RTS' are kind of "archon mode with AI teammate" already. The AI currently handles unit pathing, selection of units to attack, etc. With an alphastar powering the internal AI instead, more tactics/micro can be offloaded to AI and allow humans to focus more on strategy. That seems like it would be super cool. Examples: "Here AI, I made two drop ships of marines. Take these to the main base and find an optimal place to drop them. If you encounter strong resistance or lots of static defense, just leave and come back home" "Here AI, use these two drop ships of marines to distract while I use the main army to push the left flank. Take them into the main, natural, or 4th base -- goal is to keep them alive for as long as possible. Focus on critical infrastructure/workers where possible but mostly just keep them alive and moving around to distract the opponent." 0: Automaton 2000 AI perfectly controls 50-supply zerglings (2.5k mineral) vs. 60-supply (3k mineral, 2.5k gas) siege tanks: https://www.youtube.com/watch?v=IKVFZ28ybQs https://www.youtube.com/watch?v=IKVFZ28ybQs
- dwohnitmok 5y ago
  > Alphastar also didn't play with the same limitations that a human has. Even after removing its ability to see the entire map and finally forcing it to scroll around, alphastar never misclicks (so its APM==EPM) and can still blast nearly unlimited APM for short bursts as long as its "average APM" over an x-second period matched human's APM. > I believe Alphastar would generate more interesting strategies if we limited alphastar to a bit below human APM... No Alphastar definitely had misclicks, and it had a maximum cap on APM regardless of average that was far lower than the max burst of APM (or even EPM) of top players. When I have the time I can go dig up some games where Alphastar definitely has misclicks, and I believe the Deep Mind team has said before that it will misclick. Its APM limits are already lower than pros both on average and in bursts (and are reflected in its play, Alphastar will often mis-micro units in larger, more frantic battles such as allowing disruptor shots to destroy its own units, but it will never make the same mistake with much smaller numbers of units). > Currently its main strategy is "perfectly juggle stalkers" Definitely not. That was its strategy in its early iterations against MaNa and is no longer feasible with the stricter limitations in place. Its Protoss strategy is significantly more advanced than that now (see its impressive series of games against Serral with an amazing comeback here: https://www.youtube.com/watch?v=jELuQ6XEtEc https://www.youtube.com/watch?v=jELuQ6XEtEc and a powerful defense against multi-pronged aggression here: https://www.youtube.com/watch?v=C6qmPNyKRGw https://www.youtube.com/watch?v=C6qmPNyKRGw) (and of course by "now" I mean when Deep Mind took it off the ladder). Both of these involve an eclectic mix of units with Alphastar effectively using each type of unit and varying it in response to what Serral puts out and its own resource constraints. A lot of commentators have difficulty distinguishing Alphastar from humans when the former plays as Protoss (its Terran and Zerg play is weaker and often more mechanical). > I mean strategies that humans could learn to adopt. My main takeaways from watching Alphastar were "pros undervalue static defense and often have a less than optimal number of workers (where Alphastar's seeming overproduction of workers lets it shrug off aggressive harassment)," but I don't know if those have picked up in the meta.

cortesoft 5y ago

Wouldn’t the fact that the game is constantly changing, with new cards being added and old ones being removed, also make it harder to solve?

jdmoreira 5y ago
That's harder on humans than on computers. Computers have perfect information on what the legal cardpool is at game they are playing

perfect_wave 5y ago

An MTG limited player named Ryan Saxe created an AI that drafts and builds deck to a highly successfully degree: https://github.com/RyanSaxe/mtg https://github.com/RyanSaxe/mtg He was able to reach Mythic, the highest ranking tier on Magic Arena. Of course this is a different problem to actually playing the game (and probably significantly easier). That being said, this is one guy doing it as a side project with restricted resources. I imagine that MTG could played quite successfully by an AI if someone where to dedicate the resources. Imo much of the difficulty is in laying the groundwork. Large amounts of data don't exist publicly and laying the framework for a bot to play itself would be quite difficult (and then the computation costs would be extremely expensive).