サイエンス誌の表紙を飾ったCMUの偉人ノアムは博士号を取得し、その論文が公開された。

2 人用ノーリミット ポーカーとマルチプレイヤー ノーリミット ポーカーでトップの人間プレイヤーに勝利したゲーム AI システム Libratus と Pluribus を覚えていますか?最近、これら 2 つの AI システムの開発者の 1 人である CMU の専門家が、博士論文を完成させ、CMU を卒業する予定であることを発表しました。

現地時間9月21日、FAIRの研究科学者ノーム・ブラウン氏はTwitterでCMUの博士論文審査を無事終え、230ページに及ぶ超ハードコアな博士論文「大規模な敵対的不完全情報ゲームの均衡発見」と101ページのスライドを公開したことを発表した。

Noam 氏は論文の序文で、セクション 5.3 で説明した ReBel アルゴリズムを除き、論文内の他のすべての研究は指導者の Tuomas Sandholm 氏との共同作業で完了したと述べています。トゥオマス氏は研究プロセス全体を通じてノアム氏に辛抱強い指導を与えた。ノアムさんは、指導教官の丁寧な指導がなければ、博士号を取得することは絶対にできなかっただろうと語った。

ノアム・ブラウン氏と彼の指導教官であるトゥオマス・サンドホルム教授（右）。

ノーム・ブラウンの博士論文のタイトルは「大規模な敵対的不完全情報ゲームにおける均衡の発見」でした。不完全情報ゲームは、プライベート情報を持つ複数のエージェント間の相互作用をシミュレートします。この設定では、典型的な目標は、すべてのエージェントの戦略が最適となる均衡に近づくことです。

完全情報ゲームと不完全情報ゲームは、ゲームにおける情報ゲームの 2 つの主な形式です。ゲームにおいて、完全情報ゲームの前提は、すべてのプレイヤーがルールなどのゲームに関する情報を知っていることです。一方、不完全情報ゲームのプレイヤーは、他のプレイヤーが誰であるか、どのような戦略や行動が実行可能であるか、結果が行動にどのように依存するかなど、プレイしているゲームに関する共通の知識を持っていません。難易度の点では、情報が不完全であるとプレイヤーの意思決定の難易度が増し、ゲーム分析がより困難になります。

囲碁、チェス、チェッカーなどのボードゲームは完全情報ゲームです。ポーカーは典型的な不完全情報ゲームであり、常にノアム・ブラウンの研究の焦点となってきました。 2017 年の AI システム Libratus から 2019 年の新しいアルゴリズム Pluribus まで、それらはすべて不完全情報ゲームのカテゴリに分類されます。

ノアム・ブラウンは論文の中で、博士課程での研究期間中の一連の研究結果を要約しました。 Synced では、論文の核心部分を簡単に紹介しました。興味のある読者は、原文の論文を読むことができます。

論文アドレス: http://www.cs.cmu.edu/~noamb/thesis.pdf

スライドのアドレス: http://www.cs.cmu.edu/~noamb/thesis_slides.pdf

博士論文序論

この博士論文では、大規模な敵対的不完全情報ゲームにおける均衡の計算における一連の進歩について詳しく説明します。これらの新しい技術により、AI エージェントがノーリミット ポーカーでトップのプロ プレイヤーに勝つことが初めて可能になりました。これは、何十年にもわたって AI とゲーム理論における大きな難題でした。

反事実的後悔最小化（CFR）の改善

著者らはまず、2人プレイのゼロサムゲームでナッシュ均衡に収束する反復アルゴリズムである反事実的後悔最小化（CFR）の改良を紹介します。また、割引を利用して収束を大幅に高速化する CFR の新しい変種についても説明します。

CFR方式。

次に著者らは、大規模なゲームで収束を桁違いに高速化できる、理論的に妥当な剪定手法を紹介します。

CFR における剪定プロセス。

CFRを大規模ゲームに拡張

著者らは、自動抽象化と関数近似アルゴリズムを通じて CFR を大規模ゲームに拡張する新しいアプローチについて説明します。

具体的には、著者らは、不完全情報ゲームにおける連続アクション空間を離散化する最初のアルゴリズムを導入しており、これは局所的に最適であることが証明されています。ただし、このアルゴリズムには多くのドメイン知識が必要であり、他のゲームに拡張することは困難です。

これまでの方法の限界。

そのため、著者らは、バケットベースの抽象化の代わりにニューラル ネットワーク関数の近似を使用する CFR の変種である Deep CFR を提案しました。 Deep CFR は、大規模なゲームに拡張でき、ドメイン知識がほとんどまたはまったくない設定で CFR を展開できる、CFR の最初の非表形式です。

Deep CFR を使用して大規模ゲームにスケーリングします。

検索技術の継続的な改善

著者らは、エージェントの探索戦略が対戦相手に利用されないようにする、新しい不完全情報ゲーム探索手法を提案している。これらの新しい形式の検索は、理論と実践の両方において以前の方法よりも優れています。

さらに、著者らは、従来の方法よりも計算コストが大幅に低い深さ制限検索方法を導入しています。

Pluribus アルゴリズムにおける深さ制限検索。

最後に、著者らは、トレーニングとテスト中に強化学習と検索を組み合わせた新しい ReBel アルゴリズムを提案し、完全情報ゲームと不完全情報ゲームの研究のギャップを縮めるための重要な一歩を踏み出します。

2 人用ノーリミット ホールデムの結果の比較。

博士論文の章の一覧は次のとおりです。

テキサスポーカーAIの研究に取り組んでいるCMUの専門家、ノアム・ブラウン氏

ノーム・ブラウンは Facebook AI Labs の研究科学者です。彼は計算ゲーム理論と機械学習を組み合わせて、不完全情報マルチエージェント環境で戦略的推論が可能な AI システムの開発に取り組んでいます。彼の研究成果は、2 人用ノーリミット ポーカーとマルチプレイヤー ノーリミット ポーカーでトップクラスの人間プレイヤーに勝利した最初の 2 つのシステムである Libratus と Pluribus に適用されています。これら 2 つのゲーム AI システムは、Noam Brown に大きな栄誉をもたらしました。

2017年、ノーム・ブラウン氏とその指導者であるトゥオマス・サンドホルム氏が開発したAIシステム「Libratus」は、ペンシルベニア州ピッツバーグのリバーズカジノで行われた20日間の1対1ノーリミットテキサスホールデム大会で、世界トップクラスのプロプレイヤー4人を破りました。この研究はサイエンス誌に掲載され、別の関連論文「不完全情報ゲームのための安全でネストされたサブゲーム解決」もNIPS 2017最優秀論文賞を受賞した。

さらに、ノアムのチームは、IJCAI が授与する第 2 回マービン・ミンスキー メダルも受賞しました。

ノアムは、IJCAI 2019 カンファレンスでマービン・ミンスキー賞状を受け取りました。

2019年、Noam Brown氏と彼の指導者Tuomas Sandholm氏は、より少ない計算能力を必要とするLibratusをベースにした新しいアルゴリズムPluribusを開発しました。 12日間で1万回以上のポーカーのハンドをプレイし、Pluribusはトッププレイヤー15人を破った。

2 人以上のプレイヤー (またはチーム) が参加する大規模なベンチマーク ゲームで AI がトップ プロ プレイヤーに勝利したのはこれが初めてです。 Pluribus は Science 誌の表紙を飾っただけでなく、同誌によって 2019 年のトップ 10 の科学的ブレークスルーの 1 つとして取り上げられました。

Pluribus が Science Magazine の表紙に掲載されました。

さらに、ノアムは2017年にアレン・ニューウェル「優秀研究賞」を受賞し、2019年にはMITテクノロジーレビューによって「35歳未満のテクノロジーエリート」（MIT TR35）の1人に選ばれました。 2019 年、Noam Brown 氏と彼の指導者 Tuomas Sandholm 氏は、論文「Solving Imperfect-Information Games via Discounted Regret Minimization」を共同執筆し、AAAI Outstanding Paper Honorable Mention Award を受賞しました。