■数学基礎：フィボナッチ寿司

石取りゲーム(ニム)の第2弾「フィボナッチ寿司」。パーツは使いまわしだけれど、ルールが違うので必勝法も違うからね。Wikipediaの分類によると「二人零和有限確定完全情報ゲーム」ということになる。

ルール：
１：最初の一手のみ、寿司は何個でも取れる（ただし、全部を取ることはできない）。
２：二手目からは、相手の取った寿司の数の2倍まで取ることができる。
３：交互に寿司を取り、最後に寿司を取ったほうが勝ち（パスはできない）。

前に「蓼食うバグも寿司好きゲーム」を作ったが、必勝法を発見するというより、先手なら、どんな手を打っても勝ててしまう（しかもバグあり）。数理ゲームにしても、もう少し楽しめるものを作りたいなぁ、というのが今度の「フィボナッチ寿司」なんだけど、必勝法をコンピュータに覚えさせるのに苦労するばかりで、完成しても自分では楽しめない；；

とりあえず、必勝法と解説は後日……＾＾；

2月17日追記：必勝法はこちら

ナイナイの「やべっち寿司」ならぬ、「フィボナッチ寿司」は、そのタイトルからわかるように、戦略にフィボナッチ数列を利用している。フィボナッチ数列とは、1,1,2,3,5,8,13,21……と続いていく数のこと。

数式で書くとやたら難しいが、1+1=2、1+2=3、2+3=5というように前項ふたつの和になっていく数の並びだ。これと石取りゲームである「フィボナッチ寿司」がどう関係するかと言うと、寿司の残り数がフィボナッチ数列になるように取っていく、それだけである。

たとえば、最初、寿司の数は14個、それより小さいフィボナッチ数は、13なので、14-13で1つの寿司を取る。13の場合は、フィボナッチ数なので、1つ取る。残りが12の場合は、12より小さいフィボナッチ数は8で、12-8=4になるが、これをフィボナッチ数に分解して「3+1」とし、小さいほうを取る。なぜなら、12のとき、3を取ってしまうと、12-3=9で、今度は相手がフィボナッチ数になるように取ることができる。つまり、自分はフィボナッチ数になるように残し、相手はフィボナッチ数にできないようにする戦略だ。

というわけで、このゲームは先手必勝。後手では、どんなにがんばっても勝てない。