ニム

ニムとは

ニム（英: Nim）は、2人で楽しむことができる数学を基にしたレクリエーションゲームです。このゲームの起源は古代中国にあり、16世紀初頭に西洋で基本的なルールが整えられました。ただし、ニムという名称は1901年にハーバード大学のチャールズ・L・バウトンによって付けられたとされています。

ニムは歴史的に見ても、必勝法が数学的に証明された最初の組合せゲームであり、プレイヤーの最適な戦略によって勝敗が決まる特徴を持っています。

ゲームのルール

ゲームは有限個のコイン、または豆や石など、好きな物体の山を使って行います。2人のプレイヤーが交互に、山から1つの山から任意の個数の物体を取るというシンプルなルールです。重要なのは、回ごとに最低1個は取らなければならず、最終的に最後のコインを取ったプレイヤーが勝者となります。このようなルールを持つニムは「正規形」と呼ばれます。

必勝法

2つの山の場合

特に山が2つだけのシンプルなケースでは、試行錯誤を通じて簡単に必勝法が理解できます。山Aと山Bがあり、それぞれのコインの数をaとbとします。このとき、aとbが等しいとき（加えて言うと後手が必勝となり）、aがbと異なる場合は、先手が多い山からaとbの差の分だけコインを取れば、次に相手はaとbが等しくなることがあり得ず、先手が勝利します。このように、先手が常に有利な選択を続ければ必ず勝利を収めます。

一般的なケース

山がn個あり、それぞれの山のコインの数をA1, A2, ..., Anとした場合、次のニム和Sを用いて必勝法が示されます：

$$ S = A_1 igoplus A_2 igoplus ... igoplus A_n $$

ここで、$$igoplus$$はビットごとの排他的論理和を表します。もしSが0でないなら、必ずSを0にすることができ、次に相手はSが0でない状態にせざるを得なくなります。これを繰り返すことで、先手が確実に勝つことがわかります。

逆に、Sが0であれば後手が勝つ可能性が高くなります。

証明

先手がSからコインを取り除いたとき、得られる新しいニム和Tについての考察が重要になります。特に、$$ S ＼ {A_k} ＼ {B_k} $$という関係から導かれる補題があり、特にSが0でない状態で操作を行うことでTが0にできることがしばしば見られます。

逆形

最後にコインを取る者が負けとなる逆のルールも存在します。この形は「逆形」や「双対ゲーム」と称されています。逆形においても、プレイヤーが非常に戦略的になるため、正規形の必勝形がそのまま適用されるわけではないことにも注意が必要です。特に、山の数量とコインの数に基づく条件に従って、プレイヤーは有利な状態を維持しなければなりません。逆形においては、特定の条件を満たす場合に必勝形に変化することが可能です。

まとめ

ニムはシンプルでありながら、深い戦略を要求するゲームです。数学的な考察を通じて勝敗が決まるこのゲームは、その魅力から多くの人々に親しまれ続けています。数学的な技術と思考を楽しむための理想的なツールとして、多くのプレイヤーに愛されています。

もう一度検索