Matter of Stats

View Original

Finding an Optimal Strategy for Shut The Box: Part 5

Over the last four blog posts we’ve been slowly creating an optimal set of strategies for playing the version of Shut The Box that we introduced in the first blog.

Now that we have those strategies, in this blog we’ll be looking to extract some broad heuristics from them, if possible.

Let’s, then, firstly look at the optimal strategies for the first roll.

> library(dplyr)
> 
> OS = read.csv('Final Best Strategies and Estimated Win Rates - Boosted Sample.csv')
> 
> # Keep only those strategies that originally had rivals
> GS = read.csv('GameSpace.csv')
> OS = left_join(OS, GS[,c("StrategyNum" , "StrategyCount")], by = c("StrategyChosen" = "StrategyNum") )
> OS = OS %>% filter(StrategyCount > 1)
> 
> OS %>% filter(Open == 123456789) %>% select(TotalRolled, Removed, Occurrences, WinRate)
   TotalRolled Removed Occurrences   WinRate
1            3       3      277856 0.1050436
2            4       4      416643 0.1329508
3            5       5      555881 0.1482278
4            6       6      694545 0.1586593
5            7       7      832837 0.1705352
6            8       8      695271 0.2127314
7            9       9      555573 0.2659434
8           10      19      416806 0.1421165
9           11      56      276565 0.1462549
10          12      48      139241 0.1827192

(Note that we have excluded any strategy that had no rivals to begin with, because these strategies represent forced moves and are therefore self-optimising. That means we’re only interested in 1,568 of the 5,115 strategies.)

From this we can see that:

  • The best possible first roll is a 9, which we should use to close box 9. That elevates our probability of winning to over 26%

  • The worst possible first roll is a 2, which we can only use to close box 2. That drops our probability of winning to around 8.5% (we can’t see that in the table above because there is no rival strategy when we first roll a total of 2)

  • Note that the strategies avoid closing boxes 2 and 3 unless forced

ROLLING A 3

Next let’s consider all those strategies associated with rolling a total of 3. All strategies (and there are 64 of them) suggest removing box 3 rather than boxes 1 and 2 if box 3 is available.

> OS %>% filter(grepl("3", as.character(Open)), TotalRolled == 3) %>% select(Open, Removed, Occurrences, WinRate)

If box 3 is not available, then 1 and 2 should be shut if they are still open. Otherwise, the game is lost.

ROLLING A 4

If box 4 is still available, all strategies (and there are 64 of them) suggest removing box 4 rather than boxes 1 and 3.

If box 4 is not available, then 1 and 3 should be shut if they are still open. Otherwise, the game is lost.

ROLLING A 5

If box 5 is still available, all strategies (and there are 97 of them) suggest removing box 5 rather than boxes 2 and 3, or 1 and 4.

If box 5 is not available, then boxes 1 and 4 should be shut, except in the case where the state is “1234679”, in which case boxes 2 and 3 should be shut.

> OS %>% filter(!grepl("5", as.character(Open)), TotalRolled == 5) %>% select(Open, Removed, Occurrences, WinRate) %>% arrange(Removed)
       Open Removed Occurrences    WinRate
1      1234      14        4048 0.20034585
2     12346      14        3779 0.37576078
3    123467      14        5743 0.22009403
4   1234678      14       13711 0.10998468
5  12346789      14       61630 0.05378874
6    123468      14        6780 0.15324484
7   1234689      14       20527 0.05899547
8    123469      14        8682 0.10446902
9     12347      14        4186 0.30291448
10   123478      14        9379 0.15470732
11  1234789      14       47597 0.06334433
12   123479      14       11460 0.09886562
13    12348      14        6580 0.19817629
14   123489      14       13715 0.07969377
15    12349      14        6780 0.12920354
16  1234679      23       17123 0.05635695

ROLLING A 6

If box 6 is still available, all strategies (and there are 106 of them) suggest removing box 6 rather than boxes 1 and 5, 2 and 4, or 1, 2 and 3.

If box 6 is not available, then either boxes 1 and 5, or boxes 2 and 4 should be shut, depending on the state, as shown below:

> OS %>% filter(!grepl("6", as.character(Open)), TotalRolled == 6) %>% select(Open, Removed, Occurrences, WinRate) %>% arrange(Removed)
       Open Removed Occurrences    WinRate
1     12345      15        6108 0.45350360
2   1234578      15       21652 0.14418991
3  12345789      15       96327 0.06711514
4    123458      15       10707 0.21014290
5   1234589      15       32398 0.08747454
6      1235      15        6769 0.19796129
7     12357      15        6642 0.29915688
8    123578      15       11711 0.15011528
9   1235789      15       16098 0.06236800
10   123579      15        9471 0.09787773
11    12358      15       10282 0.19665435
12   123589      15       23176 0.07896099
13    12359      15        8664 0.12996307
14   124578      15        6234 0.09095284
15  1245789      15       10790 0.03577386
16    12458      15        3745 0.10627503
17   124589      15        5356 0.03939507
18     1234      24        5011 0.13849531
19   123457      24        9024 0.25365691
20  1234579      24       26573 0.11263312
21   123459      24       13563 0.14458453
22    12347      24        5350 0.33271028
23   123478      24       11357 0.16597693
24  1234789      24       59839 0.07075653
25   123479      24       14421 0.12627418
26    12348      24        8160 0.24093137
27   123489      24       17243 0.08612190
28    12349      24        8471 0.14083343
29     1245      24        3867 0.25187484
30    12457      24        2785 0.14757630
31   124579      24        4349 0.05541504
32    12459      24        2888 0.07306094

ROLLING A 7

If box 7 is still available, every strategy (and there are 132 of them) recommends removing just box 7.

If box 7 is not available, then either boxes 1 and 6, boxes 2 and 5, or boxes 3 and 4 should be shut, depending on the state, as shown below:

> OS %>% filter(!grepl("7", as.character(Open)), TotalRolled == 7) %>% select(Open, Removed, Occurrences, WinRate) %>% arrange(Removed)
       Open Removed Occurrences    WinRate
1   1234568      16       30711 0.18621992
2    123569      16       23896 0.14341312
3     12456      16        4548 0.25681618
4    124568      16        5207 0.12406376
5      1246      16        6401 0.22824559
6     12468      16        3872 0.09788223
7    124689      16        5180 0.03841699
8     12469      16       11296 0.05754249
9     12568      16        2997 0.09642976
10   125689      16        6442 0.04517231
11    13456      16        4699 0.21451373
12   134568      16       10366 0.08846228
13    13468      16        6453 0.11018131
14 12345689      25      138446 0.08468284
15    12356      25        8712 0.40599174
16   123568      25       12770 0.19130775
17  1235689      25       23227 0.07766823
18     1245      25        4709 0.19728180
19  1245689      25       15507 0.04797833
20   124569      25        6295 0.07243844
21    12458      25        4446 0.10863698
22   124589      25        6494 0.04234678
23    12459      25        3542 0.06013552
24     1256      25        7491 0.31224136
25    12569      25       10597 0.08549590
26     2345      25        7053 0.24727066
27    23456      25       11619 0.17540236
28   234568      25       11641 0.08762134
29    23458      25       10130 0.11451135
30     1234      34        6102 1.00000000
31    12345      34        7014 0.56658112
32   123456      34       12801 0.33013046
33  1234569      34       38510 0.15273955
34   123458      34       12682 0.25713610
35  1234589      34       38658 0.10856744
36   123459      34       16227 0.20644605
37    12346      34        5747 0.56064033
38   123468      34       10279 0.24243603
39  1234689      34       31089 0.10087169
40   123469      34       12682 0.20540924
41    12348      34        9697 0.40311437
42   123489      34       20234 0.12602550
43    12349      34       10166 0.28487114
44  1345689      34        7859 0.03639140
45   134569      34        3199 0.06408253
46     1346      34        4192 0.31106870
47   134689      34       25752 0.04162783
48    13469      34        4513 0.09107024

ROLLING AN 8

If box 8 is still available, every strategy (and there are 137 of them) recommends removing just box 8.

If box 8 is not available, then either boxes 1 and 7, boxes 2 and 6, or boxes 3 and 5 should be shut, depending on the state, as shown below:

> OS %>% filter(!grepl("8", as.character(Open)), TotalRolled == 8) %>% select(Open, Removed, Occurrences, WinRate) %>% arrange(Removed)
       Open Removed Occurrences    WinRate
1   1234567      17       21556 0.27927259
2    123467      17        7235 0.27408431
3   1234679      17       21564 0.11477462
4     12347      17        5215 0.46289549
5    123479      17       14331 0.13502198
6     12367      17        7229 0.36187578
7    124567      17        6167 0.17172045
8     12457      17        2737 0.25063939
9    124579      17        4485 0.05105909
10     1257      17        4318 0.28693840
11    12579      17        3134 0.07211232
12   134567      17        1840 0.15760870
13  1345679      17        5433 0.05374563
14    13457      17        4259 0.22798779
15    13467      17        1000 0.18100000
16   134679      17        1850 0.05297297
17     1347      17        2376 0.25757576
18    13479      17        6131 0.06344805
19    13567      17        4945 0.16299292
20    12346      26        4836 0.43837883
21   123469      26       10752 0.15690104
22   123567      26        9677 0.25007750
23   123679      26        7362 0.12320022
24    12456      26        3744 0.25293803
25  1245679      26       10817 0.05546824
26   124569      26        5377 0.05188767
27    12467      26        4249 0.17439398
28   124679      26       17069 0.06403421
29     1256      26        6211 0.24987925
30    12567      26        1814 0.13561191
31   125679      26        4863 0.05634382
32    12569      26        8861 0.07200090
33     1267      26        4082 0.31626654
34    12679      26        7847 0.08869632
35    23456      26        9687 0.22659234
36    23567      26        7974 0.13870078
37    12345      35        5958 0.50520309
38   123456      35       10892 0.40350716
39 12345679      35       97033 0.13568580
40  1234569      35       31840 0.15445980
41   123457      35        9031 0.35499945
42  1234579      35       26506 0.14962650
43   123459      35       13530 0.17967480
44     1235      35        6625 1.00000000
45    12356      35        7436 0.55957504
46  1235679      35       35499 0.11836953
47   123569      35       19980 0.20565566
48    12357      35        6458 0.50588417
49   123579      35        9435 0.17943826
50    12359      35        8637 0.29246266
51     1345      35        3688 0.19034707
52    13456      35        3927 0.21517698
53   134569      35        2650 0.07094340
54   134579      35        2213 0.06190691
55    13459      35        1410 0.05531915
56   135679      35        7179 0.04931049
57     1357      35        6542 0.30265974
58    13579      35        5851 0.09383011
59   234567      35       16084 0.13298931
60     2356      35        5404 0.27701702

ROLLING A 9

If box 9 is still available, every strategy (and there are 146 of them) recommends removing just box 9.

If box 9 is not available, then either boxes 1 and 8, boxes 2 and 7, boxes 3 and 6, or boxes 4 and 5 should be shut, depending on the state, as shown below:

> OS %>% filter(!grepl("9", as.character(Open)), TotalRolled == 9) %>% select(Open, Removed, Occurrences, WinRate) %>% arrange(Removed)
       Open Removed Occurrences    WinRate
1    123458      18        8624 0.33244434
2   1234678      18       13685 0.20219218
3    123468      18        6856 0.28135939
4    123478      18        9187 0.22085556
5     12348      18        6566 0.46360037
6   1235678      18       10234 0.17871800
7    123578      18        9457 0.21592471
8     12358      18        8175 0.43363914
9    123678      18       10198 0.21523828
10    12378      18        7529 0.29751627
11   124678      18        4033 0.12248946
12    12468      18        2604 0.17703533
13    12478      18        3886 0.15645908
14    12568      18        1887 0.17064123
15    12578      18        2366 0.12003381
16     1268      18        4041 0.27369463
17     1278      18        2644 0.28782148
18   134568      18        6860 0.15772595
19   134678      18        1051 0.10561370
20    13468      18        4348 0.17985281
21   135678      18        3397 0.09066824
22    13568      18        2716 0.15905744
23    13578      18        1907 0.13476665
24     1358      18        1856 0.24461207
25    13678      18        1795 0.11142061
26   145678      18        1000 0.05200000
27   123467      27        5665 0.28755516
28    12347      27        4216 0.44283681
29    12357      27        5270 0.42941176
30    12467      27        3385 0.22333826
31    12567      27        1571 0.15849777
32   125678      27        1658 0.08685163
33     1267      27        3198 0.31926204
34    12678      27        2280 0.12412281
35    23467      27        5830 0.18096055
36     2347      27        4747 0.25932168
37    23478      27        8821 0.10645052
38    23567      27        6416 0.16661471
39    12346      36        3814 0.51127425
40    12356      36        5818 0.57958061
41   123567      36        7789 0.30106561
42   123568      36        8475 0.25852507
43     1236      36        5101 1.00000000
44    12367      36        5763 0.52750304
45    12368      36        7537 0.39909778
46     1356      36        3626 0.24600110
47    13567      36        3903 0.14219831
48     1368      36        3970 0.25037783
49     2346      36        5282 0.22642938
50   234678      36       10367 0.08353429
51    23468      36        4251 0.09762409
52   235678      36        3858 0.05469155
53     2367      36        6774 0.27915559
54    23678      36        9643 0.11168723
55    12345      45        4800 0.38854167
56   123456      45        8679 0.48369628
57  1234567      45       17204 0.35520809
58 12345678      45       61342 0.21737146
59  1234568      45       20443 0.29804823
60   123457      45        7241 0.38944897
61  1234578      45       16945 0.23776925
62    12456      45        3067 0.56732964
63   124567      45        4957 0.27718378
64  1245678      45        6818 0.13611030
65   124568      45        3423 0.25065732
66    12457      45        2223 0.52811516
67   124578      45        5031 0.21407275
68    12458      45        2966 0.40525961
69     1345      45        2989 0.14118434
70    13456      45        3073 0.41295151
71   134567      45        1461 0.22587269
72  1345678      45        3350 0.12268657
73    13457      45        3372 0.32562278
74   134578      45        1405 0.15444840
75    13458      45        3009 0.24858757
76    14568      45        1284 0.12305296
77    14578      45        1096 0.09945255
78     1458      45        1129 0.24534987
79     2345      45        4745 0.18545838
80    23456      45        7697 0.36429778
81   234567      45       12853 0.22337198
82  2345678      45       46122 0.11805646
83   234568      45        7716 0.15266978
84    23457      45        5414 0.28481714
85   234578      45       12766 0.15157449
86    23458      45        6666 0.20387039
87    24567      45        1416 0.13912429
88   245678      45        4959 0.04839685
89     2457      45        1095 0.29771689
90    24578      45        2110 0.11232227
91     3456      45        2253 0.24722592
92    34567      45        4560 0.10811404
93   345678      45        2610 0.05708812
94    34568      45        1121 0.09545049

ROLLING A 10

There are 186 different strategies associated with rolling a 10 and:

  • 72 of them involve removing boxes 1 and 9

  • 58 of them involve removing boxes 4 and 6

  • 32 of them involve removing boxes 2 and 8

  • 20 of them involve removing boxes 3 and 7

  • 3 of them involve removing boxes 1, 4, and 5

  • 1 of them involves removing boxes 2, 3, and 5

ROLLING AN 11

There are 194 different strategies associated with rolling an 11 and:

  • 58 of them involve removing boxes 4 and 7

  • 54 of them involve removing boxes 5 and 6

  • 45 of them involve removing boxes 2 and 9

  • 29 of them involve removing boxes 3 and 8

  • 4 of them involve removing boxes 1, 4, and 6

  • 2 of them involves removing boxes 2, 4, and 5

  • 1 of them involves removing boxes 1, 3, and 7

  • 1 of them involves removing boxes 2, 3, and 6

ROLLING A 12

There are 192 different strategies associated with rolling an 12 and:

  • 67 of them involve removing boxes 4 and 8

  • 50 of them involve removing boxes 5 and 7

  • 49 of them involve removing boxes 3 and 9

  • 6 of them involve removing boxes 1, 5, and 6

  • 5 of them involves removing boxes 2, 4, and 6

  • 4 of them involves removing boxes 1, 4, and 7

  • 4 of them involves removing boxes 3, 4, and 5

  • 3 of them involves removing boxes 1, 3, and 8

  • 2 of them involves removing boxes 2, 3, and 7

  • 2 of them involves removing boxes 1, 2, and 9

WRAPPING UP

Analysing the optimal strategies in another way might yield deeper insights and clearer heuristics, but I think the best we can say, based on the foregoing, is that a player should:

  • Take out the box equal to the total rolled if that box is still open

  • Never take out boxes 1, 2, and 3 in the same roll, and generally try to keep as many of boxes 1,2, and 3 open as you can (although there are exceptions to this suggestion)

Other than that, the apparently optimal strategies are quite state-specific.

Now that we have what we think might be an optimal set of strategies, in future blogs we might look at how close to optimal might be some simple heuristics.

Suggestions, as always, are welcome, and my complete R code can be downloaded via this link.