I’m in the process of finishing up my final computer science elective at Washington University, Artificial Intelligence. I’m taking it with my roommate, Tom Mooney, who also plays Magic. Our final project for the course is to “write an AI to solve a problem,” and one of the problems we’re allowed to solve is a game.
Naturally, Tom and I chose Magic. It was a tough ride, but we’ve finally gotten a computer to play Magic optimally.
Bahahahahahaha. Hahahahahahaha. Hahaha. Hahaha. Haha. Ha.
Oh, man. I almost kept going with a straight face. I was so close. Man.
Yeah, we didn’t actually program a computer to play all of Magic optimally. What we did do – and this is still pretty cool – is come up with an AI that can attack and block optimally in a specific setting. Now before you get all excited about the prospect of bringing a laptop to a six-man draft as your third teammate, take a look at the requirements for the setting.
– Neither player ever has cards in hand
– The game begins with all the creatures in play that will ever be in play
– The only ability any creature can have is Flying
So much for Kenji versus the Magic equivalent of Deep Blue.
Believe it or not, it took a couple thousand lines of code just to get the computer to attack optimally in this simple little world. But take a look at that one little word there – optimally. How many times do you think you’ve attacked optimally in your Magic career?
Sometimes it’s trivial. Your opponent’s at one life, has no permanents, and no cards in hand… what do you do with your Raging Goblin? Turn it sideways, derf. You have three Savannah Lions on turn 2 and the opponent has played two Islands and nothing else? Seems pretty tough to go wrong by swinging with the team.
Now what about in a grand stalemate? Limited players know what I’m talking about – the board’s all gummed up with like eight creatures on each side, and both players are waiting for the right movement to strike. How do you attack optimally under those complicated circumstances?
Once you take spells, reinforcements, and combat tricks out of the equation (as we’ve conveniently done in our little world), anyone should be able to theoretically look at a board and figure out how best to attack. You have two 2/3s and I have a 3/3 and a 2/2 Flying? Attack with the Flyer only. Obviously you’ll double-block my 3/3 if I attack with it, and I’ll trade my 3/3 for one of your 2/3s. That’s a bad deal.
However, if a game state without hidden information were easy to solve, no one would bother writing Magic Puzzle articles. Check out Jeff Till work – with few exceptions, the puzzles give you every piece of information you need to figure out what to do, yet it takes us a very long time to arrive at a solution.
Still, the fact is that Magic is more complicated than this world, so why is it useful to think about it? First, sometimes you have to play as though you have all the information, even when you don’t. Consider the all-in move. There will come a time when you look a board and say to yourself, “it doesn’t matter what he has. If he has something to wreck me, I lose, but if I don’t attack here, I lose anyway.” When you lose if he’s got it and lose if you sit there, you’ve got to assume he doesn’t have it and figure out how to attack based on that assumption.
Say you’re at two life against a pinger you can’t remove. You know it will take two attacks to finish the opponent, and you have to attack just right this turn in order to deal him enough damage to finish him next turn with an alpha strike, while keeping enough blockers back to stop his inevitable counterattack. If the board’s full of creatures, there are many, many different combinations of attacks you could make; attacking correctly could win you the game, but one misstep could cost you everything.
So how does the computer do it?
Simple trial and error, believe it or not. Let’s say we have this game state.
Computer Player (20 life):
Mistral Charger
Hill Giant
Human Player (20 life):
Foot Soldiers
Foot Soldiers
It’s the computer player’s turn, so it “mentally” tries out a potential attack strategy: alpha strike!
The computer mentally bashes with Mistral Charger and Hill Giant, and assumes that the human will correctly double-block the Hill Giant with both Foot Soldiers (remember, the Computer player has no cards in hand, so there’s no chance of a combat trick here). The board then looks like this:
Computer Player (20 life):
Mistral Charger (tapped)
Human Player (18 life):
Foot Soldiers
Foot Soldiers
The computer then assumes that the human will correctly attack back with both Foot Soldiers, taking him to 16. Since the Human is now dealing damage in 4-point chunks while the Computer is dealing them in 2-point chunks (and since there are no life-saving topdecks in this world), the Human will inevitably win this game unless a piano lands on him and he stops attacking.
After having worked out how the rest of this entire game will play out, the Computer concludes that alpha striking on the original turn will lead to losing the game. No thanks! Clearly, alpha striking is right out.
So it tries something else: attacking with just the Mistral Charger. The Human player once again drops to 18 life, but now the Computer has a Hill Giant on defense. The computer then trial-and-errors its way through all the possible counterattack scenarios – the Human swings with one Foot Soldier, swings with both, or keeps them both at home – and realizes that no matter how the Human attacks, the Mistral Charger will ultimately win the race and take the game nine turns later.
Thus, the computer chooses to attack with the Mistral Charger only.
I haven’t played against him personally, but I’ve heard that GP Champion and all-around great guy Luis Scott-Vargas employs a similar strategy when working out how to attack. He’ll literally say aloud, “Okay, if I attack this way, you’ll block here and here, so that’s out… well, if I do it this way, you’ll block like this… got it. Attack like so.” (I’ve also heard that he tends to announce the correct blocks as well, and if you block differently you end up regretting it.) Basically, what I’m trying to say is that LSV is a robot.
Actually, what I’m trying to say is that you really can work out your attacks this way. It’s not particularly quick or elegant, but if you’ve got the short-term memory for it, it can be extremely effective. You don’t have to say the steps out loud, but a lot of the time all it takes to arrive at a good decision is to just try a couple of different attacks in your head, anticipate how the opponent will block and counterattack, and think of how the board will look afterwards.
Go back to the Mistral Charger/Hill Giant versus Foot Soldier/Foot Soldier example. The computer had to work all the way through to the end of the game to figure out that alpha striking with the flyer and the 3/3 was wrong (the big secret of computers is that they’re basically roomfuls of imbeciles with photographic memories), but as intelligent players we can see the writing on the wall as soon as the dust has cleared from the original attack.
I showed you the turn after the alpha strike, where the Mistral Charger was tapped, the opponent was at 18, and I’d lost my Hill Giant, and you could immediately see that I’d made a bad attack. I was down a card (a 3/3, no less), my opponent still had all his creatures intact, and I had only dealt him two damage.
People talk a lot about “thinking a few turns ahead” as a good way to improve as a Magic player, but they never really get into what that entails. Folks, this is it. It’s just trying something out in your head (before announcing it in the game), anticipating your opponent’s response, and seeing where the game state ends up.
It’s not always enough to look just one turn ahead, of course. Sometimes you need to keep looking and looking until you get enough information to make your original decision. One of the places where this comes up most often is in races. Say you’re at 16, your opponent is at 10, and you’re wondering if you should start bashing with your Azure Drake (2/4 Flying) that is otherwise holding off his Wind Drake (2/2 Flying) and Grizzly Bears (11/11 trample indestructible. Er, 2/2).
A lot of players will sink deep into thought in a board position like this, stroking their chins and musing, “To attack or not to attack? That is the question. Whether ‘tis nobler in the mind to try and kill him here…wait! I might lose! But then again I might lose if I don’t race…but what if I don’t race and find another way to kill him? Ahh!” That’s not only unhelpful, it’s a major waste of clock time.
If I ran this through our AI system, though, the computer would set right to work with trial and error.
“Let’s see. If I attack with my 2/4 Flying, you’ll decline to block and go to 8. You’ll then attack back with both 2/2s and take me to 12. I’ll attack back and take you to 6, then you’ll attack back and take me to 8. I’ll take you to 4, you’ll take me to 4. I’ll take you to 2, and you’ll kill me. Not attacking, sir.”
Sadly, the typical novice response is, “Oh, hell with it. Get in there.”
Now, of course this model is a huge simplification of Magic. In the Azure Drake example, there’s a lot more to consider than just the damage on the board. It looks like I’m going to lose the race right now… but what if my deck is full of removal? All it takes is one Dark Banishing to turn this race right around in my favor. But what if the opponent topdecks a creature to swing things back around to his side? What if he Chastises my Azure Drake?
This is why Tom and I didn’t attempt to solve all of Magic. For a human, it’s not too much harder to say “Play around Chastise” if you’re pretty sure he’s got one — that is, don’t attack when he leaves four mana open. For a computer, though… that little addition would take several times as long to write as the entire original AI did by itself.
Luckily, we’re all humans here. When we’re anticipating the opponent’s blocks and counterattacks, we can factor in these things. This is the most skill-intensive part of the whole process; in booster draft, for example, you need to be able to reason through what kind of tricks the opponent might have – remembering what you passed, considering the opponent’s draft archetype – and adjust your predictions accordingly.
In the Azure Drake example, even if everything goes according to plan… you still lose the race. You will actively need to topdeck something to make you win it (assuming the opponent doesn’t topdeck something to turn it back around again), so at the very least you know that it is a very risky play to attack. But does the fact that it’s risky mean you shouldn’t attack?
This is perhaps the greatest benefits of looking a turn or two ahead under the assumption that no spells will be played: you immediately find out which player will be favored by the strategy in question, and by how much. Say you’re Azure Drake Guy and you know your opponent’s deck is full of large monsters, while yours is full of small fry and not much removal. In such a situation, the opponent has inevitability on you; sitting there with Azure Drake on defense until you can “safely” attack may be an even worse proposition than starting a race that you will lose by default.
Looking ahead a few turns tells you that bashing with the Azure Drake will make you lose the race by two measly life points, assuming no spells are played. That’s a very close race, even if you will lose it by default – so if your topdecks are just a bit more helpful than your opponent’s, or if he makes so much as one wrong attack or block, you might yet win this race anyway. Will you have a better shot at winning the game by engaging in this close race as the underdog than by sitting on defense when the opponent has inevitability (as the super-underdog)? It will depend on the situation, of course, but that’s a much more specific and useful question to be asking than just “man, should I bash here?”
This works in Constructed as well. Say you’ve got this hand:
Island
Rune Snag
Rune Snag
Phyrexian Ironfoot
Cryptic Command
Teferi, Mage of Zhalfir
The opponent plays turn 2 Keldon Marauders. You’ve got two Islands in play, and can Rune Snag it. Do you?
Again, just look a couple turns ahead. If you don’t Snag the Marauders, you will take five damage from it unless you play the Ironfoot next turn. If you tap for Ironfoot, though, the opponent can resolve a creature that will stick around – and will possibly finish off the blocking Ironfoot with a post-combat burn spell besides. Is that okay? What’s the worst he can do to you if you let him resolve whatever he wants on his third turn? On the other hand, do you think you can hold off 15 points of damage for the rest of the game if you just take five on the chin?
Limited or Constructed, it’s all a matter of working through the opponent’s possible moves. The more you practice it, the more informed your decisions will be.
The final bit of this puzzle is time management. A computer can run through simple scenarios much faster than we can, and we’re on a short enough clock as it is. Tom LaPille first article as a columnist on Star City dealt with speeding up certain parts of your game, and this is absolutely an area where you can get ahead by hardwiring certain thought processes into your autopilot.
It is a hugely advantageous to be able to look ahead quickly. The faster you can do it, the more possible scenarios you can run through, and the more turns you can look ahead. Coming up with a predicted board state or two quickly gives you more time to debate between the different states, what needs to happen for you to arrive at them, what the odds of that happening are, and so on.
Naturally, the way you get faster at looking ahead is simply by practicing it. Start getting in the habit of looking ahead a turn or two when you’re in simple enough situations that it won’t make your brain explode. As you begin to do that more and more quickly, you’ll start to look ahead on more and more complex situations as a reflex; things like this tend to get easier the more you do them.
So give it a shot! You’d be surprised how much you can learn from something as simple as trying to figure out what the next turn’s board will look like.
Until next time,
Richard Feldman
Team :S
[email protected]