Csdrhrt

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?

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).

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