Author |
Topic: Card Game (Read 3155 times) |
|
aicoped
Junior Member
Gender: 
Posts: 57
|
Alice "Here's the deal. You give me $10. Then I will deal four cards (from a regular 52 card deck), chosen randomly, face down. You get to look at #1 first and decide whether to keep it. If not, look at #2 and decide whether to keep that one. If not look at #3, and decide. If you don't take that, then #4 is your choice. If your chosen value is n, I will pay you $n. Then we can reshuffle the entire deck, you give me another $10, and we can play again, and again, and again."
Bob "Hmmm....I need a good strategy to beat you at this game, but I think I can do it."
Help Bob out with a strategy that will win. Note that the cards all have face value with the following exceptions: Ace=1, Jack = 11, Queen = 12, and King = 13.
I can't ifnd any discussion of this problem anywhere on the site, if there is one already just please direct me to it.
Here are my thoughts.
Intuitively you should definitely keep your 3rd card if it is an 8 or higher(and i actually still think should be kept on 3rd card under certain circumstances)
Now if you do this strategy, you will have a positive outcome: 9,8,7 where you keep if the first card is nine or higher, if the first card is 8 or lower you discard it and get the second card which you keep if 8 or higher then same for third card except keep if 8 or higher unless the first two cards have a 8 or a seven removed. Then and only then do u keep a seven.
so formally a winning strategy is keep 9 or higher on card 1. keep 8 or higher on card 2, and if card 1 or 2 contianed a 7,8 then keep 7 or higher on 3rd card, else only keep eight or higher.
if you follow that you will make money. i do not believe it is "optimal, and I have not the math skills to prove it. I just made a random number generator in excel and ran about 200 simulations to make sure it was positive.
i also ran other strategies, such as always keep 10 or higher, else discard. This is not surprisingly a losing strategy, and why most people would lose money at this game. but sinc eit was cumbersome to do by hand each time, and my programming skills are non-existant, i would like to enlist the help of some uberpuzzlers.
It is a fun problem to ponder. Oh, and lastly 8,8,8 strategy also yields almost exactly the same value as 9,8,7. It may even be a better strategy, but i could not test enough to get a wide enough difference.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: Card Game
« Reply #1 on: Jan 28th, 2010, 3:02am » |
 Quote  Modify
|
If each card was from a different deck, it would be similar to the dice rolling question we had a week ago (here). But in this case each next card is dependent on the former ones (if the first card is an ace, the probability becomes smaller the next one is as well).
I'm lazy, so my approach would be to write a program to recursively solve what the best move is give a first card, given a first pair of cards and given a first triple of cards.
I'm not certain the best strategy is picking three values A,B,C and move on to the second card if the first is smaller than A, then move on to the third if the second is smaller than B, and move on to the fourth if the third is smaller than C. There's a good chance it is, but because the probabilities of later cards are dependent on the first it might not be in some cases.
(But a brute-force search would soon reveal it.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Card Game
« Reply #2 on: Jan 28th, 2010, 6:03am » |
Quote Modify
|
The best strategy of the kind "keep the ith card if it's greater than or equal to Vi) is
10,9,8; which over all possible games gives you a score of 66318616, or an average of ~10.207 per game.
For comparison,
9,8,7 gives 65794440, or ~10.126 per game
8,8,8 gives 65028600, or ~10.008 per game
But you can do slightly better: the maximum you can get is 66319160
[edit]
There are just a few exceptions you need to add, to improve on 10,9,8-strategy, namely:
if you get a 7 for your third card, keep it if the first two where 7,8; 8,7; 8,8; 9,6; 9,7; or 9,8. Or perhaps easier to remember, if it less than their average. [e2]Actually, I hadn't seen Grimbal's next post yet, which was posted earlier than my previous edit.[/e2]
[/edit]
|
| « Last Edit: Jan 28th, 2010, 6:58am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Card Game
« Reply #3 on: Jan 28th, 2010, 6:39am » |
Quote Modify
|
Lazy too.
If we approximate the problem by assuming each card has 1/13 chance for each value 1 to 13, we can compute the expected return based on the number of cards remaining, like in the dice problem towr mentioned.
With the last card, the expected return is (1+13)/2 = 7.
With 2 cards remaining, we keep the card if the value is higher than that. The return is (7*7 + 6*(7+13)/2)/13 = 8.6154. (7 chances to continue and get 7, 6 chances to stop and earn (7+13)/2 on average).
With 3 cards remaining, you keep anything above 8.6. The return is (8*8.6154 + 5*(9+13)/2)/13 = 9.5325.
With 4 cards remaining, you keep 10 or more, the return is (9*9.5325 + 4*(10+13)/2)/13 = 10.13791534. That is what you can earn on average.
If you take into account that the cards don't repeat it changes these values. But I don't think it changes them to the point where the strategy should be changed. The average return should be slightly higher due to the fact that when you discard cards, these are likely to be low values, so the return after discarding a card is often higher than computed.
Just for the last card, if you are holding a 7, you can check whether the first 2 cards average to more than 7. If yes, you should better keep your seven. If not, you should draw the last card.
But If I do the same calculations with the rule that you always keep a value 10 or above, I find a result of 10.0068. I think the real value is slightly higher. So I am a bit surprised when aicoped says it is a loosing strategy. I should run a program as towr outlined.
PS: Hi, towr, I am afraid I didn't see your last post.
PS: More precisely, under the approximation:
for the 10,9,8 or 10,9,7 strategy I get 10.13791534,
for the 10,10,10 strategy, I get 10.00682749.
|
| « Last Edit: Jan 28th, 2010, 7:16am by Grimbal » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Card Game
« Reply #4 on: Jan 28th, 2010, 7:01am » |
Quote Modify
|
There are 52*51*50*49 = 6497400 possible sets of cards. Of those, 4*51*50*49+36*4*50*49+36*35*4*49 = 1099560 keep a ten (or a J or a Q or a K) before the last card when playing ten or greater. In the remaining cases, you get the value of the last card, so the expected value playing "ten or greater" is:
( 1099560*(10+11+12+13) + (6497400-(4*1099560))*7 ) / 6497400 = 10.0461538461538461538...
Or 65273880 over all possible games.
In other words, assuming nothing went wonky in the calculations, 10,10,10 does better than 8,8,8, but worse than 9,8,7
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Card Game
« Reply #5 on: Jan 28th, 2010, 7:15am » |
Quote Modify
|
By spreadsheet, rather than full brute force, just working the expected values back from the forth card given the previous cards:
First Card: Keep 10 or better
Second Card: Keep 9 or better
Third Card: Keep 8 or better, Keep 7 if sum of first two cards > 14.
(In the case where the third card is a 7 and the first two sum to 14, the expected value of the rest of the deck is exactly 7, so you face the same odds keeping the third card or continuing.)
Expected Value of the Game: $10.20703050
Edit: Whoops, my EVs were slightly off: not all games are equally likely... Fixed, but now the spreadsheet is over the 300K attachment limit... linked instead.
--SMQ
|
| « Last Edit: Jan 28th, 2010, 8:51am by SMQ » |
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Card Game
« Reply #6 on: Jan 28th, 2010, 8:06am » |
Quote Modify
|
Here are some results from my full search program.
The score is the total income over all possible card draws. The average is the average by game. If >10, it is a winning strategy. It seems most reasonable strategies are winning.
Strategy 6,6,6: score 60969480 average 9.383673469387755
Strategy 7,7,7: score 63316344 average 9.744873949579832
Strategy 8,8,8: score 65028600 average 10.008403361344538
Strategy 10,10,10: score 65530920 average 10.085714285714285
Strategy 9,8,7: score 65794440 average 10.12627204728045
Strategy 9,9,9: score 65861640 average 10.136614645858343
Strategy 10,9,7: score 66299128 average 10.203947425123896
Strategy 10,9,8: score 66318616 average 10.206946778711485
Strategy 10,9,8?: score 66319160 average 10.207030504509497
The last strategy is 10,9,8 or 10,9,7, with the extra test to keep or not the 7 as 3rd card.
|
| « Last Edit: Jan 28th, 2010, 8:10am by Grimbal » |
IP Logged |
|
|
|
aicoped
Junior Member
Gender:
Posts: 57
|
|
Re: Card Game
« Reply #7 on: Jan 28th, 2010, 4:26pm » |
Quote Modify
|
Thanks a ton guys. I knew you would help me out.
I wish I were smart.
|
| « Last Edit: Jan 28th, 2010, 4:27pm by aicoped » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Card Game
« Reply #8 on: Jan 29th, 2010, 8:26am » |
Quote Modify
|
...okay, I see where I went wrong - after getting three cards at 9 or less, the expected value of the fourth card is going to be more than 7 - at this point I'm too lazy to work out the exact value...
|
|
IP Logged |
|
|
|
aicoped
Junior Member
Gender:
Posts: 57
|
|
Re: Card Game
« Reply #9 on: Jan 31st, 2010, 6:30pm » |
Quote Modify
|
Grimbal I did a very low number of simulations. Literally 100 just to get a feel for it.
My analysis of 10,10,10 being a losing strategy was based on 2 things.
1.) over the 100 or so sample size it did in fact do much worse than my 9,8,7 strategy, and it was losing money over 100 games, so i stopped.
2.) Since this was a riddle in the hard section, I figured the obvious strategy of "keep anything that won't lose you money" was too easy of a solution. It just seemed like it had to be wrong, so when i get a "confirmation" even off of my relatively small sample size, I stopped, especially since 9,8,7 did better. But I do agree 10,9,8?(seven rarely) now seems to be best and I understand why, so all of your help is appreciated.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print