多人数不完全情報ゲームにおける仮想自己対戦を用いた強化学習

不完全情報ゲームにおいて，ナッシュ均衡戦略は非常に重要なテーマである．特に多人数不完全情報ゲームにおいては，ナッシュ均衡解を一般に求める方法はまだ確立されていないことから，多くの関心を集めている．2人テキサス・ホールデムはCFR+ (Tamelin, 2014) によって解かれた (generally weakly solved) が，CFR+は空間計算量の観点から3人以上のテキサス・ホールデムに適用するには問題がある．本研究ではNFSP (Heinrich and Silver, 2016) と呼ばれる手法を用いて，CFR+では解くことが難しい多人数不完全情報ゲームのナッシュ均衡解を求めることを目指す．本研究では，学習部分にソフトマックス回帰を用いたFictitious Self-Play (FSP) を使用して，テキサス・ホールデムのトイゲームである2人クン・ポーカーにおいてFSPが近似的なナッシュ均衡解を求められることを示した．また，多人数ゲームである3人クン・ポーカーにおいても，FSPが近似的なナッシュ均衡解を求められることを示し，CFR+の戦略に対するFSPの戦略の平均被搾取量が減少することを示した．

Computing Nash equilibrium solutions is an important problem in the domain of imperfect information games. Attempts of solving the problem draw considerable attention especially in the domain of multiplayer games because there is currently no method that can calculate approximate Nash equilibrium solutions in a general setting. CFR+ (Tamelin, 2014) can be used to (essentially weakly) solve two-player limit Texas Hold'em, but it cannot be applied to large multiplayer games due to the problem of space complexity. In this paper, we use Neural Fictitious Self-Play (Heinrich and Silver, 2016) to calculate approximate Nash equilibrium solutions for multiplayer imperfect information games that CFR+ can hardly solve. We show that Fictitious Self-Play (FSP) with a softmax regression allows us to calculate approximate Nash equilibrium solutions in two-player Kuhn poker and three-player Kuhn poker. We also show that the exploitability of the FSP solution by that of CFR+ decreases.