ニム

ニム (英: Nim) は、2人で行うレクリエーション数学ゲーム（組合せゲーム）の一つである。起源は古代中国からあるとされ、16世紀初めの西欧で基本ルールが完成したが、名前については、一般的に1901年にハーバード大学のチャールズ・L・バウトンによって名付けられたとされる。

歴史的には、最初に必勝法が数学的に解決したゲームである^[1]。最善手を行うならば、どちらが勝つかは最初の個数の組で決まる（後述）。その必勝法と証明は組合せ論による。

ゲームのルール[編集]

有限個のコイン（石や豆でもよい）の山を有限個用意する。2人のプレイヤーが山からコインを好きな数ずつ交互に取り合っていく。

一度に取るコインは1つの山からとする。
回ごとに最低1個は取らなければいけないとする。

これを繰り返すと最後は全てのコインがなくなるが、ゲームの目的は、最後のコインを取ることである（正規形）。コイン（複数でもよい）を最後に取ったプレイヤーを勝者とする。

必勝法[編集]

山が2つの場合[編集]

特に山が2個の場合は、一般の場合よりも必勝法が簡単である。

山A, Bのコインの個数をそれぞれ $a, b$ とする。このときの必勝法を考える。まず $a \neq b$ のときを考える。先手は、AとBの山のコインの数が同じになるように、コインが多い方の山からコインを取る。以後同様に、先手は自分の回では、後手の取るのを真似ればよい。つまり、後手が片方の山から $c$ 個コインを取ったとしたら、先手は他方の山から、同じ数の $c$ 個だけコインを取ればよい。これが先手の必勝法である。

$a = b$ のときは、先手の取るのを真似ることで後手が必ず勝つ。

一般の場合[編集]

コインの山の数を $n$ とし、各山のコインの枚数を $A 1, \dots, A n$ とする。

$S=A_{1}\oplus \cdots \oplus A_{n}$ とおき、 $S\neq 0$ ならば先手必勝、 $S=0$ ならば後手必勝にできる。 $\oplus$ はビットごとの排他的論理和である。

ビットごとの排他的論理和が 0 になるようにコインを取る戦略が必勝法である。

証明[編集]

先手がコインを取り除いた後の各山のコインの枚数を $B 1, \dots, B n$ とし、 $T=B_{1}\oplus \cdots \oplus B_{n}$ とする。コインが $k$ 番目の山から取り除かれるとき、 $A_{l}\oplus B_{l}=0\;(l\neq k)$ である。排他的論理和は結合法則と交換法則および $X\oplus X=0$ を満たすため、次の等式が成り立つ。

{\begin{aligned}T&=S\oplus S\oplus T\\&=S\oplus (A_{1}\oplus B_{1})\oplus \cdots \oplus (A_{n}\oplus B_{n})\\&=S\oplus A_{k}\oplus B_{k}\end{aligned}}

次の2つの補題から従う。

補題1： $S=0$ のとき、任意の操作について $T\neq 0$ である。

証明： $A_{k}\oplus B_{k}\neq 0$ であることから明らかである。

補題2： $S\neq 0$ のとき、ある操作について $T=0$ である。

証明： $S$ の 0 でないビットのうち最高位の位置を $d$ 番目とする。 $A k$ の $d$ 番目のビットが 0 でない $k$ を1つ選ぶ（このような $k$ は必ず存在する）。 $S\oplus A_{k}<A_{k}$ であるため、 $k$ 番目の山から何枚かのコインを取り除いて $B_{k}=S\oplus A_{k}$ 枚にすることができる。このとき $T=0$ となる。

逆形[編集]

最後にコインを取った者を負けとするルールは「逆形」^[2]「逆型」「双対ゲーム」などと呼ばれている。一般に、組合せゲームの正規形と逆形では、プレイヤーが逆のことに最善を尽くすため、正規形の後手必勝形が逆形の後手必敗形とはなっていない。

実際に逆形ニムにおいては、必勝形、必勝法は次の通りである^[3]：

$n$ 個の山の内、コインが2個以上であるものの個数を $i$ とする。

$i = 0$ である後手必勝形は

1個だけの山が奇数個のみ。… (1)

である。

$i = 1$ のときは、

1個だけの山が奇数個なら、2個以上の山を空にすることで必勝形にできる。
1個だけの山が偶数個なら、2個以上の山を1個にすることで必勝形にできる。

故に $i = 1$ のときは必敗形である。

$i \geq 2$ のときは、プレイヤーがニム和を 0 にし続ければ、相手は $i = 1$ にせざるを得なくなる。

（なぜなら、 $i = 1$ のときのニム和は 0 でないから。）

故に、必勝形 $(A 1, \dots, A n)$ は

(1) または
2個以上の山が2個以上かつ、ニム和が 0 であるもの。

に限られる。//

脚注[編集]

^ Richard J. Nowakowski (Dalhousie University) The History of Combinatorial Game Theory - ウェイバックマシン（2012年1月18日アーカイブ分） 2009年1月24日。p.4
^ [組み合わせゲーム理論] 組み合わせゲームとゲーム木について | DevelopersIO（クラスメソッド株式会社）2018.03.23
^ 石取りゲーム(Nim) [いかたこのたこつぼ]

外部リンク[編集]

『ニム（複数山の石取りゲーム）の必勝法』 - 高校数学の美しい物語

この項目は、ゲームに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

[1] Richard J. Nowakowski (Dalhousie University) The History of Combinatorial Game Theory - ウェイバックマシン（2012年1月18日アーカイブ分） 2009年1月24日。p.4

[2] [組み合わせゲーム理論] 組み合わせゲームとゲーム木について | DevelopersIO（クラスメソッド株式会社）2018.03.23

[3] 石取りゲーム(Nim) [いかたこのたこつぼ]

[1]

[2]

[3]