【ゲーム制作】敵AIを数学的理論を基に作成する① ~UCB1方策~

導入

スマブラなどの格闘ゲームからオセロなどの戦略ゲームに至るまで、敵の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

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です