Skip to content →

二人零和有限確定完全情報ゲーム

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

後退解析

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

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

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

DAGの後退解析

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

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

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

問題1:石が \(N\) 個ある。交互に \(1\) 個以上 \(K\) 個以下の石を取り去る。石が取れなくなった方が負け。どちらが勝つか。\(O(1)\)で求めよ。(有名問題、yukicoder 8)

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

問題2:問題1において、取り去ったあとの石の個数が \(x_1, x_2, \ldots, x_M\) のいずれかになる操作が禁止されたとするとする。勝敗を \(O(M)\) で求めよ。(yukicoder 1313)

DAGの後退解析。

問題3:問題1において、相手が直前に取り除いた石と同数の石が取り除けない場合の勝敗を \(O(N)\) で求めよ。(yukicoder 1770)

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

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

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

問題4:問題2,3を合わせた場合について解け

解答略

問題5:問題1において、取り去ったあとの石の個数が2進表記したとき 1 が奇数個となる操作が禁止されたとするとする。勝敗を \(O(N)\) で求めよ。(SRM 701 Div2 Hard)

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

問題6:有向グラフ G の各頂点には数字が書いてある。頂点 1 に駒を置き、交互に

  • 駒を辺に沿って動かす。
  • ゲームを終了する。

のどちらかを選ぶ。十分長いターンが経ってもまだゲームが終了していないときは、強制終了する。ゲームが終了したときに、駒が置いてある頂点の数字(スコア)を先手は最大化、後手は最小化したい。数字はいくつになるか。(ARC038D)

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

問題11:
いくつかの根付き木が与えられる。交互に次のいずれかの操作を繰り返す。

  • 1ターン目ならば駒を好きな木の根に置く。
  • 葉でなければ、駒を子に移動する
  • 葉であれば、まだ選ばれていない木の根に駒を移動する

操作できなくなったほうが負け。どちらが勝つか。
(Kupc2019E)

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

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

(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\) が比較不能が成り立つようなものが存在する。

問題13:
N 個の石が相異なる非負整数座標 \(x_1, x_2, \ldots, x_N\) (\(0 < x_1 \leq \cdots < x_N\)) に置かれている。交互に、最も大きい座標に置かれている石を、他の石と重ならないように、より小さい非負整数座標に置き換える。操作できなくなったほうが負け。どちらが勝つか。
(ARC137C)

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

問題14:木の根以外の頂点に得点が書き込まれている。駒が根においてある。次の手順をゲーム終了まで繰り返す。

  • 先手は好きな頂点を1つ選び書き込まれた数字を零にする。
  • 後手は子に駒を移動する。葉に移動した場合はゲーム終了。葉でもなくとも、後手の意思で終了にできる。

ゲーム終了時点で駒がある頂点に書き込まれた数字が得点になる。先手は得点を最小化、後手は得点を最大化したい。何点になるか。(ABC246G)

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

問題12:
\(a_1, a_2, \ldots, a_N\) 個の石からなる山が \(N\) 個ある。Aさんは右端の山から好きな個数の石を取ることができ、Bさんは左端の山から好きな個数の石を取ることができる。交互に操作を行う。操作できなくなったほうが負け。どちらが勝つか。
(AGC048D)

指せる手の単調性より

  • \(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)\) で求まる。

不変量に着目する

二部グラフ

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

問題8:H 行 W 列のマスがある。N 個の駒を \((x_i, y_i)\) \((1 \leq i \leq N)\) に置いた。交互に駒を一つ選んで一つ左か下に動かすことを繰り返す。同じマスに複数の駒をおいてはいけない。操作ができなくなったほうが負け。どちらが勝つか。(yukicoder2951)

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 \) 先手必勝 が予想される。実際に正しいことが証明できる。

問題15:グリッドグラフの部分グラフと、非隣接な頂点 s, t が与えられる。交互にグラフの頂点を削除する。自分の操作で頂点 s, t を非連結にした方が勝ち。先手と後手のどちらが勝つか。(UTPC2021L)
  • s, t の点連結度が1のとき先手の勝ち。
  • s, t の点連結度が2のとき、点連結度を1にしたほうが負けなので、その直前では、2つの内素な s-t パスだけになる。二部グラフなので、このときの頂点数はそれまでの操作によらない。従って勝敗も O(1) で分かる。

グリッドグラフ

先手は1×1の白のパーツ、後手は1×1の黒のパーツをお互いに重ならないように置く。2×2の自分の色ができた方が勝ち。引き分けになることを示せ。

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

先手は1×2または2×1の白のパーツ、後手は1×2または2×1の黒のパーツをお互いに重ならないように置く。1×5または5×1の自分の色ができた方が勝ち。引き分けになることを示せ。
先手は1×1の白のパーツ、後手は1×1の黒のパーツをお互いに重ならないように置く。1×5または5×1の自分の色ができた方が勝ち。黒の2×2が白の2×2より先に発生しないような後手の手順が存在することを示せ。

偶奇

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

問題7:正整数列が与えられる。次のどちらかの操作を交互に行う。

  • すべての要素を 1 減らす。全ての要素が正整数である場合のみこの操作ができる。
  • 正整数を一つ選び、1 減らす。

操作ができなくなった方が負け。どちらが勝つか O(1) で求めよ。

(KUPC2020春E)

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

問題9:全要素の gcd が 1 であるような数列 A がある。交互に2以上の要素を選んで 1 減らしたあとに、全体を gcd(A) で割ることを繰り返す。操作できなくなったほうが負け。どちらが勝つか。(AGC010D)

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

問題10:それぞれ、\(a_i\) 個の石(\(1 \leq i \leq N\))からなる山がある。先手と後手は交互に次のどちらかの操作をする。

  • 山を2つに分割する。
  • 各山から石を一つ取り除く。ただし、各山に2つ以上の石がなくてはならない。

操作できなくなったほうが負け。どちらが勝つか。(出典 : yukicoder1852)

(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)\) の偶奇で勝敗が決する。

問題16:
グラフGが与えられる。交互に辺を追加する。連結になった方が負け。どちらが勝つか。
(AOJ2376)

連結になる直前の連結成分の大きさが 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つ以上にして相手に渡せる。他のケースはこれを元に理詰め。

問題:
グラフGが与えられる。偶点を交互に取り除く。行動できなくなったほうが負け。どちらが勝つか。

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

グラフ理論

グラフGが与えられる。先手と後手は交互に辺を選ぶ。全ての操作が終わった後、後手が選んだ辺が全域グラフであれば後手の勝ち。後手が勝つための必要十分条件はGに辺素な2つの全域木が取れることであることを示せ(Lehman)。

Nim

一山崩し

与えられた \(S \subseteq \mathbb{N}\) から好きな数 \(x\) を選んで交互に \(N \leftarrow N – x\) とする。それ以上操作できなくなった方が負け。

\(\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\) の山がある。「片方から好きな個数の石を取り除く」「両方から同じ個数の石を取り除く」の何れかができる。操作できなくなった方が負けである場合、どちらが勝つか(Wythoff’s game)

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

複数山崩し

石の個数が \(x_1, x_2, \ldots, x_n\) 個の山がある。先手は山を一つ以上選びそれぞれから \(a\) 個の石を取り去る。後手は山を一つ以上選びそれぞれから \(b\) 個の石を取り去る。操作できなくなった方が負けであるとき、勝つのはどちらか(ARC143C)。

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

非不偏ゲーム

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

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

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

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA