Facebook AI Research(FAIR)は、ポーカーのトッププレイヤを破る実力を備えた、不完全情報ゲーム(imperfect-information game)をプレーする同社の新たなAIであるRecursive Belief-based Learning(ReBeL)の論文を発表した。採用されたアルゴリズムは強化学習(reinforcement learning、RL)と状態空間検索(state-space search)を組み合わせたもので、任意の2プレイヤ型ゼロサムゲームをNash近傍に収束する。Liar's Diceをプレーしてアルゴリズムをトレーニングするためのコードは、オープンソースとして公開されている。
FAIRの研究者であるNoam Brown、Anton Bakhtin両氏がブログ記事で、システムの概要を説明している。RebeLは任意の2プレイヤ型ゼロサムゲームで使用可能な汎用目的のアルゴリズムで、プレーヤがゲーム状態に対する完全な知識を持たないような不完全情報ゲームにも対応する。プレーヤがゲーム状態に対して持つであろう信念の確率分布をモデル化することによって、ReBeLは、完全情報ゲームで使用されているAIテクニックの適用を可能にする。このアルゴリズムはゲームに対して最適なポリシに収束することが証明されており、FAIRの実装は、HUNL(Heads-Up No-Limit) Texas Hold 'Em poker)において従来のAIベンチマークのパフォーマンスを凌駕し、人間のトッププレーヤにも勝利している。Brown、Bakhtin両氏によれば、
私たちはこれを、マルチエージェントインタラクションのための普遍的テクニックの開発に向けた大きな前進であり、不正検出やサイバーセキュリティといった複雑な実世界アプリへの一歩だと考えています。
AIオートメーションのためのゲームのモデル化には通常、ゲーム状態のエンコーディングが関与する — 例えば、チェス盤上のすべてのパーツの位置、というようにである。その上で、AIエージェントがアルゴリズム(あるいはポリシ)を使って次の一手を選択し、それによってゲームの状態が更新される。チェスなど多くのゲームでは、ゲームの現在の状態に関する全情報をエージェントが把握しているので、そのゲームの状態空間を検索することが一般的な実装になる — すなわち、両プレーヤに考えられる無数のアクションをシミュレートすることで、最善の一手を見付けるのだ。"最善"の計測には価値関数(value function)が使用される。しかしながら、碁のように状態空間が極めて大きなゲームでは、検索のみでは非現実的なものになる。その代わりに、これらのゲームの研究者たちが目を向けたのがRLだ。そこではエージェントがゲームをプレーし、その結果に基づいてポリシを更新する。DeepMindのAlphaGo ZeroはRLと検索を組み合わせており、学習したポリシを使って検索空間を縮小することによって検索をガイドしている。
プレーヤがお互いの手を隠すカードゲームのように情報の不完全なゲームでは、エージェントはゲームの完全な状態を正確に判断できない。RLテクニックはある程度の効果があるものの、学習したポリシがNash均衡にアプローチするという保証はない。どちらのプレーヤもゲーム全体の状態を知らないので、未知の状態に対して信念(Belief)を形成する。さらには、相手プレーヤの取りそうなアクションを判断するために、相手プレーヤの信念に関する信念も形成しなければならない。HUNLで人間のプロを破った初めてのAIであるDeepStackは、このような再帰的理由付けを使用して生成したニューラルネットワーク用の入力を、状態検索と合わせてゲーム状態に値を割り当てるために使用している。
ReBeLもまた、再帰的プロセスを使用してゲームの未知の状態に関する確率分布を展開しており、そのプロセスをPBS(Public Belief States)として形式化している。PBSは、初期状態である一様分布を、Bayesian技法とプレーヤのアクションの観察を使って更新することで形成される。従ってPBSを生成するために必要なすべての情報は、すべてのプレーヤが利用できることになる。不完全情報ゲームをPBSに基づく連続状態の完全情報ゲームに再定式化することで、PBS空間内での検索の使用が可能になるのだ。検索時の状態評価に使用する価値関数は、セルフプレー(self-play)中にRLを使用してトレーニングされる。これによって専門的なドメイン知識の必要性を低減すると同時に、アルゴリズムをより広いゲーム領域に適用可能なものにすることができる。DeepStackもPBSと検索を使用しているが、価値関数のトレーニングはセルフプレーではなく、専門知識を使って構築した分散からPBSをランダムに生成することで行われている。FAIRの過去のポーカープレーAIであるPluribusはセルフプレーを使うが、他のプレイヤの観察に基づいた戦略の適用は行わない。
FAIRチームはReBeLがNash均衡ポリシに収束することを証明し、アルゴリズムをHUNL Texas Hold 'EmポーカーとLiar's Diceの両方でテストしている。ポーカーでReBeLはBabyTartanian8とSlumbotという２つのベンチマークボットのパフォーマンスを凌ぎ、プロのポーカープレーヤであるDong Kim氏に勝利している。ポーカーの実装コードはリリースされていないが、Liar's Dice試験のソースコードとモデルチェックポイントはGitHubで公開されている。