dynamic_programming.py

from functools import lru_cache
from fractions import Fraction

def evil_team_size(n_players: int) -> int:
    if 13 <= n_players <= 15:
        return 4  # demon + 3 minions
    elif 10 <= n_players <= 12:
        return 3  # demon + 2 minions
    elif 7 <= n_players <= 9:
        return 2  # demon + 1 minion
    else:
        raise ValueError("Defined for 7..15 only.")

@lru_cache(None)
def f(g: int, m: int) -> Fraction:
    """
    Exact P(evil wins) from the start of a day
    with g goods alive, m minions alive, demon alive.
    """
    if g == 0:
        return Fraction(1, 1)  # all alive are evil -> immediate evil win

    T = g + m + 1

    # Final 3: execute once; if demon not executed -> evil wins
    if T == 3:
        return Fraction(2, 3)

    # Skip at 4: go to night immediately; demon kills a good
    if T == 4:
        return f(g - 1, m)

    # Normal day execution (T > 4)
    # Demon executed: prob 1/T => contributes 0
    p = Fraction(0, 1)

    # Minion executed -> night kill good => (g-1, m-1)
    if m > 0:
        p += Fraction(m, T) * f(g - 1, m - 1)

    # Good executed -> if g==1 -> evil immediately; else night kill => (g-2, m)
    if g == 1:
        p += Fraction(g, T) * Fraction(1, 1)
    else:
        p += Fraction(g, T) * f(g - 2, m)

    return p

def evil_win_prob_for_n(n_players: int) -> Fraction:
    e = evil_team_size(n_players)
    g0 = n_players - e
    m0 = e - 1
    f.cache_clear()
    return f(g0, m0)

if __name__ == "__main__":
    for n in range(7, 16):
        p = evil_win_prob_for_n(n)
        print(f"N={n}: evil win = {p} ≈ {float(p):.6f}")