ゲーム状態の勝敗と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則をそのまま適用しない。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(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、循環ゲームの距離評価、独立な数ゲームの加算。

根拠