二人零和有限確定完全情報ゲームで、かつ、グランディー数が関係しないものを解析する。今の所、過去問並べただけ。

後退解析

遷移が有向グラフ \(G\) で表されるゲームの勝敗は \(v \in V(G)\) について

• \(v\) が負けのとき、\(v\) に遷移可能な頂点 \(\delta^-(v)\) は勝ち
• \(v\) から遷移可能な頂点 \(\delta^+(v)\) が全て勝ちのとき、\(v\) は負け

である。ゲームの終了条件が決められている頂点から順に決定すればよい。勝敗の確定しなかった頂点は、勝敗の確定しなかった頂点に遷移するのが最適である。従って、永遠に勝敗が決まらない。将棋ではこのような状態を避けるため、同一局面が4回現れると引き分けとする、千日手が設定されている。

DAGの後退解析

DAGの場合、後退解析は簡略化できる。閉路が存在しないので、勝敗が決まらない頂点は存在しない。

1. ゲームの終了状態に、勝敗を割り振る。
2. 勝敗が未確定の頂点を、一時的に、負け状態と仮定する。
3. トポロジカル順序の逆順に頂点 \(v\) を見る。
4. \(v\) が勝ちなら何もしない。\(v\) が負けなら、\(v\) に遷移可能な頂点を勝ちにする。

トポロジカル順序が自明ならば、手で勝敗が簡単に書き下せる場合がある。

DAGの後退解析をすればよい。先手の敗北条件は \(N = 0 \pmod {K+1} \) である。

DAGの後退解析。

DAGの後退解析。「直前に相手が \(x\) 個取り除いてなければ」勝ちという条件を論理和で配るので、各頂点の状態は

• 直前に相手が何個取り除いていようが、負け
• 直前に相手が \(x\) 個取り除いていれば、負け
• 直前に相手が何個取り除いていようが、勝ち

のいずれか。１つ目の状態が最短でも K+1 個おきにしか起きないので、更新回数は全体で \(O(N)\) になる。

解答略

DAGの後退解析。問題2の類題。

スコアについて二分探索すると後退解析になる。

木の根を選び、葉まで駒を動かしてから、次の根を選ぶのが先手後手のどちらになっているか考える。

• 先手の意思で、先手後手を入れ替えることができる
• 先手の意思で、先手後手をそのままにすることができる

(True, True) を選ぶと先手の勝ち。(False, False) を選ぶと後手の勝ち。従って (False, False) が選ばれるのは最後。(True, False) ならば先手後手は必ず入れ替わる。(False, True) ならば先手後手は必ずそのまま。従って、(False, True) は勝敗と無関係。

勝敗の単調性

あるパラメータ A が大きいほど先手が有利ならば、

• \(f_1(S, a) :=\) 状態 S でパラメータ A = a のときの勝敗

を持つ dp から

• \(f_2(S) :=\) 状態 S のとき、先手が勝つための A の最小値

を持つ dp に変更でき、状態数が減らせる。

X さんにとっての必勝法が存在するゲームを考える。X さんにとって、局面 \(B\) が局面 \(A\) と比べて劣勢であるとする。ならば、\(A\) に遷移した後に、\(B\) に遷移しないような必勝法が存在する。つまり、Xさんにとって B が A に比べて劣勢であるとき、\(A < B\) と定めると、局面が \(G_1, G_2, \ldots \)の順で遷移して、 \(i < j\) のとき \(G_i > G_j\) または \(G_i, G_j\) が比較不能が成り立つようなものが存在する。

単調性より、\(x_N\) が大きいほど先手が有利。戦略盗みにより、\(x_N-x_{N-1} \geq 2\) ならば先手の勝ち。さもなくば、\(x_N-x_{N-1} =1\) を保ちながら遷移するしかないので、最適手は \(O(N)\) でシミュレートできる。

得点はX点以上か？について二分探索して、後退解析。取り除ける頂点が多いほど先手は有利なので、dp[v] := (頂点 v の部分木でゲームをしたとき得点を X 未満にするには、予め何個の頂点の得点を零にしておく必要があるか) について dp ができる。

指せる手の単調性より

• \(a_1\) が大きいほど A さんが有利
• \(a_N\) が大きいほど B さんが有利

だから、操作は

• 山から石を一つだけ取る
• 山から石を全て取る

のどちらかであるとしても勝敗は変化しない。

• 残っている山が \(l, \ldots, r\) 番目で、\(l\) 番目の山以外は初期状態と石の個数が同じである。A さん先手で、A さんの勝ちとなる \(a_l\) の最小値 \(f(l, r)\)
• 残っている山が \(l, \ldots, r\) 番目で、\(r\) 番目の山以外は初期状態と石の個数が同じである。B さん先手で、B さんの勝ちとなる \(a_r\) の最小値 \(g(l, r)\)

\(f(l, r-1), g(l+1, r)\) から \(f(l, r), g(l, r)\) が \(O(1)\) で求まる。

不変量に着目する

二部グラフ

二部グラフ上のゲームの場合、各部集合が何らかの不変量と関連していることが多い。特に、グリッドグラフが頻出である。

H = 1 の場合を考える。N = 1 のときは先手必勝。N = 2 のときは、

• (x+y) mod 2 = 0 に置かれた駒の個数 A
• (x+y) mod 2 = 1 に置かれた駒の個数 B

について、\(A \neq B \Leftrightarrow \) 先手必勝。一般の N について、(A, B) は、駒を動かすたびに (-1, 1), (1, -1), (-1, 0), (0, -1) の何れかが足される。A-B には、-2, 2, -1, 1 が足される。従って、\(A – B \neq 0 \pmod 3 \Leftrightarrow \) 先手必勝 が予想される。実際に正しいことが証明できる。

• s, t の点連結度が1のとき先手の勝ち。
• s, t の点連結度が2のとき、点連結度を1にしたほうが負けなので、その直前では、2つの内素な s-t パスだけになる。二部グラフなので、このときの頂点数はそれまでの操作によらない。従って勝敗も O(1) で分かる。

グリッドグラフ

上手くマッチングを作る。

偶奇

偶奇が不変量に関連していることがある。

（最小値、総和）の偶奇の遷移は下図のようになる。\(N\) の偶奇によらず二部グラフになる。最小値 0 だと、全要素を 1 減らす遷移ができないが、可能な遷移は部分グラフであるので、なお二部グラフである。

gcd で割らなければ、\(\sum (A_i – 1)\) 回操作ができる。gcd は常に奇数なので、\(A_i, A_i/\mathrm{gcd}(A)\) の偶奇は同じ。従って、\(\sum (A_i – 1) = 1 \pmod 2 \Leftrightarrow\) 先手の勝ち。

(i) : \(\min(a)=1\) のとき、 \(S := \sum (a_i-1)=1 \Leftrightarrow \) 先手の勝ち。
(ii) : \(\min(a) > 1\) のとき、\(a_1\) を \(1, a_1-1\) に分割すると、(i) の \(S \leftarrow S-1\) の場合に帰着される。従って、\(S\) が奇数なら先手の勝ち。さもなくば、\(\forall i, a_i \leftarrow a_i-1\) の操作しか先手はできず、後手に \(S \leftarrow S-N\) の状態で渡される。\(N\) が奇数なら、先手の負け。\(N\) が偶数なら、\(\min(a)\) の偶奇で勝敗が決する。

連結になる直前の連結成分の大きさが k, n-k とすると、追加された辺の本数は n(n-1)/2-|E|-k(n-k) である。n が奇数ならば、連結成分は偶数と奇数の大きさが一つずつなので、 n(n-1)/2-|E| = 0 mod 2 ⇔ 先手勝利　である。

• 偶サイズの連結成分の個数
• 奇サイズの連結成分の個数
• 連結成分の個数を変えずに追加できる辺の個数の偶奇

偶と偶をマージ (-1, 0, 1)
偶と奇をマージ (-1, 0, 1)
奇と奇をマージ (1, -2, 0)
連結成分内で辺を追加 (0, 0, 1)
これより、(0, 0, 0) のほうが (1, 1, 0)より作りにくそうに見える。奇成分は常に偶数個あるから、実際、偶数が一つでもある状態で回ってこれば、偶数が2つ以上にして相手に渡せる。他のケースはこれを元に理詰め。

偶点の偶奇 \(a\) は \(|V|-\sum_v d(v) = |V|-2|E|\) に等しい。偶点 \(v\) を除くと \(a \leftarrow a-1-2d(v) \bmod 2\) となるから、\(a\) の偶奇で勝敗が決まる。

グラフ理論

Nim

一山崩し

\(\forall, x \in S, \exists y ∈ S, x + y = C\) ならば周期 \(C\) と分かる。また、\(\{1, 2, \ldots, k\} \subseteq S\) かつ \(\forall x ∈ S \setminus \{1, 2, \ldots, k\}, (k + 1) | x\) ならば、\(N = 0 \pmod {k + 1}\) ⇔ 後手勝ち である。

\(\#S \leq 2\) の時の勝敗は？
\(S = \{a, b\}\) と置く。\(a < b\) としてよい。\(N \leftarrow N \bmod {(a+b)}\) としても勝敗は変わらない。\(N < b\) かつ \(\lfloor N/a \rfloor =1 \pmod 2\) または \(b \leq N < a + b\) のとき先手勝ち。

二山崩し

\((a, b)\) の遷移をマス目上に書いてみると、\(x_i = \mathrm{mex}(x_1, x_2, \ldots, x_{i-1}), y_i = i+x_i\) によって定まる二つの山 \((x_i, y_i)\) が負けであることが分かる。

複数山崩し

図より\(a \leq b\) のときの勝敗が分かる。\(a > b\) のときは、相手に \([0, b)\) を可能な限り多く、\([b, a+b)\) を可能な限り少なくして渡したいことから最善の一手目が定まる。あとは後手の勝敗として \(a \leq b\) のときの結果を使えばよい。

非不偏ゲーム

左右のそれぞれが先手のときの勝敗を個別に分析する必要はない。

• 左右のうち、右が先手の時の勝敗が完全に分かっている。
• そのことから、左が先手のときの最善の一手目が得られる。

このとき、左が先手の時の勝敗が完全に得られる。（Xならば確実に勝つ/負ける）という条件が存在する方が条件が簡単になりやすく、そちらを主にして勝敗を分析するとよい。