Loading article…
ニムは、2人のプレイヤーが交互に異なる山や山から物を取り除く（「ニムする」）数学的な組み合わせゲームです。各ターンで、プレイヤーは少なくとも1つの物を取り除かなければならず、同じ山や山からであれば、いくつでも物を取り除くことができます。プレイするバージョンによって、ゲームの目的は最後の物を取らないこと、または最後の物を取ってしまうことです。
ニムはスプラーグ＝グランディの定理の基礎となるものであり、この定理は基本的に、すべての公平なゲームは（より大きな公平なゲームの部分ゲームとみなした場合）単一の山札を持つニムゲームと等価である、と述べている。
ニムの変種は古代から遊ばれてきた。[ 1 ]このゲームは中国発祥と言われており、中国のゲームである捡石子（jiǎn-shízǐ）、「石拾い」[ 2 ]によく似ているが、起源は不明である。ニムに関するヨーロッパで最も古い記述は16世紀初頭のものである。現在の名称は、1901年にこのゲームの完全な理論を開発したハーバード大学のチャールズ・L・ブートンによって考案されたが、 [ 3 ]その名称の由来は完全には解明されていない。オックスフォード英語辞典では、この名称は「取る」という意味のドイツ語の動詞nimmに由来するとしている。
1939年のニューヨーク万国博覧会で、ウェスティングハウス社はニムをプレイする機械、ニマトロンを展示した。[ 4 ] 1940年5月 11日から10月 27日までの6か月間、この機械に勝てたのはほんの数人だった。勝った人には「ニムチャンピオン」と書かれたコインが贈られた。[ 5 ]これはまた、史上初の電子コンピュータゲームの1つでもあった。フェランティはニムをプレイするコンピュータを製作し、1951年の英国祭で展示した。1952年、WLマックスソン社のエンジニアであるハーバート・コッペル、ユージン・グラント、ハワード・バラーは、人間の対戦相手とニムをプレイし、定期的に勝利する23キログラム（50ポンド）の機械を開発した。 [ 6 ]ティンカートイで作られたニムをプレイする機械についても言及されている。[ 7 ]
ニムというゲームは、マーティン・ガードナーが1958年2月にサイエンティフィック・アメリカン誌に寄稿した「数学ゲーム」というコラムのテーマとなった。ニムの一種は、フランス・ヌーヴェルヴァーグの映画『去年マリエンバートで』（1961年）でプレイされ、象徴的な意味を持っている。 [ 8 ]
ニムは通常、最後のオブジェクトを取ったプレイヤーが負けとなるミゼールゲームとしてプレイされます。ニムは、最後のオブジェクトを取ったプレイヤーが勝つ「通常プレイ」ゲームとしてもプレイできます。通常プレイでもミゼールゲームでも、少なくとも2つのオブジェクトがある山がちょうど1つある場合、次にオブジェクトを取るプレイヤーは簡単に勝つことができます。これにより、2つ以上のオブジェクトがある山からすべてのオブジェクト、または1つを除くすべてのオブジェクトが取り除かれると、1つ以上のオブジェクトがある山はなくなるため、プレイヤーはゲームが終了するまで交互にちょうど1つのオブジェクトを取り除くことを強いられます。プレイヤーが偶数個の非ゼロの山を残した場合（通常プレイの場合）、プレイヤーは最後に取ります。プレイヤーが奇数個の山を残した場合（ミゼールプレイの場合）、もう一方のプレイヤーが最後に取ります。
通常のゲームは2人のプレイヤーで行われ、任意の数の物が入った3つの山を使ってプレイします。2人のプレイヤーは交互に、いずれかの山から任意の数の物を取ります。目標は、最後に物を取ったプレイヤーになることです。一方、ミゼールプレイでは、相手に最後の物を取らせることが目標となります。
以下に示すのは、架空のプレイヤーであるボブとアリスの間で行われる通常のゲームの例です。彼らはそれぞれ、3個、4個、5個のオブジェクトの山からゲームを開始します。
ニムで勝つための実際的な戦略は、相手を以下のいずれかの局面に追い込み、その後は毎回、より小さな局面を作り出すことです。ミゼール方式と通常方式では、最後の指し手だけが異なります。
一般化においては、nとmは0より大きい任意の値をとることができ 、同じ値をとることも可能である。
通常プレイのニム（より正確にはニムのシステム）は、スプラーグ・グランディの定理の基礎となるものであり、この定理は基本的に、通常プレイではすべての公平なゲームは、他の通常プレイの公平なゲームと並行してプレイした場合に同じ結果をもたらすニムの山に相当すると述べている（選言和を参照）。
通常のプレイにおける公平なゲームはすべてニム値を割り当てることができるが、ミゼール規約ではそうではない。ミゼール・ニムと同じ戦略を用いてプレイできるのは、穏やかなゲームのみである。
ニムは、順序集合が互いに素な鎖（ヒープ）から構成される、順序集合ゲームの特殊なケースである。
3つのヒープを持つニムゲームの進化グラフは、ウラム・ウォーバートン・オートマトン進化グラフの3つの分岐と同じである。[ 9 ]
ニムは、任意の数の初期ヒープとオブジェクトに対して数学的に解かれており、どちらのプレイヤーが勝つか、そしてそのプレイヤーがどのような勝利への手を取れるかを簡単に計算する方法が存在する。
ゲーム理論の鍵は、ヒープサイズのバイナリデジタル和、つまり、桁上がりを無視した（バイナリでの）和です。この演算は「ビットごとの XOR」または「GF (2)上のベクトル加算」（2 を法とするビットごとの加算）としても知られています。組み合わせゲーム理論では、通常、ニム和と呼ばれ、ここでもそのように呼ばれます。xとyのニム和は、通常の和x + yと区別するために、x ⊕ yと表記されます。サイズ 3、4、5 のヒープを使用した計算例は次のとおりです。
バイナリ 10進数 011 2 3 10 ヒープ A 100 2 4 10 ヒープ B 101 2 5 10 ヒープ C --- 010 2 2 10 ヒープ A、B、C のニム和、3 ⊕ 4 ⊕ 5 = 2
同様の手順で、多くの場合、頭の中で実行しやすい方法は、ヒープのサイズを2の異なるべき乗の合計として表し、同じべき乗のペアを消去し、残ったものを加算することです。
3 = 0 + 2 + 1 = 2 1 ヒープ A 4 = 4 + 0 + 0 = 4 ヒープ B 5 = 4 + 0 + 1 = 4 1 ヒープ C -------------------------------------------------------------------- 2 = 2 1と4を約分した後に残るものは何ですか？
通常のプレイでは、勝利戦略は、すべての手をニム和が0になるように終了することです。これは、手番の前にニム和が0でなければ常に可能です。ニム和が0の場合、相手プレイヤーがミスをしない限り、次のプレイヤーは負けます。どの手番を行うべきかを判断するために、Xをすべてのヒープサイズのニム和とします。Xとヒープサイズのニム和がヒープサイズよりも小さいヒープを見つけます。勝利戦略は、そのようなヒープでプレイし、そのヒープをXで元のサイズのニム和に縮小することです。上記の例では、サイズのニム和はX = 3 ⊕ 4 ⊕ 5 = 2です。X=2の場合のヒープサイズA=3、B=4、C=5のニム和は
縮小されるヒープはヒープAのみなので、勝利条件はヒープAのサイズを1に縮小すること（2つのオブジェクトを取り除くこと）です。
ごく単純な例として、山が2つしか残っていない場合、戦略としては、大きい方の山のオブジェクト数を減らして、両方の山のオブジェクト数を同じにします。そうすれば、相手がどんな手を打っても、プレイヤーはもう一方の山で同じ手を打つことができ、最後のオブジェクトを確実に手に入れることができます。
ミゼールゲームとしてプレイする場合、ニム戦略は、通常のプレイでサイズ1の山しか残らない場合にのみ異なります。この場合、正しい手はサイズ1の山を奇数個残すことです（通常のプレイでは、そのような山を偶数個残すのが正しい手となります）。
通常プレイとミゼールゲームにおけるこれらの戦略は、少なくとも2つのオブジェクトを含む山の数がちょうど1になるまで同じです。その時点で、次のプレイヤーは2つ以上のオブジェクトを含む山からすべてのオブジェクト（または1つを除くすべてのオブジェクト）を取り除き、どの山にも1つ以上のオブジェクトが残らないようにします（つまり、残りのすべての山にそれぞれちょうど1つのオブジェクトが残るようにします）。そのため、ゲームが終了するまで、プレイヤーは交互にちょうど1つのオブジェクトを取り除くことを強いられます。通常プレイでは、プレイヤーは偶数個の非ゼロの山を残すため、同じプレイヤーが最後になります。ミゼールプレイでは、プレイヤーは奇数個の非ゼロの山を残すため、もう一方のプレイヤーが最後になります。
3、4、5の山があるミゼールゲームでは、戦略は次のように適用されます。
上記で述べた最適戦略の妥当性は、C. Boutonによって実証された。
定理：通常のニムゲームにおいて、先手を取るプレイヤーが勝利戦略を持つのは、ヒープのサイズのニム和がゼロでない場合のみである。そうでない場合は、後手を取るプレイヤーが勝利戦略を持つ。
証明:ニム和 (⊕) は通常の加法の結合法則と交換法則 (+) に従うだけでなく、 x ⊕ x = 0という追加の性質も満たすことに注意してください。
移動前のヒープのサイズをx 1 , ..., x nとし、移動後の対応するサイズをy 1 , ..., y nとする。s = x 1 ⊕ ... ⊕ x nおよびt = y 1 ⊕ ... ⊕ y nとする。移動がヒープkで行われた場合、すべてのi ≠ kに対してx i = y iであり、x k > y kである。上記の ⊕ の性質により、
つまり、合計ニムサムを更新する更新後ヒープからキャンセルする必要がありますnim 合計により、そしてニムサム。
この定理は、これら2つの補題からゲームの長さに関する帰納法によって導かれる。
補題１．s = 0の場合、どのような手が取られてもt ≠ 0 となる。
証明:可能な移動がない場合、補題は自明に真である(定義により、最初のプレイヤーは通常のプレイゲームで負ける)。そうでない場合、ヒープk内の任意の移動は (*) からt = x k ⊕ y kを生成する。x k ≠ y kなので、この数はゼロではない。
補題2．s ≠ 0の場合、 t = 0となるような移動が可能である。
証明: sのバイナリ表現における最も左（最上位）の非ゼロビットの位置をdとし、x kのd番目のビットも非ゼロとなるようなk を選択する。(このようなk は必ず存在しなければならない。そうでなければsのd番目のビットは 0 になるからである。) 次にy k = s ⊕ x kとすると、 y k < x kが成り立つ。すなわち、 dの左側のすべてのビットはx kとy kで同じであり、ビットd は1 から 0 に減少し (値が 2 dだけ減少する)、残りのビットの変化は最大で 2 d −1 となる。したがって、最初のプレイヤーは、ヒープkからx k − y kオブジェクトを取り、
t = s ⊕ x k ⊕ y k ((*)による) = s ⊕ x k ⊕ ( s ⊕ x k ) = 0。
ミゼール戦略における修正点は、サイズ2以上の山が1つしかない局面で初めて発生するという点に注目することで明らかになります。このような局面ではs ≠0となるため、この状況は勝利戦略に従うプレイヤーのターンで必ず発生します。通常のプレイ戦略では、プレイヤーはこの山をサイズ0または1に減らし、サイズ1の山を偶数個残しますが、ミゼール戦略ではその逆を行います。この時点から、すべての手は強制されます。
ニム（ただし、減算ゲームと呼ぶ方が適切）として知られる別のゲームでは、1ターンに取り除けるオブジェクトの数に上限が設けられています。プレイヤーは、任意の数のオブジェクトを取り除くのではなく、一度に1個、2個、…個、またはk個しか取り除くことができません。このゲームは、実際には1つの山だけでプレイされるのが一般的です。
ブートンの分析は、このゲームの一般的な複数ヒープ版にも容易に適用できます。唯一の違いは、最初のステップとして、ニム和を計算する前に、ヒープのサイズをk + 1で割った余りに減らす必要があることです。これによりすべてのヒープのサイズがゼロになる場合（ミゼールプレイの場合）、勝利の手は、いずれかのヒープからk個のオブジェクトを取ることです。特に、n個のオブジェクトからなる単一のヒープからの理想的なプレイでは、2番目のプレイヤーが勝つことができるのは、次の場合に限ります。
これは、 S (1, 2, ..., k )のnim シーケンスを計算することによって導かれる。
スプラーグ・グランディの定理から、上記の戦略が導き出される。
ゲーム「21」は、プレイヤーが順番に数字を言うミゼールゲームとして、何人でもプレイできます。最初のプレイヤーは「1」と言い、各プレイヤーは順番に数字を1、2、または3ずつ増やしますが、21を超えてはなりません。「21」と言わざるを得なかったプレイヤーは負けです。これは、21 − n個のオブジェクトの山を使った減算ゲームとしてモデル化できます。このゲームの2人プレイ版の勝利戦略は、常に4の倍数を言うことです。そうすれば、相手プレイヤーは最終的に21と言わざるを得なくなります。したがって、最初のプレイヤーが「1」から始める標準バージョンでは、負ける手からスタートすることになります。
21ゲームは、例えば「最大5まで足す。34になったら負け」のように、異なる数字でもプレイできます。
21のゲーム例（2人目のプレイヤーが勝利戦略に従う場合）：
似たようなゲームに「100ゲーム」があります。2人のプレイヤーが0からスタートし、交互に1から10までの数字を合計に加えていきます。100に到達したプレイヤーが勝ちです。勝利戦略は、数字が連続する数（例：01、12、23、34、…）に到達し、この数列のすべての数字を飛び越えてゲームをコントロールすることです。プレイヤーが89に到達すると、相手は90から99までの数字しか選択できず、次の答えは必ず100になります。
ニムの別のバリエーションでは、単一のヒープから任意の数のオブジェクトを削除できるだけでなく、各ヒープから同じ数のオブジェクトを削除することも許可されている。
ニムのもう一つのバリエーションは「円形ニム」で、任意の数のオブジェクトを円形に配置し、2人のプレイヤーが交互に隣接するオブジェクトを1つ、2つ、または3つ取り除きます。たとえば、10個のオブジェクトで円形にスタートし、
. . . . . . . . . .
最初の動きで3つのオブジェクトが取られる
_ . . . . . . . _ _
それからさらに３つ
_ . _ _ _ . . . _ _
それから1つ
_ . _ _ _ . . _ _ _
しかし、それでは3つの物体を一度に取り出すことはできません。
ニムの別バージョンであるグランディのゲームでは、まず複数のオブジェクトを山積みにし、2人のプレイヤーが交互にその山を異なるサイズの2つの空でない山に分けます。例えば、6つのオブジェクトは5+1または4+2の山に分けられますが、3+3の山には分けられません。グランディのゲームは、ミゼール方式または通常方式のどちらでもプレイできます。
グリーディニムは、プレイヤーが最も大きな山からのみ石を選ぶことが制限されるバリエーションです。[ 10 ]これは有限の公平なゲームです。グリーディニムミゼールはグリーディニムと同じルールですが、最後に手を動かすことができたプレイヤーが負けとなります。
石の山の中で最大の石の数をm、2番目に多い石の数をnとする。m個の石を持つ山の数をp m 、 n 個の石を持つ山の数をp nとする。すると、 p mが偶数であるゲーム局面はP局面であるという定理がある。[ 11 ]この定理は、p m が奇数である局面を考えることで示すことができる。p mが 1 より大きい場合、この山からすべての石を取り除いてp m を1 減らすと、新しいp mは偶数になる。p m = 1 (つまり、最大の山が一意である場合)には2 つのケースがある。
したがって、 p m が偶数となる状態への移動が存在する。逆に、p m が偶数の場合、任意の移動が可能であれば ( p m ≠ 0)、その移動によってゲームはp mが奇数となる状態にならなければならない。ゲームの最終局面は偶数 ( p m = 0) である。したがって、 p m が偶数となるゲームの各局面はP局面でなければならない。
マルチヒープニムの一般化は「ニム」と呼ばれた。または、1910 年に分析したEH ムーア[ 12 ]による「インデックスk」ニム。インデックスkニムでは、1つのヒープからのみオブジェクトを取り除く代わりに、プレイヤーは少なくとも 1 つ、最大k個の異なるヒープからオブジェクトを取り除くことができます。各ヒープから取り除くことができる要素の数は、上記の「減算ゲーム」のように、任意または最大r個の要素に制限される場合があります。
勝利戦略は次のとおりです。通常のマルチヒープ nim と同様に、ヒープサイズ (またはr + 1 を法とするヒープサイズ) のバイナリ表現を考慮します。通常の nim では、各バイナリ桁の XOR 和 (または 2 を法とする和) を形成し、勝利戦略は各 XOR 和をゼロにすることです。インデックスk nim への一般化では、各バイナリ桁のk + 1を法とする和を形成します 。
ここでも、勝利戦略は、各桁の合計がゼロになるように移動することです。実際、最終位置ではこのように計算された値はゼロであり、この値がゼロとなるヒープの構成が与えられた場合、最大k個のヒープを変更すれば、値はゼロ以外になります。逆に、値がゼロでない構成が与えられた場合、慎重に選択された最大k個のヒープから要素を取り出すことで、常に値をゼロにすることができます。
ビルディングニムは、2人のプレイヤーが最初にニムゲームを構築するニムの変種です。n個の石とs個の空の山が与えられたとき、プレイヤーは交互に、選択した山にちょうど1つの石を置きます。[ 13 ]すべての石が置かれたら、次のプレイヤーが動くことからニムゲームが始まります。このゲームはBN(n,s)と表記されます。
n -d ニムはボード上では、任意のハイパーロウから任意の数の連続した駒を取り除くことができる。開始位置は通常、完全なボードであるが、他のオプションも許可されている。[ 14 ]
開始時の盤面は連結していないグラフであり、プレイヤーは順番に隣接する頂点を取り除いていく。[ 15 ]
キャンディニムは、通常のニムのバリエーションで、プレイヤーは同時に2つの目標を達成しようとします。最後のオブジェクト（この場合はキャンディ）を取ることと、ゲーム終了までに最大数のキャンディを取ることです。[ 16 ]
2人用の数学ゲーム「ニム」は、多くの人が中国発祥だと信じており、おそらく世界で最も古いゲームの一つです。
\quad t&=s\oplus x_{k}\oplus y_{k}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c571cc93b20ce1e832a325504bd27e143df8d18)
