Truth from Zero?
rjlipton.wordpress.com
rjlipton.wordpress.com
I have a particular interest in having a computer play the game Magic: the Gathering at an expert level. In some ways, this seems like an ideal fit for AlphaZero - it's a two-player strategy game with a finite number of valid plays at each state, yet I'm still not sure how to deal with four key elements:
1. The game is random - it has a deck of cards that are shuffled.
2. The game has hidden information - cards in hand are hidden.
3. The cards can change the rules of the game itself. For example, a card could change the win conditions of the game. There are over 20,000 unique cards with more regularly being printed.
4. A major part of the game (perhaps the most important) is that each player chooses their own combination of sixty cards from the ever-increasing pool. This makes understanding the "metgame" extremely important - a "deck" that was good a week ago may be outclassed the following week as players react.
In addition, there are many decks that win with odd combinations of cards and often the only way to beat these decks is to know in advance how to stop the combo.
Any ideas on how best to approach this problem?
Right now I am working on building a very simple version of the game with both players playing the same three cards with no randomness. This will eventually feed a simple genetic algorithm to test different quantities of each of the three cards to find an optimal "build".
I thought about writing my own MTG engine for a while and I believe the key is in modeling the game state (and the valid/possible transitions/rules - which one could argue that are still part of the game state).
I believe exhaustively trying out all decks is not going to fly and deckbuilding should be centered around synergies + looking at what currently works (top decks).
I would personally settle on an AI bot that plays perfectly that I could feed decks to test.
Yes. I'm very likely going to use the guts of XMage to handle card text and encoding the game state and all legal actions. I'm deliberately trying to get a simpler version with only three cards working first so I can see if it's possible to "solve" (i.e. test every single possible action and response for every possible game and determine the optimal play each time) such a game.
A major issue is that determining what is in the opponents hand based on previous plays is pretty important in situations where such information cannot be brute forced and instead needs to rely on dependent probabilities.
>I believe exhaustively trying out all decks is not going to fly and deckbuilding should be centered around synergies + looking at what currently works (top decks).
I had decent success building a GA that could tweak the list for a simple burn deck by adding or removing single cards as a mutation. I only tested against a very simple opponent and all potential plays were hand-coded.
>I would personally settle on an AI bot that plays perfectly that I could feed decks to test.
The issue is that "plays perfectly" is an extremely tough bar (even against only one opposing deck). As a trivial example: Magic is full of "infinite" combos where a given loop can be completed an arbitrary amount of times. Knowing the "correct" point to stop the looping is extremely tough to code perfectly.
It's also possible to have, say, a trillion tokens on the board and it's legal to pick any one of them as a target - handling this kind of situation is also pretty hard to handle computationally.
I believe that an AI that plays perfectly while seeing everything (i.e. oppponent hand + both libraryies, so no hidden state) would still be an impressive accomplishment and could be used to fine tune the deck-building process.
Even more entertaining, is the fact that (IIRC) there are certain combos that cause infinite loops that can't interrupted, e.g. if neither player has a counter or kill spell, then the turn lasts indefinitely.
Of course you may still be able to find a strategy that works well against humans, but that would still be a cutting-edge research task.
Hidden information is a big problem, the classic benchmark for that is poker. The latest breakthrough I'm aware of was for heads-up limit Texas hold'em http://science.sciencemag.org/content/347/6218/145 That may be a difficult game, but it has vastly fewer possible states. The same approach as used in the paper would almost certainly not scale for MTG.
Dealing with cards that can arbitrarily change the rules of the game would require human-level AI almost by definition, unless you want to manually translate them into code, in which case the system would be unable to deal with new cards.
Now that I have told all about how the problems you identified are much too difficult, I want to add that that shouldn't discourage you from just playing around. Starting with a minimal test case is how poker research took off, so you're definitely on the right track.
I'm a big AI poker fan (and a big fan in general). The current state of the art is now a bot that can consistently beat the very best heads-up no limit (i.e. there are a very large number of possible legal bets) players in real money games.
http://science.sciencemag.org/content/early/2017/12/15/scien... - note the date was yesterday :)
Eventually though, online poker will be full of bots.
That's not unreasonable at all. No one is expecting you to solve general purpose AI by having the cards interpreted with NLP. And translating the cards' behavior to code is not some insurmountable task. Wizards of the Coast has presumably already done that for the online version of the game.
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.
I wonder if there is any principled statistical way to test, given a set of players, how far the best of them is from optimal. Hmm....