Probability of winning "game of twelve" with optimal play

twelve.py

import itertools

dp = [0] * 2**12
dp[0] = 1
for state in range(1, 2**12):
    for d1, d2 in itertools.product(range(6), repeat=2):
        o = 0
        s = d1 + d2 + 1
        if s < 12 and state & (1 << s):
            o = max(o, dp[state & ~(1 << s)])
        if d1 != d2 and state & (1 << d1) and state & (1 << d2):
            o = max(o, dp[state & ~(1 << d1) & ~(1 << d2)])
        dp[state] += o
    dp[state] /= 36
print(dp[(1 << 12) - 1])