Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: [1]

Author Topic: Shuffle skipping probabilities  (Read 2715 times)

0 Members and 1 Guest are viewing this topic.

trivialknot

  • Jester
  • *****
  • Offline Offline
  • Posts: 757
  • Respect: +1171
    • View Profile
Shuffle skipping probabilities
« on: May 26, 2017, 01:12:14 pm »
+5

When you shuffle a deck without a card (usually because it's in play or in your hand), the card is said to skip the shuffle.  Generally you want bad cards to miss the shuffle, and good cards not to miss the shuffle, but it's unclear just how much you should go out of your way for it.

In this article I'm going to answer some really basic questions.  How likely is a card to skip a shuffle?  Are cantrips more likely to skip the shuffle?  What's better, peddler, or lab+copper?

Example: No draw

Suppose we have deck with c non-drawing cards (where c > 5).  If c = k mod 5, then k cards will skip the shuffle.  Thus the probability that any given card skips the shuffle is k/c.  As a function of c, this looks like a sawtooth function, as k cycles through 0, 1, 2, 3, 4.  It's useful to smooth out the sawtooth part, by letting k be its average value of 2.  So on average, a given card skips the shuffle with probability 2/c.

Complication: a card will never skip more than one shuffle in a row.  2/c is the average probability per shuffle in the long run, but if we know it didn't skip the previous shuffle, then the probability is 2/(c-2).

Example: One cantrip

Suppose we have a deck with non-drawing cards and 1 cantrip.  It turns out the cantrip is about 50% more likely to skip!

Let's just consider the first shuffle.  The probability of skipping is still k/c, unless k=0, in which case it's 5/c.  Taking the average over k, we get 3/c, which is 50% more than the base probability of 2/c.

Okay, but complications:  That was only the probability in the first shuffle, what about later shuffles?  Also, the presence of a cantrip may affect the probability that other cards skip the shuffle too.  To figure this out, I ran an elementary simulation with 30-34 cards and 10k shuffles.  In this table, p_cantrip is the probability that the cantrip will skip, and p_stop is the probability that any other card will skip.

cp_cantripp_stop
304.803/c4.13793/c
310.992/c0
321.984/c1.03226/c
332.8512/c2.0625/c
343.8352/c3.09091/c

If we do some averaging, the probability that the cantrip will skip is 2.9/c, and the probability of anything else skipping is 2.06/c.  But this is still nearly a 50% difference.  This appears to invalidate some of jonaskoelker's math (although I think it is a reasonable approximation).

Example: One lab

What's the general mathematical statement?  The probability of skipping is about (2+d)/c, where d is the number of cards you draw while it's in play.  So for a lab, the probability of skipping is 4/c.  The simulation bears this out, with the probability coming out to 3.8/c for 30-34 cards.

So what's better, Peddler, or Lab + Copper?  A peddler increases the value of your deck by about 1-3/c.  Lab+copper increases the value by 1-2/c, while increasing your deck size by (1-2/c)-(1-4/c) = 2/c.  As far as money density goes, it turns out Peddler is better whenever your money density is greater than 0.5.

But of course, it's a very small improvement, on the order of 1/c.  And this is only really valid, by the way, for a low density of labs.  If you have lots of labs, they statistically tend to clump together, because a turn where you play a lab is a turn where you're more likely to find other labs.  Also, they make your average hand size larger, which makes other cards skip more often too.

Strategic comments

At this point it might be obvious that I'm more interested in the math than the strategy.  But here's some strategy takeaway:

-Statistically, if you play everything, drawing cards are a lot more likely to skip the shuffle than stop cards.
-Any cards that skip the shuffle are in most cases guaranteed to make it into the next shuffle.
-If you opt not to play a card, it's kind of like instead of skipping this shuffle, it skipped the previous shuffle and got replaced with a dead card.  Generally, this is only good if you're also preventing other good cards from skipping the shuffle.

I didn't really talk about engines, but feel free to talk about them in this thread.
Logged

Loempiaverkoper

  • Scout
  • ****
  • Offline Offline
  • Posts: 43
  • Respect: +47
    • View Profile
Re: Shuffle skipping probabilities
« Reply #1 on: May 27, 2017, 02:07:57 am »
0

I don't follow you on the 1 cantrip first shuffle. It seems to me it's likely that less cards will miss the shuffle.

We were looking for the probability that any given card would miss the shuffle.
There is 10/12 chance you get to play the cantrip before the first shuffle. Now you have got to draw 11 cards, meaning only one card misses the shuffle. While in the case of no cantrips, always 2 cards miss it.
« Last Edit: May 27, 2017, 02:10:06 am by Loempiaverkoper »
Logged

trivialknot

  • Jester
  • *****
  • Offline Offline
  • Posts: 757
  • Respect: +1171
    • View Profile
Re: Shuffle skipping probabilities
« Reply #2 on: May 27, 2017, 02:45:45 am »
0

I don't follow you on the 1 cantrip first shuffle. It seems to me it's likely that less cards will miss the shuffle.

We were looking for the probability that any given card would miss the shuffle.
There is 10/12 chance you get to play the cantrip before the first shuffle. Now you have got to draw 11 cards, meaning only one card misses the shuffle. While in the case of no cantrips, always 2 cards miss it.
I'm generalizing to a deck of any size.  By "first shuffle" I don't mean the first shuffle in the game, I mean, suppose that you're given this deck, what happens in the first shuffle?
Logged

Loempiaverkoper

  • Scout
  • ****
  • Offline Offline
  • Posts: 43
  • Respect: +47
    • View Profile
Re: Shuffle skipping probabilities
« Reply #3 on: May 27, 2017, 06:42:07 am »
0

Still it would seem to me that having a cantrip would give you more control of the amount of cards that skip the shuffle rather than less, so I won't expect the average k to go up.

Could you explain the math more? Without cantrips you use k = c mod 5, but in the hand you play the cantrip you see 6 cards instead of 5, so you have to account for that.
Logged

trivialknot

  • Jester
  • *****
  • Offline Offline
  • Posts: 757
  • Respect: +1171
    • View Profile
Re: Shuffle skipping probabilities
« Reply #4 on: May 27, 2017, 10:43:47 am »
0

Still it would seem to me that having a cantrip would give you more control of the amount of cards that skip the shuffle rather than less, so I won't expect the average k to go up.

Could you explain the math more? Without cantrips you use k = c mod 5, but in the hand you play the cantrip you see 6 cards instead of 5, so you have to account for that.
The simulation assumes that you always play the cantrip.

As you can see from the simulation, the probability that a stop card will skip is mostly unaffected by the presence of a single cantrip.  The main effect is that the size of your deck is effectively c-1 instead of c.  So we're seeing (c-1 mod 5)/(c-1)
Logged

Loempiaverkoper

  • Scout
  • ****
  • Offline Offline
  • Posts: 43
  • Respect: +47
    • View Profile
Re: Shuffle skipping probabilities
« Reply #5 on: May 27, 2017, 02:34:55 pm »
0

Let's just consider the first shuffle.  The probability of skipping is still k/c, unless k=0, in which case it's 5/c. 

why do 5 cards miss the shuffle when k=0? I only see this happening when the cantrip is in your last hand before shuffle and you play it. If the cantrip was in other hands before it, it can't be that 5 cards would miss.
Logged

trivialknot

  • Jester
  • *****
  • Offline Offline
  • Posts: 757
  • Respect: +1171
    • View Profile
Re: Shuffle skipping probabilities
« Reply #6 on: May 27, 2017, 08:15:10 pm »
0

Let's just consider the first shuffle.  The probability of skipping is still k/c, unless k=0, in which case it's 5/c. 

why do 5 cards miss the shuffle when k=0? I only see this happening when the cantrip is in your last hand before shuffle and you play it. If the cantrip was in other hands before it, it can't be that 5 cards would miss.
Nobody said 5 cards must miss the shuffle.  Rather, the probability of the cantrip missing the shuffle is 5/c.  That's because there are 5 locations where the cantrip could be such that it would miss the shuffle.  Namely, the bottom 5 cards.
Logged

Loempiaverkoper

  • Scout
  • ****
  • Offline Offline
  • Posts: 43
  • Respect: +47
    • View Profile
Re: Shuffle skipping probabilities
« Reply #7 on: May 28, 2017, 03:19:43 am »
0

Oops I thought you were still talking about any given card.
Thanks I get what you are on about now.
Logged
Pages: [1]
 

Page created in 0.042 seconds with 22 queries.