"The Theory and Design of Magic: The Gathering" Class Page

Two weeks ago, I wrote about search in a search tree. The idea was that a game (like Magic) can be broken up into a series of positions, and a good way to determine the best strategy is to evaluate all of these positions and find a path that gets you to a winning state, even when your opponent makes their best move as well. I left a few holes in that article, including how one turns the evaluation function into rules about what to do and what other shortcuts one can find in searching over this very large tree. So let’s finish that.

I briefly mentioned minimax at the end of the last article, and that’s where I’m going to start. Minimax is a strategy for evaluating these trees that should be fairly intuitive. How do players usually make decisions? Based on which outcomes are mostly likely to allow you to win. When you can look at the entire depth of a tree from your current position (as in, you can see every possible way that you win or lose), then you’re trying to reach one of those winning states. To have that happen, you probably need to make a choice on that second to last position to win. But you can also assume there that your opponent is going to make a choice one position before that that tries the most to keep you from winning. What this means is that you can guess at how a game is going to go, and how good a position is by propagating the alternating best and worst positions for you.

Let’s make that more concrete. You are at 2 life, have 2 Ashenmoor Gougers and a summoning sicknessed mogg fanatic in play before your combat step and no cards in hand.  Your opponent is tapped out with a foul imp untapped, 1 foul imp tapped, no cards in hand, and is at 5 life*. What do you do?

It should be fairly obvious that you swing with both gougers and then pop the fanatic for the kill. So let’s see how you came to that.

Your current position is listed above and you’re in your declare attackers step. Your choices are attack with 0, 1, or 2 gougers, each of which represents a different branch from your current position. If you attack with 0 gougers, nothing happens. The next major choice (I cheat a lot since magic has tons of intermediary positions for phases changes and such) is your opponent’s attack step. We assume your opponent is rational and makes his best move, which is to kill you. Technically, he could’ve done nothing during his attack step, but we won’t count on that. So you lose. We can propagate losing up a level to say that not attacking results in you losing.

The same applies for attacking with 1 gouger. You can do that, so the next position to evaluate is how your opponent blocks. He can either block with his imp, or not. Since he’s rational, he sees the lookahead 1 move to where you pop your fanatic and determines that the result of not blocking is losing, and blocking is winning. So he should choose to block, so this position for you can be generalized as a loss.

But if you attack with both, all moves for him result in losing. Thus, that can be propagated to say that your current position is a winning on because the best outcome out of all the possible next positions is a win.

So that’s minimax in its complete form. As I mentioned in the previous post, though, it’s often unfeasible to enumerate the entire tree to the end of the game. Instead, one might look maybe 5 moves ahead and consider all of those possibilities. Since these don’t have definite win/loss states, we can instead use the evaluation function to give them numerical values. We can using the same propagation method to assign the values for positions 4 moves ahead by considering the values of the 5-ahead states that it’s linked to. We can continue to work backwards until we’ve figured out the values for the next move, then pick the best one.

Even so, this is slow. So here’s where alpha-beta pruning comes in. Alpha-beta pruning applies a heuristic to minimax to avoid looking at entire trees. The basic idea here is that we don’t need to consider entire subtrees (all of the positions following a given position) if we know that that subtree can be skipped. From any position, you’re basically doing a lookahead 2 positions to see if you’re in a better spot after your opponent makes their choice. Since we can find maximums and minimums along the way, certain subtrees don’t matter as they’re already less optimal. That was ambiguous; let’s take a trivial example.

Let’s say your opponent has a prodigal pyromancer in play but with summoning sickness. It’s your turn, you have 1 life, and you know your opponent has a goblin piker on the top of their library because you excommunicated it with no cards in hand. You have a lightning bolt and goblin piker in hand with only enough mana for one of the spells, with your opponent at 6 life. From this position, you have 4 choices: bolt the pyromancer, bolt your opponent, make your opponent discard a card, or do nothing. So we can consider these each as a different path down the search tree.

The first is to bolt the pyromancer. If you do this, your opponent’s board is clean. Next, it’s your opponent’s move. They’re only options are to either play or not play their piker. If they play it, your evaluation function puts it at -10, while if they don’t play it, you’re at -5. Since your opponent is trying to minimize your evaluation function, they will play, so the action of bolting the pyromancer has a net value of -10.

The next is to bolt your opponent. If you do this, your opponent is now at 3. On their turn, they can poke with the pyromancer or not, play the piker or not. If they poke you, you die, resulting in an evaluation of -1000. Here’s where alpha-beta pruning comes in. At this point, you know that the action of bolting the pyromancer results in a worst case of -10. Bolting your opponent results in at least a worst case of -1000. There’s a chance that other actions your opponent will make will be worse (probably not), but that doesn’t matter because if you bolt your opponent, one of your opponent’s action is worse than the worst case of another action. So you don’t need to worry about considering the cases where they play the piker and so forth. This is the pruning action of not considering this sub-tree.

This example is a little trivial, but it’s hopefully very clear. Alpha-beta pruning can be used at multiple levels. For example, the position we discussed above might be 3 levels deep in another tree rooted at what you’re actual position is, and the result of that will propagate into a larger situation.

Hopefully, this all seems intuitive. Indeed, we as humans actually prune a lot more deeply than this; in a game, it would never have crossed my mind to not bolt the pyromancer, but those are other heuristics. Maybe that’ll come up in a future post. In the mean time, you can google around for alpha-beta pruning and get more rigorous explanations of how it works and why it’s actually called alpha-beta pruning.

*You’ll note I cheated majorly and made sure that no one has any tricks because minimax, in its most naive form, assumes perfect information. Maybe I’ll deal with this later

Just this morning, I figured I should pick up the starcitygames feed to make sure that I was seeking more important articles. That was a great decision, because I already have an article to write about.

In my last post, I was talking about how a Magic game can be formalized into a series of positions, each with its own set of values representing the entirety of the game. We can take all these positions and put them into a search tree, where each position is linked to others depending on what actions can lead from one to another. With this, we can now talk a little more formally about how search through that works (if you’re trying to follow in the original dailymtg article, we’re still in first section, “Basic Concept”).

So the search algorithm that a computer would use on a search tree like this would be to find the best (ambiguity in defining best because I’ll address it later) path of transitions between positions that lead from the current position to a winning position. All that really means is that the computer’s algorithm for winning is to determine each step it needs to make that gives it the best chance of winning from where it is now. That doesn’t sound nearly as nerdy.

Because that’s exactly what we as humans do, and Gavin Verhey just posted 2 articles* on starcitygames discussing that exact topic. Basically, he says that magic is a series of “decision points,” and at each, you have new choices and decisions to make and you can make the right decision by looking ahead on that road and seeing what options are there. This shouldn’t sound surprising; this is both intuitive, and very similar to what Patrick Buckland had to say in the dailymtg article.

I guess the real trick here is determining which choice is the best and doing that relatively quickly. There are obviously tradeoffs between these two goals, but I’ll see if I can walk through the intuition for how this is done step by step.

So let’s temporarily assume that we have infinite time. You’re, say, trying to figure out whether you should chump block a shambling remains with a mogg fanatic now, or wait and hope that you don’t die before you can use the mogg fanatic more effectively when you can deal 1 more point of damage to the shambling remains. Since we have infinite time, we can just see exactly where both of these decisions would lead. Even though the trees below both are still huge, they’re finite, so it can be done in infinite time (maybe think 5 monkeys with typewriters and infinite time writing the entire works of shakespeare?). This way, you can determine which is better by, say, taking the ratio of wins versus losses in each sub-tree and picking the more favorable one. So if blocking results in 1 million wins to 500,000 losses and not blocking is 2 million wins to 1.9 million losses, let the fanatic die now.

So your first instinct here is that just taking the ratio isn’t a good way to determine which path is better. Certain paths are more likely (have a greater probability) of happening. Which is true. And maybe not all of those options are equal. In that case, maybe we can weight each outcome by the probability that it would occur. But in the end, it seems like our best method is to somehow quantify (probably numerically, since this is going to be a computer algorithm) the value of various paths and pick the option that has the better summed up value in its sub-tree.

Unfortunately, we don’t have infinite time. Because our finite time is probably significantly less than the size of the tree, we can only look a few decisions and positions ahead (perhaps even as few as 1). In this case, we take shortcuts, or heuristics. One of these is to evaluate the goodness of any position and compare those. We can do that using an evaluation function, which is just a fancy word for taking a bunch of important factors, weighing them, and getting an end value. For example, our 2 choices may result in something like:

2 * 1 (for having the mogg fanatic) + .1 * 16 (being at 16 life) + .1 * 1 (for having just dealt 1 dmg to your opponent with the fanatic’s ability) + …other stuff = 5

2 * 0 (no mogg fanatic) + .1 * 20 (20 life) + .1 * 0 (didn’t pop the fanatic) + …other stuff = something less than 5

(Ignore the 2 most obvious faults that popping the fanatic is another decision and that there isn’t a linear value to life)

So it seems like in the position immediately resulting from blocking or not blocking, it’s more valuable to block. This, however, is obviously short-sighted. Maybe, your opponent can immediately do something else (like, say, play a figure of destiny that you now no longer have a mogg fanatic to kill before it pumps). So what you really want to do is look as far as you can in the future and evaluate that position, assuming that your opponent made intelligent decisions all along the way. What actually ends up happening is that you need to alternately need to look through states where your evaluation function is maximized (for when you made the best choice) and then a state where your evaluation function is minimized (for when your opponent made a choice and tried to screw you). This is a rule in game theory called “minimax”  where you’re trying to maximize your own evaluation function in a game with some adversary.

These are getting really long. Anyways, I’ll continue to talk more about this in another post. In that, hopefully I’ll finally get to talking about alpha-beta pruning and more exciting, AI-y sorts of things.

* I should make a couple comments about these articles. 1) I honestly thought they were kind of dumb, but clearly, I appreciated them enough to link to them. In some sense, he’s doing exactly what I’m doing, and taking a more complex idea and explaining it simply. So maybe I should like them more? 2) Decision-point theory, I’m pretty sure, is a term he came up with. I’ve never heard of it before, and it doesn’t really mean anything. It can either be part of game theory or ai, but it definitely isn’t legit on its own. 3) The best point I thought he made was that pros often play complex decks that require a lot of decisions, and good playskill often shows that they choose options that give them more options down the road. This actually deals with another part of search algorithms called “constraint-satisfaction problems”. In that, “forward checking” is something of a way of doing lookahead, and “least-constraining variable” is a heuristic for making choices. But that’s all another post, if it comes up again.