{{outline}} (大幅更新:2017.3.3、2021.5.15) !!! はじめに これはもともと、科学系ソーシャルコミュニティ「なぞらぼ」(nazolab.net)に提示された問題で、私もこれに回答をしたのですが、なぞらぼのサービスが終了したため、こちらに私の回答を残しておくものです。なお、そのときにやっていなかった全探索による最適な戦術の確定は、2021.5.15の更新で追加しました。 なお、なぞらぼの内容はWayback Machineには残っています。こちらもご覧ください。(提示された問題と私の回答の箇所だけ残ってました){{br}}http://web.archive.org/web/20150731075048/http://nazolab.net/qa/q/75 !!! 問題設定 桃鉄(桃太郎電鉄)は、いわゆるすごろくゲームなのだが、「サイコロを振って出た数を、折り返すことなく進まないとならない」という制約がある。{{br}}そのため、ゴール地点が行き止まりになっている場合(この代表例が「ハワイがゴール地点」である)、サイコロの出目によってはゴールに近づかず戻らないとならない場合もある。 例 [ゴール]─[A]─[B]─[C]─[D]─[E]─[F]─[G]─… [D]にいる場合、 サイコロが4以下なら前進できる(ゴールに近づける)一方、 5以上ならゴールから離れるしかない。 問題は、このように「ゴールまで一本道で、ゴールは行き止まりにあり、戻る長さは十分あるとする。このとき、各地点にいる場合(上図では[A]〜[G])のゴールするまでの回数の期待値を求めよ。ただし、ゴールするまでの回数をなるべく減らすよう行動するものとする(ゲーム中では青マス赤マスなどがあるがそれは無視する)」というものである。 !!! 回答 !! 「前進できるときは前進する」という戦術について検討する 「ゴールからnマス前にいる場合に、ゴールするまでにサイコロを振る回数の期待値」を x{{tag n}} と書く。このとき、もし「前進できるときは前進する」とするならば、回数の期待値は以下のようになる。 ,現在地,サイコロが→,1,2,3,4,5,6 ,x{{tag 1}},,1,1 + x{{tag 3}},1 + x{{tag 4}},1 + x{{tag 5}},1 + x{{tag 6}},1 + x{{tag 7}} ,x{{tag 2}},,1 + x{{tag 1}},1,1 + x{{tag 5}},1 + x{{tag 6}},1 + x{{tag 7}},1 + x{{tag 8}} ,x{{tag 3}},,1 + x{{tag 2}},1 + x{{tag 1}},1,1 + x{{tag 7}},1 + x{{tag 8}},1 + x{{tag 9}} ,x{{tag 4}},,1 + x{{tag 3}},1 + x{{tag 2}},1 + x{{tag 1}},1,1 + x{{tag 9}},1 + x{{tag 10}} ,x{{tag 5}},,1 + x{{tag 4}},1 + x{{tag 3}},1 + x{{tag 2}},1 + x{{tag 1}},1,1 + x{{tag 11}} ,x{{tag 6}},,1 + x{{tag 5}},1 + x{{tag 4}},1 + x{{tag 3}},1 + x{{tag 2}},1 + x{{tag 1}},1 ,x{{tag 7}},,1 + x{{tag 6}},1 + x{{tag 5}},1 + x{{tag 4}},1 + x{{tag 3}},1 + x{{tag 2}},1 + x{{tag 1}} ,x{{tag 8}},,1 + x{{tag 7}},1 + x{{tag 6}},1 + x{{tag 5}},1 + x{{tag 4}},1 + x{{tag 3}},1 + x{{tag 2}} ,x{{tag 9}},,1 + x{{tag 8}},1 + x{{tag 7}},1 + x{{tag 6}},1 + x{{tag 5}},1 + x{{tag 4}},1 + x{{tag 3}} ,x{{tag 10}},,1 + x{{tag 9}},1 + x{{tag 8}},1 + x{{tag 7}},1 + x{{tag 6}},1 + x{{tag 5}},1 + x{{tag 4}} ,x{{tag 11}},,1 + x{{tag 10}},1 + x{{tag 9}},1 + x{{tag 8}},1 + x{{tag 7}},1 + x{{tag 6}},1 + x{{tag 5}} 「1」としか書いてない箇所は、それでゴールできる、すなわちそのサイコロを振った1回が期待値として算定されるという意味である。それ以外の場合は、別のマスに移って同様の処理を継続するため、いま振ったサイコロの1回に、別のマスを起点としたときの期待値を加算することになる。{{br}} ちなみに、x{{tag 11}} までを考えているのは、この戦術でゴールから一番遠くまで戻されるのが x{{tag 11}} だからである(x{{tag 5}} にいるときにサイコロで6を出した場合)。 さて、上記の表の各行について、サイコロのそれぞれの目が6分の1の確率で出ることを考えると、これらの和を行単位で取ってそれぞれ6で割れば期待値となる。すなわち、 * x{{tag 1}} = 1 + [x{{tag 3}} + x{{tag 4}} + x{{tag 5}} + x{{tag 6}} + x{{tag 7}}] / 6 * x{{tag 2}} = 1 + [x{{tag 1}} + x{{tag 5}} + x{{tag 6}} + x{{tag 7}} + x{{tag 8}}] / 6 * x{{tag 3}} = 1 + [x{{tag 2}} + x{{tag 1}} + x{{tag 7}} + x{{tag 8}} + x{{tag 9}}] / 6 * x{{tag 4}} = 1 + [x{{tag 3}} + x{{tag 2}} + x{{tag 1}} + x{{tag 9}} + x{{tag 10}}] / 6 * x{{tag 5}} = 1 + [x{{tag 4}} + x{{tag 3}} + x{{tag 2}} + x{{tag 1}} + x{{tag 11}}] / 6 * x{{tag 6}} = 1 + [x{{tag 5}} + x{{tag 4}} + x{{tag 3}} + x{{tag 2}} + x{{tag 1}}] / 6 * x{{tag 7}} = 1 + [x{{tag 6}} + x{{tag 5}} + x{{tag 4}} + x{{tag 3}} + x{{tag 2}} + x{{tag 1}}] / 6 * x{{tag 8}} = 1 + [x{{tag 7}} + x{{tag 6}} + x{{tag 5}} + x{{tag 4}} + x{{tag 3}} + x{{tag 2}}] / 6 * x{{tag 9}} = 1 + [x{{tag 8}} + x{{tag 7}} + x{{tag 6}} + x{{tag 5}} + x{{tag 4}} + x{{tag 3}}] / 6 * x{{tag 10}} = 1 + [x{{tag 9}} + x{{tag 8}} + x{{tag 7}} + x{{tag 6}} + x{{tag 5}} + x{{tag 4}}] / 6 * x{{tag 11}} = 1 + [x{{tag 10}} + x{{tag 9}} + x{{tag 8}} + x{{tag 7}} + x{{tag 6}} + x{{tag 5}}] / 6 という連立方程式を解けば x{{tag 1}} から x{{tag 11}} がわかる。実際に解くと、 * x{{tag 1}} = [9322998 / 1190509] ≒ 7.831102494815243 * x{{tag 2}} = [9448236 / 1190509] ≒ 7.93629951558535 * x{{tag 3}} = [9770670 / 1190509] ≒ 8.207136611314992 * x{{tag 4}} = [9698604 / 1190509] ≒ 8.14660283962574 * x{{tag 5}} = [9504846 / 1190509] ≒ 7.983850605077324 * x{{tag 6}} = [9148068 / 1190509] ≒ 7.684165344403108 * x{{tag 7}} = [10672746 / 1190509] ≒ 8.964859568470294 * x{{tag 8}} = [10897704 / 1190509] ≒ 9.153819080746135 * x{{tag 9}} = [11139282 / 1190509] ≒ 9.356739008272932 * x{{tag 10}} = [11367384 / 1190509] ≒ 9.548339407765923 * x{{tag 11}} = [11645514 / 1190509] ≒ 9.781962169122618 となる。 !! 前進すべきでない場合を考える:手作業 上記の結果を見ると、単に前進しないほうがよい場合というのも存在しそうと判断できる。例えば現在 x{{tag 4}} にいるとして、サイコロで1を出した場合は、前進した場合(x{{tag 3}})よりも後退した場合(x{{tag 5}})のほうが、ゴールまでの回数の期待値が下がっている。この方法で「前進できる場合でも後退したほうがよい」と判断される状況は、以下のものが存在する(他は存在しない)。 * x{{tag 4}} にいるときに、サイコロで1を出す(x{{tag 3}} > x{{tag 5}}) * x{{tag 4}} にいるときに、サイコロで2を出す(x{{tag 2}} > x{{tag 6}}) * x{{tag 5}} にいるときに、サイコロで1を出す(x{{tag 4}} > x{{tag 6}}) そこで、このことを組み込んで再度計算をする。具体的には表を以下のように更新する(赤文字が更新箇所)。 ,現在地,サイコロが→,1,2,3,4,5,6 ,x{{tag 1}},,1,1 + x{{tag 3}},1 + x{{tag 4}},1 + x{{tag 5}},1 + x{{tag 6}},1 + x{{tag 7}} ,x{{tag 2}},,1 + x{{tag 1}},1,1 + x{{tag 5}},1 + x{{tag 6}},1 + x{{tag 7}},1 + x{{tag 8}} ,x{{tag 3}},,1 + x{{tag 2}},1 + x{{tag 1}},1,1 + x{{tag 7}},1 + x{{tag 8}},1 + x{{tag 9}} ,x{{tag 4}},,{{tag ""}}1 + x{{tag 5}},{{tag ""}}1 + x{{tag 6}},1 + x{{tag 1}},1,1 + x{{tag 9}},1 + x{{tag 10}} ,x{{tag 5}},,{{tag ""}}1 + x{{tag 6}},1 + x{{tag 3}},1 + x{{tag 2}},1 + x{{tag 1}},1,1 + x{{tag 11}} ,x{{tag 6}},,1 + x{{tag 5}},1 + x{{tag 4}},1 + x{{tag 3}},1 + x{{tag 2}},1 + x{{tag 1}},1 ,x{{tag 7}},,1 + x{{tag 6}},1 + x{{tag 5}},1 + x{{tag 4}},1 + x{{tag 3}},1 + x{{tag 2}},1 + x{{tag 1}} ,x{{tag 8}},,1 + x{{tag 7}},1 + x{{tag 6}},1 + x{{tag 5}},1 + x{{tag 4}},1 + x{{tag 3}},1 + x{{tag 2}} ,x{{tag 9}},,1 + x{{tag 8}},1 + x{{tag 7}},1 + x{{tag 6}},1 + x{{tag 5}},1 + x{{tag 4}},1 + x{{tag 3}} ,x{{tag 10}},,1 + x{{tag 9}},1 + x{{tag 8}},1 + x{{tag 7}},1 + x{{tag 6}},1 + x{{tag 5}},1 + x{{tag 4}} ,x{{tag 11}},,1 + x{{tag 10}},1 + x{{tag 9}},1 + x{{tag 8}},1 + x{{tag 7}},1 + x{{tag 6}},1 + x{{tag 5}} 同様に期待値を計算すると、 * x{{tag 1}} = [644175 / 83674] ≒ 7.698628008700433 * x{{tag 2}} = [653562 / 83674] ≒ 7.810813394841887 * x{{tag 3}} = [676686 / 83674] ≒ 8.08717164232617 * x{{tag 4}} = [664269 / 83674] ≒ 7.93877429069962 * x{{tag 5}} = [652332 / 83674] ≒ 7.796113488060808 * x{{tag 6}} = [632178 / 83674] ≒ 7.555250137438152 * x{{tag 7}} = [737541 / 83674] ≒ 8.814458493677845 * x{{tag 8}} = [753102 / 83674] ≒ 9.00043024117408 * x{{tag 9}} = [769692 / 83674] ≒ 9.19869971556278 * x{{tag 10}} = [785193 / 83674] ≒ 9.383954394435548 * x{{tag 11}} = [805347 / 83674] ≒ 9.624817745058202 この結果を見ると、すべての期待値が最初に示したものより小さく、また今回定めた後退の条件を使うと前進よりも期待値が下がることも確認できる。 !! 前進すべきでない場合を考える:探索する 厳密には、すべての後退の条件について確かめたうえでこれが最適と証明する必要がある。そこで以下のことを試す。 * ゴールまで6マス以内の場合で、後退するしかないときは、後退する。 * '''ゴールまで6マス以内の場合で、前進するか後退するか選べる場合は、考えうる戦術をすべて試す。'''ただし、ゴールできる場合はそのままゴールする。 * '''ゴールまで7マス以上ある場合は必ず前進する。''' この「すべて試す」というのは、 * ゴールまで2マスで、かつサイコロで1を出したとき * ゴールまで3マスで、かつサイコロで1か2を出したとき * ゴールまで4マスで、かつサイコロで1か2か3を出したとき * ゴールまで5マスで、かつサイコロで1か2か3か4を出したとき * ゴールまで6マスで、かつサイコロで1か2か3か4か5を出したとき の15個について前進か後退か選択肢があるため、試す戦術は'''2{{tag 15}} = 32768通り'''ある。 これらすべてについて計算したところ、前述の戦術が最善であった(x{{tag 1}}からx{{tag 11}}のすべてについて、さいころを振る回数の期待値を減らすことのできる他の戦術が存在しなかった)。 !! 結論 前進できるにもかかわらず後退すべき場合は、以下のもののみである(他の場合は前進すればよい)。 * ゴールから4マス手前にいて、サイコロで1か2を出した場合 * ゴールから5マス手前にいて、サイコロで1を出した場合