Compute probability of winning High Rollers dice game.

rollout.py

from fractions import Fraction
from functools import lru_cache
from itertools import *

def powerset(S):
    return chain.from_iterable(combinations(S, r) for r in range(len(S)+1))

@lru_cache(maxsize=512)
def p(S):                     #  S is a frozenset so it can be cached
    if len(S) == 0:
        return Fraction(1)

    total = Fraction(0)
    for d1 in [1,2,3,4,5,6]:
        for d2 in [1,2,3,4,5,6]:
            roll = d1 + d2
            moves = [set(T) for T in powerset(S) if sum(T) == roll]
            if len(moves) == 0:
                score, move = 0, None
            else:
                score, move = max(zip(map(lambda T: p(S-T), moves), moves))
            total += score * Fraction(1,36)
    return total

prob = p(frozenset([1,2,3,4,5,6,7,8,9]))
print("exact value: ", prob)
print(" as a float: ", float(prob))
print("1 chance in: ", 1/float(prob))