Grundy number - ペケンペイのブログGrundy number (Nimber) について説明する。 Nimber - Wikipedia Sprague–Grundy theorem - Wikipedia Grundy number はゲームにおいて先手・後手必勝の判定に使われる。Grundy number は「現在の状態から遷移できる状態達の Grundy number の中に存在しない最小の自然数」として再帰的に定義される。形式的に定義するならば、ゲームの状態全体 $S$ に対して Grundy number は関数 $g\colon S \to \mathbb{N}$ であり以下で定義されるものである。 \begin{align} g(x) = \mathrm{mex}\{g(x') \mid x' \in N(x) \} \end{align} ここで $N(x)$ は $x$ から遷移できる状態全体の集合であり
