In this game, you have an infinite deck of cards. Each time you draw a card it's value is a uniformly distributed integer on the interval [0,C].
The game lasts for R rounds.
You start the game by drawing a card and adding its value to your running total.
At each round you have two choices:
1) draw another card from the deck and add its value to your total
2) add the value of the highest card previously drawn to your total
What strategy, based on the constraints R and C, gives you the optimal total at
the end of the R rounds?
At each round (after round 1) you have a decision: draw or use your previous high card. What you have drawn already has no impact on the decision. All that matters is how many rounds are remaining and what your high card is.
In non-linear programming, this is what is called a stagecoach problem. It is solved round-by-round, working backwards from the last round. And is well suited to a computer or a spreadsheet.
Instead of trying to work out the general case, let me work out an example.
Let R = 5, C = 3
Let Draw(h,r) = Optimal Action in round r if high card = h
Let G(h,r) = Expected gain in round r and future counds, if h = H(r) and optimal strategy is used
ROUND 5)
If your high card is 0 or 1, draw for an expected gain of C/2 = 3/2.
If your high card is 2 or 3, just count your high card.
h Draw(h,5) G(h,5)
-- --------- ------
0 Yes 3/2
1 Yes 3/2
2 No 2
3 No 3
ROUND 4)
If your high card is 0 or 1, draw. (If you would draw in round n with a card, you would also draw with that high card in any earlier round.)
G(0,4) = g(1,4) = 1/4(0 + g(0,5)) + 1/4(1 + g(1,5)) + 1/4(2 + g(2,5)) + 1/4(3 + g(3,5) = 1/4(0+3/2) + 1/4(1+3/2) + 1/4(2+2)+ 1/4(3+3) = 7/2
If your high card is 3, just count the high card
G(3,4) = 3 + g(3,5) = 6
What about if your high card is 2?
If you just count the high card, you get 2 + G(2,5) = 4
If you draw, your expected gain =
1/4(0 + g(2,5)) + 1/4(1 + g(2,5)) + 1/4(2 + g(2,5)) + 1/4(3 + g(3,5) = 1/4(0+2) + 1/4(1+2) + 1/4(2+2)+ 1/4(3+3) = 15/4.
This is less than 4, so Draw(2,5) = No
In summary,
h Draw(h,4) G(h,4)
-- --------- ------
0 Yes 7/2
1 Yes 7/2
2 No 4
3 No 6
ROUND 3)
If your high card is 0 or 1, draw.
G(0,3) = G(1,3) = 1/4(0 + g(0,4)) + 1/4(1 + g(1,4)) + 1/4(2 + g(2,4)) + 1/4(3 + g(3,4)) = 1/4(0+7/2) + 1/4(1+7/2) + 1/4(2+4)+ 1/4(3+6) = 23/4
If your high card is 3, just count the high card
G(3,3) = 3 + g(3,5) = 9
What about if your high card is 2?
If you just count the high card, you get 2 + G(2,4) = 2 + 4 = 6
If you draw, your expected gain =
1/4(0 + g(2,4)) + 1/4(1 + g(2,4)) + 1/4(2 + g(2,4)) + 1/4(3 + g(3,4)) = 1/4(0+4) + 1/4(1+4) + 1/4(2+4)+ 1/4(3+6) = 6
You might as well just count the high card
In summary,
h Draw(h,3) G(h,3)
-- --------- ------
0 Yes 23/4
1 Yes 23/4
2 Optional 6
3 No 9
ROUND 2)
If your high card is 0 or 1, draw.
G(0,2) = G(1,2) = 1/4(0 + g(0,3)) + 1/4(1 + g(1,3)) + 1/4(2 + g(2,3)) + 1/4(3 + g(3,3)) = 1/4(0+23/4) + 1/4(1+23/4) + 1/4(2+6)+ 1/4(3+9) = 65/8
If your high card is 3, just count the high card
G(3,2) = 3 + g(3,5) = 12
What about if your high card is 2?
If you just count the high card, you get 2 + G(2,3) = 2 + 6 = 8
If you draw, your expected gain =
1/4(0 + g(2,3)) + 1/4(1 + g(2,3)) + 1/4(2 + g(2,3)) + 1/4(3 + g(3,3)) = 1/4(0+6) + 1/4(1+6) + 1/4(2+6)+ 1/4(3+9) = 33/4
You expect to do better by drawing
In summary,
h Draw(h,2) G(h,2)
-- --------- ------
0 Yes 65/8
1 Yes 65/8
2 Yes 66/8
3 No 12
ROUND 1)
You have to draw
Expected value of optimal strategy = 1/4(0 + g(0,2)) + 1/4(1 + g(1,2)) + 1/4(2 + g(2,2)) + 1/4(3 + g(3,2)) =
1/4(0 + 1 + 2 + 3 + 65/8 + 65/8 + 66/8 + 12) = 85/8 (if I haven't made math mistakes)
OPTIMAL STRATEGY
----------------
I see that I could have simplified this analysis some.
Optimal play:
On any round,
(a) always draw if high card <= C/2
(b) always just count the high card if high card = C
(c) if C/2 < high card < C, draw or count depending on what the high card is and how many rounds are remaining.
For instance, if C = 3 and high card = 2, draw if there are 3 or more rounds remaining.
This logic can be best determined by a computer program.
I doubt there is a simple closed expression that can determine this.
The higher your high card, or the fewer rounds there are remaining, the less likely you are to draw.
Long analysis of a simple case
