ゲームAIの課題が進み、リアルタイム戦略ゲームや不完全情報ゲームがホットスポットに

前回の 2 つの記事では、ゲーム AI の歴史におけるいくつかの古典的なアルゴリズムと画期的なイベントをレビューし、チェス、囲碁、ポーカー、麻雀などのボードゲームの AI の複雑さを数学的観点から測定する方法を紹介しました。この記事では、近年非常に成功したゲーム AI をいくつか紹介し、AI にまだ征服されていない人気ゲームをいくつか紹介します。これらは間違いなく、将来のゲーム AI の開発方向とトレンドを表しています。

人間のレベルに達するかそれを超えるゲームAI

マルチプレイヤー テキサス ホールデム: Pluribus

チェスや囲碁とは異なり、不完全情報ゲームであるテキサス ホールデムには、異なる課題があります。プレイヤーは互いのカードを見ることができず、プレイヤーはしばしばこの非対称性を利用してブラフをかけ、相手を欺きます。完全情報ゲームに適した AlphaGo/AlphaZero などのアルゴリズムは、ポーカーでは直接使用できません。 AI の分野では、テキサス ホールデムは未解決の課題として捉えられています。

CMU と Facebook が最近開発した Pluribus は、6 人対戦のノーリミット テキサス ホールデムで人間のプレイヤーに勝利しました。これらの人間のプレイヤーは全員、100万ドル以上を獲得したプロプレイヤーでした。Pluribusは12日間でこれらの人間のプレイヤーと1万回以上のゲームをプレイし、ついに勝利しました。

Pluribus は人間のマニュアルに頼ることなくトレーニングされました。その代わりに、ゼロからスタートし、自分自身のコピー 6 体と対戦することで継続的にパフォーマンスを向上させました。セルフゲームでは、Pluribus は MCCFR (モンテカルロ CFR) アルゴリズムに基づいてより優れたカードプレイスキルを検索して学習し、さまざまなセルフゲーム結果のブループリント戦略を呼び出します。無制限テキサスホールデムの状態空間は広すぎるため、ブループリント戦略は限られた戦略空間しか扱うことができません。そのため、実際の戦闘では、Pluribus はブループリント戦略を使用して予備的な決定を下し、その後のゲームでは、限られた数のステップを探索してさらに詳細な決定を下します。 Pluribus の主任開発者である Noam Brown 氏は、Pluribus の戦略のいくつかがプロのプレイヤーのプレイ方法を変えるだろうと考えています。

しかし、テキサス ホールデムは不完全情報ゲームですが、どのような状況であっても、対戦相手ごとに可能な隠れた状態の数は 1,000 程度しかありません (50 枚のデッキから 2 枚のカードを選択)。 Pluribus であれ、別の非常に成功したポーカー AI DeepStack のアルゴリズムであれ、どちらもきめ細かい検索を実行するために対戦相手のカードの確率分布を推定することに大きく依存しており、実装の難しさは比較的制御可能です。ただし、これらの近似アルゴリズムは、隠し状態の数が非常に多いゲーム (ブリッジや麻雀など) に適用するのが困難です。

図1: 5人のプロプレイヤーに対してブラフをかけるPluribus

スタークラフト2: アルファスター

AlphaStarはDeepMindとBlizzardが開発した「StarCraft 2」ゲームAI。2019年1月にトッププロプレイヤーを破った。

「StarCraft」は、マルチプレイヤーのリアルタイム戦略ゲームです。一般的な1対1のバトルモードでは、各プレイヤーは3つの種族から1つを選択し、異なるマップで戦います。ゲームの開始時に、各プレイヤーにいくつかの初期ユニットが割り当てられます。プレイヤーはこれらのユニットに基づいて、マップから開発可能なリソースを取得し、これらのリソースを使用してより多くのユニットとテクノロジーを構築する必要があります。ゲームの目的は、リソースを管理し、軍隊を編成し、敵のユニットをすべて破壊することです。

StarCraft のプレイヤーはマクロ計画とミクロ操作の両方を同時に考慮する必要があり、ゲームは最大 1 時間続くことがあるため、AI の戦略には長期的な計画機能が必要です。また、従来のチェスやカードゲームとは異なり、StarCraft のプレイヤーは、短時間でさまざまなエリアに分散された複数のユニットを継続的に操作する必要があります。さらに、StarCraft は不完全な情報のゲームでもあります。最初のマップは「戦争の霧」の層で覆われており、対戦相手の情報が見えなくなります。そのため、プレイヤーは常に相手の位置をテストし、対応する対策を講じる必要があります。

AlphaStar はディープ ニューラル ネットワークを使用して Blizzard が提供するゲーム内情報を受信し、一連の指示を出力して AI が行動を選択できるようにします。エージェントはまず人間のプレイヤーのプレイパターンを学習し、次にマルチエージェント強化学習アルゴリズムを通じてパフォーマンスをさらに向上させます。 AlphaStar のネットワーク構造は、Transformer、LSTM、自己回帰ポリシー ヘッド、ポインター ネットワーク、集中型値ベースラインを組み合わせたものです。

AlphaStarは教師あり学習の後、AIが互いに学習できるリーグメカニズムを作成しました。人口理論に基づく強化学習アルゴリズムを通じて、AIは十分な多様性を維持しながら強くなり続けることができます。 StarCraft 2 のさまざまな戦略とレースには相互依存関係があるため、このトレーニング方法により、AI を総合的な強さを強化する方向にトレーニングできます。

AlphaStar は間違いなく大成功を収めていますが、意見の相違がある人も多くいます。人間との競争において、AlphaStar には戦略を超えた非対称性がまだあります。AI は、非常に短時間で数百の異なる個人を高い粒度で操作し、さまざまなタスクを実行できます。短時間で非常に細かくマルチタスクをコントロールできるため、人間のプレイヤーに比べて大きな利点があります。さらに、AlphaStar は特定のマップ上の特定のレースでのみトレーニングされたため、まだ欠点がある可能性があります。

AlphaStar 開発チームは、このモデルが他のタスク、特に機械翻訳、言語モデル、視覚表現など、長いシーケンスのモデリングを必要とし、大きな出力スペースを持つタスクに役立つことを期待しています。

図 2: AlphaStar と MaNa (トップの人間プレイヤー) の試合の視覚化。この図は、AI の観点から見たゲームを示しています。ニューラル ネットワークに入力される元の情報、ニューラル ネットワークの内部アクティベーション ユニット、いくつかの代替アクション、および勝敗の確率が含まれています。

Dota2: OpenAI ファイブ

Dota2 も、マルチプレイヤー参加型のリアルタイム戦略ゲーム (MOBA) です。ゲームは 2 つのチームでプレイされ、各チームは 5 人の「ヒーロー」で構成されています。これらのヒーローは、多くの場合、異なる特性と独自の責任を持っています。したがって、チームの勝利は、異なる責任を持つプレイヤー間の分業と協力にかかっています。チームワークを重視するゲームです。 StarCraft と同様に、Dota2 も不完全情報ゲームです。プレイヤーはマップ上のさまざまなリソースと視界を獲得し、最終的に敵チームの中核となる建物を倒す必要があります。

AlphaStar とは異なり、Dota2 のトレーニングは完全に自己プレイからの学習に基づいており、ニューラル ネットワークは近似ポリシー最適化を通じて更新されます。多くの研究者は、Dota の長期計画問題を解決するには、長期計画と短期計画を別々に処理する階層的強化学習などの技術が必要であると考えています。しかし、強化学習のみで訓練されたポリシーが長期的な計画を立てる能力も備えていることがわかり、研究者たちはうれしい驚きを覚えました。

OpenAI Five は 5 つのニューラル ネットワークを使用して 5 人の「ヒーロー」を表現します。 5 人の「ヒーロー」のニューラル ネットワーク間には明確なつながりはありませんが、ヒーローたちは自分自身の報酬とチームの報酬の重みを制御することで協力することを学びます。

2019年4月、OpenAI Fiveはベスト3マッチでDota2世界チャンピオンのOG Clubを2-0で破りました。しかし、OpenAI Fiveの戦略がさらに分析されるにつれて、ネットユーザーはOpenAI Fiveの弱点も発見した。チーム戦は得意だがスプリットプッシュは苦手であり、OpenAI Fiveを倒すには弱点に基づいた戦術をカスタマイズする必要がある。

ゲームAIの次の挑戦：ブリッジと麻雀

上記のすべてのゲームにおいて、AI はトップレベルの人間プレイヤーのレベルに到達するか、それを超えることができます。しかし、幅広いマスベースを持つブリッジや麻雀には、既存のアルゴリズムではうまく処理できないさまざまな属性があります。これらがゲーム AI にとっての次なる課題となることは間違いありません。

橋

ブリッジは不完全な情報を持つ 4 人のプレイヤーによるゲームです。ゲームの開始時には、プレイヤーは自分のカードしか見ることができません。ブリッジは入札とプレイの 2 つのステップに分かれています。

テキサス ホールデムとは異なり、ブリッジには、特に入札とプレイの初期段階で、はるかに多くの隠された情報があります。コンピュータは完全な情報を使って検索するのが得意ですが、人間のプレイヤーは不完全な情報を使って推論したり決定を下したりするのが得意です。これはまさにコンピュータが苦手としていることです。さらに、ブリッジでは 4 人のプレイヤーの間で競争と協力の両方が行われます。プレイヤーがペアで協力する場合、対戦相手の情報だけでなく、チームメイトの情報も推測する必要があります。

現在のブリッジ アルゴリズムは、現在の状況に一致する多数の対戦相手のハンドをランダムに生成し、次にダブル ダミー ソルバー アルゴリズムを使用してカードのプレイ方法を推定し、最後にすべてのサンプル ハンドの中で全体的なパフォーマンスが最も優れたカードを選択します。このようなアルゴリズムは、ランダムに生成されたハンドの量と質、およびダブルダミーアルゴリズムのパフォーマンスに大きく依存します。ゲームの終盤では、隠されたカードがあまりないので、サンプリングして検索するアルゴリズムの方が効果的かもしれません。

1997 年以来、毎年世界コンピュータブリッジ選手権が開催されていますが、現在までトップクラスの人間プレイヤーに勝てる AI は存在しません。

麻雀

麻雀は、世界中、特にアジアで幅広い層に親しまれている、マルチプレイヤーの不完全情報ゲームでもあります。

一般的な麻雀ゲームは 4 人のプレイヤーで構成され、各プレイヤーは 13 枚の秘密カードを持つことができます。囲碁と同様に、麻雀にも非常に複雑な状態があります。テキサス ホールデムと比較すると、麻雀のどの状況でも、各対戦相手の隠れた状態の数は 10 桁以上多くなります。この不確実性により、プレイヤーが対戦相手の状態を推測することが難しくなります。ゲーム中、人間のプレイヤーは「直感」を使って、待機中のカードの状態、待機中のカードのスコアなど、意思決定に影響を与える可能性のある対戦相手の情報を推測します。自分のカードに関しては、獲得できるスコアを正確に検索することがよくあります。あいまいな推定と正確な検索のバランスをどのように取るかは、AI にとって大きな課題です。

テキサス ホールデムやブリッジとは異なり、麻雀プレイヤーはプレイする前に捨てられたカードの代わりに下のデッキからランダムにカードを引かなければなりません。このランダムに引かれた一番下のカードにより、麻雀の強いランダム性がゲーム全体に及び、ゲームの結果を大きく変えることになります。たとえば、2 人のプレイヤーが同時に同じカードを待っている場合、最終的に誰が勝者になるかは主に運次第です。

麻雀の強いランダム性は、AI の学習効率に課題をもたらすでしょう。 「プレイヤーが勝ったのは、上手にプレイしたからなのか、それとも運が良かったからなのか」を知りたい場合、この答えを得るには、通常、多数のゲームをプレイしてそれを測定する必要があります。非常にランダムな環境でより効率的に自己学習を行う方法は、AI が解決しなければならない難しい問題です。

同時に、麻雀ゲームの強いランダム性のため、麻雀 AI のレベルをどのように測定するかも課題です。

まとめ

これらの新たな課題に対処するために、将来、ゲーム AI は、多数の隠れた状態の下で推論の決定を行い、効率的に学習する能力を備える必要があり、また、ランダムなイベントやコラボレーションに対処するためのより強力な能力も必要になります。私たちは、ゲーム AI テクノロジーがこれらの難しいゲームで継続的に進歩し、ゲームから学んだ経験と能力を現実世界に適用して、人間がさまざまな複雑なタスクをよりうまく完了できるように支援することを期待しています。