← テーブル
スタディホール · 3/6止めるか、続けるか
デスク · 振り直しゲームのソルバー
1
ブリーフィング · スタディホール

止めるか、続けるか

使う場面:面接の期待値パズル、ハイ・オア・ロー

ゲーム中に選択できるときは、最後の判断から逆向きに解きます。各段階で、手元の値が続けた場合の期待値を上回るならそれを残します。

V₀ = (s+1)/2 Vₖ = E[ max(X, Vₖ₋₁) ]

Vₖ は、s面のサイコロで振り直しがk回残っているときのゲームの価値です。しきい値ルールは、Vₖ₋₁ より厳密に大きい目なら残す、です。

仕組み:Vₖ = E[ max(X, Vₖ₋₁) ] の読み方
sサイコロの面の数。
Vₖ振り直しがk回残っていて、最適にプレイしたときのゲームの価値。
V₀ = (s+1)/2振り直しが残っていなければ次の目を受け入れるしかないので、ゲームの価値は1回振ったときのふつうの期待値です。
Xこれから見る目。
Vₖ₋₁この目を捨てた場合の価値:振り直しが1回少ない同じゲーム。
max(X, Vₖ₋₁)Xを見たあとの利得:Xを残すか、残りのゲームと交換するか。大きいほうを取ります。
E[ … ]出うるすべての目について、その利得を平均します。

計算例:6面サイコロ、振り直し1回

V₀ = 3.5。1、2、3なら振り直し(価値3.5)のほうが良いので max = 3.5。4、5、6なら残す。よって V₁ = (3.5 + 3.5 + 3.5 + 4 + 5 + 6) ÷ 6 = 25.5 ÷ 6 = 4.25。

振り直し2回ならしきい値は4.25に上がり、残すのは5と6だけ:V₂ = (4 × 4.25 + 5 + 6) ÷ 6 = 28 ÷ 6 = 4.67。

なぜ逆向きに解くのか?続けた場合の価値が分からなければ、最初の判断を評価できません。続きが分かっているのは最後の判断(ふつうの期待値)だけなので、そこから1歩ずつ戻ります。この方法は後ろ向き帰納法と呼ばれ、アメリカンオプションを二項ツリーで評価する方法そのものです。各ノードで、今すぐ行使するか保有を続けるかの大きいほうを取ります。

覚え方
  • 6面サイコロ、振り直し1回 = 4.25。2回 = 4.67。この2つは暗記しよう。
  • 目 > 続けた場合の価値なら残す。全体の平均と比べてはいけません。
遊び方からいつでも再表示できます。