ニムと二進数の必勝法

複数の山から、毎手一つの山だけを選んで1個以上の石を取ります。最後の石を取った側が勝つ通常のニムでは、各山の個数を排他的論理和で合わせた「ニム和」が0かどうかで、すべての局面の勝敗を判定できます。

山の合計では勝敗が分からない

一手で二つの山から取ることはできません。一つの山からなら、1個でも全部でも取れます。例えば2個と2個の二山では、先手が片方を減らしたら後手がもう片方を同じ数にできます。しかし1個と3個なら、先手が3個の山から2個取って1個ずつにできます。合計はどちらも4個ですが、手番側の勝敗は反対です。各山への分かれ方を記録する必要があります。

ニム和は桁上がりしない足し算

二進数の各桁で、1が奇数個なら1、偶数個なら0とします。これがXORで、記号は⊕です。例えば3⊕5⊕7は、011、101、111を桁ごとに合わせて001、すなわち1になります。同じ数はx⊕x＝0となり、0とのXORは元の数です。普通の足し算と混同しないよう、計算の途中で二進表記を並べると確かめやすくなります。

0を相手に渡す手を探す

ニム和sが0でなければ、ある山の個数hをh⊕sへ減らせます。ただしh⊕sがhより小さい山を選びます。3、5、7ならs＝1で、3の山を2へ減らすと2⊕5⊕7＝0になります。5を4、7を6へ減らす手も勝ちを保ちます。必勝手が一つとは限らないため、見本と違う手でもニム和が0なら同じ目的を達成しています。

なぜ必ず0へ戻せるのか

sの最上位の1に注目します。その桁が1の山を選ぶと、h⊕sはその桁が0になり、より上の桁は変わらないためhより小さくなります。よって実際に石を取り除いて実現できます。一方、ニム和0の局面で一山をhからkへ変えると、新しい和はh⊕kで0にはなりません。この二つの性質により、0を渡す側が最後の石を取るまで応答を続けられます。

使える条件を確かめる

最初のニム和が0なら、先手は必ず0を崩すため、相手が正しく戻せば負けます。最後の石を取ると負けるミゼールでは終盤の扱いが変わります。また、1、3、4個だけ取れる制限付きの山では、個数そのものをXORしてはいけません。その場合は各山のグランディ数を求めます。XORという計算だけでなく、何をXORする規則なのかが重要です。

関連項目