石取りゲーム（ニム）

山から交互に石を取って、最後の1個を取ったら勝ち。このゲームには必勝法があり、しかも計算で書けます。⭐ 先を読まなくても勝てます。

⭐ 「強い」は「たくさん読む」ではありません

○×ゲームの「さいきょう」は、最後まで読み切って強くなっていました。何十手も先を数えるから強い ── コンピュータの強さは、たいていそう説明されます。

⭐ 石取りゲームは、そうではありません。このページの「さいきょう」が見ているのは1手先だけです。 それでも絶対に間違えません。必勝法が、読むかわりに計算で書けるからです。

⭐⭐ 必勝法 ── けたごとに「1」を偶数にする

それぞれの山の石の数を2進で書いて、縦に並べます （2進については n進数の変換 のページで扱っています）。 そしてけたごとに「1」がいくつあるかを数えます。

⭐ どのけたも「1」の個数が偶数 ── この形を相手に渡せば勝ちです。 逆に、自分の番でこの形になっていたら、どう取っても勝てません。

上の遊ぶところで「⭐ 必勝法を見る」を押すと、 いまの形の表がそのまま出ます。取るたびに数が変わるので、偶数がくずれる／そろうのを目で追えます。

定番の「1・3・5・7」は、実は先手が不利です

1・3・5・7 は、けたごとの1が 2・2・4 でぜんぶ偶数（合わせると 0）。 ところが7 を1個だけ減らして 1・3・5・6 にすると 2・2・3 になり、1のけたが奇数にくずれます（合わせると 1）。 ⭐ たった1個で、勝ち負けが入れ替わります。

だから1・3・5・7 から始めて、先に取ると、 相手が必勝法を知っているかぎり勝てません。 ⭐ 上の並びを3・4・5に変えると、こんどはあなたが勝てる形から始まります。「さいきょう」相手でも勝てるので、 ぜひ試してみてください。

なぜ、けたごとの偶数でうまくいくのか

大事なことが2つあります。 (1) 偶数の形を渡されたら、必ずくずれる。石を取ると、その山の数が変わります。数が変われば2進のどこかのけたが変わるので、 そのけたの「1」の個数は必ず奇数になります。 つまり相手は偶数の形を保てません。

(2) くずれた形は、必ず偶数に戻せる。奇数のけたがあるとき、そのうちいちばん大きいけたに注目します。 そのけたに「1」を持っている山が必ずあり、その山は石を減らすだけでぜんぶのけたを偶数にそろえられます （いちばん大きいけたが 1 から 0 に変わるので、数は必ず小さくなります）。

この2つがあるので、偶数の形を渡し続けることができます。 石は取るたびに減るので、いつか必ず終わります ── そして終わったとき、最後の1個を取ったのは自分です。

この説明は「そうなるはず」で終わらせていません。 このページの単体テストが山4つ・各6個までの全2400局面を最後まで読み切って、 上の規則と1局面も食い違わないことを確かめています （山を5つに増やしても崩れません）。 ⭐ だからこのページには「出どころ」の節がありません。よそから持ってきた話ではなく、その場で数えた結果だからです。

⭐ 「最後に取ったら負け」にすると、1か所だけ変わります

ルールを1行変えて最後の1個を取らされたら負けにしても、 必勝法はほとんど同じです。変わるのは終わりぎわだけ。

山がぜんぶ1個以下になったときだけ、規則がひっくり返ります。 そこから先は1個ずつ交互に取るしかないので、残っている山の数が偶数なら、いま打つ人が勝ちです （奇数だと最後を取らされます）。 それ以外の場面では、けたごとに偶数でまったく同じです。

この例外も総当たりで確かめてあります。2個以上の山が1つでも残っていれば、2つの遊び方は同じ答えになることも、別に固定してあります。

この道具が使っている数

ここに出している数は、すべてその場で計算したものです。 たとえば 1・3・5・7 のけたごとの1の個数は 2・2・4、 合わせると 0 で、 先に取る人は負け。 文章に手で書き写した数はひとつもありません。