ディープマインドAIは人間に対して84%の勝率を誇り、ウエスタンアーミーチェスで初めて人間の専門家のレベルに到達した。

DeepMind はゲーム AI の分野で新たな成果を上げました。今回はチェスです。

AI ゲームの分野では、人工知能の進歩はボードゲームを通じて実証されることが多いです。ボードゲームは、制御された環境で人間と機械がどのように戦略を立て、実行するかを測定および評価できます。数十年にわたり、事前に計画を立てる能力は、チェス、チェッカー、将棋、囲碁などの完全情報ゲーム、およびポーカーやスコットランドヤードなどの不完全情報ゲームにおける AI の成功の鍵となってきました。

Stratego は、AI 研究の次のフロンティアの 1 つとして登場しました。ゲームのステージとメカニズムを視覚化したものが、下の図 1a に示されています。このゲームでは、次の 2 つの課題に直面します。

まず、ストラテゴのゲームツリーには 10,535 個の可能な状態があり、これはよく研究されている不完全情報ゲームであるノーリミット テキサス ホールデム (10,164 個の可能な状態) や囲碁 (10,360 個の可能な状態) よりも多くなっています。

第二に、Stratego では、特定の環境で行動するには、ゲーム開始時に各プレイヤーが 1,066 を超える展開について推論する必要がありますが、ポーカーでは 103 のハンドペアしかありません。囲碁やチェスなどの完全情報ゲームにはプライベート展開フェーズがないため、Stratego でのこの課題の複雑さを回避できます。

現時点では、最先端のモデルベースの完全情報計画技術を使用することはできず、ゲームを独立した状況に分割する不完全情報検索技術を使用することもできません。

これらの理由から、Stratego は大規模な政策相互作用を研究するための挑戦的なベンチマークを提供します。ほとんどのボードゲームと同様に、ストラテゴは、比較的ゆっくりと、慎重に、論理的に決定を順番に下す能力をテストします。ゲームの構造が非常に複雑なため、AI研究コミュニティはほとんど進歩しておらず、人工知能エージェントはアマチュアの人間プレイヤーのレベルにしか到達できません。したがって、Stratego のような不完全な情報の下で、人間のデモンストレーション データなしで、エンドツーエンドの戦略を学習して最適な決定を下すエージェントをゼロから開発することは、AI 研究における大きな課題の 1 つとなっています。

最近、DeepMind の新しい論文で、研究者らは、人間によるデモンストレーションを必要とせずにモデルフリーの方法で Stratego の自己対戦を学習するインテリジェント エージェントである DeepNash を提案しました。 DeepNask は以前の SOTA AI エージェントを打ち負かし、ゲームの最も複雑なバリエーションである Stratego Classic で人間の専門家レベルのパフォーマンスを達成しました。

論文アドレス: https://arxiv.org/pdf/2206.15378.pdf.

DeepNash は本質的には、研究者が正規化ナッシュダイナミクス (R-NaD) と呼ぶ、構造化されたモデルフリーの強化学習アルゴリズムです。 DeepNash は R-NaD とディープ ニューラル ネットワーク アーキテクチャを組み合わせ、ナッシュ均衡に収束します。つまり、インセンティブ競争下でプレイすることを学習し、それを悪用しようとする競合他社に対して堅牢です。

下の図 1b は、DeepNash アプローチの概要を示しています。研究者らは、Gravon ゲーム プラットフォーム上で、さまざまな SOTA Stratego ボットおよび人間のプレイヤーとのパフォーマンスを体系的に比較しました。結果によると、DeepNashは97％以上の勝率で現在のすべてのSOTAロボットを打ち負かし、人間のプレイヤーと激しく競争し、2022年の年間ランキングと期間ランキングでトップ3にランクインし、勝率は84％でした。

研究者らは、学習アルゴリズムにいかなる検索方法も導入することなく、AIアルゴリズムが複雑なボードゲームで初めて人間の専門家のレベルに到達できたと述べ、また、AIがストラテゴのゲームで人間の専門家レベルを達成したのも初めてだった。

方法の概要

DeepNash は、エンドツーエンドの学習戦略を使用して Stratego を実行し、ゲームの開始時にボード上に駒を戦略的に配置します (図 1a を参照)。ゲームプレイ段階では、研究者は統合されたディープ RL とゲーム理論のアプローチを使用します。エージェントは自己プレイを通じて近似的なナッシュ均衡を学習することを目指します。

この研究では、探索なしの直交パスを採用し、自己ゲームにおけるモデルフリー強化学習とゲーム理論アルゴリズムのアイデアである正規化ナッシュダイナミクス（RNaD）を組み合わせた新しい方法を提案します。

モデルフリーの部分とは、この研究では対戦相手の可能な状態を追跡するための明示的な対戦相手モデルを構築しなかったことを意味します。ゲーム理論の部分は、強化学習法に基づいて、エージェントの学習行動をナッシュ均衡に向けて導くという考えに基づいています。この構成アプローチの主な利点は、プライベート状態をパブリック状態から明示的にモックする必要がないことです。さらに複雑な課題は、このモデルフリーの強化学習アプローチを R-NaD と組み合わせて、チェスの自己プレイを人間の熟練プレイヤーと競争できるようにすることですが、これはこれまで達成されていません。この組み合わせた DeepNash アプローチは、上の図 1b に示されています。

正規化ナッシュダイナミクスアルゴリズム

DeepNash で使用される R-NaD 学習アルゴリズムは、収束を達成するための正規化の考え方に基づいています。R-NaD は、下の図 2b に示すように、3 つの主要なステップに依存しています。

DeepNashは、(1)コアトレーニングコンポーネントであるR-NaD、(2)モデルが極めて起こりそうもないアクションを取る残余確率を減らすための学習ポリシーの微調整、(3)低確率のアクションを除外してエラーを修正するためのテスト時の後処理の3つのコンポーネントで構成されています。

DeepNash のネットワークは、残余ブロックとスキップ接続を備えた U-Net バックボーンと 4 つのヘッドというコンポーネントで構成されています。最初の DeepNash ヘッドは値関数をスカラーとして出力し、残りの 3 つのヘッドは展開中およびゲームプレイ中のアクションの確率分布を出力することによってエージェント ポリシーをエンコードします。この観測テンソルの構造を図 3 に示します。

実験結果

DeepNash は、いくつかの既存の Stratego コンピュータ プログラムと比較しても評価されました。Probe は 3 年前 (2007、2008、2010) に Computer Stratego World Championship で優勝しました。Master of the Flag は 2009 年に優勝しました。Demon of Ignorance は Stratego のオープン ソース実装です。Asmodeus、Celsius、Celsius1.1、PeternLewis、および Vixen は、2012 年にオーストラリア大学プログラミング コンテストに提出されたプログラムで、PeternLewis が優勝しました。

表 1 に示すように、DeepNash は敵対的にトレーニングされておらず、自己プレイのみを使用しているにもかかわらず、これらすべてのエージェントに対して大部分のゲームで勝利しています。

下の図 4a は、DeepNash で頻繁に繰り返される展開を示しています。図 4b は、DeepNash (青) が駒の点では劣勢 (7 と 8 を失っている) ですが、赤の対戦相手が 10、9、8、および 2 つの 7 を持っているため、情報では優勢である状況を示しています。図 4c の 2 番目の例は、DeepNash が 9 で相手の 6 を捕獲する機会があったが、この動きは考慮されなかったことを示しています。これはおそらく、DeepNash が 9 のアイデンティティを保護することが物質的な利益よりも重要であると考えたためです。

下の図 5a では、研究者は、プレイヤーが駒の価値が実際よりも高いと偽るポジティブ ブラフを示しています。 DeepNashは未知の駒であるScout (2)を使って相手の8を追いかけ、10であるかのように見せかけます。相手はこの駒が 10 かもしれないと考え、スパイの隣に誘導します (スパイが 10 を獲得できる場所)。しかし、この駒を捕獲するために、相手のスパイはディープナッシュのスカウトに負けました。

2 番目のタイプのブラフは、下の図 5b に示すように、ネガティブ ブラフです。これは、プレイヤーが駒の価値を実際よりも低く見せかけるアクティブ ブラフの反対です。

下の図 5c はより複雑なブラフを示しており、DeepNash は非公開のスカウト (2) を相手の 10 の近くに移動させており、これはスパイと解釈できます。この戦略により、青は数手後に赤の 5 を 7 で捕獲することができ、それによって資材を獲得し、5 がスカウト (2) を捕獲するのを防ぎ、それが実際にはスパイではないことを明らかにすることができます。