本記事はヨットで325点が達成される確率に関する記事です．
『世界のアソビ大全51』におけるルールを前提としますので，325点は達成可能な最大の得点になります．
この確率を最大化する戦略を採用した場合，3.610891364602\times{10}^{-15} となります．
既約分数で表すと，
\frac{319130499507922112188286628635683772218857335457720431310938791697014394461154989031483452803032063543337756165983}{88379978039869263971884965720466348182637029432792923611162733644394572938580364878372716876453932812064005444887830012255797248}
です．
解法
動的計画法で解きます．
達成済みの役（2^{12} 通り），出目の状態（不確定の目も考えて \binom{11}{5} 通り），振り直し回数（0, 1, 2）を管理します．
出目の状態にはあらかじめ連番のIDを振っておきます．出目の各状態に対しホールドによって遷移可能な状態のリスト，未確定の目が1つ確定した場合の遷移先と，各状態が各役を達成するか否かを前計算することで高速化します．
値は有理数を持ちますが，毎回Fractionの演算をやると遅くなります．常に分母は6の累乗としておいて最後に約分してやれば十分なので，そのような形式の有理数を扱うクラスを定義します．
コードはChatGPTにこれらの方針を与えて書かせた上で，一部修正して作りました．Colaboratoryで実行に1分くらいかかりました．
from __future__ import annotations
from functools import lru_cache
from fractions import Fraction
from typing import Dict, List, Tuple
# ============================================================
# SixFrac: exact rational number of the form a / 6^b
# - __add__: align exponents with powers of 6
# - div6(): divide by 6 via b += 1 only (do not touch numerator)
# ============================================================
MAX_B: int = 180
POW6: List[int] = [1] * (MAX_B + 1)
for i in range(1, MAX_B + 1):
POW6[i] = POW6[i - 1] * 6
class SixFrac:
__slots__ = ("a", "b")
a: int
b: int
def __new__(cls, a: int = 0, b: int = 0) -> SixFrac:
a_i = int(a)
b_i = int(b)
if a_i == 0:
b_i = 0
obj = super().__new__(cls)
obj.a = a_i
obj.b = b_i
return obj
def __hash__(self) -> int:
return hash((self.a, self.b))
def __add__(self, other: SixFrac) -> SixFrac:
if self.a == 0:
return other
if other.a == 0:
return self
if self.b == other.b:
return SixFrac(self.a + other.a, self.b)
if self.b < other.b:
diff = other.b - self.b
return SixFrac(self.a * POW6[diff] + other.a, other.b)
diff = self.b - other.b
return SixFrac(self.a + other.a * POW6[diff], self.b)
def div6(self) -> SixFrac:
if self.a == 0:
return self
nb = self.b + 1
if nb > MAX_B:
raise ValueError(f"Exponent too large: {nb} > {MAX_B}")
return SixFrac(self.a, nb)
def __lt__(self, other: SixFrac) -> bool:
if self.a == 0 and other.a == 0:
return False
if self.b == other.b:
return self.a < other.a
if self.b < other.b:
diff = other.b - self.b
return self.a * POW6[diff] < other.a
diff = self.b - other.b
return self.a < other.a * POW6[diff]
def __le__(self, other: SixFrac) -> bool:
return self == other or self < other
def __eq__(self, other: object) -> bool:
if not isinstance(other, SixFrac):
return False
if self.a == 0 and other.a == 0:
return True
if self.b == other.b:
return self.a == other.a
if self.b < other.b:
diff = other.b - self.b
return self.a * POW6[diff] == other.a
diff = self.b - other.b
return self.a == other.a * POW6[diff]
def to_float(self) -> float:
return self.a / POW6[self.b]
def __repr__(self) -> str:
return f"{self.a}/6^{self.b}"
# ============================================================
# State: counts of faces 1..6 with total <= 5
#
# We index **all** count-vectors (c1..c6) with sum <= 5:
# number of states = C(11, 5) = 462.
#
# Interpretation:
# sum(c1..c6) = k means "k dice are already fixed, and (5-k) dice are still undecided".
# The transition next_states() fixes one more die (adds 1 to some face).
# ============================================================
DiceCounts = Tuple[int, int, int, int, int, int]
StateId = int
N_CATS: int = 12
ALL_MASK: int = (1 << N_CATS) - 1
class State:
__slots__ = ("counts",)
counts: DiceCounts
def __init__(self, counts: DiceCounts) -> None:
assert len(counts) == 6
self.counts = counts
def __hash__(self) -> int:
return hash(self.counts)
def __eq__(self, other: object) -> bool:
return isinstance(other, State) and self.counts == other.counts
def total(self) -> int:
return sum(self.counts)
def is_5kind(self) -> bool:
return any(c == 5 for c in self.counts)
def is_small_straight(self) -> bool:
present = [1 if c > 0 else 0 for c in self.counts]
return (
(present[0] and present[1] and present[2] and present[3]) or
(present[1] and present[2] and present[3] and present[4]) or
(present[2] and present[3] and present[4] and present[5])
)
def is_big_straight(self) -> bool:
present = [1 if c > 0 else 0 for c in self.counts]
return (
(present[0] and present[1] and present[2] and present[3] and present[4]) or
(present[1] and present[2] and present[3] and present[4] and present[5])
)
def next_states(self) -> List[State]:
"""
If total < 5, fix one additional die as each face (6 successors).
If total == 5, there is no successor (already fully fixed).
"""
res: List[State] = []
if self.total() < 5:
for f in range(6):
n = list(self.counts)
n[f] += 1
res.append(State(tuple(n))) # type: ignore[arg-type]
return res
def unfix(self) -> List[State]:
res: List[State] = []
for f in range(6):
if self.counts[f] > 0:
n = list(self.counts)
n[f] -= 1
res.append(State(tuple(n)))
return res
def can_mask(self) -> int:
"""
Bitset of categories that can be taken *at perfect score* from this state.
Only meaningful when total == 5; otherwise returns 0.
"""
if self.total() != 5:
return 0
m = 0
# Upper: need 5-of-a-kind of that face.
for cat in range(6):
if self.counts[cat] == 5:
m |= (1 << cat)
# For 325-perfect, Choice/FourDice/FullHouse at max all require 66666.
if cat == 5:
m |= (1 << 6) | (1 << 7) | (1 << 8)
if self.is_small_straight():
m |= (1 << 9)
if self.is_big_straight():
m |= (1 << 10)
if self.is_5kind():
m |= (1 << 11)
return m
# ============================================================
# Enumerate all states with sum <= 5 (462 states), and build transitions
# ============================================================
ID_OF: Dict[State, StateId] = {}
STATE_OF: List[State] = []
def gen_compositions_upto(total: int = 5) -> List[State]:
"""
Generate all 6-tuples of nonnegative integers (c1..c6) with sum <= total.
Count is C(total+6, 6) = C(11, 5) = 462 when total=5.
"""
res: List[State] = []
cur = [0] * 6
def rec(i: int, rem: int) -> None:
if i == 6:
res.append(State(tuple(cur))) # type: ignore[arg-type]
return
for x in range(rem + 1):
cur[i] = x
rec(i + 1, rem - x)
rec(0, total)
return res
for st in gen_compositions_upto(5):
ID_OF[st] = len(STATE_OF)
STATE_OF.append(st)
N_STATES: int = len(STATE_OF) # 462
NEXT: List[List[StateId]] = [[ID_OF[nst] for nst in st.next_states()] for st in STATE_OF]
CAN: List[int] = [st.can_mask() for st in STATE_OF]
UNFIX: List[List[StateId]] = [[ID_OF[nst] for nst in st.unfix()] for st in STATE_OF]
START_ALL: StateId = ID_OF[State((0, 0, 0, 0, 0, 0))]
# ============================================================
# DP
# ============================================================
@lru_cache(maxsize=None)
def dp(mask: int, final_id: StateId, rerolls_left: int) -> SixFrac:
if mask == ALL_MASK:
return SixFrac(1, 0)
# In this representation, "final" means total == 5, i.e. NEXT[final_id] is empty.
if NEXT[final_id]:
raise ValueError("dp called with non-final state (total < 5)")
if rerolls_left > 0:
return best_hold(mask, final_id, rerolls_left)
eligible = CAN[final_id] & (~mask)
if eligible == 0:
return SixFrac(0, 0)
best = SixFrac(0, 0)
e = eligible
while e:
lsb = e & -e
c = lsb.bit_length() - 1
e -= lsb
nmask = mask | (1 << c)
val = roll_expect(nmask, START_ALL, 2)
if best < val:
best = val
return best
@lru_cache(maxsize=None)
def roll_expect(mask: int, start_id: StateId, next_rerolls_left: int) -> SixFrac:
# Once all categories are filled, remaining dice do not matter.
if mask == ALL_MASK:
return SixFrac(1, 0)
# total == 5 <=> fully fixed roll outcome -> hand off to dp
if not NEXT[start_id]:
return dp(mask, start_id, next_rerolls_left)
acc = SixFrac(0, 0)
for nid in NEXT[start_id]: # length 6 when total < 5
acc = acc + roll_expect(mask, nid, next_rerolls_left)
return acc.div6()
@lru_cache(maxsize=None)
def best_hold(mask: int, cur_id: StateId, rerolls_left: int) -> SixFrac:
"""
Decide which dice to keep by repeatedly 'unfixing' one die at a time.
cur_id: current kept-dice state (total<=5).
rerolls_left: rerolls available *before* performing the next reroll.
"""
# stop here: reroll the remaining dice once
best = roll_expect(mask, cur_id, rerolls_left - 1)
# or unfix one more die and continue deciding
for uid in UNFIX[cur_id]:
val = best_hold(mask, uid, rerolls_left)
if best < val:
best = val
return best
def prob_perfect_325() -> SixFrac:
return roll_expect(0, START_ALL, 2)
if __name__ == "__main__":
pr = prob_perfect_325()
print("Optimal probability of PERFECT 325 as SixFrac a/6^b:")
print(Fraction(pr.a, 6 ** pr.b))
print(f"approx = {pr.to_float():.12e}")