ニムゲームの話題                           戻る

 当HPにおいて、いろいろなところにニムゲームに関する話題が取り上げられている。

 お茶の時間 パズル&クイズ の中の、「石取りゲーム」「石取りゲーム(2)
石取りゲーム(3)」「石取りゲーム(4)」「石取りゲーム2020」「三山崩しゲーム」など。
また、投稿一覧の中の、「石取りゲーム」など。

 そもそも「ニム(nim)」とは、2人で行うゲームで、交互に石を取り合い勝者を決めるもの
を言う。この名前は、1901年にバウトン(ハーバード大学)によって名付けられたとのこと
である。 日本では、山崩しゲームとか石取りゲームなどと呼ばれる場合もがある。

 ニムゲームには必勝法があり、二進法を用いて説明される。

 交互に山の一つを選んで、そこから好きなだけの石を取る。2つ以上の山には同時に手を
つけない。最後に石を取り除いた人が勝ちとする。

 ・各山の石の個数を2進法で表し、各桁(ビット)毎の和を求める。

  この和は、排他的論理和(2つの値が一致しないときに値1を返す)で求められ、ニム和
とも呼ばれる。

 各桁毎の和がすべて0 → 先手必敗

 各桁毎の和が一つでも1 → 先手必勝

であることが知られている。

例 山をA(2個)、B(1個) とする。

 先手が勝つためには、Aから1個とり、A、B同数にして後手に手を渡す。
 後手は、どちらか(Aとする)から1個取ると、先手はBから1個取って、先手勝ちとなる。

 石の個数を2進法で表すと、 A(10)、B(01)
このとき、各桁毎の和は、 1、1 となり、一つでも1があるので、先手必勝となる。

例 山をA(3個)、B(2個) とする。

 先手が勝つためには、Aから1個とり、A、B同数にして後手に手を渡す。
 後手は、どちらか(Aとする)から1個または2個取るしかないが、先手はBから後手が取っ
 た数を取れば、必ず先手勝ちとなる。

 石の個数を2進法で表すと、 A(11)、B(10)
このとき、各桁毎の和は、 0、1 となり、一つ1があるので、先手必勝となる。

例 山をA(3個)、B(3個) とする。

 先手がどのように石をとっても、A、B同数が崩れてしまうので、必ず後手勝ちとなる。

 石の個数を2進法で表すと、 A(11)、B(11)
このとき、各桁毎の和は、 0、0 となり、すべて0となるので、先手必敗となる。

例 山をA(3個)、B(4個)、C(5個)とする。

 石の個数を2進法で表すと、 A(11)、B(100)、C(101)
このとき、各桁毎の和は、 0、1、0 なので、一つ1があるので、先手必勝となる。

 勝ち方の例としては、次の通りである。

 各桁毎の和で、1をなくし全て0にして手を渡せば、渡された方が必敗となる。

 そこで、Aから2個とると、 A(1個)、B(4個)、C(5個) で、A(01)、B(100)、C(101)
このとき、各桁毎の和は、 0、0、0 なので、後手必敗である。

 次に例えば、後手がBから3個取ると、 A(01)、B(01)、C(101)
このとき、各桁毎の和は、 1、0、1 で、一つでも1があるので、先手必勝となる。

 次に、各桁毎の和をすべて0にして後手に手を渡すためには、先手は、Cから5個全部
取ればよい。このとき、A(1個)、B(1個)、C(0個)で、A(01)、B(01)、C(00)から、各桁
毎の和は、0、0 で、後手必敗である。後は言うまでもなく、簡単な手順で先手の勝ちとなる。


問 題  交互に1枚以上5枚以下のカードを取り続け、最後にカードを取った方が負けと
     なるゲームがある。

(1) 7枚のカードの場合、勝つのは先手か後手か?

(2) 23枚のカードの場合、先手が勝つためには最初何枚取るか?

(解)(1) 先手が1〜5枚のカードを取ると残りは、2〜6枚

     よって、後手は、最後に1枚残すようにカードが取れるので、後手必勝である。

(2) 先手・後手合わせて6枚になるように取り続け、カードの枚数が7枚になったときに、

  手を相手に渡せば必ず勝てる。

 よって、カードの枚数が、 7 、13=7+6 、19=7+6+6 、・・・ では必ず後手必勝

 23枚のカードの場合、先手が勝つためには、4枚カードをとり、19枚にして相手に手を渡

せば、先手必勝である。  (終)