導入
スマブラなどの格闘ゲームからオセロなどの戦略ゲームに至るまで、敵のAIが必要になります。今回は、数学的に性能が保証された戦略AIを作成する方法を紹介します。
今回は、「UCB1方策」というものを紹介します。
UCB1方策の概要
UCB1方策というのは、多腕バンディット問題に対する戦略の一つです。
多腕バンディット問題とは、複数の「報酬の期待値が分かっていない」選択肢があるときに、報酬を最大化する選択肢の選び方を考える問題です。
多腕バンディット問題の例は、「勝率が不明な複数のスロットがあって、金貨をどういう風に入れたら報酬を最大化できるか」という問題です。
UCB1方策の具体的な手順
①まず、全ての選択肢を１回ずつ試します。
②その後、UCBスコアが最大になる選択肢を試します。（UCBスコア＝μ＋c√(ln(N)/n)）
（μ：その選択肢の現時点の勝率。c：定数。理論上は√2だが問題によって調整する必要がある。小さくするほど現時点の勝率を重要視し、大きくするほど探索を重要視する。N：全ての選択師の探索回数の合計、n：その選択肢の探索回数。）
（※lnは自然対数で、logの底がネイピア数eであるものです。）
③手順②を繰り返します。
UCB1方策が戦略ゲームのAIに使える理由
戦略ゲームはモンテカルロ法を使うことにより「多腕バンディット問題」とみなすことができるからです。
モンテカルロ法とは、乱数を使って特定の値を推定する方法です。ランダムに点を打って、円の面積を推定するのもモンテカルロ法です。
ある選択肢を選んだとき、「それ以降の選択肢はどちらかが勝つまで完全にランダムに選び、勝敗を決める」とします。
１つの選択を選ぶと、ある特定の確率で「勝利」という報酬を得られるので、これは多腕バンディット問題になっています。
「選択肢を試す＝1$失う」、「勝利＝10$貰う」などと考えると分かりやすいです。
UCB1方策の実現例
RPGゲームの戦闘で、ドラゴンＡＩに最適な行動を選ばせる場合を考えます。
選択肢は、「Ａ：殴る」「Ｂ：火を吐く」「Ｃ：力を溜める」です。
まずは手順①。Ａを選ぶと結果は「敗北」。Ｂ、Ｃは「勝利」でした。
現在のUCBスコアは、Ａは０、Ｂ、Ｃは１。
続いて手順②。定数ｃ＝√2とします。Ｂを選ぶと結果は「敗北」でした。
現在の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