Building a Magic: The Gathering AI, Part 2: MVP
This is part 2 in a series, you may want to read part 1 first.
In the introduction to this series I covered what I’m trying to do at a high level. I unfortunately can’t just say “Computer, solve Magic”. I have to tell the computer what Magic is, and tell it ways it might be solved, and then it might do so, if I told it the right things (computers may be lazy but at least they are deterministic). So, as they in various places, let’s start at the beginning.
Computer, Magic is…
The Magic website has two sets of rules. There is a nice, short easy-to-read one here. It is nice, short, and easy-to-read because it’s very incomplete and basically useless. Then there are the long (225 pages!), difficult-to-read official rules here. They have the nice feature of being complete, but also have the aesthetic of something an aging lawyer wrote on his 486DX laptop.
Convert 225 pages of rules into code? Not actually that big of a problem, all things considered. It would take a while but in some respects 225 pages would be easier to convert than 50 pages, when the extra 175 pages are written by (and because of) pedantic nerds, selected from a population where median nerdery is very high and median pedantry is even higher.
But, there’s a monkey wrench. 19,989 monkey wrenches, actually, as of this writing. The cards. A large number of those cards have additional rules on them, many of which intentionally break the ones in the big fat rulebook.
“Learn the rules like a pro, so you can play Magic cards that break them like an artist.”
― Pablo Picasso, allegedly
Let’s take a look at some of them:
100.2a In constructed play (a way of playing in which each player creates their own deck ahead of time), each deck must contain at least sixty cards. A constructed deck may contain any number of basic land cards and no more than four of any card with a particular English name other than basic land cards.
704.5j If a player controls two or more legendary permanents with the same name, that player chooses one of them, and the rest are put into their owners’ graveyards. This is called the “legend rule.”
And lest you think that some rules just can’t be broken:
So now we have 225 pages of negotiable rules, and twenty thousand upjumped pieces of paper that want to be part of those negotiations.
Handling all of that at once is simply not going to happen, so let’s try and find ways to clarify and hopefully the goal.
The AI will only ever make legal decks and play legal games.
I could write something that cheated or invent some new format where you can play with 10 card decks or use 40 lightning bolts and 20 lands, but what’s the point? Magic cards only have value in context, and the more context we remove the further from anything useful we’ll drift. Note that this doesn’t necessarily mean the AI will make good decks, as we’ll discuss later in this article).
The AI will only play Standard Magic.
Magic releases 7 sets of cards every year, two “blocks” of 3 sets as well as a core set. The Standard format was devised to stop people with 20 year old cards worth thousands of dollars from scaring away fresh blood (I mean new players). It also keeps the “meta” (i.e. what everyone else is playing) fresh, a topic we’ll discuss more in the future. This drops 20,000 cards down to about 1,500. Woohoo we’re 85% done! Except with a couple of hundred cards coming out every 2–3 months we’ll never really be done…
The AI will never concede.
I’m just throwing this out there because a) I never concede, if you’re going to beat me I’m going to make you work for it and b) it’s probably more work to figure out when to concede than it is to just play it out.
Those are the three hard-and-fast rules, but that still leaves a huge amount of work to be done. So we’re going to rotate adding mechanics, cards, and intelligence. Follow along and this should make sense.
Of course, like Magic, I reserve the right to break theses rules at any time…
Minimum Viable Product
You might have thought that MVP in the title was most valuable player, but you are wrong (shame on you). A term of art in software development, especially startsups, that is kind of a joke but kind of not is the “minimum viable product”. Much like the word “reasonable”, “viable” is a word with more than enough play for entrepeneurs to think they are fooling their investors. They’re usually wrong, and it’s usually not actually “viable” but nobody is dangling my salary like a carrot on a stick to get this done, so there’s no need to overstate it.
Version 0.0.1
What’s the simplest, legal game of Standard Magic that one can possibly play, since we can’t concede.
New Behaviors:
- Each player has a 60 card deck.
- One player randomly goes first.
- The first player skips the draw phase.
- Each player must draw each turn.
- Each player must discard down to 7.
- If a player runs out of cards and must draw, they lose.
New Cards:
- Mountain (M19)
Note: I use the term “away” and “home” in my code, and therefore in my descriptions, because “on the draw” and “on the play” gets a little confusing. This is appropriated from baseball where the away team bats first (“on the play”), and the home team bats second (“on the draw”).
Results:
So, I coded this up. Each player has 60 Mountains. They each draw 7 cards. On turn one, the home player discards a random card, home and away players have 52 and 53 cards in their libraries, respectively. On turn two it’s 51 and 52, and so on until, in every game the home player loses the game because they run out of cards first. Legal? Yes. Useful? Not really. But we did play a full game of Magic.
Version 0.0.2
New behavior:
- Each player plays a land, each turn, if able.
New cards:
- None
Results:
This means that neither player has to discard any more, but otherwise the away team still always wins.
Let’s pause here to talk about two things:
Where’s the source code?
At the moment I don’t plan on sharing anything except code snippets, where appropriate, for a few reasons:
- Most importantly: I want this series to be about AI concepts and Magic theory, not programming syntax.
- I’m not interested in maintaining an open source project.
- I write code for a living, and would need clearance to share things freely (not that they wouldn’t let me, but it’s just a hassle).
Goldfish Decks
This is a term for an opponent that does nothing, much like a goldfish. In this case, the opponent will have a deck of 60 cards, 5 of each land. They will not be able to do anything except soak damage. This means that I won’t have to code reactions, blocking and so on.
The first “complete” version of the AI is basically going to be the deck that can generate X (typically 20) damage in the fewest turns, or the deck that can generate the most damage in X turns (like where most aggro decks will slow down). This won’t necessarily be a realistic play style but could offer some information around building burn decks.
So for now, 0.0.2 (once we add the other 4 basic lands) gives us a goldfish deck to play against, so we can lock the opponent at that level. Both sides will use the same AI, it’s just that the goldfish will never be able to do anything.
To try and make things clearer, I’m going to refer to the “real” deck that will have creatures and spells as the “robot” deck.
Version 0.0.3
New Behaviors:
- Tapping lands (i.e. filling mana pool)
- Summoning creatures
New Cards:
- Plains (M19)
- Island (M19)
- Swamp (M19)
- Forest (M19)
- Fire Elemental (M19)
In each first main phase, the AI will now play a land, tap all of it’s lands and check each of it’s cards to see what it can summon. If something is able to be summoned, it plays it.
Results:
Since we’re not attacking yet, the away team still wins every time.
Version 0.0.4
New Behaviors:
- Attacking
New Cards:
- None
Results:
The robot deck now has 56 Mountains and 4 Fire Elementals. Unsurprisingly, it now wins almost every time(99.96%). It doesn’t actually win every time because there are so few creatures it still runs out of cards sometimes before it can inflict 20 damage.
Turn Count Results:
- Min: 8
- Average: 20.02
- Max: 54
- p25/50/75: 12/18/25
So this tells us that … it’s a terrible deck. Half the time it takes 18 turns to beat the goldfish, ouch. But that wasn’t the point, we know the mechanism works, and we’ve got some basic stats, so can start comparing different decks.
Getting to the point where the AI can actually kill it’s opponent is a decent milestone and a good place to stop, but you probably didn’t just spend 6 minutes reading this far to find out that a deck with 4 creatures is bad, yet better than a deck with 0, so we shall carry on!
Version 0.0.5
New Behaviors:
- None
New Cards:
- Bogstomper (M19)
- Frenzied Raptor (XLN)
- Gigantosaurus (M19)
- Knight of New Benalia (DOM)
- Primordial Wurm (DOM)
- Swab Goblin (RIX)
- Sworn Guardian (RIX)
- Yargle, Glutton of Urborg (DOM)
Results:
So what we did here is to look for cards that have no special abilities, and are the cheapest options for their respective power level. This ended up being 9 cards. There are no basic creatures currently in Standard at power 8.
The winner is, unsurprisingly, the one with the bet power to mana ratio. Gigantosaurus weighs in at an impressive 2.0 and can do 20 damage (which only requires two hits) as early as turn 7, and half the time by turn 16. Interestingly, the Frenzied Raptor comes in second place despite having the 4th highest ratio. The rest are in the same ballpark, with the exception of the Sworn Guardian who is only 1 power but costs 2 mana. Besides being inefficient on attack, he just doesn’t have enough time to peck his opponent to death, as shown by also having the lowest win rate.
I won’t be bothering with win rate on future goldfish battles, simply adding any 5th creature to the deck brings this to 100%, even for weak-ass Sworn Guardian, so it no longer is useful.
So we now handle about 1% of the cards in Standard, and have real numbers to try and beat (it won’t be hard). We’ll try to double our coverage next time.
Find out more on the next installment!
Clap for the monkey, he loves it!
