Guest Article: The Fallacy of Cycling

This article is written by yaron.  He is the Round 6 Champion of the BoardGameGeek Dominion League.

Suppose I have 9 cards in my draw deck: 3 Golds and 6 Victory cards.  What is the probability of my next draw being a Gold?

Well, that’s an easy one: 3/9 = 1/3.  You have a 1 in 3 chance of drawing Gold.

Now, suppose my right hand opponent played a Tribute, putting the top 2 cards of my deck into my discard pile.  What is my probability of drawing Gold now?

Still 1 in 3.  The third card from the top (which is the one you draw after being Tributed) is just as likely to be a Gold as the first one.

Doesn’t the answer depend on the specific cards discarded by the Tribute?

Sure.  But coming in, no one knows what these cards will be.  Averaging over all possible outcomes, your chance is still 1 in 3.  The Tribute didn’t help or hinder your position.

Okay.  Now suppose I played a Loan last turn, finding my first Gold and discarding it.  What are my chances of drawing Gold now?

Just like before, 1 in 3.

Wait, that can’t be true!  I’ve just discarded a Gold!

That’s true.  However, you’ve also discarded some Victory cards on the way to that Gold.  Your deck has 2 Victory cards for every Gold, so you discard an average of 2 Victory cards before discarding the Gold, leaving the proportion of Gold in your deck 1 in 3.

Okay, but that’s because I have a lot of junk.  If my deck had more Gold and less victory cards, playing the Loan would definitely be bad for my next draws, right?

Wrong.  If you had less junk, then yes, you would discard less junk on the way to your Gold.  But you would also have less junk remaining in your deck afterwards.  If 2 out of every 3 cards in your deck were Gold, then after playing the Loan, there would still be an average of 2 Gold for every 3 cards in your deck.

So the desirability of cycling has nothing to do with the quality of my deck?

Exactly.  In a good deck, you’ll cycle away some good cards, but the cards you draw in their stead will be just as good.  In a pile of Curses, you’ll cycle away a lot of junk, but the cards you end up drawing will be just as junky.  It just doesn’t matter.

As an example, let’s look at the Adventurer.  Which is a better buy, Adventurer or Gold?

The answer depends only on the Treasures in your deck.  If your average Treasure is bigger than $1.5, and you have actions to spare, then Adventurer might be better for you than Gold.

However, the answer emphatically does not depend on the amount of Curses in your deck.  If the average Treasure in your deck is worse than $1.5, then no matter how many Curses your deck has, the Adventurer is not worth it.  The Adventurer’s cycling effect has no inherent advantage in a Cursy deck.  The proportion of Curses drawn will be just the same, whether you play an Adventurer or not.

What if I track my discards, and realize that my best cards have yet to be drawn?

Sure, if you know that the one undrawn card in your deck is your only Platinum, it would make sense to skip playing the Loan.  On the other hand, if you know there’s a Silver there, but there are Platinums in your discard pile, play the Loan to skip the Silver and get at the Platinum.

Note, however, that these considerations depend on the quality of your remaining draws compared to the rest of your deck.  They have nothing to do with your overall deck quality.  There’s no general reason to avoid playing your Loan when your deck is brimming with Gold and Platinum—your Loan is no better and no worse than a Copper.

How about cycling in order to draw my new acquisitions faster?  Is that a good idea?

It is.  In the early game and mid-game, you are adding cards to your deck that are better than your existing average.  Cards that cycle your deck will make you reshuffle faster, getting your newest and best cards into your hand.  However, in the late game, most of your new acquisitions are Victory cards.  Cycling your deck becomes a bad idea at that point, because you’d rather not draw these new cards.

Again, this has nothing to do with overall deck quality.  A trimmed monster that’s buying multiple Grand Markets and Platinums each turn can benefit from cycling, because the cards bought are even better than the existing average.  On the other hand, you should try to avoid cycling when buying Estates with your pile of Gardens and Curses.  The cards you are cycling away are bad, but the new Estates are even worse.

This entry was posted in Guest Articles. Bookmark the permalink.

32 Responses to Guest Article: The Fallacy of Cycling

  1. Ryan says:

    I agree overall, but disagree with your point that you don’t want to cycle late when you’re buying victory cards. While yes, each victory card you buy brings down the average $ value of your deck, it probably took some good cards to buy that province. So when you just used two golds and a militia to buy a province, you probably do want to continue to cycle your deck to get those good cards back, even though the province has technically decreased the quality of your deck.

    • Curses says:

      Yaron would agree if those cards that attained the Victory Card were also in the discard pile. However, if you were drawing from your entire deck, your probablility would be equivalent.

    • theory says:

      I think that falls under the category of “if you are tracking your discards and know that your discard is better than your deck average”.

      • Ryan says:

        I don’t think you even need to be tracking your discards for this to matter. Presuming a no colony game (for simplicity), you’ve probably built your deck to try to get to $8 to buy a province. Unless you’re always overshooting that $8 anyway, and are trying for multiple buys, achieving $8 in your hand is a success. This is one of your (likely) better hands. The best thing you can do is cycle your deck and get those cards back up again.

        • theory says:

          Well, that’s exactly the thing. If the $8 represents the best your deck can do, then yeah, you want to cycle it. But if the $8 represents just another turn in a deck that can consistently produce $8, then there’s no benefit to cycling. For me, the latter is more common when I am consistently buying Provinces.

  2. Guy Srinivasan says:

    Something’s not right here but I can’t quite lay my finger on it. Then I ran some simulations … In a deck of 17 Estates, 1 Loan and 2 Golds if you play the Loan no matter what you’ll draw ev 0.4848 Golds per hand rather than 0.5. Up it to a hundred cards (97 Estates) and I’m getting 0.0906 Golds rather than 0.1. With 5 Loans that’s 0.0951 rather than 0.1. With a Loan and 95 Golds, 4.748 instead of 4.75.

    Do I have a bug or does something make sense here? Where’s the asymmetry?

    Okay, say our deck’s 3 cards: Loan, Gold, and Estate. And we draw just 2 cards per turn, and play our Loan whenever it’s in hand. Then there are 3 possible states at the beginning of each turn: LG in hand, LE in hand, or GE in hand, with the third in our draw deck (it can’t be in the discard since just before drawing there are always either 0 or 1 cards in our draw deck (or 3 at beginning of game), not 2). From those we get the transition matrix
    [1/3,1/3,1/3]
    [1/3,1/3,1/3]
    [1/2,1/2,0]
    which gives long-run 0.625 Golds per hand rather than 0.6666.

    What’s the simple, intuitive reason? It has something to do with shuffling, and the fact that if you get a Gold Estate hand you’re guaranteed your next draw contains a Load, but I don’t know what.

    • Tim says:

      First of all, very interesting article. There’s a reason why I can hardly beat Yaron.🙂

      Nevertheless, Guy has a point here actually. I would try to explain this intuitively.

      The starting point is that if you discard N cards randomly from your deck, the quality does not change. (Ignore reshuffling effects.)

      Now it is actually not so clear how to deduce from here to Yaron’s second argument, which is:

      when you play a Loan, the average quality does not change.

      Nevertheless, from this argument we can easily deduce that:

      if you play any number of Loans (without triggering reshuffle), the average quality of the deck does not change.

      Here I am going to show this is not true. Suppose we have only golds and estates. Playing N Loans is equivalent to discard some number of cards X with N gold in it, where the last card among the X cards must be a gold. Note that if the X cards were allowed to be in arbitrary order, this discarding effect evidently produces no change of deck quality. However, now we have the constraint that the last card has to be a gold, this favors those X cards which have higher than average number of golds in it. This implies that the actual procedure, playing any number of Loans, degrades the average value of the deck. Since this contradicts the deduced argument, Yaron’s second argument cannot be true.

      • topherbear says:

        I think you’re wrong about a cursey deck and an adventurer. An adventurer’s value increases in a cursey deck because you’re guaranteed to draw coins with it. Its value is not from cycling, but from finding the gold amidst the dross. This is less important in a lean deck than in the cursey deck. It helps me pull the good stuff from the deck on any given turn, which is harder without the adventurer.

        Say I have a hand of 2 curses, 2 silver, and an adventurer. The adventurer guarantees that I will find two more treasure amidst a wealth of curses. Definitely a higher value, IMO.

        • theory says:

          Adventurer is worth it in your scenario because your Treasures are worth more than $1.5 on average, not because of the Curses.

        • rrenaud says:

          Tthe adventurer only guarantees you find money if the adventurer is in your hand. If you the adventurer were instead a gold, modulo the cycling effect, it’s as though the adventurer searched and found a copper and a silver. If the only money in your deck is coppers, regardless of how many curses you have, the adventurer will only pull $2.

          Adventurer might be relatively better in a curse-filled deck because this mitigates one of its disadvantages compared to gold, it’s less likely to be double drawn with other actions. And it might be that in a curse filled game, you want variance, so you are willing to trade a definite $3 for a chance at $4 or $5 at the cost of a possible $2.

          But how much money that adventurer eventually brings in* is going to be the average value of the money in your deck. If the money in your deck is mostly coppers and the rest silvers, the adventurer is a bad buy compared to gold, regardless of how many curses are in it.

          *There is the exception having all your money in hand, and none in the deck/discard.
          *Likewise, you could manipulate your deck with a card like scout.

          • Personman says:

            There actually is a potential reason for Adventurer to be better than Gold in a curse-heavy deck: it finds *itself* again faster. Sure, if you turn up a copper and a silver, it’s the same value as having just bought a gold, and your remaining draw pile hasn’t gotten worse or better. BUT, unless you trigger a shuffle with the Adventurer, there is a better chance in a curse-heavy deck that you get rid of a turns’ worth of crap that you would have had to deal with before drawing your Gold again.

      • Yaron says:

        Tim, I’m not sure I’m following your reasoning.

        In a deck where each card has an equal chance of being a Gold and an Estate, if you play 100 Loans, you will discard exactly 100 Golds, and an average of 100 Estates. The last card discarded is a Gold, but it’s still one of the 100.

        • rrenaud says:

          The “end process at money” introduces a bias towards having seen more than the expected amount of money. The simplest way to see this is to consider a small deck. You have 1 loan in hand, 1 gold, and 1 vp. According to your original argument, you should discard one vp for every gold, but actually..

          If the deck is vp, gold, you discard one vp, but if the deck is gold, vp, you don’t discard any vp. The hunt for money process introduces a bias in the distribution. Overall then, you discard .5 * 1 + .5 * 0 = .5 vp per gold.

          • Yaron says:

            Ah, I see what you mean. It’s the same effect I mentioned in my replay to Guy below, we’re just giving it a different name.

            The reason I’m not comfortable attributing it to “end process at money”, is because it’s dependent on the finiteness of the deck.

            To see this, suppose instead of drawing cards from a deck, you flipped a coin with “Gold” on one face, and “Estate” on the other. If you flip it repeatedly until you get “Gold”, how many times can you expect to get “Estate” before that?

            Here the answer is 1, not 0.5, even though the process ends with “Gold”. The difference between this example and yours is having a finite deck to draw from.

            Anyway, I see now that we’re saying the same thing, just emphasizing different parts of the explanation.

          • Morphenius says:

            You make a great point! I think another way to see this is that if you discard N cards at random from a deck of Estates and Gold, it’s possible for you to discard N estates. But that can never happen with a Loan, so there’s a slight bias toward discarding more Golds when using the Loan. I think this bias gets stronger the larger the Estate:Gold ratio is. (The Loan moves the probability of getting N Estates to that of getting N-1 Estates and 1 Gold, so the bias corresponds in strength to the likelihood of being able to draw N Estates in a row. So in a deck with 8 Estates, 1 Loan, and 1 Gold, the Loan should – I think – make your situation significantly worse each time. But if you have 8 Gold, 1 Estate, and 1 Loan, the probability of getting that Estate as your next card always pretty small, so the Loan only hurts you very slightly.)

            And sorry to come into this discussion so late. I just now found this blog. (Great stuff!)

        • Tim says:

          Hi Yaron,

          Now I think I agree with your argument in the infinite deck limit, although I cannot really understand it intuitively. My argument is somehow flawed actually, but let me just rephrase it like this:

          Suppose you just flip some number of cards. If the last one is a gold then you discard all of them. If the last one is not a gold then you retry. My argument is to say that this procedure in average would discard more gold than the average density times the number of cards, as among the cards you draw, the more gold there is, the more likely the last card would be a gold.

          Up to here the argument is okay I think, but it seems that this sampling is actually different from playing any number of loans.

        • George Locke says:

          Playing 100 loans, you will discard exactly 100 Golds, but the average number of estates discarded is certainly more than zero. The average number of estates drawn will be 100 minus the average number of consecutive estates on the bottom of the deck, which will be… 1.951. (The probability of a run of length X at the edge is Product((100-i)/(200-i)) where i runs from 0 to X-1. Average length is the sum of (X * P(X)) from X=1 to 100.)

    • Yaron says:

      Guy, thanks for this challenging criticism. I think I can give a simple explanation for the effect you describe (or rather, two explanations).

      1. A Loan can cause a Gold, an Estate, or another Loan to be skipped, but it will never skip itself. So, by playing Loans, you increase the incidence of Loans compared to other cards. This is demonstrated by your ingenious 3-card thought experiment: the Loan will discard the Gold and the Estate equally, but nothing will ever cause the discard of the Loan. This increases the incidence of the Loan from 2/3 to 3/4, while reducing the other two cards form 2/3 to 5/8.

      This suggests the following modification to my analysis: playing a cycler will cause you to re-draw the cycler sooner. This can be nice if the cycler in question is an Adventurer, but not as good with something like a late game Loan.

      This explanation, however, is inadequate. Following your example, I ran some simulations, and it seems that in “real” decks, the increased incidence of Loans comes mainly at the expense Golds, not Estates (can you corroborate this with your own results?). So the Symmetry between Golds and Estates does break, and that needs explaining.

      2. The analysis in the OP implicitly assumed an infinite deck, where each card has a certain probability of being a Gold, independently of each other card. In reality (and in our simulations), we are dealing with finite decks, that have a finite number of Golds in them. Each Gold drawn or skipped reduces the incidence of Gold further in the deck, and each Estate does the opposite. This turns out to be relevant.

      Consider a big deck full of Estates, with N Golds inserted in N random spots. If I cut the deck in a random position, and start counting Estates to the nearest Gold, How much of the deck will I discard before getting to it?

      The “infinite deck” assumption suggests an answer of 1/N. With N Golds in the deck, it predicts I will see 1/N of the deck before getting to the next Gold. However, in a finite deck, I will only see (on average) 1/(N+1) of the deck. This means that the proportion of Estates discarded is slightly lower than their proportion in the deck, and the proportion of Golds is slightly Higher.

      (Interestingly, this result holds whether I shuffle the deck after each pass, or just cycle it in the same order (effectively treating it as “circle” of cards with no starting and end points). So it’s not the shuffle, per se, that is to blame.)

      The difference between 1/N and 1/(N+1) is small for large values of N. This means that the effect can be ignored in decks with many treasures (as demonstrated by your 95-Gold simulation). However, in a deck with just 2-3 pieces of Gold/Platinum, and no other treasure, the effect can be significant.

      • Tim says:

        Hi Yaron,

        Can you elaborate on how you derive the 1/N and 1/(N+1) respectively? That is very interesting.

        Also, what I was trying to say above actually is not coming from the finiteness of the deck. My argument as I replied above is quite independent of the size of the deck.

        It just seems unintuitive for me that the number of estates discarded is just the average number of estates per gold, even in the infinite deck limit. Do you have an intuitive way to explain that? (I guess that is what a Poisson process is, but …)

        • Guy Srinivasan says:

          Tim,

          The way I’ve always internalized the “draw until you see a Gold” is “have a boy”. If everyone has kids until they have their first boy, will there be more girls or boys born? Answer: it’s still 50%, of course, because no matter what at each stage of the game you’ve got a coinflip at each.

          I don’t know why I find this formulation more intuitive, now that I look at it.🙂

          • guided says:

            The “have a boy” example is not intuitive to me, and in fact I had to do the grungy math (including deriving the infinite sum of (n-1)/2^n) to convince myself the answer is still 50%😉

        • Ingix says:

          OK, some more math from a late comer:

          The error in yaron’s article is the fact that he choose to apply the mathematics of the Bernoulli process, which assumes that the chance of flipping over a treasure/non-treasure while executing Loan does not change over time. That however is not true.

          Let’s say you have a hand containing Loan. Your remaining deck contains 10 treasure and 10 other cards. If you play Loan, the probability of the first card to be a treasure is of course 10/20=1/2. If it isn’t a treasure card, you turn over the next card. But now (taking into consideration that the first card wasn’t a treasure card), the probability of it being a treasure is 10/19, slightly more than one half. If it isn’t a treasure you turn over the next card,a.s.o. The probability will change in each step, which makes yaron’s model incorrect.

          Generally,if you have N cards in your deck, containing T treasure cards, yaron’s model predicts that you turn on average N/T cards over during Loan (including the final treasure card), see http://en.wikipedia.org/wiki/Geometric_distribution for details.

          This supports his thesis that Loan doesn’t change how many treasure you will draw later: If say N=9 and T=3 (his initial example), then you turn over and discard on average 3 cards, including the final treasure (Gold in his example). That means you still have on average 6 cards including 2 Gold left in your deck, the same density as before.

          However, as said above, that isn’t true. If you do the ugly math, it turns out that the average number of cards you turn over with Loan is (N+1)/(T+1). Since normally N > T, this value is lower than N/T, so you skip over less than the ‘fair share’ of non-treasure cards. As can bee seen, the difference between those two values is biggest if N and T are small, that’s why the biggest effects where seen in simulations with N=3.

          Taking into account that what I called T is called N by yaron, that explains his results: His initial assumption (infinite deck, so N and T are so big that N/T = (N+1)/(T+1)) says you turn turn over N/T cards, so 1/T of the deck (1/N in his Nomenclature). His simulations suggest that in a finite deck the value is is 1/(T+1) of the deck (N/(T+1) cards turned over with Loan), while the calculation shows it’s (N+1)/(T+1).

          I’d like to give a nice ans simple explanation of this (N+1)/(T+1) result, but I can’t. I had to go through explicitly calculating the probabilities that you turn over exactly i cards (1 <= i <= N-T+1) with Loan (which turns out to be Choose (N-i, T-1)/Choose (N,T)) and then do the explicit calculation of the expected value.

          • DG says:

            The simplest explanation is probably to look at ‘slots’ between two treasure cards. In each slot there can be any number of the other cards from the deck, including none. All the other cards are included in these slots. How many slots are there? Well there is one slot before each treasure card and one slot after the last treasure card. This divides the other cards between T+1 slots, giving the N+1/T+1 result with a little algebra.

      • Guy Srinivasan says:

        Yaron,

        I noticed in the 3-card example that Loan’s effect is the same as “mill one”. After some more simulations, I found the following surprising deck: 2 Mills, 2 Golds, 8 Estates, draw 3 cards per turn. This appears to draw about 0.6025 Gold per hand rather than 0.6. So I think these may be unintuitive artifacts of small decks and finite possible states rather than stemming from a nice general principle.

        (I didn’t see that the Loans came at the expense of Gold rather than Estates, with a few tries all at draw 5, some Loans, some Gold, 7 Coppers, and 3 Estates… sometimes it seemed a bit more, but it didn’t feel significant. I didn’t do a bunch of tests to check though.)

    • guided says:

      Do note that the differing incidence of Golds you observe between playing your Loans and not playing them is much smaller than the $1 provided by the Loan. Maybe it’s already obvious, but I would say–barring situations where you are near-certain the Loan’s effect will actually hurt you, e.g. 1 card left and you know it’s a Plat, or you already have big treasures in hand and the Loan will cause a shuffle–you always want to play Loan if the $1 is useful to you.

    • George Locke says:

      There is a simple, intuitive explanation for this: loan preferentially removes treasure from your deck. (I’m just talking about the dig and discard part, not the trashing.)

      If you dig through and discard a fixed number of cards, then there’s no change to the quality of your deck: you’re not biasing what remains in your deck at all. If you dig until you find a treasure, then there’s slightly less treasure in your deck afterward: you are biasing your search toward finding treasure, so you expect to have less treasure in your deck afterwards.

      It’s really easy to see this if you think of a deck with a bunch of junk and one treasure remaining in it. If you play the loan, you’re going to dig through the junk until you find the treasure. Whatever remains in your deck is pure junk.

      However, your simulations show that the size of this effect is small (it’s not a very intensive biased search), and overall Yaron has the right idea.

  3. guided says:

    This article also hints at one of the reasons I believe Minion to be overpowered: With few exceptions, it is not possible to catch up to a Minion deck by buying green cards. Once you start buying them, an opposing Minion deck causes rapid cycling, putting the purchased VP cards in your hand very quickly.

    Early on (before most Minion decks are even functional yet), the Minion’s attack is largely ineffective: quickly cycling your deck while you’re buying good cards at least partially offsets the hand size reduction. But once you begin purchasing green cards, Minion’s attack becomes devastating.

    • Keith Grant says:

      Yes, but if your opponent is using a Minion deck, his is cycling just as quickly as yours, if not faster (considering he’s likely performing multiple redraws). He may get to selectively use the good cards as he goes, but his deck will come to a halt as soon as he can’t maintain at least one Minion in every hand plus an action-based coin source in most of those same hands.

      • guided says:

        Two things:

        1. The Minion player has a choice of whether to cycle, and may play other actions from the hand before doing so (Festival, Peddler, any number of +$ actions given another action, other cyclers like Village and Laboratory).

        2. Even without much deck trimming, 6 or 7 Minions is enough to get 4 Provinces quickly before the deck begins to really choke.

        So, don’t let your opponents get 6 or 7 Minions, right? The best defense against a Minion deck is usually a Minion deck. My objection is that most of the time there is simply no other adequate defense, and a Minion deck is a boring, uncreative strategy that requires little thought.

        • George Locke says:

          While I am with you in disliking Minion games, I disagree that Minion decks are always boring. When there’s a village or two available, adding terminals to a Minion deck is pretty fun IMO.

    • guided says:

      My specific suggestion for what to do about the problem as I see it is to nerf the attack. Given its self-synergy Minion would be arguably worth $5 with no attack attached, but I wouldn’t go that far. Here’s one idea:

      +1 Action
      Choose one: +$2; or discard your hand, +4 cards, and each other player with at least 5 cards in hand either discards his hand and draws 4 cards or discards down to 3 cards in his hand.

      It’s probably not underpowered if the opponents must only discard down to 4, but I don’t think it’s especially overpowered even if they have to discard down to 3.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s