DeepMind がサイエンスに戻ってきました! AI「ウォールブレイカー」が人間のマスターを倒すために悪巧みをする

最近、DeepMind の AI エージェント DeepNash が、Stratego で人間のプロプレイヤーを破り、トップ 3 にランクインすることに成功しました。

12月1日、論文はScience誌に正式に掲載されました。

論文アドレス: http://www.science.org/doi/10.1126/science.add4679

この AI を使用してジョン ナッシュに敬意を表します

今日の時代、ゲームプレイ AI はまったく新しい段階にまで発展しています。

過去には、多くの科学者が AI のトレーニングにチェスや囲碁を使用していましたが、DeepMind は今回、チェスや囲碁よりも複雑で、ポーカーよりも賢い古典的なボード ゲームである Stratego を使用しました。

そして、DeepNash という名前のこの AI エージェントは、Stratego 自体と対戦することで、Stratego をゼロから学習しました。

現在、DeepNash は、世界最大のオンライン Stratego プラットフォームである Gravon の人間の専門家の間で史上トップ 3 にランクされています。

#DeepNash は、ゲーム理論とモデルフリーの深層強化学習に基づいた、まったく新しいプレイ方法を採用しています。

この名前には、アメリカの有名な数学者ジョン ナッシュに敬意を表する意図もあることがわかります。

彼が提案したナッシュ均衡は、非協力ゲーム均衡とも呼ばれ、ゲーム理論の非常に重要な部分です。

Stratego の秘密は何ですか?

ボード ゲームは、制御された環境で人間と機械がどのように戦略を策定し、実行するかを研究できるため、歴史的に AI の進歩のベンチマークとなってきました。

そして、このStrategoの謎は何でしょうか?

チェスや囲碁との違いは、Stratego が不完全な情報ゲームであることです。プレイヤーは対戦相手の駒の正体を直接観察することができません。

この複雑さのため、AI ベースの Stratego システムは、どれだけ頑張ってもアマチュア レベルであることが多く、「専門家」のレベルに到達することはできません。

かつて、さまざまなAIがゲームで大勝し、人間を完全に圧倒したのは、「ゲームツリー検索」と呼ばれるAI技術のおかげです。

「ゲーム ツリー検索」は、情報が完全に把握されているさまざまなゲームですべての関係者を殺すことができますが、Stratego のようなゲームでは、拡張性が十分ではないため、やや無力です。

現時点で、DeepNash はゲーム ツリー検索を完全に破りました。

実際、DeepNash はゲーム自体をはるかに超えた Stratego の価値を習得しました。

現実の世界は非常に複雑であることが多く、情報は限られています。真に高度な AI システムは、Stratego のような環境に直面します。

DeepNash は、AI がどのように結果のバランスをうまく取り、不確実性の下で複雑な問題を解決できるかを示すことに成功しました。

Stratego の遊び方

Stratego はターンベースのキャプチャ ザ フラッグ ゲームです。ゲームでは、プレイヤーはブラフを掛けたり、回りくどい戦術を使用したり、情報を収集したり、巧みに操作したりする必要があります。

これはゼロサム ゲームであるため、1 人のプレイヤーが得たものは、対戦相手にとっても同じ量の損失となります。

それは私たちの軍事チェスに非常によく似ています。

Stratego は、より多くのチェスの駒、より多くの軍事階級、よりシンプルなチェス盤のデザインがあり、鉄道、キャンプ、審判がないという点で軍事チェスとは異なります。

双方が陣形を組むとき、すべてのチェスの駒は直立し、相手側から見えないようにする必要があります。

陣形が完成したら赤側が先に動き、その後順番に1枚ずつ動かします。

チェスの駒のうち、軍旗と地雷は移動できません。偵察兵は水平方向と垂直方向に任意のマスを移動できますが、チェスの駒を横切ることはできません。他のチェスの駒は水平または垂直に 1 マスしか移動できません。

双方の駒が同じマス目にある場合は、一緒に剥がして大きさを判定し、勝った駒を後ろ向きに元の位置に戻し、負けたチェスの駒は取り除かれます。

Stratego の勝利方法は中国の軍用チェスに似ており、相手の軍旗を奪取するか、動いているチェスの駒をすべて破壊することで勝利となります。

Stratego が AI にとってこれほど難しいのはなぜですか?その理由の一つは、それが不完全な情報のゲームであることです。

Stratego の 2 人のプレイヤーは、40 個の駒を開始フォーメーションに配置するときに、互いに隠れます。

プレイヤーは同じ知識にアクセスできないため、意思決定を行う際には、考えられるすべての結果のバランスを取る必要があります。

Stratego チェス駒の種類とランキング

左: チェス駒のランキング。ゲームでは、スパイに襲われた 10 (元帥) を除いて、より高い軍事ランクを持つ駒が勝ち、鉱山労働者に捕獲された唯一の例外を除いて、常に爆弾が勝ちます。

中: 考えられる先発フォーメーション。旗は安全に後方に隠し、側面には爆弾を設置して保護する必要があります。 2つの水色のエリアは「湖」なので決して立ち入ってはなりません。

右: 進行中のゲーム。ご覧のとおり、青チームのスパイが赤チームのマーシャルを捕まえています。

このゲームは AlphaZero を困惑させました

Stratego では情報は隠蔽されています。

他のプレイヤーと遭遇した場合にのみ、相手の駒の正体が明らかになります。

チェスと囲碁の違いは、両プレイヤーが各チェスの駒の位置と正体を正確に知っているため、「完全情報ゲーム」であるということです。

DeepMind の AlphaZero は、完全情報ゲームでは常に優れたパフォーマンスを発揮してきましたが、Stratego ではつまずいてしまいました。

チェスでは、AlphaZero が 4 時間後に Stockfish を上回り、将棋では、AlphaZero が 2 時間後に Elmo を上回り、囲碁では、AlphaZero が 30 AlphaGo で Elmo を上回り、AlphaGo を上回りました。

Stratego はテキサス ホールデムに似ており、人間と同様の能力が必要です。人間は不完全な情報で意思決定を行い、ブラフを掛ける必要があります。

アメリカの作家ジャック・ロンドンはかつてこう指摘しました、「人生において、私たちは常に良いカードを持っているわけではありませんが、時には悪いハンドでも良いプレーができることもあります。」

実際、多くの AI はポーカーのプレイにも非常に優れていますが、Stratego に直面すると混乱します。このゲームのプロセスは長すぎます。

勝つためには、プレイヤーは何百もの動きをする必要があります。そのため、ゲーム内での推論は多数の連続したアクションに基づいて行われなければなりませんが、その過程では、それぞれのアクションが最終結果にどのような影響を与えるかを明確に把握することは困難です。

チェス、ポーカー、囲碁、ストラテジーのサイズの違い

そして、チェス、囲碁、ポーカーと比較して、可能なゲーム 状態の数 (「ゲーム」)ツリーの複雑さ」）はチャートから外れており、解決するのが非常に困難です。

これが、Stratego が非常にエキサイティングな理由です。これは、AI コミュニティにおける数十年にわたる課題を表しています。

Stratego: AI が征服できる高台

長年にわたり、Stratego ゲーム内で人工知能をどのように目立たせるかが AI 研究者の焦点となってきました。

このゲームで人間のプレイヤーを倒すには、主に 2 つの困難があります。

まず、このゲームのゲーム ツリーには 535 乗の状態が 10 個あります。つまり、ゲーム内には 535 乗の可能なレイアウトが 10 個あります。対照的に、Go では可能なレイアウトは 10 個しかありません。

第二に、Stratego では、人工知能は 10 の 66 乗以上で相手の展開戦略を推論する必要がありますが、ポーカーには可能なカードのペアが 1,000 しかありません。

したがって、Stratego の複雑なレイアウトを解読するのは簡単ではなく、人間の Stratego プレイヤーに勝つ方法は、AI 研究者にとって前例のない課題です。

他の AI を完全に倒すにはどうすればよいでしょうか? R-NaD という核心武器に頼る

DeepNash が他の AI を完全に上回った理由は、ゲーム理論とモデルフリーの深層強化学習を組み合わせた新しい手法を採用しているからです。

「モデルなし」とは、DeepNash がゲーム内の対戦相手の状態を明示的にシミュレートしようとしないことを意味します。

特にゲームの初期段階では、DeepNash が相手の駒についてほとんど知らないため、このモデリングは、たとえ完了できたとしても無効になる可能性が高くなります。

さらに、Stratego のゲーム ツリーは非常に複雑であるため、DeepNash はゲームをプレイするときに他の AI が使用するモンテカルロ ツリー検索を使用できません。後者は、それほど複雑ではないボード ゲームやポーカーにおける AI の画期的な成果の鍵となります。

均衡戦略は、双方が交代で行動する完全情報ゲームでは役割を果たすことができますが、不完全情報ゲームでは不十分であることがわかります。

DeepNash は、新しいゲーム理論アルゴリズムのアイデアである正則化ナッシュ動的プログラミング (正則化ナッシュ動的、R-NaD) を採用しています。

#このモデルフリーの強化学習アルゴリズムは、DeepNash の中核です。

DeepNash を導き、その学習行動をナッシュ均衡の方向に発展させます。

DeepNash は、R-NaD とディープ ニューラル ネットワーク アーキテクチャを組み合わせて、ナッシュ平衡に収束します。

報酬変換、動的計画 (ダイナミクス)、更新反復 (udate) の 3 つのステップが含まれます。

研究チームは、アルゴリズムが元のゲームのナッシュ均衡に収束したことを証明するために一連の固定点が生成されるまで、これら 3 つのステップを繰り返し適用しました。

最強の Stratego ロボット (コンピューター ストラテジー ワールド チャンピオンシップの優勝者数名を含む) と対戦した場合、DeepNash の勝率は 97% であり、多くの場合 100% の勝率に達します。

Gravon ゲーム プラットフォームで、DeepNash は人間のトップ プレイヤーに対して 84% の勝率を達成し、史上トップ 3 にランクされました。

もちろん、この方法ではプレイヤーの勝率が保証されないため、ゲーム理論を通じてナッシュ均衡に到達することはできません。

均衡戦略は完全な情報があるゲームでのみ完全に適用できます。不完全な情報があるゲームでは、予想外に勝つためには他の戦略が必要です。

初期編成で、DeepNash は並外れたゲームプレイを採用しました。悪用を困難にするために、DeepNash は予測不可能な戦略を開発しました。

これは、対戦相手がその後の一連の試合で自分のパターンを発見できないように、最初の展開が十分に柔軟である必要があることを意味します。

ゲームの段階では、DeepNash は、自身が悪用されないようにするために、一見同一のアクション間でランダム化 (ランダム化) するよう最善を尽くします。

このプロセスでは、情報を隠すことが非常に重要です。

情報を隠して対戦相手を混乱させる

現実のシナリオでは、人々は勝つために他の手段も使用します。はったり。

「ゲーム理論の父」フォン・ノイマンは次のように述べています。「現実の生活は、『はったり』、『ちょっとした欺瞞』、そして『他人が自分が何をしようとしているかを推測する』ことに満ちています。」

「レッドアイズ・アンド・ブルーアイズ自殺問題」テレンス・タオ著: わかってる、知っている、知っている、知っている、知っている...

この点では、DeepNash も同様に優れています。

研究チームは、DeepNash の 2 つのブラフテクニック、アクティブ ブラフ (ポジティブ ブラフ) とパッシブ ブラフ (ネガティブ ブラフ) を実証しました。

いわゆるアクティブブラフとは、自分のチェスの駒が高いレベルであるかのように見せかけ、相手を威嚇することです。簡単に言えば「ハッタリ」です。

この例では、DeepNash が良い教訓を教えてくれました:

人間のプレイヤー (赤チーム) と対戦するとき、DeepNash (青チーム) は 7 を犠牲にしました (メジャーなどの他の駒を犠牲にしました) ) と 8 (大佐)、相手の 10 (元帥)、9 (将軍)、8 と 2 つの 7 を見つけます。

この時点で、DeepNash (青側) は相手の最も強力な駒の多くを発見し、同時に自身の重要な駒を隠しました。

一見すると、DeepNash は明らかに不利な立場にあるように見えます。7 と 8 がアウトですが、人間の対戦相手はランク 7 以上のすべての駒を保持しています。

しかし、DeepNash は最後に笑いました。対戦相手の上層部から得た信頼できる情報に基づいて、勝利確率は 70% であると推定されました。

最終的には勝ちました。

ブラフの「芸術」

ポーカーでは、優れたプレイヤーは、たとえ自分が弱くても、相手を威圧する心理戦を繰り広げます。

ディープナッシュは、このブラフ戦略、つまりネガティブ ブラフも学びました。

これは、私たちがよく「豚のふりをして虎を食べる」と呼ぶものです。高レベルのチェスの駒を低レベルのチェスの駒に偽装し、相手がだまされるまで待ってから、勝つのです。一気に。

次の例では、DeepNash は 2 (非常に弱いスカウト) を使用して、正体を明らかにした相手の 8 を追跡します。

人間の対戦相手は、これに基づいて追跡者が 10 人である可能性が高いと判断し、追跡者をスパイの待ち伏せサークルに誘い込もうとします。

最終的に、ディープナッシュは小さなチェスの駒 2 を使用して、相手の重要なチェスの駒のスパイを破壊することに成功しました。

人間のプレイヤー (赤側) は、自分の 8 を追いかけている未知の駒は DeepNash の 10 に違いないと確信しています (この時点で DeepNash はすでに唯一の 9 を失っているからです。

以下は、DeepNash と (匿名の) 人間の専門家との 4 つの完全なゲーム ビデオ、ゲーム 1、ゲーム 2、ゲーム 3、およびゲーム 4 です。クリックすると、さらに驚きが表示されます (ビデオ アドレスは引用資料にリストされています)。 )

私は DeepNash のプレイ レベルに驚きました。人造 Stratego プレイヤーが人間のプレイヤーに勝つために必要なレベルに近づいているという話は聞いたことがありません。

しかし、DeepNash と個人的に対戦した後、 Gravon でトップ 3 にランクインしたことには驚きません。私の予測: 人間の世界選手権への参加が許可されれば、非常にうまくいくでしょう。

——Vincent de Boer、共著者この論文の元Stratego世界チャンピオン

未来は計り知れない

DeepMindのこの新しいR-NaDメソッドは、完全なまたは他の2人プレイヤーのゼロゲームに直接適用できることがわかります。不完全な情報を含むゲームを合計します。

R-NaD には、2 プレイヤー ゲームの設定を超えて、大規模な現実世界の問題を解決する可能性があります。

さらに、R-NaD はまた、

たとえば、他人の意図や環境情報が分からない交通管理の規模最適化において、R-NaD は最適化を行うことが期待されています。

人間の世界は本来、予測不可能です。

現在、人々は不確実性に直面しても堅牢な汎用 AI システムを作成しており、そのおかげで私たちは人間に対してより自信を持つことができます。 . 未来は想像力に満ちています。

参考:

http://www.science.org/doi/10.1126/science.add4679

https://www .nature.com/articles/d41586-022-04246-7

https://www.deepmind.com/blog/mastering-stratego-the-classic-game-of-imperfect-information

https://youtu.be/HaUdWoSMjSY

https://youtu.be/L-9ZXmyNKgs

https://youtu.be/EOalLpAfDSs

https://youtu.be/MhNoYl_g8mo

以上がDeepMind がサイエンスに戻ってきました! AI「ウォールブレイカー」が人間のマスターを倒すために悪巧みをするの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。