2
$\begingroup$

Suppose there is a single player card game in which there is a deck of $n$ cards. A card is either red, green or blank. Initially, the deck consists of $r_0$ red, $g_0$ green and $b_0$ blank cards such that $r_0+g_0+b_0 = n$. All cards initially are put into a draw pile. If variable numbers are difficult, we may assume $n=20,r_0=9,g_0=1,b_0=10$.

Each turn, the player draws cards from his draw pile until the number of drawn red cards is equal to the number of drawn green cards plus 3 (or until there is nothing left to draw). For instance, he may draw RRR or RGGRRRR or BGRBRRBBR. Each drawn card, regardless of its color, gains 1 point. The goal of the game is to score many points.

After each turn, the drawn cards are put to the side into a secondary pile. Whenever the draw pile is exhausted but the secondary pile is not empty, the secondary pile gets shuffled and put into the draw pile, such that drawing may continue. In this fashion, the deck gets recycled deterministically. (This is also how it works in the card game Dominion.)

Just before putting the drawn cards in the secondary pile, the player may, from the cards he had drawn, either pick a red card and color it blank, or a blank card and color it green. This means the cards slowly improve over time, and it may eventually be possible to draw the whole deck in single turn if enough green (or few enough red) cards exist.

The game ends after $n$ turns. The only choice the player has is his preference in coloring reds vs. blanks. I wonder about three questions:

  1. Which strategy should he follow to maximize the score?
  2. Do different strategies offer different variance?
  3. Do they depend on the initial color distribution?
$\endgroup$
  • $\begingroup$ I'm not sure how to tag this, please feel free to add tags. $\endgroup$ – mafu Dec 24 '18 at 3:06
  • $\begingroup$ "... until the number of drawn red cards is equal to ...". What happens if this never occurs? $\endgroup$ – Robert Israel Dec 24 '18 at 3:31
  • $\begingroup$ @RobertIsrael Then the whole draw pile (and then the secondary pile, if exists) gets drawn in a single turn, i.e. the whole deck is drawn. I've added this in the question. $\endgroup$ – mafu Dec 24 '18 at 3:33
  • $\begingroup$ Still trying to prove that red→blank is always preferable. Idea #1: R→B is more helpful than B→G if and only if RG→BB is helpful (which seems plausible). Idea #2: Since sampling w/o replacement makes analysis so difficult, imagine you have a nearly infinite deck of only R/G cards. Then the problem is gambler's ruin and the expected points are $S/(r-g)$ where $S=3$ is the number of "strikes" allowed, and $r,g$ are the (nearly constant) fraction of red and green cards in the deck. #3 Consider the effect of transforming a random card on the run length of each deck permutation separately. $\endgroup$ – user326210 Mar 3 at 8:07
1
$\begingroup$

I suspect removing red first (by converting red to blanks) might be the best strategy. First of all, if you have fewer than three red cards, your expected number of points is equal to the total number of cards. (And if you don't, your expected number of points is always a little less, no matter how many green cards you have.) So reducing your number of reds seems like the best long-term goal.

Second, I've tabulated your specific example (r=9, g=1, b=10) and it looks like reducing your number of reds is also locally the best goal (i.e. at any given round, you get a better effect by lowering your number of reds than increasing your number of greens).

enter image description here

This image shows the expected number of cards drawn when playing a round with a certain number of reds, a certain number of greens, and enough blanks to make the total number of cards equal to 20. After each round, you have the option to convert a red card into a blank one (moving down) or convert a blank card into a green one (moving rightward). An optimal series of rounds starting from (r=9, g=1, b=10) is shown in blue. The ideal strategy is to reduce the number of reds to less than 3. After that, the expected number of cards is maximal and it doesn't matter how you move.

I note that in general, moving downward seems to be the ideal local choice. I suspect it is also the correct global choice, i.e. that moving downward always improves your expected value more than moving rightward.


Edit: I used a Python program to compute the expected number of draws.

seen = {}
def expected_draws(reds, greens, blanks, strikes=3) :
    global seen
    if seen.get((reds, greens, blanks, strikes)) :
        return seen.get((reds, greens, blanks, strikes))

    if strikes == 0 or reds < 0 or greens < 0 or blanks < 0 or (not reds and not greens and not blanks):
        return 0


    n = float(reds + greens + blanks)
    ret = 0
    ret += (reds/n) * (1 + expected_draws(reds-1, greens, blanks, strikes-1))
    ret += (blanks/n) * (1 + expected_draws(reds, greens, blanks-1, strikes))
    ret += (greens/n) * (1 + expected_draws(reds, greens-1, blanks, strikes+1))

    seen[(reds, greens, blanks, strikes)] = ret
    return ret
$\endgroup$
  • $\begingroup$ Thank you, well explained and I believe your reasoning is right. How did you calculate the expected number of draws? $\endgroup$ – mafu Feb 27 at 12:40
  • $\begingroup$ @mafu Thanks! I used a computer program to calculate the expected number of draws over all possible card arrangements; see above. $\endgroup$ – user326210 Feb 27 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.