1.「数研部員と勝負！」とは？

開成の文化祭では, 毎年「数研部員と勝負!」というゲームをやっている. 例年, ゲームの問題が 3 問ほど出され, 来た人は数研部員と対戦する.

「数研部員と勝負!」で出される問題の例 (2017 問題 2)

最初石が $50$ 個あり, カウンターの値は $10$ である. 各プレイヤーは, 自分の番のとき「石の数をカウンターの値だけ減らす」「カウンターの値を $1$ 減らす」のいずれか 1 つを選んで操作する. 先手と後手は交互に自分の番が来る. 石の数を $0$ 未満にすることやカウンターの値を $0$ にすることができないとき, 先に操作を行えなくなった人が負けとして, 先手・後手のどちらが勝つか？

2. 完全情報ゲーム

「完全情報ゲーム」は, プレイヤーの手番の時に, その前に各プレイヤーが行った選択 (or 意思決定) すべてを知っている, というゲーム.

• 完全情報ゲームの例: チェス, オセロ, 3 目並べ, すごろく など
• 完全情報ゲームではない例: じゃんけん, ポーカー など

この講義で扱う (+「数研部員と勝負！」に出せる) 問題は、次のようなゲームである.

• 完全情報ゲーム
• どのゲームにも「勝ち」「負け」(+ 引き分け?) が定義される
• 最初の状態も含めて, 確率や運の要素がない
• 2 人で対戦するゲーム

「数研部員と勝負！」には引き分けのあるゲームを入れてもいいです (もちろん, 両者が最適に行動した際にどちらかが勝たなければならないですよ!?) が, この講義では「勝ち」「負け」が決まっているものに限定する.

3. ゲームの「状態」と「勝敗」

ゲームの途中の状態に対して,「この状態で自分の番になって, この後両者ともに最適な戦略を取ったとき, 自分・相手どちらが勝つか？」を考える. もし自分が勝てるとしたら W (winning state), 相手が勝てるとしたら L (losing state) とする. ゲームの最初の状態が W であれば「先手必勝」, L であれば「後手必勝」となる.

ゲームの状態「W」と「L」の関係

(a) W の状態で, 明らかな勝ちではない場合は, 次のターンで L の状態に持ち込める方法がある.
(b) L の状態で, 明らかな負けではない場合は, どの操作をしても, 次の状態は W になる.

これを利用することで, 先ほど挙げた問題 (「数研部員と勝負！」2017 問 2) を解くことができる.

4. ゲームの戦略 〜物真似戦略〜

物真似戦略は, ゲームが「対称」であるときに使える戦略のテクニック. 後手が先手の動きに対応する操作をして後手が勝つ, あるいはその逆のパターンもある.

物真似戦略を使える問題

$25$ 枚のコインが 1 列に並べられている. 最初, すべてのコインは表を向いている. これを使ってゲームを 2 人で行う. 各プレイヤーは, 自分の番のとき,「表を向いているコインの中で, 隣に表を向いているコインが少なくとも $1$ つあるものを選び, これを裏返す」という操作を行う. 操作を行えなくなった方が負けとするとき, どちらのプレイヤーが勝つか?

5. Nim

Nim は, 組み合わせゲーム理論の中でも重要なゲームである. これは次のようなゲームである.

「$n$ 個の石の山があり, それぞれ $a_1$, $a_2$, $\dots$, $a_n$ 個の石がある. これを使って 2 人でゲームを行う. 各プレイヤーが自分の番でする操作は, 『石山を 1 つ選び, これに含まれている石を $1$ つ以上 (全部でもよい) 取り除く』 である. 操作を行えなくなった方が負けである.」

例えば, $n=3$, $a=(3,4,5)$ のとき,「石山が $3$ 個あり, それぞれ $3$, $4$, $5$ 個の石がある」という状態からゲームを始める.

• (例 1) $n=3$, $a=(3,4,5)$ で勝てるのはどちらか?
• (例 2) $n=3$, $a=(3,5,6)$ で勝てるのはどちらか?

XOR とは?

XOR (排他的論理和, exclusive or) は次のように定義される.

例えば, $3 \operatorname{XOR} 5 = 6$ です. なぜなら, $3 = {011} _ {(2)}$, $5 = {101} _ {(2)}$ と表され, 同じ位置にある桁の値が違うのは $2^1$, $2^2$ の位なので, この XOR は $2^1+2^2=6$ となる.

また, XOR は足し算や掛け算と同じように, 交換法則 ($x \operatorname{XOR} y = y \operatorname{XOR} x$) と結合法則 ($(x \operatorname{XOR} y) \operatorname{XOR} z = x \operatorname{XOR} (y \operatorname{XOR} z) = x \operatorname{XOR} y \operatorname{XOR} z$) が成り立つ.

Nim の勝敗

$a_1 \operatorname{XOR} a_2 \operatorname{XOR} a_3 \operatorname{XOR} a_4 \operatorname{XOR} \cdots \operatorname{XOR} a_n = 0$ のときに限って後手必勝で, そうでないとき先手必勝であることが知られている. 今からこのことを証明してみよう.

証明

まず, 最適な戦略は, XOR が $0$ 以外のときに $0$ にすることで, 次の人の番 (XOR が $0$ のとき) の操作では XOR が $0$ 以外の状態にしかできない, ということを繰り返すものである. 最終的に負けるのは XOR が $0$ のときなので, その戦略を使えば XOR が $0$ 以外のときの状態が W, $0$ のとき L であることが分かる. 以下に, 最適な戦略が実行可能であることを示す.

Part 1 - XOR が $0$ のとき

ここでは XOR が $0$ のとき, どのような操作をしても次の XOR が $0$ 以外になることを示す. まず, ある値を $a_i$ から $A$ に変えるとき, そのときの XOR の値を $X$ として, XOR の値は $X \operatorname{XOR} (a_i \operatorname{XOR} A)$ に変わる. $X=0$ のとき, 次の XOR も $0$ にするためには, $a_i \operatorname{XOR} A = 0$, すなわち $a_i=A$ でなければならない. ゲームのルールでは, $a_i>A$ でなければならないので, これは達成可能ではない.

Part 2 – XOR が $0$ 以外のとき

ここでは XOR が $0$ 以外のとき, 次の XOR を $0$ にする方法があることを示す. まず, その時点での XOR の値を $X$ とする. $2^k\leq X<2^{k+1}$ であるような整数 $k$ はただ 1 つ存在する. また, $a_1$, $a_2$, $a_3$, $\dots$, $a_n$ の中で, $2^k$ の位が $1$ であるもの (これを $a_i$ とする) は 1 つ以上ある (もし全部 $0$ だとすると, $X$ の $2^k$ の位が $0$ になることより矛盾) そのとき, $a_i=p\times 2^{k+1}+q$ ($p$, $q$ は $a_i$ を $2^{k+1}$ で割った商・あまりで, $q\geq 2^k$) は $p\times 2^{k+1}+0$, $p\times 2^{k+1}+1$, $p\times 2^{k+1}+2$, $\dots$, $p\times 2^{k}-1$ のいずれにも変えることができる. 次の番のときの XOR を $Y$ とすると $X \operatorname{XOR} Y = a_i \operatorname{XOR} (p \times 2^{k+1} + r) = (p \times 2^{k+1} + q) \operatorname{XOR} (p \times 2^{k+1} + r) = q \operatorname{XOR} r$ が成立し, その値は $2^k$ 以上 $2^{k+1}$ 未満である. $r$ は $0$ 以上 $2^k-1$ 以下のすべての整数をとりうるので, $X \operatorname{XOR} Y = q \operatorname{XOR} r$ は $2^k$ 以上 $2^{k+1}$ 未満のすべての整数をとりうる. この中に $X$ が含まれるから, $Y$ を $0$ にすることができる.

6. Grundy 数

「Grundy 数」という概念を使うと, すべてのゲームが Nim と同じように扱えるようになります.

Grundy 数とは?

あるゲームの状態 $X$ から操作をしてできる, 次のターンの状態を $Y_1$, $Y_2$, $\dots$, $Y_n$ とすると, この状態の Grundy 数 $\operatorname{grundy}(X)$ を「$0$ 以上の整数の中で, $\operatorname{grundy}(Y_1)$, $\operatorname{grundy}(Y_2)$, $\dots$, $\operatorname{grundy}(Y_n)$ の中に登場しない最小の数」とする. (これは帰納的に定義できる)

Grundy 数が $0$ のときこの状態は L で, $0$ 以外のときこの状態は W である.

Nim と Grundy 数

「Grundy 数が $x_1$, $x_2$, $x_3$, $\dots$, $x_n$ であるような $n$ 個のゲームがあり, 各プレイヤーは自分のターンのときに, $n$ 個のうち $1$ 個のゲームを選んで 1 回操作をする. 操作を行えなくなった方が負け」というゲームを考える. 例えば Nim だと, $n$ 個のゲームに分割でき, $i$ 個目のゲームは「$a_i$ 個の石があり, 各プレイヤーは $1$ 個以上の石を取り除くことができる. 操作を行えなくなった方が負け」になる.

実はこのゲームの Grundy 数は $x_1 \operatorname{XOR} x_2 \operatorname{XOR} x_3 \operatorname{XOR}\cdots\operatorname{XOR} x_n$ となる. 証明は, Nim の勝敗の証明と同じようなテクニックでできるので, ここでは省略する.

Nim の例だと,「$a_i$ 個の石があり, 各プレイヤーは $1$ 個以上の石を取り除くことができる. 操作を行えなくなった方が負け」というゲームに「分割」することができる. この部分的なゲームの Grundy 数 は $a_i$ となるので, Nim 全体の Grundy 数は $a_1 \operatorname{XOR} a_2 \operatorname{XOR} a_3 \operatorname{XOR}\cdots\operatorname{XOR} a_n$ となる.

(例題)

(1)

$n$ 個の石があり, これを使って 2 人でゲームを行う. 各プレイヤーは自分のターンのときに,「$1$ 個以上 $5$ 個以下の石を取り除く (ただし, 石の数を $0$ 未満にすることはできない)」という操作をする. 操作を行えなくなった方が負けである. さて, このときの Grundy 数を求めなさい.

(2)

5 つの石の山があり, それぞれの石の山には $31$, $41$, $59$, $26$, $53$ 個の石がある. これを使って 2 人でゲームを行う. 各プレイヤーは自分のターンのときに,「$1$ 個の石の山を選び, ここから $1$ 個以上 $5$ 個以下の石を取り除く (ただし, 石の数を $0$ 未満にすることはできない)」という操作をする. 操作を行えなくなった方が負けである. そのとき, 先手必勝か? それとも後手必勝か?

(3)

$n$ 枚の紙幣がある札束があり, これを使って 2 人でゲームを行う. 各プレイヤーは自分のターンのときに,「$4$ 枚以上の紙幣がある 1 つの札束を選び, これを $2$ 枚以上の紙幣が入った札束 2 つに分割する」操作をする. 操作を行えなくなった方が負けである. $n=2$, $3$, $4$, $5$, $\dots$, $10$ のとき, 先手必勝か? それとも後手必勝か?

練習問題

Q1

8 × 8 のマス目を使って 2 人でゲームを行う. 先手は白い駒を, 後手は黒い駒をたくさん持っている. 各プレイヤーは自分のターンのときに,「自分が持っている駒を, まだ駒が置かれていないマスの中に置く」操作ができる. となりあうマスが同じ色の駒であるような場所を最初に作った人が負けである. このゲームは先手必勝か? 後手必勝か? それとも引き分けか?

Q2

座標 $(x,y)$ ($x$, $y$ はともに整数) にコインが置かれている. これを使って 2 人でゲームをする. 各プレイヤーは自分のターンのときに,「$(x,y)$ の駒を $(x-1,y-2)$ または $(x-2,y-1)$ に移動させる」操作ができる. 最初 $x$ 座標または $y$ 座標を負にしたプレイヤーが負けである. このゲームは先手必勝か? それとも後手必勝か?

Q3

5 つの数 $245$, $420$, $660$, $864$, $1001$ があり, これを使って 2 人でゲームをする. 各プレイヤーは自分のターンのときに「$2$ 以上の数を 1 つ選び, これを自分自身以外の約数に変える」操作をする. 全部 $1$ にした方が勝ちである. このゲームは先手必勝か, それとも後手必勝か?