Skip to content

Instantly share code, notes, and snippets.

@jhwaters
Created April 16, 2018 11:36
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jhwaters/69764363c6d7f0dbeb77786cb925e98b to your computer and use it in GitHub Desktop.
Save jhwaters/69764363c6d7f0dbeb77786cb925e98b to your computer and use it in GitHub Desktop.
from fractions import Fraction
class ShutTheBox:
# possible moves for each sum
moves = {i: tuple() for i in range(1,13)}
for a in range(1,10):
moves[a] += ((a,),)
if a < 9:
for b in range(a+1,10):
if a+b <= 12:
moves[a+b] += ((a,b),)
if b < 9:
for c in range(b+1,10):
if a+b+c <= 12:
moves[a+b+c] += ((a,b,c),)
if c < 9:
for d in range(c+1,10):
if a+b+c+d <= 12:
moves[a+b+c+d] += ((a,b,c,d),)
# count number of ways each sum can be obtained
roll2 = {i: 0 for i in range(2,13)}
for a in range(1,7):
for b in range(1,7):
roll2[a+b] += 1
known_states = {} # stores known win probabilities
def __init__(self, state=None):
# state: dict with keys 1-9; value is True if the tile is shut, False if not
self.state = {i: False for i in range(1,10)} if state is None else state
def __str__(self):
return ''.join(['_' if self.state[i] else str(i) for i in range(1,10)])
def evaluate_move(self, move):
newstate = {}
for i in range(1,10):
if self.state[i]:
if i in move: # not a valid move (loss)
return 0
else:
newstate[i] = True
else:
newstate[i] = bool(i in move)
if False in newstate.values(): # game is unfinished
return ShutTheBox(state=newstate).win_chance()
else: # win
return 1
def best_move(self, roll):
return max([self.evaluate_move(m) for m in self.moves[roll]])
def win_chance_1d(self): # rolling 1 dice
return Fraction(sum([self.best_move(roll) for roll in range(1,7)]), 6)
def win_chance_2d(self): # rolling 2 die
return Fraction(sum([self.best_move(roll) * self.roll2[roll] for roll in range(2,13)]), 36)
def win_chance(self):
s = str(self)
if s in ShutTheBox.known_states: # use already-calculated win probability
return ShutTheBox.known_states[s]
else: # calculate win probability and store
can_roll_1 = self.state[7] and self.state[8] and self.state[9]
w = max(self.win_chance_1d(), self.win_chance_2d()) if can_roll_1 else self.win_chance_2d()
ShutTheBox.known_states[s] = w
return w
if __name__ == '__main__':
game = ShutTheBox()
w = game.win_chance()
print("odds of winning: {}/{} = {}".format(w.numerator, w.denominator, float(w)))
if input("display odds for all game states? (yes/no) ").lower() in ['yes', 'y']:
pairs = [(ShutTheBox.known_states[state], state) for state in ShutTheBox.known_states]
for win_prob, state in sorted(pairs, reverse=True):
print("{}: {}".format(state, float(win_prob)))
@jhwaters
Copy link
Author

Probability of winning a new game, assuming perfect play: 956177159 / 9795520512 = 0.0976137161704307

All possible game states sorted by win probability (123______ means 1, 2, and 3 are still open, while all others are shut):

123______: 0.3333333333333333
1234_____: 0.26483196159122085
123_5____: 0.25814471879286693
12345____: 0.24483096136259716
12_4_____: 0.24228395061728394
123__6___: 0.2414551897576589
1234_6___: 0.23030621284865113
12__5____: 0.22993827160493827
12_45____: 0.22539437585733882
_2_4_____: 0.2222222222222222
_23______: 0.2222222222222222
1___5____: 0.2222222222222222
1__4_____: 0.2222222222222222
1_3______: 0.2222222222222222
12_______: 0.2222222222222222
123456___: 0.22081773452979728
_234_____: 0.21669238683127573
1_34_____: 0.21604938271604937
123_56___: 0.21128281702484378
123___7__: 0.21116255144032922
1234__7__: 0.2105159750800183
1_3_5____: 0.20833333333333334
12___6___: 0.20743312757201646
12345_7__: 0.20541203068637912
12_4_6___: 0.1994813100137174
_2345____: 0.1900148605395519
__34_____: 0.18981481481481483
_2__5____: 0.18981481481481483
1____6___: 0.18981481481481483
123_5_7__: 0.1897505144032922
12_4__7__: 0.18955761316872427
12_456___: 0.18866455189757658
1_345____: 0.18818587105624143
1234_67__: 0.18818309264339786
1234567__: 0.18721215863449564
1_3__6___: 0.18492798353909465
1_34_6___: 0.1776406035665295
_234_6___: 0.17722622313671696
12____7__: 0.17592592592592593
12345__8_: 0.17426648577876
_23_5____: 0.1741255144032922
1_3_56___: 0.17376828989483312
1234___8_: 0.17247930479347662
123__67__: 0.1705961362597165
_2_45____: 0.16949588477366256
123_567__: 0.16943813347812833
12_45_7__: 0.16881001371742113
1_3456___: 0.16877429126657523
1__45____: 0.16820987654320987
______7__: 0.16666666666666666
_____6___: 0.16666666666666666
____5____: 0.16666666666666666
___4_____: 0.16666666666666666
__3______: 0.16666666666666666
__3_5____: 0.16666666666666666
_2_______: 0.16666666666666666
_2___6___: 0.16666666666666666
1________: 0.16666666666666666
1_____7__: 0.16666666666666666
12_4___8_: 0.16291580932784636
1__4_6___: 0.16242283950617284
1234_6_8_: 0.16199450085945571
12__56___: 0.1616226566072245
123456_8_: 0.16078678617134828
123____8_: 0.16005086877000457
_23__6___: 0.1598508230452675
_23456___: 0.15668938614540467
1_3_5_7__: 0.15612139917695472
12__5_7__: 0.15599279835390947
123_5__8_: 0.153494608291419
12_4_67__: 0.1529528177869227
1_3___7__: 0.1527777777777778
12_4567__: 0.15051674509729207
12345_78_: 0.1466936931263301
12345678_: 0.1450168047486398
_23_56___: 0.14497599451303156
1_345_7__: 0.14427583447645176
___45____: 0.14351851851851852
__3__6___: 0.14351851851851852
_2____7__: 0.14351851851851852
1234__78_: 0.14209636805873088
123__6_8_: 0.141431136640756
__345____: 0.14017489711934156
123_56_8_: 0.13922246381183423
_______8_: 0.1388888888888889
_2_456___: 0.1386816986739826
_234__7__: 0.138460219478738
12_45__8_: 0.13817443987197073
1_34567__: 0.1376360231544988
12__5__8_: 0.13744570187471422
12345___9: 0.13671749309895173
1__45_7__: 0.1356738683127572
_2345_7__: 0.13564529035208048
1______8_: 0.13425925925925927
1234_678_: 0.13424932533079872
1__456___: 0.13164437585733882
1_34__7__: 0.13117283950617284
12_____8_: 0.13027263374485595
_234___8_: 0.1301797553726566
1__4__7__: 0.12962962962962962
123456__9: 0.12931849516809016
1_34_67__: 0.1291330875628715
12_456_8_: 0.1281274013425291
_23___7__: 0.12705761316872427
123_5_78_: 0.12532566967687853
_234567__: 0.12506291120510085
1234_6__9: 0.1243054629417941
1_3__67__: 0.12414266117969822
1234____9: 0.12406883478128335
123___78_: 0.12323173868312758
12_4_6_8_: 0.12266017946959305
12___67__: 0.12212791495198902
__3456___: 0.12165637860082304
1_3_567__: 0.12065614997713763
___4_6___: 0.12037037037037036
__3___7__: 0.12037037037037036
1234567_9: 0.11877133497650727
123_5678_: 0.11875102977682377
12345_7_9: 0.11832578928093618
12__567__: 0.11828060699588477
_23__67__: 0.11754115226337448
1___56___: 0.11676954732510288
_234_67__: 0.11669810242341107
123_5___9: 0.11644566377076665
12_4__78_: 0.11585862482853224
1_34___8_: 0.1148619684499314
12__5___9: 0.11439757658893461
12_4____9: 0.11389746227709191
12___6_8_: 0.11365454961133974
12_45_78_: 0.11364353518899557
123_56__9: 0.11362630241409677
123_____9: 0.11356881572930956
1_345__8_: 0.11356524348422496
_2_4_6___: 0.11291152263374486
________9: 0.1111111111111111
123__678_: 0.11079298284052227
_2_____8_: 0.11033950617283951
1_34_6_8_: 0.11028056412894376
_23_5_7__: 0.11003943758573388
123__6__9: 0.10852242417314434
_2__56___: 0.10776748971193416
_2345__8_: 0.1077258135192806
1_3456_8_: 0.10762727909236397
1234__7_9: 0.10755950566478688
12_45678_: 0.10738411835403648
1234_67_9: 0.1067825313334406
1___5_7__: 0.10648148148148148
1_3__6_8_: 0.1057813214449017
1_3____8_: 0.10545267489711935
__34_6___: 0.1051954732510288
12__56_8_: 0.10419107700807803
1__4_67__: 0.10300925925925926
_2_4__7__: 0.10262345679012345
_23_567__: 0.10229004724889498
_23456_8_: 0.10220338722925028
1_______9: 0.10185185185185185
12_4_678_: 0.10046443155260885
12_45___9: 0.1000157178783722
123_5_7_9: 0.09907449745126928
1__4567__: 0.09892618312757202
123456_89: 0.09816793000657646
123456789: 0.0976137161704307
123_567_9: 0.09744760810113447
____56___: 0.09722222222222222
___4__7__: 0.09722222222222222
12345__89: 0.09665365825533785
1_3_5__8_: 0.09600765889346136
__345_7__: 0.09585048010973937
_234_6_8_: 0.09567960771985978
123___7_9: 0.09565043438500229
__3_56___: 0.09542181069958848
_2_4_67__: 0.09505744170096021
1_345678_: 0.09470502980046233
12___6__9: 0.0946359167809785
12_4_6__9: 0.09462520004572474
1_345_78_: 0.09409710314738606
1__4_6_8_: 0.09366426611796982
_2_45__8_: 0.09315700731595793
12__5_78_: 0.09293195587562872
1_34____9: 0.09237825788751715
12_456__9: 0.09206707564903724
123__67_9: 0.09087090276719335
_2___67__: 0.09079218106995884
_2_45_7__: 0.09070644718792867
12345_789: 0.08997154565909402
12____78_: 0.08959190672153636
_2_4567__: 0.08935971079103795
1234_6_89: 0.0887910053309069
12_4__7_9: 0.0887631458619113
_234__78_: 0.08795760459533608
_2345678_: 0.08694266067399768
__3_5_7__: 0.08693415637860083
1234___89: 0.0867975510804586
1____6_8_: 0.08667695473251029
__3____8_: 0.08641975308641975
_2345_78_: 0.08615501003403953
1_34_678_: 0.08591507423919117
1_3_56_8_: 0.08586129210486207
12__56__9: 0.08570054107605547
12_45_7_9: 0.08555288827922573
1_3_5_78_: 0.08529092363968907
1_3___78_: 0.08466220850480109
12______9: 0.084619341563786
1___5__8_: 0.08359053497942387
12_4567_9: 0.08337190034970957
1234_6789: 0.08315918332283515
___456___: 0.0830761316872428
1_3456__9: 0.08276197257785907
1_345___9: 0.08266175125743026
__34567__: 0.0824188385916781
1__45__8_: 0.08166152263374486
1__4___8_: 0.08063271604938271
1_34__78_: 0.08004329561042524
12_4_67_9: 0.07962752597419093
_2_4___8_: 0.07960390946502058
_234_678_: 0.07921969466036681
1234__789: 0.07913939632409807
12__5678_: 0.07904921918660773
1__456_8_: 0.07821252000457247
_23____8_: 0.07797496570644719
1____67__: 0.0779320987654321
_2345___9: 0.07789161332114007
123_56_89: 0.07756813770837215
1_3_5___9: 0.07730338363054412
_23_5__8_: 0.07717478280749886
_2______9: 0.07716049382716049
_2__5__8_: 0.0767318244170096
1_3_5678_: 0.07637440145049026
1_34_6__9: 0.07629601051668954
123_5__89: 0.07617409111500618
__3__67__: 0.07587448559670781
_23__6_8_: 0.07583876314586191
_23_56_8_: 0.07560021655743535
_23456__9: 0.07513992616301715
12__5_7_9: 0.07497427983539094
____5_7__: 0.07407407407407407
__34___8_: 0.07407407407407407
12____7_9: 0.07407407407407407
1_34567_9: 0.07404760197392561
123_56789: 0.07386595588397865
_23_5___9: 0.07341678097850937
___45_7__: 0.07330246913580248
1_3_56__9: 0.07330008763907941
_234____9: 0.07328818015546411
_2__567__: 0.07313100137174211
__3_567__: 0.07304526748971193
_2__5_7__: 0.0727880658436214
1_345_7_9: 0.07275551872173958
_23___78_: 0.07259516460905349
1_3__678_: 0.07195573273891175
123__6_89: 0.07108430339633186
1___567__: 0.07094478737997256
_234_6__9: 0.07092454465782655
_2_456_8_: 0.07084238302088096
123_5_789: 0.07046926716700443
__34__7__: 0.07021604938271606
12___678_: 0.07000885916780979
1__45_78_: 0.06935156607224509
12_45__89: 0.06898481557689376
_2____78_: 0.06893004115226338
12_456_89: 0.06876361201784394
12_4___89: 0.06864426154549612
1_3_5_7_9: 0.0676678478890413
1____6__9: 0.0676440329218107
12__567_9: 0.066553572033396
12_456789: 0.06616328986356984
1___56_8_: 0.06600794467306813
_2_4__78_: 0.06597222222222222
__34_67__: 0.06580075445816186
123____89: 0.06563404968754763
1___5___9: 0.06532921810699588
_234567_9: 0.065064827868945
_23__678_: 0.06492376828989484
1_____7_9: 0.06481481481481481
1__4__78_: 0.06481481481481481
__34_6_8_: 0.06421467764060357
1__45678_: 0.0640558119633694
1_____78_: 0.06404320987654322
_2_45_78_: 0.06395926211705533
12___67_9: 0.06390984606005182
123__6789: 0.06377419262556897
1__4_678_: 0.06361454046639232
12_45_789: 0.06343676614619496
12_4_6_89: 0.06338869519382208
__345__8_: 0.06280006858710563
_23_5678_: 0.06274972639248759
12__5__89: 0.06273100518213687
___4___8_: 0.0625
_2345_7_9: 0.06217294111669969
1_34__7_9: 0.06199988568815729
1_34_67_9: 0.06194034827008078
123___789: 0.06174089791952446
1_3___7_9: 0.06147119341563786
1_3__6__9: 0.061185413808870596
1_3_567_9: 0.06101725367914783
___4_67__: 0.06095679012345679
__3456_8_: 0.06081747256515775
12_4__789: 0.059479468322918255
1__4____9: 0.05941358024691358
_23_56__9: 0.059150821775135906
__3__6_8_: 0.05898491083676269
_2__5___9: 0.05829903978052126
1_3_____9: 0.058127572016460904
_23_5_78_: 0.058078751333638164
_2_45678_: 0.05803631438508696
1_3456_89: 0.057792707116123894
12_4_6789: 0.05765919445608732
1_3456789: 0.05712123927611046
_23_____9: 0.05667009602194788
_2_4____9: 0.056584362139917695
1__4_6__9: 0.05654149519890261
_234_67_9: 0.05588618668394046
___4567__: 0.05521262002743484
_2___6__9: 0.05486968449931413
1_34_6_89: 0.05464284693644261
__3___78_: 0.05452674897119342
1__4__7_9: 0.05452674897119342
12__56_89: 0.05439100365797896
1___5_78_: 0.05422668038408779
1_345__89: 0.05400500273078291
_234__7_9: 0.05385516689529035
_2__56_8_: 0.05374799954275263
_2___6_8_: 0.05354080932784636
_234___89: 0.053264555707971346
_23__6__9: 0.053169295839048926
_23456_89: 0.053167469289864724
12___6_89: 0.05277992112482853
1_34___89: 0.052476280292638317
__3_____9: 0.05246913580246913
1___56__9: 0.0515546410608139
_2345__89: 0.051522093938932076
__345678_: 0.051464210338024355
1_345_789: 0.05136939148701361
_____67__: 0.05092592592592592
1__45_7_9: 0.050740169181527205
_2_4_678_: 0.05071873571101966
1_3__67_9: 0.0505115454961134
_23_567_9: 0.050293506240579856
__345_78_: 0.05023291037951532
___45__8_: 0.05015432098765432
__34____9: 0.05015432098765432
12_____89: 0.0495827617741198
_23__67_9: 0.049516079865874106
_23_5_7_9: 0.04944939795762841
_2_456__9: 0.049435108977290046
12__5_789: 0.049042162017985065
1___5_7_9: 0.04835390946502058
1_34_6789: 0.04802238527536453
_23___7_9: 0.04801097393689986
1__4_67_9: 0.047603737997256514
_2_45___9: 0.04746799268404207
_2_4_6_8_: 0.04711434042066758
12__56789: 0.04694484253661272
_234_6_89: 0.04663397268582025
1__4567_9: 0.04660271554133008
1__45___9: 0.046553497942386834
______78_: 0.046296296296296294
1__456__9: 0.04626771833561957
_2345_789: 0.04617333682737124
__3_5___9: 0.04612482853223594
____567__: 0.04603909465020576
_2_4_6__9: 0.04585333790580704
__34_678_: 0.04538537379972565
___4_6_8_: 0.04513888888888889
1_3__6_89: 0.0448245313214449
_2__5_78_: 0.04479595336076818
__3_5__8_: 0.04415294924554184
1_3_56_89: 0.04403883586089519
__3456__9: 0.044031492912665754
1___5678_: 0.043892175354366715
_234_6789: 0.04323508990473543
1_3_56789: 0.04314002298114936
_2__5678_: 0.043071749733272366
1_3_5_789: 0.042827778624532166
__34__78_: 0.04282407407407408
_234__789: 0.04271306986570475
_____6_8_: 0.04243827160493827
1_3_5__89: 0.04227871132449322
_2__56__9: 0.04220964791952446
1_34__789: 0.04206636120002032
1_3____89: 0.04120941929583905
_2_____89: 0.04080932784636488
12____789: 0.04069501600365798
_2___678_: 0.04063786008230453
1______89: 0.04063786008230453
__3__678_: 0.040594993141289434
___456_8_: 0.04023062414266118
1___567_9: 0.04019490169181527
___4__78_: 0.040123456790123455
1____678_: 0.03982338820301783
_2_4567_9: 0.03940583244424122
__345___9: 0.039180384087791495
_2____7_9: 0.03909465020576132
_23_5__89: 0.038916831783772796
____5__8_: 0.038580246913580245
12___6789: 0.03834877866263611
__3___7_9: 0.03806584362139918
1____67_9: 0.03789437585733882
_2_4_67_9: 0.03756572930955647
1_3___789: 0.037508573388203015
__3_56_8_: 0.037365683584819384
__3_5678_: 0.03728590344459686
1__4_6_89: 0.037115626428898034
______7_9: 0.037037037037037035
_23_56_89: 0.03698671689331459
__34567_9: 0.03676673715896967
__3_5_78_: 0.03665123456790124
1_3__6789: 0.03618406429406087
__34_6__9: 0.03613683127572016
_23_56789: 0.035460574409953316
_2_4__7_9: 0.035322359396433474
1__456789: 0.03526990031583939
_23____89: 0.03526520347508002
1__456_89: 0.034516222755677485
___45_78_: 0.034486454046639234
_2_45__89: 0.034155426002133824
_____6__9: 0.033950617283950615
__345_7_9: 0.033936328303612255
_2_456_89: 0.03363745046486816
1__45_789: 0.03335821997408932
_2_45_7_9: 0.03335048010973937
1____6_89: 0.03335048010973937
_2___67_9: 0.03309327846364883
_2_4___89: 0.03277892089620485
_23___789: 0.03275034293552812
__3_5_7_9: 0.03249314128943759
1__4_6789: 0.03244015298734949
___45678_: 0.03230321692577351
1__4___89: 0.032064471879286696
__3_56__9: 0.03203589391860997
_23__6789: 0.03188718267879219
1__4__789: 0.031464334705075446
_23__6_89: 0.03136828100391201
_2__5__89: 0.03135002286236854
____56_8_: 0.03129286694101509
_23_5_789: 0.03112847751443716
_2_456789: 0.031084133163417953
___4_678_: 0.030907064471879287
_______89: 0.030864197530864196
____5___9: 0.030864197530864196
1___5__89: 0.030378372199359852
_2__567_9: 0.03027358634354519
1___56_89: 0.030142604023776862
1__45__89: 0.029913980338363056
__3__6__9: 0.029749657064471878
__3_567_9: 0.02932575064776711
___4_6__9: 0.029320987654320986
_2__5_7_9: 0.028978052126200273
__3____89: 0.02863511659807956
__34__7_9: 0.02863511659807956
_2_45_789: 0.02848084853257464
_2_4__789: 0.027825407712238986
___4____9: 0.027777777777777776
__3456_89: 0.02707933771105353
__34_67_9: 0.02700617283950617
__34___89: 0.026920438957475996
1_____789: 0.026748971193415638
__3456789: 0.02663997361654445
1___5_789: 0.02619170096021948
_2_4_6_89: 0.02610120408474318
_2____789: 0.025977366255144033
_2__56_89: 0.02591385967586242
_2_4_6789: 0.025903010635235143
__34_6_89: 0.02587972488949855
____5_78_: 0.0257201646090535
1___56789: 0.02559910519229792
____56__9: 0.025034293552812073
_2___6_89: 0.024805669867398263
___4__7_9: 0.024691358024691357
__3__67_9: 0.023834019204389576
__3___789: 0.022890946502057613
_2__56789: 0.022334470101102476
__345__89: 0.022181260478585582
__34_6789: 0.022077400760385443
___456__9: 0.021690672153635116
_2__5_789: 0.021676383173296752
___45___9: 0.021604938271604937
___4_67_9: 0.021433470507544582
__345_789: 0.021380945274263746
____5678_: 0.021219135802469136
1____6789: 0.02067615454961134
_____678_: 0.0205761316872428
____5_7_9: 0.0205761316872428
___4567_9: 0.020061728395061727
__34__789: 0.0200212429507697
_2___6789: 0.019618770004572475
__3_56789: 0.01871307357025521
___45_7_9: 0.018689986282578876
__3__6_89: 0.018489940557841793
__3_5__89: 0.017946959304983995
__3_5_789: 0.017630220240816948
__3__6789: 0.017211076817558298
____567_9: 0.016975308641975308
_____67_9: 0.01646090534979424
___4___89: 0.01646090534979424
__3_56_89: 0.016267210282985316
___4_6_89: 0.016032235939643348
______789: 0.015432098765432098
___456789: 0.015100806110179681
___4__789: 0.014660493827160493
___456_89: 0.014565233958238074
___4_6789: 0.014374714220393233
_____6_89: 0.013717421124828532
___45__89: 0.012259945130315501
___45_789: 0.012195644718792868
____5__89: 0.012002743484224965
____56_89: 0.011859853680841335
____56789: 0.010359510745313215
____5_789: 0.0102880658436214
_____6789: 0.009002057613168725

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment