放課後の教室で、ハルさんとソラさんが机の上におはじきを15個ならべました。「順番に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個にそろえることができるからです。
わり算の「あまり」が、答えを教えてくれる
では、最初のおはじき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の倍数なら、先に取る人は苦しい。ただし、相手が間違えてくれれば、まだ勝つチャンスは残っています。
コンピュータと石取りゲームをしてみましょう。最後の石を取った人の勝ちです。まず普通に遊んで、そのあと「余りを見る(ヒント)」を押して、のこりの石を(取れる最大の数+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人のゲームでは、「先に動く人が必勝(必ず勝てる)」か「後に動く人が必勝」か、どちらかが決まっている。岡山大学理学部の公開資料にも、そう書かれています。実際には、将棋のように、局面が多すぎて全部は調べつくせないゲームもあります。それでも、「勝てる形」と「負ける形」を見わけるという発想は、パズルやゲームのプログラムを考えるときの土台です。
ふだんの勝負の前に、少し立ち止まってみてください。「このゲームは、残りがいくつのときが苦しいのか」。ゴールから逆向きにたどる習慣がつくと、スポーツの作戦でも、予定の立て方でも、「最後に何をしておくべきか」から考える力が育ちます。ハルさんも、次の日からは、ソラさんと互角に戦える(かもしれない)ようになりました。
