読者です 読者をやめる 読者になる 読者になる

いものやま。

雑多な知識の寄せ集め

馬跳びゲームを考えてみた。(その2)

ゲーム

馬跳びゲームについては、昨日の記事を参照。

今日はその必勝法について。

基本的な考え方

必勝法は、逆算で考えていくといい。

馬跳びゲームの場合、9cmのラインの手前を取れれば、必ず勝てる。

自分が先手(Aの消しゴムを使う)として、9cmのラインの手前を取れた場合のパターンは、次の4通り。

case 1

  7   8   9  10 |
  |   |   |   | |
----------------+
    A   A

case 2

  7   8   9  10 |
  |   |   |   | |
----------------+
    B   A

case 3

  7   8   9  10 |
  |   |   |   | |
----------------+
A   _   A

case 4

  7   8   9  10 |
  |   |   |   | |
----------------+
B   _   A

case 1、2の場合

この場合、相手の手番で、2つの場合が考えられる。

  • 10cmのラインの手前に相手がジャンプしてくる。
  • 10cmのラインの手前に相手がジャンプしてこない。

ジャンプしてきた場合、一番前のAをジャンプすれば、10cmのラインを越えられるので、勝ち。

そうでない場合、一番前のAを前進させる。
そうすると、以下のようになる。
(XはAまたはB)

  7   8   9  10 |
  |   |   |   | |
----------------+
    X   _   A

このようになれば、相手がジャンプをしてきても相手の消しゴムは絶対に9cmのラインの手前で止まるので、次に一番前のAを前進させることで10cmのラインを絶対に越えられる。

このことから分かる重要なことは、case 1、2の形になれば、自分の手番でも相手の手番でも、必ず自分が勝てるということ。

case 3、4の場合

この場合、case1、2の状態になるまで待っていればいい。
というのも、case1、2の状態になれば、それが自分の手番でも相手の手番でも絶対に勝つことが出来るから。

そして、消しゴムは前にしか進まないので、手を進めていく中で、手詰まりになって必ずcase1、2の状態になる。

なので、この場合も必勝となる。

再帰的に考える

このことに気がつければ、あとは再帰的に考えていけばいいだけ。

9cmのラインの手前が取れれば必勝であるという事実が意味することは、(N-2)cmのラインの手前が取れれば、Ncmのラインの手前を必ず取れるということに他ならない。

なので、

  • 10cmのラインを越える(=11cmのラインの手前を取る)ためには、9cmのラインの手前を取れればいい。
  • 9cmのラインの手前を取るには、7cmのラインの手前を取れればいい。
  • 7cmのラインの手前を取るには、5cmのラインの手前を取れればいい。
  • ...
  • 1cmのラインの手前を先手がとることで、先手必勝となる。

このように、細かい動きをあまり考える必要もなく、1cm、3cm、5cm、7cm、9cmのラインの手前を取れるように移動するだけで、必勝となる。

改善策

これを改善するには、次の縛りを入れるとよさそう。

一番先頭にある消しゴムは、前進させることが出来ない。

もちろん、一番先頭にある消しゴムはジャンプをすることも出来ないので、必然的に動けないということになる。

こうすると、簡単な必勝法は見つからないんじゃないかな・・・?
(もちろん、二人零和有限確定完全情報ゲームなので、必勝法は必ず存在するのだけど)

バリアント

なお、この動き方のシステムで、いくつかバリアントを考えることも出来る。

  • 0/1/2/3の目の4面ダイスを振って、出た目以外の消しゴムを動かすことが出来る。
    (0が出たらどれを動かしてもいい。1が出たら、1番前の消しゴムは動かせない)
  • 消しゴムに1〜6の番号をつけ、秘密裏に3つの消しゴムを賭ける。
    終了条件を満たしたとき、先頭の消しゴムから得点をつけ、賭けていた消しゴムの得点がもらえる。

こういったバリアントを入れると、動きが確定じゃなくなったり、完全情報じゃなくなるので、必勝法はなくなってくる。
面白くなるかどうかは分からないけど。

今日はここまで!