basic_probability.py

from fractions import Fraction

def demon_win_prob(n_players: int) -> Fraction:
    """
    Exact probability Demon wins under:
      - N players, 1 Demon
      - No kill Night 1
      - Day 1: random execution
      - Starting Night 2: Demon kills 1 each night (not self)
      - Each day: random execution EXCEPT:
          if the day would start with 4 alive, town skips execution,
          goes to night -> 3 alive, then does final 3 execution.
      - At 3 alive: final execution happens; Demon wins if not executed => 2/3
    """
    if n_players < 4:
        raise ValueError("Need at least 4 players for this model.")
    alive = n_players
    p = Fraction(1, 1) 

    # Day 1 execution (no Night 1 kill)
    p *= Fraction(alive - 1, alive)   # survive random execution 14/15
    alive -= 1 

    # Night/day cycles until we reach final 3
    while alive > 3:
        # Night kill (starting Night 2)
        alive -= 1  # Demon kills a good player

        if alive == 3:
            break

        # Day phase
        if alive == 4:
            # Town skips execution at 4, goes to next night to reach 3
            alive -= 1  # next night kill
            break
        else:
            # Random execution
            p *= Fraction(alive - 1, alive)
            alive -= 1

    # Final 3 execution
    p *= Fraction(2, 3)
    return p


if __name__ == "__main__":
    print("N\tP(win)\t\tapprox")
    for n in range(7, 16):
        p = demon_win_prob(n)
        print(f"{n}\t{p}\t{float(p):.6f}")