ゲーム状態の勝敗とGrundy数
概要
game状態・Grundy DP
各状態の勝敗またはGrundy数を後続状態から求める。
手を打てない側が負けるnormal playで、有限で非循環な局面遷移では、後続に必敗局面が一つでもあれば必勝、なければ必敗とする。独立なimpartial gameの和はGrundy数のXORで評価する。局面の符号化と勝敗を合成する原理を区別し、通常のNim型ゲームに部分集合DPの知識は要求しない。
ABC354 Eはこの勝敗再帰を残存カード集合へ適用する複合例である。主技法はゲームだが、問題は集合状態も学んだ位置に掲載する。集合の符号化をゲーム一般の前提へ引き上げない。
考え方
normal playの局面値を後続から定義する
二人が交互に合法手を選び、手を打てない側が負けるnormal playを扱う。impartial(不偏)とは、同じ盤面から選べる合法手が手番の人によらないことをいう。盤面を頂点、合法手を有向辺とした有限DAGで、後続がない終端は手番側必敗。終端から逆の依存順に「後続に必敗が一つでもあれば必勝、全て必勝なら必敗」と求める。
Grundy数はこの分類を独立和へ拡張する値である。集合Aに現れない最小の非負整数をmex(A)と定義し、g(v)=mex{g(u) | v→uが合法手} とする。例えばmex{0,2}=1、mex∅=0なので終端のgは0。定義から、g(v)と同じ値の後続はなく、0,…,g(v)−1は全て後続に現れる。従ってg=0からは必ず非零へ移り、非零からは0へ移れる。DAG上の帰納法により、単独局面はg=0なら必敗、非零なら必勝となる。
独立和のXORから勝敗と手を求める
独立和では、一手で一つの成分だけを動かし、他の成分の合法手は変わらない。各成分の値をg_1,…,g_mとし、X=g_1 XOR … XOR g_mとする。ABC229 H公式解説のXOR判定は、次の二方向で証明できる。
- X=0なら、一手で変える成分のg_iは必ず別の値hになるので、新しいXはg_i XOR h≠0。0から0へ移る手はない。
- X≠0なら、Xの最上位の1と同じbitを持つg_iを選ぶ。h=g_i XOR Xはg_iより小さいので、mexの定義により値hの後続が存在する。その手を選ぶと新しいXは0になる。
全成分が終端ならX=0で手番側が負け、全playは有限なので、X=0は手番側必敗、X≠0は手番側必勝と結論できる。実際の戦略は、上記のhを持つ後続を合法手から探して示せばよい。Grundy数は単なる勝敗bitではなく、和にしたときの振る舞いを保持する値である。
成立条件と計算量
局面数S・合法遷移数Tに対し、後続を先に評価する勝敗DPはO(S+T)。出次数t_vの局面ではmex≤t_vなので、0,…,t_vの出現だけをmarkして最初の欠番を探せばGrundy計算も合計O(S+T)。mark配列は局面ごとに必要範囲を初期化するかtimestampで再利用し、グラフと値の記憶はO(S+T)。盤面の列挙・合法手生成・状態圧縮の費用は別途含める。
有限・非循環・impartial・normal playと、和を使う場合の成分の独立性が全て必要。最後の手を打つ側が負けるmisère playでは、石一個を取るだけでもg=1による通常判定と実際の勝敗が逆になる。partizan game、循環局面、複数成分を同時に変える手にもこのXOR則をそのまま適用しない。
問題一覧
- ABC354 E「Remove Pairs」 公式問題組合せ: 部分集合・bitmask状態DP
技能・出典
主題: ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。)。既習技能: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。主タグ: game状態・Grundy DP / 補助タグ: 部分集合・bitmask状態DP
- ABC368 F「Dividing Game」 公式問題組合せ: 素因数分解と約数構造
技能・出典
主題: ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。主タグ: game状態・Grundy DP / 補助タグ: 素因数・約数分解
- ABC278 F「Shiritori」 公式問題組合せ: 部分集合・bitmask状態DP
技能・出典
主題: ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。)。既習技能: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。主タグ: game状態・Grundy DP / 補助タグ: 部分集合・bitmask状態DP
- ABC380 F「Exchange Game」 公式問題
- ABC297 G「Constrained Nim 2」 公式問題
- ABC278 G「Generalized Subtraction Game」 公式問題
技能・出典
主題: ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。)。既習技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: game状態・Grundy DP / 補助タグ: 対話protocolとquery設計、状態・配置の正規化
- ABC255 G「Constrained Nim」 公式問題
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC212 H「Nim Counting」 公式問題
技能・出典
主題: 分離可能線形変換・Walsh–Hadamard変換(Kronecker積で表される多次元線形変換を各軸の小変換へ分離し、stride走査で正変換または逆変換を計算できる。)。既習技能: ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。)。主タグ: 分離可能線形変換・Walsh–Hadamard変換 / 補助タグ: game状態・Grundy DP、法上の四則演算・高速累乗・逆元
- ABC265 Ex「No-capture Lance Game」 公式問題
技能・出典
主題: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。既習技能: 独立な数ゲームの和(全ての後続局面が数で、左選択肢の全値が右選択肢の全値より小さいことを確認し、その間の最も単純な二進有理数を局面値とする。独立和は厳密な数の加算で評価する。一般のpartisan gameは数とは限らず、この規則を適用しない。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。) / 分離可能線形変換・Walsh–Hadamard変換(Kronecker積で表される多次元線形変換を各軸の小変換へ分離し、stride走査で正変換または逆変換を計算できる。)。主タグ: 畳み込み・相互相関 / 補助タグ: 独立な数ゲームの和、game状態・Grundy DP、分離可能線形変換・Walsh–Hadamard変換
- ABC433 G「Substring Game」 公式問題
技能・出典
主題: Suffix Automatonで部分文字列集合を表す(endpos同値類を状態にし、suffix linkと必要なcloneを正しく作って全部分文字列の遷移を線形状態数で表せる。)。既習技能: ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。)。主タグ: Suffix Automaton / 補助タグ: game状態・Grundy DP
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。DAG上の勝敗再帰からGrundy数へ進み、独立なゲームの和をXORで評価する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-game
習得する技能
- 後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 最小十分状態からDPを設計する。
このUnitを直接前提とする単元: なし。
状態遷移を設計できることを前提に、後続状態の勝敗やGrundy数から現在局面を分類する。
このUnitでは扱わないもの
- 有限DAGの得点差minimax、循環ゲームの距離評価、独立な数ゲームの加算。