導入
スマブラなどの格闘ゲームからオセロなどの戦略ゲームに至るまで、敵のAIが必要になります。今回は、数学的に性能が保証された戦略AIを作成する方法を紹介します。
今回は、「UCB1方策」というものを紹介します。
UCB1方策の概要
UCB1方策というのは、多腕バンディット問題に対する戦略の一つです。
多腕バンディット問題とは、複数の「報酬の期待値が分かっていない」選択肢があるときに、報酬を最大化する選択肢の選び方を考える問題です。
多腕バンディット問題の例は、「勝率が不明な複数のスロットがあって、金貨をどういう風に入れたら報酬を最大化できるか」という問題です。
UCB1方策の具体的な手順
①まず、全ての選択肢を1回ずつ試します。
②その後、UCBスコアが最大になる選択肢を試します。(UCBスコア=μ+c√(ln(N)/n))
(μ:その選択肢の現時点の勝率。c:定数。理論上は√2だが問題によって調整する必要がある。小さくするほど現時点の勝率を重要視し、大きくするほど探索を重要視する。N:全ての選択師の探索回数の合計、n:その選択肢の探索回数。)
(※lnは自然対数で、logの底がネイピア数eであるものです。)
③手順②を繰り返します。
UCB1方策が戦略ゲームのAIに使える理由
戦略ゲームはモンテカルロ法を使うことにより「多腕バンディット問題」とみなすことができるからです。
モンテカルロ法とは、乱数を使って特定の値を推定する方法です。ランダムに点を打って、円の面積を推定するのもモンテカルロ法です。
ある選択肢を選んだとき、「それ以降の選択肢はどちらかが勝つまで完全にランダムに選び、勝敗を決める」とします。
1つの選択を選ぶと、ある特定の確率で「勝利」という報酬を得られるので、これは多腕バンディット問題になっています。
「選択肢を試す=1$失う」、「勝利=10$貰う」などと考えると分かりやすいです。
UCB1方策の実現例
RPGゲームの戦闘で、ドラゴンAIに最適な行動を選ばせる場合を考えます。
選択肢は、「A:殴る」「B:火を吐く」「C:力を溜める」です。
まずは手順①。Aを選ぶと結果は「敗北」。B、Cは「勝利」でした。
現在のUCBスコアは、Aは0、B、Cは1。
続いて手順②。定数c=√2とします。Bを選ぶと結果は「敗北」でした。
現在のUCBスコアは、Aは√(2ln2)≒1.18、Bは1/2+√(ln2)≒1.33、Cは1+√(2ln2)≒2.18
再度②。Cを選ぶと結果は「勝利」でした。
現在のUCBスコアは、Aは√(2ln3)≒1.48、Bは1/2+√(ln3)≒1.55、Cは1+√(ln3)≒2.05.
再度②。Cを選ぶと結果は「敗北」でした。
現在のUCBスコアは、Aは√(2ln4)≒1.67、Bは1/2+√(ln4)≒1.68、Cは2/3+√(2ln4/3)≒1.63
再度②。Bを選ぶと結果は「敗北」でした。
(本来は何十回、何百回とする必要がありますが、今回はここで終了します。)
現在、最も勝率が高い選択肢はCなので、ドラゴンはCを選択する。
問題点
UCB1方策は、原始モンテカルロ法を少し改良した程度の戦略です。なので、まだまだ全然弱いです。
※今回は、このUCB1方策に探索木を組み合わせたUCTという強力な方策を紹介する準備として紹介しました。
数学的理解
UCB1方策の手順②の式を導出したい人向け。
↓ 研究者の方が書かれている記事です
多腕バンディット問題におけるUCB方策を理解する · THINKING MEGANE (monochromegane.com)
↓ 多腕バンディットに使われる統計学の定理の紹介
参考文献
https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1894-14.pdf
https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%83%86%E3%82%AB%E3%83%AB%E3%83%AD%E6%9C%A8%E6%8E%A2%E7%B4%A2
https://ja.wikipedia.org/wiki/%E5%A4%9A%E8%85%95%E3%83%90%E3%83%B3%E3%83%87%E3%82%A3%E3%83%83%E3%83%88%E5%95%8F%E9%A1%8C