回答(暫定)「前進できるときは前進する」という戦術について検討する前進すべきでない場合を考える結論(暫定)(最終更新:2017.3.3)はじめにこれはもともと、科学系ソーシャルコミュニティ「なぞらぼ」(nazolab.net)に提示された問題で、私もこれに回答をしたのですが、なぞらぼのサービスが終了したため、こちらに私の回答を残しておくものです。Machineには残っています。こちらもご覧ください。桃鉄(桃太郎電鉄)は、いわゆるすごろくゲームなのだが、「サイコロを振って出た数を、折り返すことなく進まないとならない」という制約がある。そのため、ゴール地点が行き止まりになっている場合(この代表例が「ハワイがゴール地点」である)、サイコロの出目によってはゴールに近づかず戻らないとならない場合もある。例[ゴール]─[A]─[B]─[C]─[D]─[E]─[F]─[G]─...[D]にいる場合、サイコロが4以下なら前進できる(ゴールに近づける)一方、5以上ならゴールから離れるしかない。問題は、このように「ゴールまで一本道で、ゴールは行き止まりにあり、戻る長さは十分あるとする。このとき、各地点にいる場合(上図では[A]〜[G])のゴールするまでの回数の期待値を求めよ。ゴールするまでの回数をなるべく減らすよう行動するものとする(ゲーム中では青マス赤マスなどがあるがそれは無視する)」というものである。回答(暫定)これが最適という保証ができていないため、「暫定」としています。このとき、もし「前進できるときは前進する」とするならば、回数の期待値は以下のようになる。x5「1」としか書いてない箇所は、それでゴールできる、すなわちそのサイコロを振った1回が期待値として算定されるという意味である。それ以外の場合は、別のマスに移って同様の処理を継続するため、いま振ったサイコロの1回に、別のマスを起点としたときの期待値を加算することになる。いるときにサイコロで6を出した場合)。上記の表の各行について、サイコロのそれぞれの目が6分の1の確率で出ることを考えると、これらの和を行単位で取ってそれぞれ6で割れば期待値となる。9.781962169122618となる。前進すべきでない場合を考える上記の結果を見ると、単に前進しないほうがよい場合というのも存在しそうと判断できる。いるとして、サイコロで1を出した場合は、前進した場合(x3)よりも後退した場合(x5)のほうが、ゴールまでの回数の期待値が下がっている。この方法で「前進できる場合でも後退したほうがよい」と判断される状況は、以下のものが存在する(他は存在しない)。x6)そこで、このことを組み込んで再度計算をする。具体的には表を以下のように更新する(赤文字が更新箇所)。9.624817745058202この結果を見ると、すべての期待値が最初に示したものより小さく、また今回定めた後退の条件を使うと前進よりも期待値が下がることも確認できる。厳密には、すべての後退の条件について確かめたうえでこれが最適と証明する必要があると思われるものの、おそらくこれが最適になるであろうと考えている。結論(暫定)ゴールから4マス手前にいて、サイコロで1か2を出した場合は、後退する。ゴールから5マス手前にいて、サイコロで1を出した場合は、後退する。Perl5.026001。