35年前、大学生協で買ったポケコンに、ビンとりが入っていました。
棚に並んだ瓶を、コンピュータと交互に取る。1回に取れるのは3本まで。そして最後の1本を取らされたほうが負けです。
ずいぶん遊びました。そして、よく負けていた記憶があります。当時はそれを、自分の下手さのせいだと思っていました。
1段・21本から作りました
Claudeに作ってもらったビンとりには、モードが2つあります。ひとつが、ポケコンにあったのと同じ1段・21本。右の端から、1回に3本まで取ります。
作っている途中で、Claudeがさらっと言いました。「この21本は、先手が何をしても勝てません」と。
4で割って1余ったら、渡された人の負け
理由は拍子抜けするほど単純でした。
相手が1本取れば自分は3本、2本なら2本、3本なら1本。相手が何本取っても、合わせて4本になるように取り返せる。つまり、相手に渡る本数を4本ずつ減らしていけます。
だから、相手に渡すときに4で割って1余る本数にできれば、そこで勝ちが決まります。あとは4本ずつ削って、最後は相手に1本だけを渡して終わり。相手はそれを取るしかありません。
相手に渡せば勝てる本数 1 5 9 13 17 21
いちばん右に、21があります。
21本というのは、渡された人が負ける形そのものでした。そして人間はいつも先手です。つまりこのゲーム、始まった瞬間に、こちらが「渡された人」になっています。
だから「むずかしい」では勝てませんでした
理屈はそうでも、本当にそうなのか。同じ規則で動くシミュレータを書いて、20万局ずつ戦わせました。
1段・21本（人間の勝率）
てきとう 最善手
かんたん 39.9% 96.7%
ふつう 11.3% 63.9%
むずかしい 0.0% 0.0%
「てきとう」は適当に取る人、「最善手」は毎回いちばん良い手を指す人です。
「むずかしい」は0.0%。四捨五入ではなく、20万局で1勝もしていません。最善を尽くしても勝てない。最初から詰んでいるからです。
裏を返すと、「かんたん」と「ふつう」で勝てるのは、CPUがわざと間違えてくれているからでした。35年前に私が勝てた日も、たぶんそういう日だったのだと思います。
段が4つになると、割り算では足りません
これでは身も蓋もないので、4段モードを足してもらいました。棚が4段あって、本数はばらばら。段ごとに、何本でも取れます。
段がひとつなら「4で割った余り」で済みました。段が増えると、これが効かなくなります。代わりに出てくるのが排他的論理和（XOR）です。
各段の本数を2進数で書いて、桁ごとに足して2で割った余りを並べる。繰り上がりのない足し算だと思えば近いです。これをニム和と呼びます。
3本 011
4本 100
5本 101
6本 110
------------
ニム和 100 （＝4）
ニム和が0の形を相手に渡せれば、勝ちです。上の例は0ではないので、いま手番の人に勝ち目があります。
この話、ずいぶん新しいものかと思っていたら1901年でした。ハーバード大学のチャールズ・L・ブートンが「Nim, a game with a complete mathematical theory」という論文で解いています。「ニム」という名前も、このとき彼が付けたものです。それまでは「ファンタン」と呼ばれていたそうです。
「最後を取ったら負け」が効くのは、ほんの一瞬でした
ここで気になったのが、「最後を取ったら勝ち」との違いです。ビンとりは取らされたら負けなので、ふつうのニムとは逆向きのルールになります。
ところが、違いはほとんどありませんでした。4段それぞれ0〜7本、4096通りの形を全部調べたところ、答えが変わるのは16通り。0.4%だけです。
しかもその16通りは、すべてどの段も1本以下になった形でした。つまり、終盤のほんの数手だけ。それまでは、ふつうのニムとまったく同じように指していい。
実戦用に言い換えると、こうなります。
- 2本以上の段があるうちは、ニム和が0になるように渡す
- 全部の段が1本ずつになったら、本数が奇数になるように渡す
最後の最後だけ、ひっくり返る。これもブートンの論文の第6節に、もう書いてありました。124年前です。
4段なら、たいてい勝てます
4段の初期配置は、各段1〜7本で合計9本以上という条件で作っています。この条件を満たす2331通りを全部調べたところ、先手が勝てる形は2044通り、87.7%でした。
そのうえで、最善手を指す人を20万局戦わせた結果が、これです。
4段・ばらばら（人間の勝率）
てきとう 最善手
かんたん 38.7% 99.0%
ふつう 14.1% 94.4%
むずかしい 0.5% 87.7%
「むずかしい」で87.7%。配置を数えて出した87.7%と、ぴったり同じ数字になりました。完璧なCPU相手でも勝てる配置なら必ず勝てるということで、シミュレータの検算にもなっています。
もうひとつ。同じ「むずかしい」でも、てきとうに取ると0.5%です。1段の0.0%と並べると、このゲームの性格がよく出ていると思います。知っているかどうかが、ほぼすべて。
35年越しの答え合わせ
ポケコンのビンとりで負け続けていたのは、下手だったからではありませんでした。先手で21本を渡された時点で、もう負けていただけです。
当時の私がそれを知っていたら、たぶんもっと早く飽きていたと思います。知らなかったから、何度も挑みました。それはそれで、悪くない時間でした。
4段モードのほうは、知っていれば9割近く勝てます。ニム和の話を頭に入れて、ビンとりをどうぞ。むずかしいで勝てたら、それは実力です。
コメント