-
-
Save jhwaters/69764363c6d7f0dbeb77786cb925e98b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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):