(大幅更新:2017.3.3、2021.5.15)
これはもともと、科学系ソーシャルコミュニティ「なぞらぼ」(nazolab.net)に提示された問題で、私もこれに回答をしたのですが、なぞらぼのサービスが終了したため、こちらに私の回答を残しておくものです。なお、そのときにやっていなかった全探索による最適な戦術の確定は、2021.5.15の更新で追加しました。
なお、なぞらぼの内容は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 から x11 がわかる。実際に解くと、
となる。
上記の結果を見ると、単に前進しないほうがよい場合というのも存在しそうと判断できる。例えば現在 x4 にいるとして、サイコロで1を出した場合は、前進した場合(x3)よりも後退した場合(x5)のほうが、ゴールまでの回数の期待値が下がっている。この方法で「前進できる場合でも後退したほうがよい」と判断される状況は、以下のものが存在する(他は存在しない)。
そこで、このことを組み込んで再度計算をする。具体的には表を以下のように更新する(赤文字が更新箇所)。
現在地 | サイコロが→ | 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 |
同様に期待値を計算すると、
この結果を見ると、すべての期待値が最初に示したものより小さく、また今回定めた後退の条件を使うと前進よりも期待値が下がることも確認できる。
厳密には、すべての後退の条件について確かめたうえでこれが最適と証明する必要がある。そこで以下のことを試す。
この「すべて試す」というのは、
の15個について前進か後退か選択肢があるため、試す戦術は215 = 32768通りある。
これらすべてについて計算したところ、前述の戦術が最善であった(x1からx11のすべてについて、さいころを振る回数の期待値を減らすことのできる他の戦術が存在しなかった)。
前進できるにもかかわらず後退すべき場合は、以下のもののみである(他の場合は前進すればよい)。