>> I have a particular interest in having a computer play the game Magic: the
Gathering at an expert level.
Well, hi. I have a similar interest in M:tG AI. My degree dissertation was a
rules engine with an AI player and a parser for ability text (at the time, in
2011, it was probably the only such parser).
I should say my AI player was fairly weak- I started with the ambition of
writing a halfway decent player using metagame knowledge, but I got quickly
distracted by the task of writing the ability text parser, that I found a lot
more interesting at the time.
It might surprise you to know there has been some academic interest in playing
M:tG at an expert level. The best results seem to have been achieved with
Monte Carlo Tree Search [1], the part of AlphaZero that isn't a neural net.
That paper used MCTS to attempt to solve combat only, and then only with
vanilla creatures (no abilities, no spells).
The community rules engine Forge (which you know about, since you have read
the List of MTG Engines thread on CCGHQ) also uses MCTS, or at least did last
time I checked (a while ago). Forge also uses per-card expert-level domain
knowledge, i.e. it has specific rules on how to play each card. I don't know
too much about its AI, like I say it was a while ago that I looked into it,
but I can say that, given a strong deck and a favourable matchup it can
sometimes play an almost perfect game. This depends a lot on the kind of deck-
it's much better with straightforward beatdown decks, it's completely
incompetent with combo decks (probably because it does not have any deck-level
domain knowledge to guide its plays). It's surprisingly inept at playing burn
decks- because by default it's instructed to prioritise burn for removal (the
sensible approach in terms of card advantage, which burn decks turn on its
head however). I find however that given a powerful deck (say, Affinity or
Jund) I can still dominate it no matter what it's playing. It will always make
some egregious mistake, or blindly apply one of its heuristics when it really
should not.
Then there's the official rules engine video game, Magic Duels (previously,
Duels of the Planeswalkers) [2]. According to a writeup by its lead designer
[3] I believe it's probably also using MCTS - the description in the link is
not for technical people so it's hard to tell, but it would match both
Alpha-Beta minimax and MCTS, so I'll go out on a limb and say probably MCTS.
I think there are three, let's say, levels of play that an AI agent will have
to be measured against. The first is playing a known deck with known cards
(the player has access to the deck and cards in training); the second is
playing an arbitrary deck with possibly perviously unseen cards; the third is
building a coherent deck with a viable strategy from a pool of possibly unseen
cards. The same levels pertain to opponents' decks - the AI player should be
able to play against known decks, or arbitrary decks, or build a deck to beat
a specific opponent [4].
Of the above levels, I believe that level one (playing a known deck against a
known deck) is probably attainable with AlphaGo-like self-play. I'd start with
two simple decks (burn vs beats, say) and use a rules engine to generate all
possible moves in each possible board situation. That can still grow very
fast, faster than any game of chess or Go (and those grow very rapidly)
because of the complexity of the game- but keeping the card pool artificially
low might allow a chance to get a competent player out of it. Of course,
self-play can be complemented with heuristics- and there is some good quality
expert knowledge about what matters in M:tG (card advantage, tempo, etc). Like I say above, Forge uses per-card heuristics and it does pretty well, so it's a promising direction for research.
For second or third level play, I don't think those are things that you can
achieve with self-play only, or even self-play with (a lot) of expert
knowledge. I think you need a kind of multi-disciplinary approach, with
specialised techniques to handle parsing and "understanding" the text of
unseen cards, etc.
Anyway, this is getting a bit long- good luck and do make a lot of noise on
the internets if you end up with something even marginally better than what's
already out there. M:tG is a reach seam of AI research material that has been
left untapped so far, a bit surprisingly so.
_________
[1] Ensemble determinization in MCTS for the imperfect information card game M:tG,
by Peter Cowling, Colin Ward, Edward Powley:
[4] If you want to be more thorough you can extend this to a two-axis scheme.
For instance, a level 1-2 game would be using a known deck against an unknown
deck, etc.
Well, hi. I have a similar interest in M:tG AI. My degree dissertation was a rules engine with an AI player and a parser for ability text (at the time, in 2011, it was probably the only such parser).
I should say my AI player was fairly weak- I started with the ambition of writing a halfway decent player using metagame knowledge, but I got quickly distracted by the task of writing the ability text parser, that I found a lot more interesting at the time.
It might surprise you to know there has been some academic interest in playing M:tG at an expert level. The best results seem to have been achieved with Monte Carlo Tree Search [1], the part of AlphaZero that isn't a neural net. That paper used MCTS to attempt to solve combat only, and then only with vanilla creatures (no abilities, no spells).
The community rules engine Forge (which you know about, since you have read the List of MTG Engines thread on CCGHQ) also uses MCTS, or at least did last time I checked (a while ago). Forge also uses per-card expert-level domain knowledge, i.e. it has specific rules on how to play each card. I don't know too much about its AI, like I say it was a while ago that I looked into it, but I can say that, given a strong deck and a favourable matchup it can sometimes play an almost perfect game. This depends a lot on the kind of deck- it's much better with straightforward beatdown decks, it's completely incompetent with combo decks (probably because it does not have any deck-level domain knowledge to guide its plays). It's surprisingly inept at playing burn decks- because by default it's instructed to prioritise burn for removal (the sensible approach in terms of card advantage, which burn decks turn on its head however). I find however that given a powerful deck (say, Affinity or Jund) I can still dominate it no matter what it's playing. It will always make some egregious mistake, or blindly apply one of its heuristics when it really should not.
Then there's the official rules engine video game, Magic Duels (previously, Duels of the Planeswalkers) [2]. According to a writeup by its lead designer [3] I believe it's probably also using MCTS - the description in the link is not for technical people so it's hard to tell, but it would match both Alpha-Beta minimax and MCTS, so I'll go out on a limb and say probably MCTS.
I think there are three, let's say, levels of play that an AI agent will have to be measured against. The first is playing a known deck with known cards (the player has access to the deck and cards in training); the second is playing an arbitrary deck with possibly perviously unseen cards; the third is building a coherent deck with a viable strategy from a pool of possibly unseen cards. The same levels pertain to opponents' decks - the AI player should be able to play against known decks, or arbitrary decks, or build a deck to beat a specific opponent [4].
Of the above levels, I believe that level one (playing a known deck against a known deck) is probably attainable with AlphaGo-like self-play. I'd start with two simple decks (burn vs beats, say) and use a rules engine to generate all possible moves in each possible board situation. That can still grow very fast, faster than any game of chess or Go (and those grow very rapidly) because of the complexity of the game- but keeping the card pool artificially low might allow a chance to get a competent player out of it. Of course, self-play can be complemented with heuristics- and there is some good quality expert knowledge about what matters in M:tG (card advantage, tempo, etc). Like I say above, Forge uses per-card heuristics and it does pretty well, so it's a promising direction for research.
For second or third level play, I don't think those are things that you can achieve with self-play only, or even self-play with (a lot) of expert knowledge. I think you need a kind of multi-disciplinary approach, with specialised techniques to handle parsing and "understanding" the text of unseen cards, etc.
Anyway, this is getting a bit long- good luck and do make a lot of noise on the internets if you end up with something even marginally better than what's already out there. M:tG is a reach seam of AI research material that has been left untapped so far, a bit surprisingly so.
_________
[1] Ensemble determinization in MCTS for the imperfect information card game M:tG, by Peter Cowling, Colin Ward, Edward Powley:
http://orangehelicopter.com/academic/papers/tciaig_magic.pdf
[2] Duels of the Planeswalkers: The Magic Engine, by Patrick Buckland
https://magic.wizards.com/en/articles/archive/duels-planeswa...
[3] Duels of the Planeswalkers: All About AI, by Patrick Buckland
https://magic.wizards.com/en/articles/archive/duels-planeswa...
[4] If you want to be more thorough you can extend this to a two-axis scheme. For instance, a level 1-2 game would be using a known deck against an unknown deck, etc.