なぜ排他的論理和=0がニムの必勝法なのか

ニムというゲームをご存知でしょうか。
標準的には以下のようなルールです。

• 2人プレイ。
• 場には、コインの山がいくつか並んでいる。
• コインの山の数はいくつでもよい。
• 各山のコインの枚数は何枚でもよい。
• 各プレイヤーは、自分のターンが来たら1つの山から好きな枚数だけコインをとれる。
• 複数の山から同時にとるのはなし。
• パスはなし。
• 最後のコインをとった人が勝ち。
• 必勝法がある。

やってみよう

まずは私(A)とやってみましょう。
といってもあなた(B)の手番も私が勝手に進めますが。

山は3つで、それぞれ3枚、4枚、5枚としてます。
あなた(B)が先攻でいいですよ。
常に先手必勝or後手必勝ではないのでご安心を。


B1) (3,4,5) -> (3,1,5)
A1) (3,1,5) -> (3,1,2)
B2) (3,1,2) -> (3,0,2)
A2) (3,0,2) -> (2,0,2)
B3) (2,0,2) -> (1,0,2)
A3) (1,0,2) -> (1,0,1)
B4) (1,0,1) -> (1,0,0)
A4) (1,0,0) -> (0,0,0) 私の勝ち!


あなたを善戦させた結果けっこう長くなってしまいました(笑)

あなたは、B4で(1,0,0)を私に渡してしまっています。
なので、山が最後のひとつになった状態で自分の番が来たときは、その山のコインを全部とれば勝ちです。


では、山が2つになったときはどうでしょう。

B2から山が2つになっています。
A2, A3を見てください。

山が2つのときは、2つの山のコインの数を同じにして相手に渡すと勝つことができます。
コインの枚数が同じ2つの山をもらった人は、どちらかの山をすべて取ってしまうと、次の相手のターンが山1つになってしまうので、最低でも1枚残すような形でとる必要があります。

また、パスは無しなので最低でも1枚は取らなくてはいけません。
なので、例えば(4,4)で貰ったら、(4,3)か(4,2)か(4,1)で返すしかありません。

しかし、どちらで返しても、次のターンで相手に真似されます（同じ取り方をされます）。
(4,3) -> (3,3), (4,2) -> (2,2), (4,1) -> (1,1)というように。

a>bなる(a,b)を受け取った相手は、必ず(b,b)で返すことができるので、一度でも同じ枚数の2山を受け取ってしまうと、以後この状態から抜け出すことができません（相手がミスしなけば）。

そうこうしているうちに、コインの枚数は確実に減っていくので、最終的に自分のターンで(1,1)を受け取ってしまいます。
こうなると負けですね。

排他的論理和=0

では、山の数が3つ以上のときは？
山2つになるまで適当にプレーしていると、運悪く自分の番に(a,a)を受け取ってしまうかもしれません。

2山の必勝法は、知らない人でも数回プレーしていれば気づくので、友だちを騙そうとしてもすぐに見破られてしまいます。
なので、3山以上のときの必勝法も覚えておく必要があります。

これを自力で気づくのはほぼ無理でしょう。


3山以上のときの必勝法は、各山のコイン枚数の排他的論理和が0の状態で相手に渡し続ける、です。

この状態を「必勝形」と呼んでいるサイトが多いです。
排他的論理和=0って書くと長いですよね。

必勝形なんですが、自分のターンで必勝形を作って相手に渡すことが条件です。
必勝形を貰ってしまうと、負けるのでご注意を。


ちなみに、排他的論理和というは、2進数の計算方法の1つで、繰り上がりを無視するという特徴があります。

⊕（○の中に＋）という記号を使います。
⊕も、ふつうの足し算と同じように各桁を足していきます。

2進数なので、通常は、1+1のときその桁は0になり、繰り上がりで上の桁に+1しますが、排他的論理和では、この繰り上がりを無視します。
つまり1+1=0になります。

他は全部ふつうの足し算と一緒です。

• 0+0=0
• 0+1=1
• 1+0=1
• 1+1=0

例えば、4は2進数で100、7は111なので、4⊕7=100⊕111=011になります。
また、3は2進数で11なので、3⊕4⊕7=011⊕100⊕111=0になります。

これは必勝形なので、(3,4,7)という山をもらうと、このあと相手がミスをしない限り負けます。


では、さきほどのゲーム例を排他的論理和で見ていきましょう。
[]内が排他的論理和です。


B1) (3,4,5)[10] -> (3,1,5)[111]
A1) (3,1,5)[111] -> (3,1,2)[0]
B2) (3,1,2)[0] -> (3,0,2)[1]
A2) (3,0,2)[1] -> (2,0,2)[0]
B3) (2,0,2)[0] -> (1,0,2)[11]
A3) (1,0,2)[11] -> (1,0,1)[0]
B4) (1,0,1)[0] -> (1,0,0)[1]
A4) (1,0,0)[1] -> (0,0,0)[0] 私の勝ち!


まず、ぱっと見て思いつくことをあげていきましょう。

貰ったら負け確の(0,0,0)は、もちろん必勝形です。
0の和なので繰り上がりを考えるまでもなく0です。


また、貰い続けたらいずれ負ける形(a,a)も必勝形です。
同じ2つの値は、各桁の1同士が打ち消し合う（繰り上がり無しのため）ので、この排他的論理和は必ず0になります。


このように、山1つのときの必勝法・全部取る（A4）でも、山2つのときの必勝法・2つの山の枚数を同じにして相手に渡す(A2, A3)でも、排他的論理和=0になっていることが確認できます。


次に赤ペン、青ペンのところです。

私(A)は必勝形で、あなた(B)に渡しています。

一方、必勝形を受け取ったあなた(B)は、必勝形でない形で私(A)に返しています。

Aの行の矢印の右側（私の操作後）は、すべて必勝形になっています。
これは必勝法である、排他的論理和=0で相手に渡し続けるという方法を守っているためです。


実は、排他的論理和≠0の状態を受け取った場合、1回の操作で必ず排他的論理和=0の状態にすることができます(定理1)。

また、排他的論理和=0の状態を受け取った場合、ニムのルール上、排他的論理和=0の状態で返すことはできません(定理2)。

このことは簡単に証明でき、親切なサイトには証明も載っています。
英語版のウィキペディアがわかりやすかったです。

なので、一度必勝形を渡してしまえば、その後もずっと相手に必勝形を渡し続けることができます。


両者このことを知っていた場合、相手に先に必勝形をされてしまうと負けてしまいますよね。
じゃあ、先手必勝でしょうか？

いえいえ、それは早計です。
結論からいうと、初期状態によります。

初期状態が必勝形でないなら先手必勝、必勝形なら後手必勝です。

初期状態が必勝形でないなら、先手は必ず必勝形を相手に渡せます（定理1）。

逆に初期状態が必勝形なら、先手はどう頑張っても必勝形以外の形にすることしかできないので（定理2）、後手に必勝形を作られて負け確です。


さきほどの例ではどうでしょうか。

B1の矢印の左側を見てください。(3,4,5)[10]です。

私は親切にも、必勝形でない初期状態で、あなたに先手を譲っています。
なので、あなたがB1で、例えば(3,4,5)[10] -> (1,4,5)[0]といった適切な操作をしていれば、勝ち確だったわけです。

排他的論理和=0なのはわかった。ではなぜ排他的論理和=0なのか？

実例を見るにたしかに排他的論理和=0が良さそうだ。

他のサイトの証明を見ると、一度、排他的論理和=0にしてしまえば、その後はずっとそれを維持できることもわかった。


では、排他的論理和=0はそもそもどこから出てきたのか。

この疑問に応えているサイトは見当たらなかったので、ここでわかりやすく定性的に説明していきます。


結論からいうと、排他的論理和=0に着目する理由は、

1. (0,0,0)の排他的論理和が0という点
2. 排他的論理和=0を渡し続ければ勝てるという点(定理1,2)

の2つです。


ニムの勝利条件は最後のコインを取ることなので、逆をいうと敗北条件はコイン0枚の状態で自分のターンになってしまうことです。

つまり、両者ともどうにかして相手に(0,0,0)の状態を渡したいわけです。


では、これがどのように排他的論理和=0にむすびつくのでしょうか。

一度、排他的論理和=0を受け取った人は、その後も排他的論理和=0を受け取り続けるのでした（定理1,2）。


たしかに、(0,0,0)も排他的論理和も0ですが、それ以外にも排他的論理和が0の状態はたくさんあるので、1回や2回、排他的論理和=0の状態を受け取ったからといって、すぐに負けるわけではありません。


しかし、ここでもうひとつのニムのルールが効いてきます。

それは、パスはなし（=最低でも1枚は取らないといけない）、ということです。

これがあるために、それぞれのターンでコインは必ず1枚以上減っていきます。

初期状態のコインの合計枚数がN枚だとすると、2人合わせてたかだがN回の操作でゲームは終了してしまいます。

そして、初期状態を(a,b,c)とすると、そこから可能な状態数は最大でもa*b*c個しかありません。
この状態数の集合は、ゲーム進行とともに減少していき、増えることはありません。

これは、全体の状態数だけでなく、排他的論理和=0の状態数についても同じです。

例えば、初期状態(3,4,5)の例では、ここからゲームが進めると、(1,4,5)[0], (1,2,3)[0], (1,0,1)[0]など排他的論理和=0の状態はたくさんあるように見えます。

ですが、これら必勝形の状態数もゲーム進行とともに減少していき、最後にただひとつ、負け確の状態である(0,0,0)だけが残ります。


つまり、負ける人は、排他的論理和=0の集合の中から状態を渡されるが、排他的論理和=0の集合は減少していくため、最後に残る(0,0,0)を受け取る運命にある、ということになります。


また、定理1,2があるために、ずっと相手のターンの開始状態を排他的論理和=0の集合に拘束できます。
以上2つの理由があるために、排他的論理和に着目しています。

今日のベストプラクティス

まず、ゲームで勝つ。
次に、必勝法の理論を説明して論破。
これで2回勝てます！！！