NIM（石取りゲーム）

NIMと英語ではいい、日本では「石取りゲーム」「三山崩し」と呼ばれるゲームがあります。チップ（硬貨を模したプラなどの円盤）を3か所に置きます。チップの数は適当で良いです。この3つの場所を「山」ということもあります。 2人でゲームをし、交代でチップを取ります。このとき、いくつ取っても良いが、一つの場所（山）からしか取れません。 2つ以上の場所から取るのはルール違反です。また、必ず石は取らなくてはならず、パスすることはできません。こうして、最後にチップを取った者が勝者になります。

例

具体的な例を紹介しましょう。最初の山が2-3-4だったとします。

A: 右の山から3つ取り、2-3-1にする

B: 左の山から1つ取り、1-3-1にする

A: 中央の山から3つ取り、1-0-1にする

B: 左の山から1つ取り、0-0-1にする

A: 右の山から1つ取り、0-0-0にする。

最後のチップをAが取ったので、Aの勝ちです。勝敗が決まると、最後はかならず0-0-0の形になります。

勝ちパターン

しばらくやってみると、勝ちパターンがあることが分かります。例えば、自分が石を取って、0-1-1の形で相手に手を回すと、相手はどちらかの山からひとつ石を取るしかなく、最後の石は自分が取ることができます。このような勝ちパターンを「必勝形」と呼ぶことにします。「必勝形」はその形をもって相手の手番にすることに注意してください。逆に言えば、相手に必勝形を作られて、自分の手番になり、互いに最善手をくりかえせば、自分の負けになります。

必勝形には、他にも0-2-2や0-3-3のように、1か所がゼロで、他の2か所が同じ数のものがあります。また、1-2-3も必勝形です。少し考えてみれば、これらが必勝形であることがわかると思います。

必勝形の分析

必勝形を分析して、そのパターンの成り立ちが分かれば、NIMに勝てるようになります。これは難しい問題ですが、すでにこのパターンの仕組みは知られています。ポイントは数字を二進数で表すことです。いくつかの必勝形を二進数で書いてみましょう。

必勝形	二進数
0-3-3	0-11-11
1-2-3	1-10-11
1-4-5	1-100-101
2-4-6	10-100-110

気づいたでしょうか。ビットごとに見ると、1が偶数個（0個の場合も偶数個です）であることがわかります。例えば、2-4-6のときは、10-100-110で、左端（4の位）が1が2個で偶数、中央（2の位）が1が2個で偶数、右端（1の位）が1が0個で偶数です。

コンピュータ言語では、ビットごとの排他的論理和（XOR）をとる演算が定義されていることが多いです。 Rubyの場合は、^がそれにあたります。排他的論理和では、

0^0=0
1^0=1
0^1=1
1^1=0

となります。上の例では1桁だけですが、2桁以上の数でもこの演算子でビットごとの排他的論理和を計算できます。例えば、

3^5=011^101=110=6

となります。

必勝形では、それぞれの数の排他的論理和をとるとゼロになります。例えば、1-2-3は必勝形ですが、

1^2^3（十進数表記）=1^10^11（二進数表記）
= 00（二進数表記、各ビットの1の数が偶数だから全部0になる）
= 0

排他的論理和がゼロの状態からチップを取ると、排他的論理和が0では無くなります。そこから、うまくチップを取ると再び排他的論理和がゼロになります。このことは、成り立つことが知られています。証明はインターネットで探せばどこかにあるでしょう。

したがって、ひとたび必勝形を作り、相手に手番を渡したプレーヤーは、常に排他的論理和がゼロの状態をキープすることができます。そして最終的に勝利を手に入れることができるのです。

コンピュータで必勝形を探す

コンピュータで必勝形を探すプログラムは簡単です。要するに排他的論理和がゼロになるような取り方を計算するだけですから。このプログラムをRubyで作ってみました。起動時に引数で3つの山のチップの数を与えると、必勝形を作って表示します。もしも、最初に与えたチップの数がすでに必勝形であれば、プレーヤーは勝つことができません。その場合は、プログラムは"Lost"と表示します。

class Nim
    attr_reader(:a, :b, :c)
    # The arguments below must be non-negative.
    # If some of them are negative, they will be replaced by the absolutes of them.
    def initialize(a=0,b=0,c=0)
        @a = a>=0 ? a : -a
        @b = b>=0 ? b : -b
        @c = c>=0 ? c : -c
    end
    def try
        x = @a^@b^@c
        return false if x == 0
        if @a > @a^x
            @a = @a^x
        elsif @b > @b^x
            @b = @b^x
        elsif @c > @c^x
            @c = @c^x
        else
            return false
        end
        true
    end
    def to_s
        "#{@a}, #{@b}, #{@c}"
    end
end

def usage
    $stderr.print "Usage: ruby nim.rb a b c\n"
end

if ARGV.size != 3
    usage
    return
end

h = Nim.new(ARGV[0].to_i, ARGV[1].to_i, ARGV[2].to_i)
if h.try
    print h
else
    print "Lost"
end