人間を超えたゲームAIの基盤となった経済学 〜ナッシュ均衡とその計算アルゴリズム〜 | | AI tech studio

AI Lab 経済学チームの森下(@GotaMorishita)です. 今年7月に複数人のポーカーで圧勝したポーカーAI, Pluribus[1]が話題になりました. Pluribusやその元となったLibratus[2]で用いられた理論は, ミクロ経済学の一分野であるゲーム理論のナッシュ均衡でした. ポーカーを展開型ゲームとして定式化し, そのゲームのナッシュ均衡を求め, それを最適戦略としたのです. ナッシュ均衡を求めるアルゴリズムはコンピューターサイエンスでは盛んに研究されており, LibratusやPluribusではCounterfactual Regret Minimization (CFR)と呼ばれる展開型ゲームのナッシュ均衡計算アルゴリズムを応用したものが使われています[3]. 弊ブログでも, 先日, CFRアルゴリズムを花札「こいこい」に適用させた例を紹介しました(こちら

[yasudayasu]

状態数が膨大な不完全情報ゲームは, 長年, ゲームAIでは未解決問題の１つとして残っていた. HartとMas-Colellが, Regret Matchingと呼ばれるアルゴリズムをEconometricaで2000年に発表.契機にポーカーAIの攻略が一気に進みました.