玉を取れ！〜石取りゲーム必勝法〜

新しい記事をアップしました。こちらの方が簡潔です。
http://d.hatena.ne.jp/igaris/20110903/1315040936

タイトルは, 変な意味ではありません. 科挙とかじゃないですよ.
今回は, 石取りゲームとか, うんたらかんたらと言われる, 二人でやるゲームについての考察です.
有名なので, 知ってる方も多いのでは？
その昔, 平成教育委員会でも取り上げられたことがあります.

「ルール」
・玉が $x$ 個あります.
・一度に取れる玉の数は $1$ 個以上 $a$ 個以下です.
・二人が交互に玉を取ります.
・最後の玉を取った方が負けです.

ちなみに, このゲームは「二人零和有限確定完全情報ゲーム」と呼ばれるものの一種です.

・二人 → 二人でやるんだよっ.
・零和 → 二人の勝ち負けポイントを足すと常に $0$ . 例えば, 勝ちを $1$ , 負けを $-1$ , 引き分けを $0$ とすると, 勝負がついたときは $1+(-1)=0$ , 引き分けだったときも $0+0=0$ .
・有限確定 → 有限回のうちにゲームが終わる.
・完全情報 → 相手がどんな手を取ったのか, ゲームが今どのような状態なのかが, 双方ともに完璧に把握できる.
・ゲーム → ゲームだよっ.

二人零和有限確定完全情報ゲームは色々なものがありまして, 有名なところではオセロ, 囲碁, 五目並べ, ◯×ゲームなどがそうです.
この石取りゲームも, 明らかに二人零和有限確定完全情報ゲームですね.
それから, 二人零和有限確定完全情報ゲームは, 先手か後手に必勝法が存在するか, 双方ともに最善を尽くせば必ず引き分けになる, ということが数学的に証明されています.
石取りゲームには引き分けがないので, 先手と後手のどちらかに必勝法が存在することは明らかですね.
そんなわけで, 今回は, 石取りゲームの必勝法を確立してみましょ, って話なのです.

次の事実がとっても有用です.

「相手がいくつ取ろうとも, 次に自分が取った個数との和が『一度に取れる数の最大数 $+ 1$ 』になるようにできる.」

例えば, 一度に $3$ つまで玉を取れたとし, 相手が $x$ 個取ったときに自分が $y$ 個取ることを $x \rightarrow y$ で表すと,
$1 \rightarrow 3$
$2 \rightarrow 2$
$3 \rightarrow 1$
という風にして, 和が常に $3+1=4$ になるようにできます.
今後, このような戦法を「コケコッコ戦法」と呼ぶことにします.

この事実を使うと, 必勝法は簡単です.

$x = k(a+1)+r$ で $0 \leq r \leq a$ として…
(1) $r = 1$ のとき.
後手必勝です.
コケコッコ戦法を使うことで, いずれはこちらが取り終わった段階で玉が $1$ つだけ残り, 相手がそれを取らざるを得なくなります.
(2) $r \neq 1$ のとき.
先手になって, $r = 0$ なら $a$ 個を取り, そうでないなら $r-1$ 個（これは $a$ より小さい）個を取ればよろし.
すると, (1) に帰着できます.

わーい♪
意外と簡単でした.

ついでに, 最後の玉を取った方が負け, ではなく, 最後の玉を取った方が勝ち, というバージョンについても考えてみましょ.
実はこれも簡単で, 最初に $x = k(a+1)$ の形を作っておけば, あとはコケコッコ戦法で勝つことができます.

めでたしっ！

しかしながら, これではあまりに簡単すぎます.
テイルズオブファンタジアというテレビゲームの中でも, ミニゲームとして登場したくらいです.
そこで, ここからが本題です. 今までのは前振りです. 前振りが長かったですね.

石取りゲームを, 次のように一般化してみたっぺよ.

「一般化した石取りゲームのルール」
・箱が $n$ 個あるの.
・ $i$ 番目の箱には玉が $x_i$ 個入ってるの.
・ $i$ 番目の箱から一度に取れる玉の数は $1$ 個以上 $a_i$ 個以下なの.
・二人が交互に玉を取るの.
・最後の玉を取った方が勝ちバージョンと負けバージョンがあるの.

このゲームの最後の玉を取った方が勝ちバージョンを Rem-W(n), 負けバージョンを Rem-L(n) で表すことにします.
玉を取り除く（Remove）ので, その頭文字を取ってみました. 後述の Nim ともかけています.
W は Win, L は Lose の略です. 安直です.
そうすると, 先述の二つは Rem-L(1) と Rem-W(1) になります.

では, その必勝法はどうなるのかっ！
実はそう簡単な話ではなく, 私は三日三晩, 考え続けました.
そうして, やっと, 必勝法を確立することができたのですっ！
壮絶な戦いでした….
その戦いの記録が, この記事なのです.

一般の $n$ について考える前に, まずは $n = 2$ の場合について考えてみることにします. 小さなことからコツコツと.

W と L のどちらを先に考えるか.
W の方が良いです.
何故なら, W の必勝法を少し変えれば L の必勝法が作れるから.

Rem-W(2)

以後, $x_1 = m_1$ , $x_2 = m_2$ である状況を $(m_1,m_2)$ で表します.
それから, $x_i$ を $a_i+1$ で割った余りを $r_i$ で表します.
あと, i 番目の箱を $P_i$ と書くことにします.

(1) $(k_1(a_1+1), k_2(a_2+1))$ のとき.
後手必勝.
それぞれの箱にコケコッコ戦法を適用.

(2) $(k_1(a_1+1)+r_1, k_2(a_2+1))$ or $(k_1(a_1+1),k_2(a_2+1)+r_2)$ で, $r_1, r_2 \geq 1$ のとき.
先手になって, $r_1$ or $r_2$ を $0$ にすれば, (1) のパターン.

(3) $(k_1(a_1+1)+r_1,k_2(a_2+1)+r_2)$ で, $r_1, r_2 \geq 1$ のとき.
自分のターンで (2) のような状態を作ってしまうと, そこから相手に (1) の局面を作られて負けてしまうので, 常に $r_1, r_2 \geq 1$ の状態を保つ必要があります.
いささか天下り的ですが, この場合は $r_1 = r_2$ であれば後手必勝です.
例えば, 自分のターンが終わって $(r,r)$ かつ $r \leq \mathrm{min}(a_1,a_2)$ という局面になったとすると, そこから常に相手と同数を取るようにすれば勝てますね.
したがって, 必勝法は次のようになります.

$r_1 \neq r_2$ なら, 先手になって $r_1 = r_2 = r$ とした上で
(1) $x_1 = k_1(a+1)+r$ の状態で, 相手が $P_1$ から取ったとき.
コケコッコ戦法.
(2) $x_1 = r_1$ の状態で, 相手が $P_1$ から取ったとき.
$P_2$ から同数取る.
※ $P_2$ についても同様.

Rem-L(2)

(1) $(k_1(a_1+1)+r_1,k_2(a_2+1)+r_2)$ で, $r_1$ と $r_2$ の少なくとも一方が $0$ か $1$ のとき.
$(r_1, r_2) = (1, 0)$ or $= (0, 1)$ でない場合は, 先手になって片方の箱からいくつかを取ってそのようにする.
以後はコケコッコ戦法.

(2) $(k_1(a_1+1)+r_1,k_2(a_2+1)+r_2)$ で, $r_1, r_2 \geq 2$ のとき.
これもいささか天下り的ですが, 先述したのと同じように $r_1 = r_2$ とできれば勝つことができます.
そこで, $r_1 \neq r_2$ のときには, 先手になって $r_1 = r_2$ としておきます.
そして, 途中までは, コケコッコ戦法で進めていきます.
すると, ある局面で $(k_1(a_1+1)+r, r)$ のような状態になるはずです（ $P_2$ についても同様）.
このとき,

　(2)-1 相手が $P_1$ から取る → コケコッコ戦法.
　(2)-2 相手が $P_2$ から取る →
　　(2)-2-1 $r_2 = 1$ になった → $r_1 = 0$ とする.
　　(2)-2-2 $r_2 \geq 2$ になった → $r_1 = r_2$ とする.

このような操作を繰り返していくと, 次の二つのパターンのいずれかに到達します.

(i) $(r,r)$
(ii) $(k_1(a_1+1),1)$

(i) 相手が $P_1$ から取ったとして（ $P_2$ でも同様）,
$x_1 = 0$ → $x_2 = 1$
$x_1 = 1$ → $x_2 = 0$
$x_1 \geq 2$ → $x_2 = r_1$
となるように取っていけば勝てる.

(ii)
相手が $P_1$ から取る → コケコッコ.
相手が $P_2$ から取る → $P_1$ から $a_1$ 個を取り, $x_1 = (k-1)(a_1+1)+1$ とする.

以上で, Rem-W(1), Rem-L(1), Rem-W(2), Rem-L(2) については, 先手か後手かを自由に選べるという条件のもとで, 必勝法を確立できました.
あー, 長かった.
だけど, まだ, 一般の n の場合について考察していません.
内容的には, まだ半分くらいです.
あー, 長い.
ここまで読んで下さった皆さんは, ここらでちょっと休憩をはさむことをお勧めしちゃいます.
そのあとで, また戻ってきてくださいね♡

さて, いよいよ Rem-W(n) と Rem-L(n) についてですが, 場合分けが多くなって煩雑になってしまうのではないかと思いきや, そんなことはありません.
$r_i = 0$ である箱については, Rem-W(1) の必勝法を適用すれば, 勝敗には関係しないので, その存在を無視できます.
同様に, $r_i = r_j$ となるような二つの箱についても, Rem-W(2) の必勝法を適用すれば, その存在を無視できます.
すると, 結局のところ, 各 $r_i$ が $0$ でなく, かつ, 互いに異なる状況のみを考えれば良いことになります.

さらには！
実のところ, 最初から各 $i$ について $x_i = r_i$ であるような場合だけを考えれば良いことも分かります.
何故かと言うと, $x_i = k_i(a_i+1)+r_i$ である $P_i$ から玉が取られた場合には, コケコッコの適用によって勝敗に影響はない上, $x_i = r_i$ である箱から玉が取られた場合には, 各 $i$ について $x_i = r_i$ であると見なして, その必勝法を適用すれば, それぞれの箱の $k_i(a_i+1)$ の部分はまたコケコッコの適用によって勝敗に影響がないことにより, 必勝パターンが得られるからです.

これで, 考えるべき問題が大分簡単になりました。
整理すると, 次のようになります.

ルール
・箱が $n$ 個あるの.
・ $i$ 番目の箱には玉が $x_i$ 個入ってるの.
・ $i \neq j$ なら $x_i \neq x_j$ なの.
・ $i$ 番目の箱から一度に取れる玉の数は $1$ 個以上なの.
・二人が交互に玉を取るの.
・最後の玉を取った方が勝ちバージョンと負けバージョンがあって, どっちでもいいの.

要するに, 一度に取れる玉の数に上限がなくなって, さらに, 各 $x_i$ が初期状態においては全て異なる, というバージョンです.

特に, 最後の玉を取った方が勝ちバージョン（の, 条件 $3$ を除いたもの）は大昔から広く知られていたようで, 現在では Nim（ニム）と呼ばれています.
そしてもちろん, 歴史が古いだけあって必勝法も確立されています.
とは言え, 必勝法を自分で編み出すことが楽しいのであって, 確立された必勝法の解説を読んでも, 何も面白くありません.
そこで, 私は自力での証明を試みました.
ところがっ！
私がニムの存在を知ったとき, 「その必勝法の証明には二進数表現と排他的論理和が使われる」という記述を見つけてしまったのですっ！
あーらら. あらら. あれまー.
完全に独力で証明したかったというのに. あれまー.
少しがっかりしたのですが, 二進数表現と排他的論理和を使うなんていう発想はおそろく独力では無理だっただろうと思われたので, それらをヒントに, 残りの部分は自分で穴を埋めてみることにしました.
考えることは楽しいこと, です.

というわけで, ファインディング・ニモならぬ, ファインディング・ニムの必勝法です！

Nim-W(n) および Rem-W(n)

まずは Nim-W(n) から.

Rem-W(2) での考察から, 最終的に同数の $2$ つの箱だけが残れば, 後手必勝となります.
また, 具体的な $n$ について色々といじってみると, 後手必勝のパターンが他にもいくつか見つかります.
そうして, それぞれのパターンを解析してみた結果, 共通の性質がありました.

各 $x_i$ を二進数表現に直し, その $j$ 桁目のビットを $x_{i,j}$ で表す.
それらのうち, 桁数が最大のものの桁数を $k$ とおく.
桁数が $k$ 未満のものについては, 先頭から $0$ を補完していって, 同じく桁数が $k$ のビット列を作る.
$j$ 桁目のビットの排他的論理和を $XOR(j)$ で表す.
すなわち, $\mathrm{XOR}(j) := \left(\sum x_{i,j}\right)%2$ と定義する.

このように定義して考えると, 後手必勝のパターンにおいては, 常に
$\forall j, \mathrm{XOR}(j) = 0$
が成り立っていました.
ということは, 自分のターンが終了した時点で, 常にこの状態にすることができれば勝てそうな感じがします.
以下, この状態を $S$ で表し, そうでない場合, つまり $\exists j, \mathrm{XOR}(j) = 1$ である状況を $\bar{S}$ で表すことにします.

「定理1」
ある局面で $S$ になったとすると, そこからいくつか玉を取ったら必ず $\bar{S}$ になるよ.
「証明」
$P_i$ から取ったとすると, ある $j$ について $x_{i,j}$ の値が反転する.
他の箱の $j$ 桁目のビットには変化がないから, 仮定より, $\mathrm{XOR}(j) = 1$ となる.

「定理2」
ある局面で $\bar{S}$ になったとすると, そこからいくつかの玉を取って $S$ にすることができるのよ.
「証明」
桁数の最大値を $k$ とし, ビット列 $h$ を $h_i = \mathrm{XOR}(x_k) \mathrm{XOR}(x_{k-1}) \cdots \mathrm{XOR}(x_1)$ で定義する.
(1) 玉の数の二進数表示の桁数が $k$ である箱が奇数個の場合.
$x_i$ の桁数が $k$ だったとする.
$i$ 番目以外の全ての箱について $h$ を作ると, 仮定より $\mathrm{XOR}(k) = 0$ であるから, $h$ を数の二進数表現と考えると $h < x_i$ .
ゆえに, $P_i$ からいくつか取って $x_i = h$ とすればよい.
(2) 玉の数の二進数表示の桁数が $k$ である箱が偶数個の場合.
$\mathrm{XOR}(k) = 0$ であるから, $k$ 桁目は無視して考えてよい.
次に, 残り $k-1$ 桁で考え, ここでも $\mathrm{XOR}(k-1) = 0$ であれば, 以下同様.
ここで, 仮定より, ある $j$ について $\mathrm{XOR}(j) = 1$ である.
よって, 上記操作を続けていった際に必ずそのような桁に到達し, そこにおいて (1) を適用する.

この二つの定理により, とても都合の良いことが判明します.
一度, こちらのターンで $S$ を作ることができたとすると, 定理1より, 相手は次のターンで $\bar{S}$ を作らざるを得なくなります.
ここで, 定理2により, こちらのターンでまた $S$ を作ることができ, 以下同様.
ところで, 最終的には箱が二つのみ残るわけですが, この局面において, 相手は $\bar{S}$ を作らざるを得ないことから, 相手のターンが終わった段階で二つの箱の玉数は異なっているはずです.
そこで, こちらが $S$ を作る, すなわち二つの箱の玉数を同数にすれば, あとは Rem-W(2) の必勝パターンに帰着されます.
したがって, 以上のことから, 常に $S$ を作り続ければ必勝, ということになります.
$S$ の作り方については, 上記定理2を参照のこと.
また, 自分のターンで $S$ を作るには, 初期状態において $S$ であれば後手に回り, 逆に $\bar{S}$ であれば, 先手に回り $S$ を作っておく, という戦法を取ればよいことが分かります.

あー, できたー.
できたぞー.

と, ここまで書いたところで, 割と重大なことに気付きました。
各 $r_i$ が異なるという条件を, 全く使っていませんね.
ということは, 最初から $r_i = 0$ である箱や $r_i = r_j$ である二つの箱も一緒くたにして考えても良かったのです.
あーららっ. 失態っ！
まあ, 議論に間違いはありません.
それに, $r_i = 0$ である箱や $r_i = r_j$ である二つの箱というのは, それらを単体で見ると $S$ が成り立っているわけで, これらを除いて考えることによって計算の無駄を省くことができるのも事実です.

というわけで, Rem-W(n) については, 先述の戦術を使えば良いです.
すなわち,

(1) $x_i = k_i(a_i+1)+r_i$ である箱 $P_i$ から玉が取られた場合.
コケコッコ.
(2) $x_i = r_i$ である箱 $P_i$ から玉が取られた場合.
各 $i$ について $x_i = r_i$ であると見なして, Nim_W(n) 必勝法を適用.

とすれば勝てます.

Nim-L(n) および Rem-L(n)

いよいよ大詰めです. これで終わりです. 早く終わりたいよー.
まずは, Nim-L(n) から.

$S$ を保つ方が主導権を握れるので, 途中までは Nim-W(n) の必勝法と同一で良さそうです.
いずれは二つの箱が残るはずですが, 自分のターンが終わったところで $(1,1)$ だと, 負けてしまいます.
ところで, 箱がいくつか残っている状況で, それらの他に $(1,1)$ の組がいくつかあった場合を考えてみると, これは勝敗に影響を及ぼさないことから, 無視できます.

(1) 相手のターンが終わったところで $(1,1)$ のペアがいくつか（なくても良い）と, そうでないペアが一つだけ残ったとき.
先の自分のターンでは $S$ にしたので, $(1,1)$ でないペアは玉数が異なるはずです.
すると, Rem-L(2) の必勝法が使えます.
(2) 相手のターンが終わったところで $(1,1)$ のペアがいくつか（なくても良い）と, 箱が $P_i$ が一つだけ残ったとき.
まず, $x_i = 1$ となることはあり得ません.
これは, こちらが常に $S$ を作ることと, (1) によります.
よって, ここで $x_i = 1$ となるように取れば勝てます.

以上で, Nim-L(n) の必勝法の完成です.
Rem-L(n) については, 次のようになります.

(1) $x_i = k_i(a_i+1)+r_i$ である箱 $P_i$ から玉が取られた場合.
コケコッコ.
(2) $x_i = r_i$ である箱 $P_i$ から玉が取られた場合.
各 $i$ について $x_i = r_i$ であると見なして, Nim_L(n) 必勝法を適用.

以上で, 全ての場合の必勝法を述べることができましたっっっ！！！

ようやく, 長きに渡る戦いの歴史が幕を閉じました.
天下を統一した気分です.

思い返せば, ○×ゲームの必勝法を考察したのが小学校6年生の頃.
その頃から, 私の興味関心は変わっていないようです.
三つ子の魂百までも, とは, よく言ったものですね.