考える力AI照合済み

必勝法ゲーム(ニム)

先に取るほうが必ず勝てる?
← 一覧にもどる
イメージ図(AI生成)

放課後の教室で、ハルさんとソラさんが机の上におはじきを15個ならべました。「順番に1個から3個まで取って、最後の1個を取った人が勝ちね」。じゃんけんに勝ったハルさんが、先に取ることになりました。最初に何個取るのがいいのでしょう。じつはこのゲーム、運ではなく、ある計算ひとつで「どう取れば必ず勝てるか」がわかるのです。

まず予想!

石が15個あります。2人が交代で1〜3個ずつ取り、最後の1個を取った人が勝ちです。先に取る人は、最初に何個取ると必ず勝てる?

先に取るのは、得? 損?

ハルさんは考えました。「先に動けるんだから、有利に決まってる。まずは1個かな」。ソラさんは2個取って、残りは12個。ハルさんが1個、ソラさんが3個、ハルさんが2個、ソラさんが2個、ハルさんが3個……と進んで、気がつくと、最後の1個を取ったのはソラさんでした。

もう1回。今度は、ハルさんが2個、ソラさんが1個。何度くり返しても、勝つのはなぜかソラさんです。「ずるしてない?」とハルさんが聞くと、ソラさんは笑って言いました。「ずるじゃないよ。お兄ちゃんに教わった、ちょっとしたコツがあるだけ」。先に取れるのに、勝てない。ハルさんは、すっかり不思議な気持ちになりました。コツの正体を知るには、ゲームの終わりから考えるのが近道です。ふつうは「最初に何個取ろうか」と始めから考えますが、このゲームでは、勝負の決まるところから、時間を逆向きにたどっていくのです。

ゴールから、逆向きに考えてみる

まず、残りの石が1個、2個、3個のときを考えます。自分の番なら、全部取ってしまえばその場で勝ちです。では、残りがちょうど4個のときはどうでしょう。1個取れば残りは3個、2個取れば残りは2個、3個取れば残りは1個。どれを取っても、相手に「全部取れる数」を渡してしまいます。つまり、残り4個で自分の番になった時点で、相手が正しく取り続けるかぎり、もう勝てません。

ここがコツの入り口です。残りが5個、6個、7個のときは、1個から3個を取って「ちょうど4個」にして相手に渡せます。すると、相手は先ほどの「勝てない形」に立たされます。残りが8個ならどうでしょう。どう取っても、5個から7個が相手に残るので、相手に4個にされてしまい、今度はこちらが勝てない形です。

こうして調べていくと、勝てない形は4、8、12、16……と、4ずつ飛んでならびます。つまり、4の倍数です。自分の番で残りが4の倍数なら苦しい。そうでなければ、相手に4の倍数を渡せるので、有利になれる。「なぜ4なのか」といえば、一度に取れるのが3個までなので、1回ずつの取り合いで合わせて4個にそろえることができるからです。

勝てない形:4,8,12,16,…

わり算の「あまり」が、答えを教えてくれる

では、最初のおはじき15個にもどりましょう。15を4でわると、3あまり3です。あまりの3個を取れば、残りは12個。ちょうど4の倍数になります。ハルさんは、1個や2個ではなく、3個取ればよかったのです(そして、そのあとも正しく取り続ければ、です)。1個取ると残りは14個で、14を4でわったあまりは2。ソラさんが2個取って、12個にしてしまいます。

そのあとは、「相手と合わせて4個」を守るだけです。ソラさんが1個取ったら、ハルさんは3個。2個取られたら2個。3個取られたら1個。1ラウンドで必ず合わせて4個になるので、残りは12、8、4、0と減っていき、最後の1個はハルさんが取れます。相手がどう動いても、同じことのくり返しです。

これは、石の数や取れる数を変えても同じです。1個から最大で4個まで、どの個数でも取れるゲームなら、4+1=5でわります。22個、1〜3個のゲームなら、22÷4=5あまり2。先に2個取って、残りを20個にします。もしあまりが0で、はじめから4の倍数なら、先に取る人は苦しい。ただし、相手が間違えてくれれば、まだ勝つチャンスは残っています。

15÷4=3あまり3 → 3個取る
さわってみよう

コンピュータと石取りゲームをしてみましょう。最後の石を取った人の勝ちです。まず普通に遊んで、そのあと「余りを見る(ヒント)」を押して、のこりの石を(取れる最大の数+1)でわった余り(はじめの設定では4)を見ながら遊んでみてください。コンピュータに勝てるでしょうか。(スライダーで石の数や取れる数を変えると、新しいゲームになります。)

山が3つになると? ブートンの発見

いま遊んだのは、石の山がひとつだけで、取れる数に上限がある、いわば「やさしい版」です。本家の「ニム」というゲームでは、石の山がいくつかあり、取る山を選びます。そして1回に、選んだ山から好きなだけ取れます。最後の石を取った人の勝ち、というところは同じです。

「ニム」という名前で書かれた論文は、1901年に『アナルズ・オブ・マセマティクス』という数学の雑誌に載った、ハーバード大学のチャールズ・ブートンのものだと、研究者のLisa Rougetet氏が紹介しています。ブートンは、このゲームの勝ち方を完全に説明してみせました。山の石の数をそれぞれ2進法(0と1だけで数を表す書き方。たとえば5は101)で書いてたてにそろえ、桁ごとに1の数を数えます。どの桁も偶数なら、ブートンのいう「安全な形」です。

「安全な形」を相手に渡せば、相手がどう取っても安全ではなくなり、こちらはまた安全な形に戻せます。ひとつの山で1〜3個ずつ取るゲームでは、4の倍数が安全な形(相手に渡せば、こちらが必ず勝てる形)でした。山が増えても、考え方は同じです。「勝てる形」と「負ける形」を見分けて、そこへ相手を追いこんでいく。この論文は、ゲームを数学で調べる分野(組合せゲームの理論)の出発点のひとつとみなされています。

ニムをする機械が、万国博覧会にやってきた

ニムの勝ち方は、「この形ならこう取る」と、手順がきっちり決まっています。ということは、機械にもできるはずです。1940年、アメリカの電機会社ウェスチングハウスが、ニムで人と対戦する機械「ニマトロン」を作りました。ニューヨークの万国博覧会で人びとの前に出されたと、Rougetet氏の論文は伝えています。

この機械の特許(アメリカの特許番号2,215,544)には、エドワード・コンドンら3人の名前があります。特許の書類によると、出願は1940年4月26日、特許が認められたのは同じ年の9月24日です。ランプの列を山に見立てて、人が押しボタンでランプを消していく。人が「勝てる形」を相手に渡せない手を打つと、中のリレー(電気で動くスイッチ)が2進法の計算をして、機械が「相手を負けの形にする手」を打ちます。1901年の論文から約40年。紙の上の数学だった勝ち方が、電気の機械になって、万博の来場者と勝負していたことになります。計算の手順がはっきりしたゲームは、機械に任せられる。この考え方は、のちのコンピュータの勉強にもつながっていきました。

ルールをひとつ変えると、勝ち方も変わる

さて、ゲームのルールを少しだけ変えてみましょう。「最後の1個を取った人が負け」にしたら、どうなるでしょうか。さっきの4の倍数のルールをそのまま使うと、失敗します。最後の1個を取りたくないのですから、「相手に最後の1個を取らせる」ことがゴールになるのです。

考え方は同じで、ゴールから逆向きにたどります。残りが1個なら、取るしかないので負け。残りが2個、3個、4個なら、1個から3個取って1個にして、相手に渡せば勝ち。残りが5個は、どう取っても2〜4個が残り、負け。こうして、負けの形は1、5、9、13……と、4でわって1あまる数になります。

15個のゲームなら、15÷4=3あまり3なので、2個取って13個にします。13÷4=3あまり1。これで相手に負けの形を渡せました。同じ「石取り」でも、勝ち負けの決め方が変わると、先に取る人にとっての最善の手が変わる。ルールをよく読むことが大事だとわかります。

今日、どこで使う?

遊びの場面なら、すぐ使えます。「1から順に、2人で交代して1〜3個ずつ数を言い、20を言った人の勝ち」という数字ゲームは、石取りと同じです。20÷4=5あまり0なので、正しく数えれば、後から言う人が必ず勝てます。先に言う人は、相手が間違えるのを待つしかありません。友だちとの暇つぶしでも、「どっちが有利なゲームか」を先に見ぬけるわけです。

おたがいに全部の情報が見えていて、運の要素がなく、引き分けもなく必ず終わる2人のゲームでは、「先に動く人が必勝(必ず勝てる)」か「後に動く人が必勝」か、どちらかが決まっている。岡山大学理学部の公開資料にも、そう書かれています。実際には、将棋のように、局面が多すぎて全部は調べつくせないゲームもあります。それでも、「勝てる形」と「負ける形」を見わけるという発想は、パズルやゲームのプログラムを考えるときの土台です。

ふだんの勝負の前に、少し立ち止まってみてください。「このゲームは、残りがいくつのときが苦しいのか」。ゴールから逆向きにたどる習慣がつくと、スポーツの作戦でも、予定の立て方でも、「最後に何をしておくべきか」から考える力が育ちます。ハルさんも、次の日からは、ソラさんと互角に戦える(かもしれない)ようになりました。

ひとことで言うと残りの石を(最大+1)でわった余りで考える。

使ってみよう

石が22個、1〜3個取れます。あなたが先に取るとき、最初に何個取る?
22 ÷ 4 = 5 あまり 2
余りの2個を取ると、残りは20個(4の倍数)
確かめ:22 − 2 = 20 = 4 × 5
答え:2個
石が20個、1〜3個取れます。あなたが先に取るとき、必ず勝てる取り方はある?
20 ÷ 4 = 5 あまり 0
余りが0なので、最初から負けの形
1個取って、相手が間違えるのを待つ(相手が正しければ勝てません)
答え:ない(20は4の倍数)
石が17個、1回に1〜4個取れます。あなたが先に取るとき、最初に何個取る?
最大が4個なので、4 + 1 = 5 でわる
17 ÷ 5 = 3 あまり 2
2個取ると残り15個(5の倍数)
答え:2個

よくある「あれ?」

1〜3個取れるゲームなので、3でわった余りで考える → 4(=最大+1)でわった余りで考える
「3個まで」と書いてあるので、3が大事に見えるから。でも1ラウンドで合わせて取る数は、3ではなく4個にそろえます。
先に取る人が、いつも有利 → 4の倍数のときは、後に取る人が有利
先に動けるのは得に思えるから。でも石が12個や16個だと、先に取る人はどう取っても負けの形になり、正しく返されると勝てません。

これ、どこで使う?

1から順に数を言い合うゲームでも同じです。「2人が交代で1〜3個の数を続けて言い、20を言った人の勝ち」なら、20 ÷ 4 = 5 あまり 0 なので後に言う人が必勝です。ルールを数にすなおに置きかえて、余りを見るのが近道です。

なるほど2問

ほんとうは…・出典

この章は「山が1つ」のかんたんな版

本家のニム(三山崩し)は、石の山が複数あり、取る山を選びます。その必勝法は、各山の石の数を2進法で書いて排他的論理和(XOR)を考える、少しむずかしい方法です。この章で扱ったのは、山が1つで取れる数に上限がある、いわば「引き算ゲーム」で、余りだけで必勝法が決まります。

最後の1個を取ると負け、のルール

ルールを逆にして「最後の1個を取った人が負け」にすると、必勝の形は変わります(この場合は、残りを4でわって余りが1になる形が負けの形です)。この章は「最後を取った人の勝ち」だけを扱いました。

コンピュータの強さ

このゲームのコンピュータは、AIで学習しているのではなく、余りの計算どおりに動く簡単なプログラムです。勝てる形では必ず勝ち、負ける形では1個取るだけです。

【未確認】現行の学習指導要領解説のページ番号

出典の「あまり」の記述(第3学年)は、解説PDFの本文を直接確認しました。ただしPDFの正確なページ番号は確認していません(未確認)。

【未確認】他の大学・研究機関の資料

ニムの一般論は岡山大学理学部の公開資料で確認しました。一松信『石取りゲームの数理』など書籍の内容は、実際には開いて確認していません(未確認)。

数値はこのサイトのオリジナル

石の数や例題の数値は、この章のための例です。

【未確認】「ニム」という名前の由来

名前の由来は、確認できる資料を読めていないので、本文には書きませんでした(未確認)。

【未確認】ニマトロンの展示の細かい事情

展示の年(1939〜40年の万博のうち、いつ展示されたか)や、対戦回数・勝敗数などは、資料によって書き方がちがうため、本文には書いていません。Bouton本人の論文(1901年)も、原文は直接開けていません。上の記述は、Rougetet氏の論文と特許の本文で確認できた範囲です(未確認の部分あり)。

ハルさんとソラさんは架空の登場人物

導入の物語に出てくる2人と「お兄ちゃんに教わったコツ」は、この章のための架空の話です。

出典と確認状態(AI照合済み)

例題・数値はこのサイトのオリジナルです(実在の店・商品とは関係ありません)。

この章で、まちがいや古くなった情報に気づいたら、報告フォームから教えてください