7 ms·

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 act

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.

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.