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

Home > Games
Card game (Posted on 2006-08-12) Difficulty: 3 of 5
Jack has challenged you to play a card game with him. The idea of the game is that a player gets a random card and after seeing it it's placed back in the deck. The player may get as many cards as he/she wants and the sum of the values of these cards represents the points this player got. However if the player gets an ace he/she gets zero points as total and the other player may try. How should one play this game (how many cards should be picked) for maximum chance of winning against Jack?
Face cards can be interpreted so that king is 13 points, queen is 12 points and jack is 11 points.

No Solution Yet Submitted by atheron    
Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer assisted solution | Comment 2 of 6 |

The strategy for the second player (presumably Jack) will be just to continue drawing until the mark's (Jack's intended victim's) total is exceeded or an ace is drawn.

At any given stage of the mark's progress, all that matters as to whether to continue drawing or not is how much is being risked in terms of total accumulated thus far, as all cards are replaced in the deck.  It doesn't matter how many cards it took to accumulate a given total.  It must take into consideration how hard it will be for Jack to beat the total built thus far, as well as the likelihood of reducing that probability by the chance of increasing the total further.

The probability of having, at some point in the draw, if extended indefinitely, any given total exactly, will be the sum of the probabilities of reaching 13 less to 2 less, also exactly, multiplied by 1/13--the probability of increasing by that amount.  The probability of equalling or exceeding any given amount will be the sum of all the transition probabilities encountered in the exact-total calculation, so that for example, the probability of equalling or exceeding a total of 6 will be the sum of the probabilities of getting a 6 to begin with, achieving a total of exactly 2 and then immediately getting a 4, achieving a total of exactly 3 and then immediately getting a 3 and achieving a total of exactly 4 and then immediately getting a 2.

The following first part of the program computes these and stores them in arrays for further computation:

DEFDBL A-Z
DIM exact(14)
DIM atLeast(14)
DIM al(200), ex(200)

CLS
OPEN "cardgame.txt" FOR OUTPUT AS #2

rep14 = 2
exact(12) = 1
atLeast(12) = 1

DO
  FOR i = 1 TO 12   ' rep14 - 13 to rep14 - 2
    p = exact(i) / 13
    FOR j = i + 1 TO 14
     atLeast(j) = atLeast(j) + p
    NEXT
    exact(14) = exact(14) + p
  NEXT

  IF rep14 - 13 >= 2 THEN
   IF rep14 - 13 < 70 THEN
    PRINT #2, USING "#### #.#######  #.#######"; rep14 - 13; exact(1); atLeast(1)
   END IF
   al(rep14 - 13) = atLeast(1) ' store for later use
   ex(rep14 - 13) = exact(1)   ' store for later use
  END IF

  FOR i = 1 TO 13
    exact(i) = exact(i + 1)
    atLeast(i) = atLeast(i + 1)
  NEXT
  exact(14) = 0: atLeast(14) = 0
  rep14 = rep14 + 1
LOOP UNTIL rep14 - 13 > UBOUND(al)

The tabulation is:

total   exact    at least
   2 0.0769231  0.9230769
   3 0.0769231  0.9171598
   4 0.0828402  0.9112426
   5 0.0887574  0.9048703
   6 0.0951297  0.8980428
   7 0.1019572  0.8907251
   8 0.1092749  0.8828823
   9 0.1171177  0.8744765
  10 0.1255235  0.8654674
  11 0.1345326  0.8558118
  12 0.1441882  0.8454631
  13 0.1545369  0.8343717
  14 0.0887052  0.8224843
  15 0.1005927  0.8156608
  16 0.1014990  0.8079229
  17 0.1033197  0.8001153
  18 0.1047550  0.7921676
  19 0.1058752  0.7841095
  20 0.1066156  0.7759653
  21 0.1069170  0.7677641
  22 0.1067124  0.7595397
  23 0.1059277  0.7513311
  24 0.1044807  0.7431828
  25 0.1022803  0.7351458
  26 0.0992259  0.7272781
  27 0.0952062  0.7196453
  28 0.0960155  0.7123218
  29 0.0956011  0.7049360
  30 0.0951793  0.6975820
  31 0.0945856  0.6902605
  32 0.0938490  0.6829847
  33 0.0929806  0.6757656
  34 0.0919985  0.6686132
  35 0.0909265  0.6615364
  36 0.0897947  0.6545421
  37 0.0886407  0.6476348
  38 0.0875110  0.6408163
  39 0.0864618  0.6340846
  40 0.0855607  0.6274337
  41 0.0848880  0.6208521
  42 0.0840838  0.6143223
  43 0.0832597  0.6078543
  44 0.0824062  0.6014497
  45 0.0815350  0.5951108
  46 0.0806548  0.5888389
  47 0.0797744  0.5826346
  48 0.0789018  0.5764982
  49 0.0780439  0.5704288
  50 0.0772060  0.5644254
  51 0.0763909  0.5584865
  52 0.0755982  0.5526103
  53 0.0748235  0.5467950
  54 0.0740571  0.5410394
  55 0.0732829  0.5353427
  56 0.0725116  0.5297055
  57 0.0717442  0.5241277
  58 0.0709831  0.5186089
  59 0.0702299  0.5131487
  60 0.0694860  0.5077464
  61 0.0687518  0.5024013
  62 0.0680275  0.4971127
  63 0.0673127  0.4918798
  64 0.0666067  0.4867019
  65 0.0659083  0.4815783
  66 0.0652167  0.4765085
  67 0.0645309  0.4714918
  68 0.0638509  0.4665279
  69 0.0631776  0.4616163


 
  so for example, at the outset if play is continued until an ace is received, there is about 6.31776% probability that a total of 69 will be reached exactly at some point and a 46.16163% probability that 69 will be either reached or exceeded before an ace is received.
 
  By the way, the value for 57 -- about .524 probability of reaching or exceeding 57 -- has been verified within statistical error bounds by:
 
  DEFDBL A-Z
  RANDOMIZE TIMER
  FOR tr = 1 TO 1000000
    t = 0
    DO
      n = INT(RND(1) * 13 + 1)
      IF n = 1 THEN t = 0: EXIT DO
      t = t + n
    LOOP UNTIL t >= 57
    IF t >= 57 THEN goodCt = goodCt + 1
    PRINT goodCt / tr
  NEXT
 
From this information we can figure at what total accumulated value it is worthwhile to stop drawing.  If one stops drawing, the probability of a win will be just 1 minus the probability that Jack will equal or exceed one unit higher (he will try for a win rather than a tie, as, if he has equalled the mark's total, there is only 1/13 chance that an additional draw will cause him to lose, and presumably a win is more 14/13 as good as a draw).  If the mark continues to draw, there is 1/13 probability that he will get an ace, and 1/13 for each of the cards that will bring his total to 2, 3, ..., 13 points higher than he has now, so the 1/13 probabilities have to be multiplied by the probabilities of winning with that total, each of which is 1 minus Jack's probablity of exceeding the respective totals.

The continuation of the first program above calculates these:

FOR i = 10 TO 60
  pStay = 1 - al(i + 1)
  t = 0
  FOR j = i + 2 TO i + 13
    t = t + 1 - al(j + 1)
  NEXT
  pHit = t / 13
  PRINT #2, i, pStay, pHit
  IF pHit < pStay AND goal = 0 THEN goal = i
NEXT

resulting in these probabilities:

curr. total     prob win by staying       prob of win by drawing
 10            .1441882204164286           .195798845084751
 11            .1545368793337383           .2034316083323801
 12            .1656282809042325           .2107551613206228
 13            .1775157331606735           .2181409670795046
 14            .1843392103899933           .2254949002502773
 15            .1920771070236544           .2328163866823629
 16            .1998847203854702           .2400922010472654
 17            .20783239042962             .2473113546167851
 18            .2158904672016828           .2544637058827389
 19            .2240347115129421           .2615405152228656
 20            .2322359101182142           .2685348606749596
 21            .2404602919285935           .275442141746531
 22            .2486689382155137           .2822606581132129
 23            .2568172248311731           .2889922746936896
 24            .2648542031234106           .2956431833881866
 25            .2727219220078283           .3022247731082874
 26            .2803546852554571           .3087546209596385
 27            .2876782382436999           .3152226060387756
 28            .2950640440025816           .3216271999394957
 29            .3024179771733538           .3279661398899891
 30            .309739463605439            .3342380628816992
 31            .3170152779703413           .3404422771334842
 32            .3242344315398614           .3465787661334042
 33            .3313867828058157           .352648132434221
 34            .3384635921459422           .3586515097771782
 35            .3454579375980366           .3645904321377698
 36            .3523652186696082           .3704666514965362
 37            .3591837350362899           .3762818943768501
 38            .3659153516167664           .3820375457698001
 39            .3725662603112636           .3877342474058434
 40            .3791478500313645           .3933713954681635
 41            .3856776978827154           .398949214034861
 42            .3921456829618527           .4044679983062969
 43            .3985502768625728           .4099282347789793
 44            .4048892168130661           .4153305375039483
 45            .411161139804776            .4206756111689864
 46            .4173653540565608           .4259642089667207
 47            .4235018430564809           .4311970919463181
 48            .4295712093572978           .4363749918839753
 49            .4355745867002548           .4414985811000174
 50            .4415135090608463           .4465684534375128
 51            .4473897284196128           .4515851216469873
 52            .4532049712999267           .4565490376214268
 53            .4589606226928767           .461460643332284
 54            .46465732432892             .4663204619594581
 55            .4702944723912403           .4711290334438752
 56            .4758722909579379           .4758869152633492
 57            .4813910752293736           .4805946690068027
 58            .4868513117020563           .485252851911372
 59            .4922536144270255           .4898620102065885
 60            .4975986880920638           .4944226750484849


we see that 57 is the first total at which you have a greater probability of winning if you keep what you have than if you try to better it by drawing again. So the mark's best strategy is to stop drawing if his total is 57 or more.

But what exactly is the mark's probability of winning? The 48.139% is only his probability of winning given that he already has a current total of 57.  He might not get that far, as he could draw an ace before that.  On the other hand, in going for the 57, he might actually wind up with, say, 63.

The following continuation of the program takes into consideration all the ways of equalling or exceeding a given goal total, multiplying those probabilities by the probability of winning (of Jack's losing), given the actual achieved total:

ex(0) = 1: al(0) = 1
FOR g = goal - 54 TO goal + 60
  tProb = 0
  FOR i = g - 13 TO g - 1
   FOR j = g - i TO 13
    IF j <> 1 AND i >= 0 THEN
     tProb = tProb + ex(i) * (1 - al(i + j + 1)) / 13
    END IF
   NEXT
  NEXT
  PRINT #2, USING "### #.##########"; g; tProb
NEXT


The results are:

goal prob of win
  3 0.1188516514
  4 0.1227139586
  5 0.1270201525
  6 0.1317558583
  7 0.1369178187
  8 0.1424875490
  9 0.1484288944
 10 0.1546828135
 11 0.1611611602
 12 0.1677390935
 13 0.1742458581
 14 0.1805239550
 15 0.1841746788
 16 0.1882727512
 17 0.1923537692
 18 0.1964327244
 19 0.2004734639
 20 0.2044443975
 21 0.2083144312
 22 0.2120545844
 23 0.2156392375
 24 0.2190474673
 25 0.2222643221
 26 0.2252818839
 27 0.2280998937
 28 0.2307222880
 29 0.2332727620
 30 0.2357151953
 31 0.2380469554
 32 0.2402628119
 33 0.2423598052
 34 0.2443366976
 35 0.2461939561
 36 0.2479336067
 37 0.2495590186
 38 0.2510746117
 39 0.2524854812
 40 0.2537969329
 41 0.2550139089
 42 0.2561405017
 43 0.2571766089
 44 0.2581239345
 45 0.2589843642
 46 0.2597601266
 47 0.2604536654
 48 0.2610675490
 49 0.2616043794
 50 0.2620667110
 51 0.2624569830
 52 0.2627774727
 53 0.2630302779
 54 0.2632173382
 55 0.2633405053
 56 0.2634016644
 57 0.2634027249
 58 0.2633455873
 59 0.2632321237
 60 0.2630641615
 61 0.2628434732
 62 0.2625717714
 63 0.2622507088
 64 0.2618818832
 65 0.2614668454
 66 0.2610071095
 67 0.2605041624
 68 0.2599594689
 69 0.2593744688
 70 0.2587505601
 71 0.2580891042
 72 0.2573914240
 73 0.2566588052
 74 0.2558924979
 75 0.2550937193
 76 0.2542636554
 77 0.2534034636
 78 0.2525142737
 79 0.2515971891
 80 0.2506532865
 81 0.2496836154
 82 0.2486891971
 83 0.2476710246
 84 0.2466300644
 85 0.2455672571
 86 0.2444835185
 87 0.2433797406
 88 0.2422567926
 89 0.2411155208
 90 0.2399567499
 91 0.2387812829
 92 0.2375899012
 93 0.2363833655
 94 0.2351624156
 95 0.2339277710
 96 0.2326801318
 97 0.2314201787
 98 0.2301485743
 99 0.2288659628
100 0.2275729711
101 0.2262702087
102 0.2249582682
103 0.2236377260
104 0.2223091422
105 0.2209730609
106 0.2196300112
107 0.2182805069
108 0.2169250472
109 0.2155641170
110 0.2141981873
111 0.2128277155
112 0.2114531459
113 0.2100749095
114 0.2086934248
115 0.2073090981
116 0.2059223233
117 0.2045334827

and indeed 57 is the best goal to have, though the probability of a win is only a little better than 1/4.


  Posted by Charlie on 2006-08-12 16:07:57
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 (1)
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