僕のノート、見てってください

エンジニアリングや英語、趣味について徒然なるままに

Expectimax とは何か？ Minimaxとの違いは？

機械学習

Expectimaxについて、 日本語で解説してるサイトを見つけられなかったので
自力で Expectimax を調べてみた結果を整理してみる。

ExpectiMaxとは

行動を確率の分岐として描けるような場合に、
ある分岐以降の価値(重み)を、その分岐の1つ先の階層にある価値を平均した値で表現し、 その値が最大となる分岐を選択する探索方法。

機械学習でも用いられる探索方法の一つ。
特に、2人プレイのゼロサムで、かつ、プレイヤーの実力とサイコロのような運の要素が絡むゲームにおける人工知能分野で活用されている。例えば、バックギャモンや、カーリングなど。

説明資料

ひとまず、概念をざっと見ておく。 f:id:naosk8:20170209173447p:plainf:id:naosk8:20170209173546p:plainf:id:naosk8:20170209173553p:plain
(引用: Washington Univ. Artificial Intelligence Slides, Luke Zettlemoyer, 2011.)

十分伝わった気がする。

有効なケース

  • パックマンの操作ロジックにて、敵が不規則な動きをするように設定された場合に、時に偶然の回避で延命できる。

苦手なケース

  • パックマンの操作ロジックにて、敵が単調な動きをするように設定された場合(最短距離を直進してくる等)に、鉢合わせる可能性がある。

参考資料