riddler_classic_2018_04_13.py

## riddler_classic_2018_04_13.py
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)))