ニム

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

歴史的には、最初に必勝法が数学的に解決したゲームであるRichard J. Nowakowski (Dalhousie University)  2009年1月24日。p.4。最善手を行うならば、どちらが勝つかは最初の個数の組で決まる（後述）。その必勝法と証明は組合せ論による。

 ゲームのルール 
有限個のコイン（石や豆でもよい）の山を有限個用意する。2人のプレイヤーが山からコインを好きな数ずつ交互に取り合っていく。
 一度に取るコインは1つの山からとする。
 回ごとに最低1個は取らなければいけないとする。
これを繰り返すと有限回で全てのコインがなくなるが、最後にコイン（複数でもよい）を取ったプレイヤーにより勝敗を決める。最後にコインを取った者を勝者とするルールは正規形と呼ばれている。

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

山A, Bのコインの個数をそれぞれ  とする。調べ上げていっても容易に類推されるように、後手必勝形は  のときのみである。 ならば、先手が多い山から  と  の差だけコインを取ると、次に相手は  にせざるを得なくなる。先手がこれを繰り返すと必ず勝つ。

 ならば、後手が上記を実行すると必ず勝つ。

 一般の場合 
コインの山の数を  とし、各山のコインの枚数を  とする。

 とおく。ただし、 はビットごとの排他的論理和（ニム和）を表すものとする。

 のときは 必ず  にでき、すると次に相手は  にせざるを得なくなる。これを繰り返すと必ず勝てる。  ならば先手必勝、 ならば後手必勝にできる。

 証明 
先手が  の  からコインを取り除いて  になったとする。 

とおく。排他的論理和は交換法則、結合法則および  を満たすため、次の等式が成り立つ。

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

補題1： のとき、任意の操作について  である。

証明： であることから明らかである。

補題2： のとき、ある操作について  である。

証明： の ビットのうち 0 でない最高位を  の位とする。 の  の位が 0 でない  を1つ選ぶ（このような  は必ず存在する）。 であるため、番目の山から何枚かのコインを取り除いて  枚にすることができる。このとき  となる。

 逆形 
最後にコインを取った者を負けとするルールは「逆形」（クラスメソッド株式会社）2018.03.23「逆型」「双対ゲーム」などと呼ばれている。一般に、組合せゲームの正規形と逆形では、プレイヤーが逆のことに最善を尽くすため、正規形の後手必勝形が逆形の後手必敗形とはなっていない。

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

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

 である後手必勝形は
 1個だけの山が奇数個のみ。… ()
である。

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

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

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

故に、必勝形  は
  または
 2個以上の山が2個以上かつ、ニム和が 0 であるもの。
に限られる。//

 脚注 

 関連項目 
 不偏ゲーム
 ニム和
 映画『去年マリエンバートで』 - 作中でニムが重要な役割を担う

 外部リンク 


Category:組合せゲーム理論
Category:数学ゲーム
Category:ゲーム