Building a Magic: The Gathering AI, Part 1: Introduction
Magic: The Gathering is an immensely complex game. With 10s of thousands of unique cards to choose from, the number of possible decks is astronomical, and the number of ways to play those decks is similarly enormous. This has made it very difficult to build a good MtG (as the cool kids call it … online) AI, especially while the people who get paid to beat these games have been distracted by other games like Go and StarCraft. Therefore, being the overconfident jackass programmer that I am, I’ve decided to build one!
Why Magic?
“We choose to build a Magic AI in this decade and do the other things, not because they are easy, but because they are hard.”
— JFK? … maybe?
I’ve played a large number of different games over the years, almost all of which would be far simpler to write an AI for and would be far better suited to my non-existent AI-writing skills. Magic appeals to me because it’s probably the most complex game that has sustained any kind of popularity (25 years and counting). Hearthstone is a fun game with a much smaller card base, but it’s just so random I lost my taste for it. Dominion would be fairly straightforward as it’s generally a race and well-suited to optimization. Board games would be fun but rarely last long enough that I’d still want to play it by the time I “finished” the AI.
Why Me?
“God sent me to Earth to show people how to play Magic: The Gathering.”
— Cristiano Ronaldo, probably.
The chances of success here are … low, for a number of reasons:
- I don’t have a lot of time to spend on this. Family, work, etc.
- I don’t really know what I’m doing — I’ve never built an AI, have standard programmer-level math skills, and don’t really know anything about machine learning.
- I haven’t played Magic in years, from Revised through Ice Age (before Magic theorycraft was really a thing), briefly returned during Avacyn Restored, and have just recently started playing again on Arena. I am barely familiar with the current cards and am not yet a decent player.
However, I am pretty good at problem solving and programming, am a quick learner, and am interested in all aspects of this project, so who knows what will happen?
So… Let’s get started!
Let’s start by being reductive. An AI player, just like a human player, basically just has to do one thing, over and over:
- When presented with a choice, make the best one.
It’s that simple. If you do that every time, you will almost always win (e.g. my Warhammer 40,000 career /brag). Unless your opponent does the same thing. Or if the cards or dice or RNG doesn’t cooperate (e.g. my entire X-Wing career /cry).
Wow, that was easy!
Not so fast, buck-o! Let’s break that rule into two pieces and see what you think then.
“When presented with a choice”
A human has a magical ball of goo in their head. It is usually hooked up to some fixed-lens cameras and omnidirectional microphones. After a few years of being generally useless, and an inordinate amount of effort by other humans, the system starts to work together. It eventually becomes really good at pattern recognition. Humans have a quaint network protocol for communicating that is self-organizing but low bitrate. Their memory is reasonable but very lossy. They almost universally suck at math. Really. They are terrible.
A computer is made of shiny bits of sand and metal. They are terrible at coming up with new ideas. They are really good at math and have amazing memory but strangely have never expressed any interest in using them except to please the slow, silly meatbags. They stupidly rely entirely on said meatbags to gain any understanding of the world whatsoever.
So this means that the choices come from the inconsistent, unpredictable humans, who made way too many cards with way too many rules, and the computers don’t understand them. This complicates our otherwise elegant approach. Also, while the computer is happy to work for the humans, they are lazy and will never do anything unless asked.
Enter the brave, humble programmer. This is a special type of human whose deviant brain prefers talking to dumb, simple computers rather than smart, interesting people. Those smart, interesting people will often pay respectable sums of money to these poor souls to talk to their computers for them. After spending all day talking to someone else’s computers, the programmers then mock the smart, interesting people by spending that money on more computers, which they go home and continue to talk to, without getting paid.
So, the programmer (that’s me, if you’re skimming. Don’t lie. Medium has all sorts of fancy gizmos and we know when you’re skimming) needs to enumerate (if you doubted that I’m a programmer please notice I just used the word enumerate) the choices for the computer, so it can then do the easy part of simply choosing the right one.
In a game like poker, there are a few choices (call, raise, fold). In a game like chess, there are more (16 pieces, each with roughly 1–10 options). In magic, there are generally a similar number as chess for game play, but an incalculable (to mere humans) number of choices when making a deck, which is just as important as the game itself. We’re waaay beyond if-then-else logic that so impressed you that time you spent 6 hours writing an Excel macro instead of just filling in those 22 cells with a bold green “OK” yourself.
“make the best one”
OK, so the programmer wrote a bunch of mumbo-jumbo computer lingo and came up with the list of 32 gojillion choices. Surely this sexy computer with it’s nano-somethings and mega-whatevers can just sort those by bestiness and voila!, the best one is at the top for us to copy and paste into our game for an easy win.
Unfortunately, bestiness doesn’t exist. I’m not kidding, go look it up in the dictionary, it’s not there. Even if it did exist, computers don’t give a flying saucer what it is or what it means. If you tell it the bestiness it will remember it, it will add it, it will do all sorts of interesting operations with awesome sounding names like modulo with it, but it won’t come up with it on its own. It won’t even give you a hint. Ungrateful piece of junk.
The trick is in the name
So if computers won’t figure out the choices, and won’t figure out which is the best, why do we rescue them from those factories and keep them safe and dry and feed them delicious electricity? AI is supposed to think so we don’t have to, right?
Fool. Only a human could be so wrong. AI. A.I. Artificial Intelligence.
artificial
1. made by human work or art, not by nature; not natural
2. made in imitation of or as a substitute for something natural
“made by human”, “imitation”, “substitute”. This whole thing is a scam! We spend all this time taking care of computers, and still do all the work? And then we only end up with an imitation?! Seems like the computers really are the smart ones here, doesn’t it? Why do we let this happen?
Two answers. Math, and memory. Humans are so bad at math, and our memories are so wonky that we spend all day pushing buttons and burning dinosaurs to make electricity simply keep the computers happy so we can borrow their amazing math skills and memory.
Dude, what are you talking about! I just wanted a new freaking decklist. Orzhov is killing me!
Ok so I’ve gone a bit far afield on the Magic thing at this point. But basically if we’re going to keep talking about AI I felt it was important that we all really understand what it is. It’s simply humans coming up ways to get computers help them cheat on their math homework. We don’t cheat because we’re bad students, we cheat because the right way is basically impossible with something as complex as Magic.
We’re going to start with some basic AI concepts, explore and hopefully test some MtG theory, and if all goes well, we’re probably still going to get mana hosed and lose to an 8 year old who is only here because he thought it was Pokemon night.
It will be a fun ride, and I hope you stick around.
I also hope you hit the clappy thing.
Just sayin’.
Part 2 is now available!
