トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

桃鉄ハワイで、ゴールするまで何回さいころを振るかの期待値

(最終更新:2017.3.3)

はじめに

これはもともと、科学系ソーシャルコミュニティ「なぞらぼ」(nazolab.net)に提示された問題で、私もこれに回答をしたのですが、なぞらぼのサービスが終了したため、こちらに私の回答を残しておくものです。

なお、なぞらぼの内容はWayback Machineには残っています。こちらもご覧ください。(提示された問題と私の回答の箇所だけ残ってました)
http://web.archive.org/web/20150731075048/http://nazolab.net/qa/q/75

問題設定

桃鉄(桃太郎電鉄)は、いわゆるすごろくゲームなのだが、「サイコロを振って出た数を、折り返すことなく進まないとならない」という制約がある。
そのため、ゴール地点が行き止まりになっている場合(この代表例が「ハワイがゴール地点」である)、サイコロの出目によってはゴールに近づかず戻らないとならない場合もある。

例

[ゴール]─[A]─[B]─[C]─[D]─[E]─[F]─[G]─…

[D]にいる場合、
サイコロが4以下なら前進できる(ゴールに近づける)一方、
5以上ならゴールから離れるしかない。

問題は、このように「ゴールまで一本道で、ゴールは行き止まりにあり、戻る長さは十分あるとする。このとき、各地点にいる場合(上図では[A]〜[G])のゴールするまでの回数の期待値を求めよ。ただし、ゴールするまでの回数をなるべく減らすよう行動するものとする(ゲーム中では青マス赤マスなどがあるがそれは無視する)」というものである。

回答(暫定)

これが最適という保証ができていないため、「暫定」としています。

  「前進できるときは前進する」という戦術について検討する

「ゴールからnマス前にいる場合に、ゴールするまでにサイコロを振る回数の期待値」を xn と書く。このとき、もし「前進できるときは前進する」とするならば、回数の期待値は以下のようになる。

現在地 サイコロが→ 1 2 3 4 5 6
x1 1 1 + x3 1 + x4 1 + x5 1 + x6 1 + x7
x2 1 + x1 1 1 + x5 1 + x6 1 + x7 1 + x8
x3 1 + x2 1 + x1 1 1 + x7 1 + x8 1 + x9
x4 1 + x3 1 + x2 1 + x1 1 1 + x9 1 + x10
x5 1 + x4 1 + x3 1 + x2 1 + x1 1 1 + x11
x6 1 + x5 1 + x4 1 + x3 1 + x2 1 + x1 1
x7 1 + x6 1 + x5 1 + x4 1 + x3 1 + x2 1 + x1
x8 1 + x7 1 + x6 1 + x5 1 + x4 1 + x3 1 + x2
x9 1 + x8 1 + x7 1 + x6 1 + x5 1 + x4 1 + x3
x10 1 + x9 1 + x8 1 + x7 1 + x6 1 + x5 1 + x4
x11 1 + x10 1 + x9 1 + x8 1 + x7 1 + x6 1 + x5

「1」としか書いてない箇所は、それでゴールできる、すなわちそのサイコロを振った1回が期待値として算定されるという意味である。それ以外の場合は、別のマスに移って同様の処理を継続するため、いま振ったサイコロの1回に、別のマスを起点としたときの期待値を加算することになる。
ちなみに、x11 までを考えているのは、この戦術でゴールから一番遠くまで戻されるのが x11 だからである(x5 にいるときにサイコロで6を出した場合)。

さて、上記の表の各行について、サイコロのそれぞれの目が6分の1の確率で出ることを考えると、これらの和を行単位で取ってそれぞれ6で割れば期待値となる。すなわち、

  • x1 = 1 + [x3 + x4 + x5 + x6 + x7] / 6
  • x2 = 1 + [x1 + x5 + x6 + x7 + x8] / 6
  • x3 = 1 + [x2 + x1 + x7 + x8 + x9] / 6
  • x4 = 1 + [x3 + x2 + x1 + x9 + x10] / 6
  • x5 = 1 + [x4 + x3 + x2 + x1 + x11] / 6
  • x6 = 1 + [x5 + x4 + x3 + x2 + x1] / 6
  • x7 = 1 + [x6 + x5 + x4 + x3 + x2 + x1] / 6
  • x8 = 1 + [x7 + x6 + x5 + x4 + x3 + x2] / 6
  • x9 = 1 + [x8 + x7 + x6 + x5 + x4 + x3] / 6
  • x10 = 1 + [x9 + x8 + x7 + x6 + x5 + x4] / 6
  • x11 = 1 + [x10 + x9 + x8 + x7 + x6 + x5] / 6

という連立方程式を解けば x1 から x11 がわかる。実際に解くと、

  • x1 = [9322998 / 1190509] ≒ 7.831102494815243
  • x2 = [9448236 / 1190509] ≒ 7.93629951558535
  • x3 = [9770670 / 1190509] ≒ 8.207136611314992
  • x4 = [9698604 / 1190509] ≒ 8.14660283962574
  • x5 = [9504846 / 1190509] ≒ 7.983850605077324
  • x6 = [9148068 / 1190509] ≒ 7.684165344403108
  • x7 = [10672746 / 1190509] ≒ 8.964859568470294
  • x8 = [10897704 / 1190509] ≒ 9.153819080746135
  • x9 = [11139282 / 1190509] ≒ 9.356739008272932
  • x10 = [11367384 / 1190509] ≒ 9.548339407765923
  • x11 = [11645514 / 1190509] ≒ 9.781962169122618

となる。

  前進すべきでない場合を考える

上記の結果を見ると、単に前進しないほうがよい場合というのも存在しそうと判断できる。例えば現在 x4 にいるとして、サイコロで1を出した場合は、前進した場合(x3)よりも後退した場合(x5)のほうが、ゴールまでの回数の期待値が下がっている。この方法で「前進できる場合でも後退したほうがよい」と判断される状況は、以下のものが存在する(他は存在しない)。

  • x4 にいるときに、サイコロで1を出す(x3 > x5
  • x4 にいるときに、サイコロで2を出す(x2 > x6
  • x5 にいるときに、サイコロで1を出す(x4 > x6

そこで、このことを組み込んで再度計算をする。具体的には表を以下のように更新する(赤文字が更新箇所)。

現在地 サイコロが→ 1 2 3 4 5 6
x1 1 1 + x3 1 + x4 1 + x5 1 + x6 1 + x7
x2 1 + x1 1 1 + x5 1 + x6 1 + x7 1 + x8
x3 1 + x2 1 + x1 1 1 + x7 1 + x8 1 + x9
x4 1 + x5 1 + x6 1 + x1 1 1 + x9 1 + x10
x5 1 + x6 1 + x3 1 + x2 1 + x1 1 1 + x11
x6 1 + x5 1 + x4 1 + x3 1 + x2 1 + x1 1
x7 1 + x6 1 + x5 1 + x4 1 + x3 1 + x2 1 + x1
x8 1 + x7 1 + x6 1 + x5 1 + x4 1 + x3 1 + x2
x9 1 + x8 1 + x7 1 + x6 1 + x5 1 + x4 1 + x3
x10 1 + x9 1 + x8 1 + x7 1 + x6 1 + x5 1 + x4
x11 1 + x10 1 + x9 1 + x8 1 + x7 1 + x6 1 + x5

同様に期待値を計算すると、

  • x1 = [644175 / 83674] ≒ 7.698628008700433
  • x2 = [653562 / 83674] ≒ 7.810813394841887
  • x3 = [676686 / 83674] ≒ 8.08717164232617
  • x4 = [664269 / 83674] ≒ 7.93877429069962
  • x5 = [652332 / 83674] ≒ 7.796113488060808
  • x6 = [632178 / 83674] ≒ 7.555250137438152
  • x7 = [737541 / 83674] ≒ 8.814458493677845
  • x8 = [753102 / 83674] ≒ 9.00043024117408
  • x9 = [769692 / 83674] ≒ 9.19869971556278
  • x10 = [785193 / 83674] ≒ 9.383954394435548
  • x11 = [805347 / 83674] ≒ 9.624817745058202

この結果を見ると、すべての期待値が最初に示したものより小さく、また今回定めた後退の条件を使うと前進よりも期待値が下がることも確認できる。

厳密には、すべての後退の条件について確かめたうえでこれが最適と証明する必要があると思われるものの、おそらくこれが最適になるであろうと考えている。

  結論(暫定)

  • ゴールから4マス手前にいて、サイコロで1か2を出した場合は、後退する。
  • ゴールから5マス手前にいて、サイコロで1を出した場合は、後退する。
  • それ以外は前進する。