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

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


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

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

とりあえず、必勝法と解説は後日……^^;

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

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

20070217_01

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

20070217_02

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

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

“■数学基礎:フィボナッチ寿司” への3件の返信

  1. ふらふらとたどり着きました。
    なかなか難しいゲームにしばし・・・・キーィ!勝てない!

  2. >なぜなら、12のとき、3を取ってしまうと、
    全部で14個のこのゲームの場合、直前に相手は1つしか取っていないので3つは取れません。
    また残り11個のときは1つ取るように表で書かれてあるのですが、3つ取るべきです。そうすると相手は残り8個となり、全部は取れないのでフィボナッチ数にするために3つ取りに来ることになりますが結果的に残り5個となり全部取ることができます。
    決して相手に残りフィボナッチ数にされることが悪いとはいえないと思います。

  3. > 全部で14個のこのゲームの場合、直前に相手は
    > 1つしか取っていないので3つは取れません。
    ゲームスタート時は、何個でも取ることができるので、
    プレイヤーが先手のとき、2個取ることもできます。
    自ら勝機を逃す手ですが、この場合、残り12個で、
    コンピュータは、倍の4個まで取ることができます。
    遊んでもらえれば、わかりますが、残り11個で、且つ
    COM側が3個取れる状況にあるとき(プレイヤーが先手で
    3個取ったときと、COM先手で、次にプレイヤーが2個
    取った場合)、COMは、3個取って、残りを8個にします。
    解説の表を作成するときに間違えました。というか、
    3個取れない場合でしたね。説明不足でした;;

コメントは受け付けていません。