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.05635695ROLLING 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.07306094ROLLING 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.09107024ROLLING 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.27701702ROLLING 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.09545049ROLLING 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.