Mathemagics: Onslaught Fetch Lands Revisited
Garrett Johnson
6/17/2003
There's a fable running around American pop culture about the old game show: Let's make a Deal, and it's known as the Monte Hall problem. It goes something like this. Monty gives you three doors to choose from. He tells you that behind two of the doors is something worthless, like a donkey. But behind the other door is a car. After you choose a door, Monty reveals one of the other doors, showing you the donkey, and asks you if you'd like to switch doors. Should you switch, stay where you are, or does it not matter? Most people jump to the conclusion that it doesn't matter. That now we have merely a 50% chance of being right, up from 33.3%. But they're wrong. It turns out that you should switch. It turns out that you have a 66.6% chance of getting the car if you switch, and only a 33.3% chance of getting the car if you don't. I've heard a lot of explanations for why this is, but the best, (meaning the clearest, if not the most mathematically valid,) goes like this:
1. You chances of being at the right door immediately after you choose the first time are 33.3%.
2. Monty hasn't changed that, since he can always find at least one door with a donkey behind it, no matter which door you choose. Therefore, your odds of being right in your first choice stay the same, 33.3%.
3. Since one of the other doors have been eliminated, the remaining 66.6% chance goes to the door that you haven't chosen. So you should switch, QED.
(Ed: Like most people, I thought that Monty's revealing of the donkey creates a new problem, in which there are two doors, one of which hides a car and one of which hides a donkey. This is true, but the assumption that each door has an equal probability of holding the car, simply because there are two doors, is not. How could your chances of finding the car go from 33% before to 50% after his revealing? They can't, and they don't. By showing you the donkey Monty does not create a new problem in which you have no information, as was the case when you made your first choice. He's creating a new problem in which one of the doors has an unequal probability of hiding the car, because of the relationship between the initial problem and the problem he creates by showing the donkey. Fun stuff!)
For this article, I had intended to move on from the fetch-land problem and address some of the more interesting and powerful land thinners, i.e. Krosan Verge, Krosan Tusker, and briefly, at least, Thawing Glaciers. However, the volumes of feedback I got on my first article convinced me to defer that article and put a little more work into fetch lands. A lot of people felt very strongly about this issue, and I seem to have jumped to the conclusion that fetch-lands won't work a little too fast, and I need to present more coherent data. The basic problem many have complained about is the distinction between the expectation value of the number of extra cards drawn, versus the odds of actually drawing one at various points in the game. The data I presented showed that we could expect to draw only .02 extra cards on turn 3, .07 extras on turn 6, .14 extras on turn 9, and .24 extras on turn 12, but these are merely averages, reflecting the sum of all the combinations of cards, and their commensurate odds, added together and averaged out. This does not actually tell us the chances at any point in the game that we will have drawn more cards than we should have without the fetch lands. And while one could argue that .24 extra cards on turn 12 represent a 24% chance of drawing an extra card by then, the math is far more complex. The .24 cards is a product of summing over all the probabilities for drawing extra cards, given by the formula:
In this formula, t is the total number of cards drawn, E(t) is the expected number of extra spells drawn after t draws, P(n,t) is the odds of drawing n spells from t draws, Pn(n,t) is the odds of drawing n spells from a "natural" 0/20 deck, and finally, En(t) is simple the number of spells we'd expect to draw given the 0/20 deck, which would simply be 2/3*t.
From this formula, we can see that since the sum is weighted, the probabilities on the extreme ends of the sum contribute a lot more since they're multiplied by more significant numbers. For example, at turn 6, (12 cards drawn, 8 spells expected,) we could posit a situation where P(8,12) = 50% and P(9,12) = 50%, and is zero everywhere else. This would yield an expected number of extra spells drawn of 0.5, precisely corresponding to the 50% chance of drawing an extra spell. But what if we add a 3rd term? What if we now say P(8,12) = P(9,12) = P(10,12) = 33.3%? Now our expectation is that we'll draw fully one extra spell at turn 6, but in reality the odds of drawing an extra card in only 66.6%. Obviously, these are extreme examples, but the point is that the expectation value of the number of extra spells and the odds of drawing an extra do not match up one-to-one. What we really want is not the expectation value of cards drawn, but rather the odds of drawing an extra, regardless of how many. This gives us the chances that we will benefit from the fetch lands. These odds are given by:
In this formula, B(t) is the odds of gaining a benefit from the fetch lands, P(n,t) is the odds of drawing n spells from t draws, and Pn(n,t) is those same odds given the 0/20 "true" land deck. In this equation, we simply add up all the cases where we draw extra spells, (from 2/3 * t to t,) and subtract out all the cases where we draw fewer spells. Not that in fact all these terms add, since we'd expect that P(n,t) > Pn(n,t) for n > 2/3 * t, and the opposite for n < 2/3 * t. Also not that in this formula, there is no mention of the case n = 2/3 * t. This is because this case reflects neither help nor hindrance.
All right. That's enough math for now. I must admit even I'm getting tired of it at this point. I just wanted give you all the background behind the tricks I'm using next. First, I needed to determine Pn(n,t) to give us the baseline we will subtract from. Fortunately, an additional Monte Carlo simulation is not necessary here. As I mentioned last week, for the simple case of 20 true land those odds are given by the Hyperbolic Function:
Calculating P(n,t) for the 4/16 and 8/12 cases requires a simulation, however, since there is no closed-form combinatorial math that can give us our answer.
(Ed: I'm not sure this is true, as the systems can be modeled as reasonably simple recursive functions. Any professors, grad students, or ambitious undergrads want to enlighten us?)
After running a simulation with 500K repetitions, however, I was displeased with the variation I was seeing from simulation-to-simulation, and I upped the repetitions to 2 million. The results, all three cases, superimposed on each other:
Now, since for each of the above equations we are asked to subtract the Pn() from P(), I subtract these two curves to get the divergence from the "natural" odds, which we can then sum up to get B(t), the odds of getting some sort of benefit:
These curves give us a visual idea of how we benefit from the fetch lands. If this were a truly continuous function, we'd integrate over these two curves, but since it's impossible to draw a fractional number of cards, we're only interested in the points where the curves intersect whole, nonnegative integers between 0 and t, inclusive. Summing up these curves yield the following results:
When comparing these numbers to our previous data, this makes a great deal of sense, showing us results that are roughly half of our previous expectation value. This difference is the result of the expectation value being skewed by all the cases where we draw multiple extra spells.
Finally, we need to make one more check of our data: With P(n,t), we can now recalculate E(t) a second time, and compare it to our original results. If my math is legit here, (and I think it is,) we should have estimates the agree fairly well:
As expected, we have pretty good agreement here, with the notable exception of turn 3 in the 4/16 case, but this can be attributed to the exceedingly small sample that we can glean from turn 3. The fact that there is so little variance at turn 3 makes it difficult to get enough cases where there is a difference between the 4/16 case and the 0/20 case. This makes our sample size exceedingly small at this data point. This has the effect of increasing the error, since the percent error in a randomly obtained sample of size n is given by:
This is more evidence that the sample size needed to be increased from 500,000 to 2,000,000, as it would cut our error in half.
At this point, the question is: How much pain are we willing to endure to gain a marginal increase in our odds of drawing a spell? The 4/16 case is just too marginal even to think about. Even in the 8/12 case, we only see a 7.2% chance at turn 9 of getting an extra spell of some sort, and at an average cost of 2 life. The 12th turn is marginally better at 11.2%, but at a cost of 2.5 life. If one is playing a very aggressive deck the life trade might be justifiable, but I don't believe a deck that aggressive would still be playing at turn 9. It's game would have functionally been over by turn 5, turn 6 at the latest. See, here's the problem: A deck that can be aggressive enough to sacrifice 22 life over 9 games to see one extra card draw by turn 12 may not even be around on turn 12. The ratios get worse for turn 9: 28 life over 14 games for that one card.
There is another concern as well: The assumption that your mono-colored aggro deck will always be the aggressor is not valid in this format: Sligh, the most aggressive deck in the format, and certainly the case where the purported thinning effect of fetch lands are used the most, often becomes burning bridge against UG Madness, and becomes a control deck at least half the time in the mirror. Recall the lessons about beatdown: While Flores teaught us in his canonical Dojo treatise to identify the beatdown deck in every game, Zvi reminds us in many of his own more recent articles that the identity of the beatdown deck can change many times during the game itself!
What this argument boils down to is simple: Any deck blasÃ© enough about it's life totals to pay 22 life per card can't wait so long to get it. And any deck that expects to live long enough to see the card advantage has to be more concerned with staying alive in the early game to pay the life. The deck that can take advantage of Onslaught fetch land thinning simply does not exist. Certainly not in Type II today; Perhaps not ever. Personally, I have never had a dog in the fetch-land race, but I don't believe the numbers bear out the contention that fetch-lands are worth it.
There were a couple of other questions regarding my previous article that I'd like to go over. First of all, several people have asked me to consider the effect of card drawing on these numbers. While I've not actually run any simulations, two things will happen: First, card drawing will effectively accelerate the number of turns that elapse, since for the simulation a turn is little more than a card draw and a land drop. An extra card is like a time walk to this simulation. Second, it will very slightly reduce the effectiveness of fetch lands given the accelerated turn rate. This is because it alters a fundamental rule in the simulation: That each turn we will always play a fetch land over a basic land, if we can. It's possible, (we'd have no choice on turn 4,) that we will lay a basic land, play a card drawer, and get a fetch-land in our extra cards. We would then need to play that fetch land later, reducing its effectiveness.
Another question was about more land. Many people pointed out that a 20 land deck is pretty rare nowadays, even for Sligh and White Weenie. While I agree, I felt I needed to pick a horse on the land, and 20 seemed as good as any, considering I was dealing entirely in mono-colored aggro decks. Moreover, the number just get worse for thinning if we add more land. This is because each fetch-land we activate will still cost us one life, but it would remove a smaller fraction of the total available land for each activation, (5.0% for the 20 land case, 4.2% for the 24 land case.)
The other major question I received was about providing other people with my source code. I'm afraid I can't do that, because at its core, it's not just a Monte Carlo simulator. It's a much bigger project that I've been working on for a while now, a sort of deckbuilding tool that, once it's done, will provide a lot more information that just average land draws. Since it might be something that I end up selling some day, I don't plan on giving away a product that might someday have value. Moreover, half the code doesn't even work right now. Having written it, I know how to utilize only the segments that are stable. The rest is in development. I am, however, more than willing to run simulations by requests for anyone who asks.
Which brings me to my final point: Next week I will be writing up the Krosan Verge/Krosan Tusker article, (and I may include Eternal Dragon as well, if time permits,) but after that I'm plum out of ideas. That's why I need your help. Send me a problem that you're having trouble deciding on. I'd love to run the simulation for you, and report the results.
-Garrett Johnson
6/17/2003
There's a fable running around American pop culture about the old game show: Let's make a Deal, and it's known as the Monte Hall problem. It goes something like this. Monty gives you three doors to choose from. He tells you that behind two of the doors is something worthless, like a donkey. But behind the other door is a car. After you choose a door, Monty reveals one of the other doors, showing you the donkey, and asks you if you'd like to switch doors. Should you switch, stay where you are, or does it not matter? Most people jump to the conclusion that it doesn't matter. That now we have merely a 50% chance of being right, up from 33.3%. But they're wrong. It turns out that you should switch. It turns out that you have a 66.6% chance of getting the car if you switch, and only a 33.3% chance of getting the car if you don't. I've heard a lot of explanations for why this is, but the best, (meaning the clearest, if not the most mathematically valid,) goes like this:
1. You chances of being at the right door immediately after you choose the first time are 33.3%.
2. Monty hasn't changed that, since he can always find at least one door with a donkey behind it, no matter which door you choose. Therefore, your odds of being right in your first choice stay the same, 33.3%.
3. Since one of the other doors have been eliminated, the remaining 66.6% chance goes to the door that you haven't chosen. So you should switch, QED.
(Ed: Like most people, I thought that Monty's revealing of the donkey creates a new problem, in which there are two doors, one of which hides a car and one of which hides a donkey. This is true, but the assumption that each door has an equal probability of holding the car, simply because there are two doors, is not. How could your chances of finding the car go from 33% before to 50% after his revealing? They can't, and they don't. By showing you the donkey Monty does not create a new problem in which you have no information, as was the case when you made your first choice. He's creating a new problem in which one of the doors has an unequal probability of hiding the car, because of the relationship between the initial problem and the problem he creates by showing the donkey. Fun stuff!)
For this article, I had intended to move on from the fetch-land problem and address some of the more interesting and powerful land thinners, i.e. Krosan Verge, Krosan Tusker, and briefly, at least, Thawing Glaciers. However, the volumes of feedback I got on my first article convinced me to defer that article and put a little more work into fetch lands. A lot of people felt very strongly about this issue, and I seem to have jumped to the conclusion that fetch-lands won't work a little too fast, and I need to present more coherent data. The basic problem many have complained about is the distinction between the expectation value of the number of extra cards drawn, versus the odds of actually drawing one at various points in the game. The data I presented showed that we could expect to draw only .02 extra cards on turn 3, .07 extras on turn 6, .14 extras on turn 9, and .24 extras on turn 12, but these are merely averages, reflecting the sum of all the combinations of cards, and their commensurate odds, added together and averaged out. This does not actually tell us the chances at any point in the game that we will have drawn more cards than we should have without the fetch lands. And while one could argue that .24 extra cards on turn 12 represent a 24% chance of drawing an extra card by then, the math is far more complex. The .24 cards is a product of summing over all the probabilities for drawing extra cards, given by the formula:
In this formula, t is the total number of cards drawn, E(t) is the expected number of extra spells drawn after t draws, P(n,t) is the odds of drawing n spells from t draws, Pn(n,t) is the odds of drawing n spells from a "natural" 0/20 deck, and finally, En(t) is simple the number of spells we'd expect to draw given the 0/20 deck, which would simply be 2/3*t.
From this formula, we can see that since the sum is weighted, the probabilities on the extreme ends of the sum contribute a lot more since they're multiplied by more significant numbers. For example, at turn 6, (12 cards drawn, 8 spells expected,) we could posit a situation where P(8,12) = 50% and P(9,12) = 50%, and is zero everywhere else. This would yield an expected number of extra spells drawn of 0.5, precisely corresponding to the 50% chance of drawing an extra spell. But what if we add a 3rd term? What if we now say P(8,12) = P(9,12) = P(10,12) = 33.3%? Now our expectation is that we'll draw fully one extra spell at turn 6, but in reality the odds of drawing an extra card in only 66.6%. Obviously, these are extreme examples, but the point is that the expectation value of the number of extra spells and the odds of drawing an extra do not match up one-to-one. What we really want is not the expectation value of cards drawn, but rather the odds of drawing an extra, regardless of how many. This gives us the chances that we will benefit from the fetch lands. These odds are given by:
In this formula, B(t) is the odds of gaining a benefit from the fetch lands, P(n,t) is the odds of drawing n spells from t draws, and Pn(n,t) is those same odds given the 0/20 "true" land deck. In this equation, we simply add up all the cases where we draw extra spells, (from 2/3 * t to t,) and subtract out all the cases where we draw fewer spells. Not that in fact all these terms add, since we'd expect that P(n,t) > Pn(n,t) for n > 2/3 * t, and the opposite for n < 2/3 * t. Also not that in this formula, there is no mention of the case n = 2/3 * t. This is because this case reflects neither help nor hindrance.
All right. That's enough math for now. I must admit even I'm getting tired of it at this point. I just wanted give you all the background behind the tricks I'm using next. First, I needed to determine Pn(n,t) to give us the baseline we will subtract from. Fortunately, an additional Monte Carlo simulation is not necessary here. As I mentioned last week, for the simple case of 20 true land those odds are given by the Hyperbolic Function:
Calculating P(n,t) for the 4/16 and 8/12 cases requires a simulation, however, since there is no closed-form combinatorial math that can give us our answer.
(Ed: I'm not sure this is true, as the systems can be modeled as reasonably simple recursive functions. Any professors, grad students, or ambitious undergrads want to enlighten us?)
After running a simulation with 500K repetitions, however, I was displeased with the variation I was seeing from simulation-to-simulation, and I upped the repetitions to 2 million. The results, all three cases, superimposed on each other:
Now, since for each of the above equations we are asked to subtract the Pn() from P(), I subtract these two curves to get the divergence from the "natural" odds, which we can then sum up to get B(t), the odds of getting some sort of benefit:
These curves give us a visual idea of how we benefit from the fetch lands. If this were a truly continuous function, we'd integrate over these two curves, but since it's impossible to draw a fractional number of cards, we're only interested in the points where the curves intersect whole, nonnegative integers between 0 and t, inclusive. Summing up these curves yield the following results:
Case | Odds | Expectation |
---|---|---|
Turn 3 (4) | 0.65% | 0.0022 |
Turn 6 (4) | 1.72% | 0.0298 |
Turn 9 (4) | 3.50% | 0.0634 |
Turn 12 (4) | 5.44% | 0.1121 |
Turn 3 (8) | 1.28% | 0.01907 |
Turn 6 (8) | 3.44% | 0.07314 |
Turn 9 (8) | 7.19% | 0.14383 |
Turn 12 (8) | 11.22% | 0.244665 |
When comparing these numbers to our previous data, this makes a great deal of sense, showing us results that are roughly half of our previous expectation value. This difference is the result of the expectation value being skewed by all the cases where we draw multiple extra spells.
Finally, we need to make one more check of our data: With P(n,t), we can now recalculate E(t) a second time, and compare it to our original results. If my math is legit here, (and I think it is,) we should have estimates the agree fairly well:
As expected, we have pretty good agreement here, with the notable exception of turn 3 in the 4/16 case, but this can be attributed to the exceedingly small sample that we can glean from turn 3. The fact that there is so little variance at turn 3 makes it difficult to get enough cases where there is a difference between the 4/16 case and the 0/20 case. This makes our sample size exceedingly small at this data point. This has the effect of increasing the error, since the percent error in a randomly obtained sample of size n is given by:
This is more evidence that the sample size needed to be increased from 500,000 to 2,000,000, as it would cut our error in half.
At this point, the question is: How much pain are we willing to endure to gain a marginal increase in our odds of drawing a spell? The 4/16 case is just too marginal even to think about. Even in the 8/12 case, we only see a 7.2% chance at turn 9 of getting an extra spell of some sort, and at an average cost of 2 life. The 12th turn is marginally better at 11.2%, but at a cost of 2.5 life. If one is playing a very aggressive deck the life trade might be justifiable, but I don't believe a deck that aggressive would still be playing at turn 9. It's game would have functionally been over by turn 5, turn 6 at the latest. See, here's the problem: A deck that can be aggressive enough to sacrifice 22 life over 9 games to see one extra card draw by turn 12 may not even be around on turn 12. The ratios get worse for turn 9: 28 life over 14 games for that one card.
There is another concern as well: The assumption that your mono-colored aggro deck will always be the aggressor is not valid in this format: Sligh, the most aggressive deck in the format, and certainly the case where the purported thinning effect of fetch lands are used the most, often becomes burning bridge against UG Madness, and becomes a control deck at least half the time in the mirror. Recall the lessons about beatdown: While Flores teaught us in his canonical Dojo treatise to identify the beatdown deck in every game, Zvi reminds us in many of his own more recent articles that the identity of the beatdown deck can change many times during the game itself!
What this argument boils down to is simple: Any deck blasÃ© enough about it's life totals to pay 22 life per card can't wait so long to get it. And any deck that expects to live long enough to see the card advantage has to be more concerned with staying alive in the early game to pay the life. The deck that can take advantage of Onslaught fetch land thinning simply does not exist. Certainly not in Type II today; Perhaps not ever. Personally, I have never had a dog in the fetch-land race, but I don't believe the numbers bear out the contention that fetch-lands are worth it.
There were a couple of other questions regarding my previous article that I'd like to go over. First of all, several people have asked me to consider the effect of card drawing on these numbers. While I've not actually run any simulations, two things will happen: First, card drawing will effectively accelerate the number of turns that elapse, since for the simulation a turn is little more than a card draw and a land drop. An extra card is like a time walk to this simulation. Second, it will very slightly reduce the effectiveness of fetch lands given the accelerated turn rate. This is because it alters a fundamental rule in the simulation: That each turn we will always play a fetch land over a basic land, if we can. It's possible, (we'd have no choice on turn 4,) that we will lay a basic land, play a card drawer, and get a fetch-land in our extra cards. We would then need to play that fetch land later, reducing its effectiveness.
Another question was about more land. Many people pointed out that a 20 land deck is pretty rare nowadays, even for Sligh and White Weenie. While I agree, I felt I needed to pick a horse on the land, and 20 seemed as good as any, considering I was dealing entirely in mono-colored aggro decks. Moreover, the number just get worse for thinning if we add more land. This is because each fetch-land we activate will still cost us one life, but it would remove a smaller fraction of the total available land for each activation, (5.0% for the 20 land case, 4.2% for the 24 land case.)
The other major question I received was about providing other people with my source code. I'm afraid I can't do that, because at its core, it's not just a Monte Carlo simulator. It's a much bigger project that I've been working on for a while now, a sort of deckbuilding tool that, once it's done, will provide a lot more information that just average land draws. Since it might be something that I end up selling some day, I don't plan on giving away a product that might someday have value. Moreover, half the code doesn't even work right now. Having written it, I know how to utilize only the segments that are stable. The rest is in development. I am, however, more than willing to run simulations by requests for anyone who asks.
Which brings me to my final point: Next week I will be writing up the Krosan Verge/Krosan Tusker article, (and I may include Eternal Dragon as well, if time permits,) but after that I'm plum out of ideas. That's why I need your help. Send me a problem that you're having trouble deciding on. I'd love to run the simulation for you, and report the results.
-Garrett Johnson