ニム(1901) — 石取りゲームが「解かれた」最初の例と、電球で指す機械

はじめに — 石の山を取り合うだけの遊びが、最初に「解かれた」

これは1901年に名前を得た遊びである。石の山がいくつか並ぶ。二人が交互に、好きな山から好きな数だけ石を取る。最後の一個を取った者が勝つ(逆に、取った者が負けとする形も古くから遊ばれる)。それだけだ。

ハーバード大学のチャールズ・L・バウトンは、この遊びに「ニム(Nim)」の名を与え、論文「Nim, a game with a complete mathematical theory」を Annals of Mathematics 誌に発表した。題名のとおり、必勝の理屈が完全に明らかになったのである。

私はこの遊びを、パズルの歴史の入口に置きたい。運のない二人用の遊びが、数学で「解き切れる」ことを、人々が初めてはっきり見た例だからだ。本稿ではその理屈と、のちに電気仕掛けの機械がこの遊びを指した経緯をたどる。

石の山が並ぶ卓のイメージ（イメージ・AI生成）

その時代の文脈 — 起源は霧の中、名前は1901年

ニムに似た石取り遊びは、古くからあったと考えられている。中国の「撿石子(jiǎn-shízǐ、石拾い)」に似た遊びが起源かもしれないと言われるが、はっきりした証拠はなく、起源は不明である。ヨーロッパの記録は16世紀初めまでさかのぼる。

1901年、バウトンが名前と完全な分析を与えた。オックスフォード英語辞典は、名前をドイツ語の「nimm(取れ)」にたどっている。ただし、なぜその語を選んだかについて、私は本人の言葉を確かめていない。

当時、この遊びを解いたのは紙と鉛筆である。電子計算機はまだない。あるのは盤の上の石と、数を並べて眺める人の頭だけだった。この「手で解ける」という性質が、のちに機械へ移される理由になる。

紙と鉛筆でニムを解く机のイメージ（イメージ・AI生成）

メカニクス — 二進数で書くと、勝ち負けが見える

必勝法の鍵は「ニム和」である。各山の石の数を二進数で書き、桁ごとに足して、繰り上がりを捨てる(排他的論理和、XOR)。たとえば3、5、6個の山は、二進数で011、101、110。桁ごとに足すと000になる。

ニム和が0なら、次に動く側は負ける。0でなければ、次に動く側が勝てる。山を一つ選んで石を減らし、ニム和を0に戻せばよい。相手がどう動いても、ニム和は0でなくなる。これを繰り返せば、最後は自分が取る。

逆形(最後に取る者が負け)でも、ほとんどの局面は同じ手で進み、終盤だけ形が変わる。山がすべて1個になりそうなとき、「1個だけの山」の数が偶数か奇数かで決まる。ここは別の考え方になる。

つまりニムは、ルールが単純でも、勝敗が最初から決まっている遊びである。「知っている側が必ず勝つ」という性質は、遊びとしては残酷だ。だが数学としては、これ以上ないほど美しい。

三つの山と二進数の列の対応を示すイメージ（イメージ・AI生成）

現代への系譜 — 数学の標準部品、そして最初の「遊ぶ機械」

ニムの理屈は、のちの理論の土台になった。1930年代に R. P. Sprague(1936年)と P. M. Grundy(1939年)が、それぞれ独立に、運の要素がなく双方が同じ手を指せる遊びは、すべて一つのニムの山と同じ性質を持つことを示した。スプレイグ・グランディの定理である。

機械の側にも、ニムは早くから現れる。エドワード・コンドンが1939年の冬に考え、ウェスティングハウス社の技師ジェラルド・タウニーとウィラード・デールが作った「ニマトロン」は、1940年のニューヨーク万国博覧会で展示された。七個の電球が四列に並び、継電器(リレー)で動いた。特許は1940年9月に認められている。

遊んだ人数は、資料によって5万人とも10万回ともされ、数字は揃わない。ただ、機械が勝つことが圧倒的に多かった点は共通する。機械は一定の型でしか指せなかったとも伝わる。コンドンは後年、これを「冗談のようなもの」と考えていたと語ったと伝えられる。

1951年には、英国のフェランティ社が「ニムロッド」を作った。設計はジョン・ベネット、製作はレイモンド・スチュアート=ウィリアムズで、英国祭(5月5日)と、同年10月のベルリン産業展で披露された。添えられた冊子は、ゲームの機械が、ずっと複雑な実用の問題にも使える力を示すと説いた。

ニマトロンがニムロッドに影響したと言う資料もあるが、私は設計者本人がそう述べた証拠を確かめていない。ここでは、二つの機械が同じ遊びを選んだ事実を記すにとどめる。選ばれた理由は想像できる。ルールが短く、必勝法が明快で、電球で盤を見せられたからだ。

電球の列から真空管へ、機械が遊びを指すイメージ（イメージ・AI生成）

参考文献

本記事で参照した情報源(論文の書誌は Wikipedia の記述による。原論文そのものは未確認):

・Wikipedia: Nim

・Wikipedia(日本語): ニム

・Wikipedia: Sprague–Grundy theorem

・Wikipedia: Nimatron

・The Nimatron of Edward Condon (Brandeis University 掲載資料)

・Wikipedia: Nimrod (computer)

おわりに — 解けた遊びが遺したもの

歴史が示したのは、ニムが「負けた遊び」ではないことだ。解けたからこそ、理論の部品になり、機械の最初の相手にもなった。解けた遊びは、遊びとしては終わっても、考え方としては生き続ける。

今のパズルも、同じ問いの上にある。この盤面は解けるのか。誰が勝つのか。最短で何手か。1901年の紙の上で始まったその問いを、私たちはいまも解き続けている。

石を一つ手に取って、考えてみてほしい。三つの山の前で、あなたは最初に何を取るか。

静かな卓上に石が一つ残るイメージ（イメージ・AI生成）