All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
Optimal Card Drawing Strategy 2 (Posted on 2010-10-02) Difficulty: 5 of 5
In the problem Optimal Card Drawing Strategy, an optimal strategy was determined for a card game. Give a closed expression for the expected score when using the optimal strategy.

No Solution Yet Submitted by Daniel    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts I have my doubts ... | Comment 1 of 5
Well, as I said in my solution to the prior problem, I have doubts that a closed expression for the value of the game exists.  But I was wrong about the previous problem, so maybe I'm wrong here too.

Working backwards from the last round, and using notation from the last problem:

IF YOUR HIGH CARD GOING INTO THE LAST ROUND IS H, then the strategy is to draw if H <C/2, and just count your high card otherwise. 

Incremental gain in the last round = 
if H < C/2,  then C/2
if H >= C/2, then H
Or (don't know if it will be helpful), greater(H, C/2)

What about if there are two rounds remaining?
Well, we will only draw if 
2>= H(H+1)/((C-H+1)*(C-H))  (see previous solution)

And already I'm having trouble figuring it out.
Let's pick a specific case which demonstrates my problem.  
C = 19, 3 rounds

At last round, strategy is to draw if high card = 9 or less.  Expected value of last round, based on high card, is

H  Value
-- -------
0-9  9.5
10   10
11   11
12   12
13  13
14  14
15  15
16  16
17  17
18  18
19  19
      average of the above values = 12

At next to last round, strategy is to draw if H card = 11 or less.

If H is between 0 and 9, then the expected value of the last two rounds = C/2 (random card this round) + 12 = 21.5.

If H is between 12 and 19, then we will not be drawing, and the value of the last two rounds = 2H.

But if H = 10 or 11 going in to last to next round, then things are complicated.  The expected value is not 21.5.  If H = 10 and we draw anything lower than a 10, then the value of the last round is 10, not 9.5.  So, expected value of last two rounds = 
9.5 + .05*(11*10 + 11 + 12 + ...+19) = 21.75

Similarly, if H = 11 and we draw anything lower than a 11, then the value of the last round is 11, not 9.5 or 10.  So, expected value of last two rounds = 
9.5 + .05*(12*11 + 12 + ...+19) = 22.3

 Expected value of last two rounds, based on high card going into the next to last round, is

H  Value
-- -------
0-9  21.5
10   21.75
11   22.3
12   24
13  26
14  28
15  30
16  32
17  34
18  36
19  38
      average of the above values = 25.2535

So, if the game is only three rounds long, then the first round is always a random draw, expected value = 9.5.  Total value of the game = 9.5 + 25.3525 = 34.8525, when C = 19 and R = 3.  (While it is always possible that I have made a mistake, I will test any proposed solution using this case.)

If the game is more than 3 rounds, then the situation with 3 rounds to go is even more complicated.  While I can see how to calculated the game value easily enough for any given C and R, using a spreadsheet or computer program, I remain doubtful that there is a neat closed expression that doesn't involve multiple minimums and summations.

Over to you, Daniel


 

Edited on October 3, 2010, 1:44 am
  Posted by Steve Herman on 2010-10-03 01:21:28

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information