できてへんやんけーッ!! 基本的な2人ゲームが～～～～!!

自分は競プロにおいて、2人ゲームの問題が非常に苦手です。Writer各位は僕を潰したければ2人ゲームを出すことを推奨します。

これを反省して、2人ゲームの必勝法の証明の流れと、3種類の「基本的な2人ゲームの勝ち方」(手順復元含め)を紹介していきます。

1. 2人ゲームの必勝法の証明の流れ

2人ゲームの必勝法の証明をする時は、大まかに以下のような形になります。

1. ゲームにおいて何かしらの状態Xを見つける。状態Xを手番で貰った人は負けである。

2. 状態Xでないものを手番で貰った人間は、必ず状態Xで返せることを示す。(勝ち側の証明)

3. 状態Xを手番で貰った人間が、状態Xで返すことが不可能であることを示す。(負け側の証明)

この具体的な適用を含め、以降では3つの基本的なゲームに勝利していきます。

2. 「基本的な2人ゲームの勝ち方」

2-1. トポソ可能な有向グラフで駒を動かすゲーム

図のようなトポロジカルソート可能な有向グラフ上で以下のゲームを行う。

• 最初、駒が1つ、頂点S上にある。
• 先手後手交互に、駒を辺に沿って動かす。
• 駒が動かせなくなったプレイヤーが負け。

(グラフの頂点が斜めに並んでいるのは辺を書き込みやすくするためで、(前の要素 -> 後ろの要素)の辺しかない二次元配列でも同じようなゲームができます)

このゲームの必勝法は以下です。

• まず、それ以上移動できない頂点に L (Lose)のラベルを付ける。
• ある頂点について、そこから移動できる頂点全てにラベルが付いたら、以下の判定を行う。
• そこから移動可能な L のラベルが付いた頂点が1つでもあるなら、W (Win)のラベルを付ける。
• L のラベルが付いた頂点に移動できないなら、 L のラベルを付ける。
• 最終的な勝敗は、頂点 S についたラベルで決まる。これが W なら先手必勝、 L なら後手必勝である。

ラベルをつけたグラフはこんな感じ。

実装は、「ラベルがまだ付いていない移動可能な頂点数」を管理しながら、頂点 \(V\) にラベルを付ける際に \(X \rightarrow V\) 辺がある頂点 \(X\) の「ラベルがまだ付いていない移動可能な頂点数」を1つ減らし、これが0になればqueueに入れる…といったことをすると \(N\) 頂点 \(M\) 辺のグラフについて \(O(N+M)\) で可能です。

手順の復元は、以下のような感じでできます。

(勝ち側)どこでもいいので、Lのついた頂点に移動させる。この条件を満たす頂点ならどこに動かしてもよい。

(負け側)Wのついた頂点に移動せざるを得ず、どの頂点を選択しても以降の流れで相手に負かされる。

証明は以下のような感じ。

1. 状態X「Lのついた頂点に移動させられない」⇔「そこが L の頂点である」状態Xを手番で貰った人は負けである。

2. (勝ち側の証明) 状態Xでないなら、その頂点はラベル W で、これは定義からどこかしら L のついた頂点に移動可能である。

3. (負け側の証明) 状態Xなら、その頂点はラベル L で、もしそこからどこにも動けないなら負けである。動ける頂点があったとしても、これも定義から W の頂点に移動させざるを得ず、その頂点はどこかしら「Lのついた頂点に移動させられる」ので、状態Xでない。

2-2. 最大化 vs 最小化 : 「今ここでやめたらN点」ゲーム

長さ \(L\) の得点表 \(A=\{A_1,A_2,...,A_L\}\) がある。これを使って2人で以下のようなゲームを行う。

• 最初、得点表の \(A_1\) を矢印が指している。
• 先攻後攻交互に、「やめる」か「続ける」かを選ぶ。
• もし「やめる」場合、現在矢印が指している得点が確定し、ゲームが終了する。
• 「続ける」場合、得点表の矢印を \(A_i \rightarrow A_{i+1}\) と移動させて、相手に手番を回す。但し、矢印が既に \(A_L\) を指している場合、「続ける」ことはできない。
• 先攻は得点を最大化、後攻は得点を最小化する。この時、両者が最適に行動した場合の得点を求めよ。

このゲームの得点を求めるには、以下のように得点表を後ろから辿ってやればよいです。

\(A_L\) を指して辞めざるを得なくなった手番の方の仮得点を \(A_L\) とする。

そこから得点表を以下のルールで遡る。

• 先攻の場合、仮得点を \(max(\)後攻の仮得点\(,A_i)\) とする。
• 後攻の場合、仮得点を \(min(\)先攻の仮得点\(,A_i)\) とする。

最終的な得点は、先攻の最終的な仮得点になる。

証明は、ざっとこんな感じです。

各々のプレイヤーについて、今やめて決まる得点が相手の仮得点と同じかそれより良いなら、今やめるべきである。そうでなければ、今やめても損なので、相手に手番を渡して相手に決断させた方が得である。

復元は簡単で、求まった得点で「やめられる」タイミングのうち一番最初でゲームをやめることになります。

2-3. Nim

石の山が \(N\) 個ある。 \(i\) 番目の山の 石の数は\(A_i\) である。

この石の山たちに対して、先攻後攻交互に以下の操作を行う。

• 石の山をどれかひとつ選び、そこから1つ以上の石をとる。とる石の数に上限はない。 

先に操作ができなくなった方が負けである。

結論が有名なので結論から言うと、 \(A_1\ xor\ A_2\ xor\ ...\ xor\ A_N\) が \(0\) なら後手必勝、そうでないなら先手必勝です。

「\(A_1\ xor\ A_2\ xor\ ...\ xor\ A_N = 0\)」 を状態Xとして証明に代入してみて、それを示しながらゲームも復元していきます。

1. 状態X「\(A_1\ xor\ A_2\ xor\ ...\ xor\ A_N = 0\)」 状態Xを手番で貰った人は負けである。

2. 状態Xでないものを手番で貰った人間は、必ず状態Xで返せることを示す。(勝ち側の証明)

3. 状態Xを手番で貰った人間が、状態Xで返すことが不可能であることを示す。(負け側の証明)

負け側の証明は簡単です。まず、全ての山の石が \(0\) の場合は操作が不可能となり負けです。そうでない場合でも、xorが0の状態で手番を貰った場合、どれか1つの山の石の数の少なくとも1つのbitを石をとることによって反転させてしまうので、全体のxorは0でなくなってしまいます。

勝ち側の証明(と復元)は少しだけ難しいです。

大まかな流れだけ理解するなら図を見ていただけるとわかりやすいです。

まず、全体の xor をとります。これは、仮定より非0です。

次に、全体のxorの最上位bitを見つけます。

そして、そのbitが立っている要素を任意に1つ見つけます。(これは、xorの定義より最低1つは存在します)

その要素に全体のxorをxorすると、その要素は必ず元の要素より小さくなり、全体のxorは0になります。(図では、 1100(12) に 0100(4) を xor している)

全体の xor が0になることを示すのは簡単で、(全体のxor) xor (全体のxor) = 0という関係を利用して変動します。

全体のxorを最上位bitが1の要素にxorすると必ず元の値より小さくなることは、そのbitによって減少する値が \(2^k\) なのに対して、それ以下のbitの値の影響はすべて \(0 \rightarrow 1\) という変動を起こしたとて \(2^k - 1\) となるので、その要素の値は減少します。

(実装では、「bit i が立っている要素の添え字」をsetなどのデータ構造を使って管理するなり、Queueをいい感じに活用したりすると高速にできます。)