本文へ
ハクソク

世界を動かす技術を、日本語で。

情報の大半が隠された状態で、ゲーム「ストラテゴ」はこれまでAIを悩ませてきた

元記事: 原文(arstechnica.com)

概要

  • Stratego は長らくAIが攻略できなかったボードゲーム
  • Ataraxos が世界最高峰プレイヤーを圧倒
  • 隠された情報量 と ブラフ がAI開発の難関
  • 少ない計算資源 での学習成功
  • 先行AIの課題を 新手法 で克服

Stratego攻略のAI「Ataraxos」、人間トップを圧倒

  • Deep Blue が1997年にGarry Kasparovを、 AlphaGo が2016年にLee Sedolを破るなど、AIは多くのボードゲームで人間を凌駕
  • しかし、 Stratego は長年AIにとっての難関として残存
  • DeepMind のDeepNash（2022年発表）ですら、安定してトッププレイヤーを破れず
  • Carnegie Mellon、MIT、New York University、Stanford University の研究チームが開発したAI「 Ataraxos」が、Strategoの伝説的プレイヤー Pim Niemeijer に15勝1敗4分の圧勝
  • 16枚のGPU と 数千ドル のコストで学習を達成

Strategoの難しさとAIの課題

  • Strategoは 40個の駒 で構成され、各駒の正体は対戦相手に非公開
  • 勝利条件は 相手の旗を奪取
  • 駒同士の戦闘 でのみ正体が公開され、敗者は除外される
  • 隠された情報 が膨大で、戦略の幅が非常に広い
    • 例：Texas Hold’emでは隠されたカードは2枚（1,326通り）に対し、Strategoは 40駒の並び順 で「デシリオン（10の33乗）」超の初期配置パターン
  • ゲームの 手数 も圧倒的に多く、1ゲームで 2,000手 に及ぶことも
  • ブラフ （虚勢・欺き）の要素が重要
    • 弱い駒を強く見せかけて相手を牽制
    • ブラフの頻度やバランスが勝敗を左右
  • これらの要素が従来AIの 戦略学習 を困難にしていた

Ataraxosの技術的ブレイクスルー

  • 少ない計算資源 での効率的な学習
  • 膨大な隠れ情報 への対応力
  • 長期戦略 と ブラフ を適切に取り入れた意思決定
  • これにより、人間トッププレイヤーを安定的に上回るパフォーマンスを実現

参考文献・リンク

提供: ハクソク · 要約更新:

AIによる日本語要約です。内容は原文とあわせてご確認ください。

Hacker Newsの議論を読む

Hackerたちの意見

これで、2022年の「モデルフリーのマルチエージェント強化学習によるストラテジーゴのマスタリング」が少し見えてきたね。どうやら2022年の「マスタリング」はまだ達成されてなかったみたい。4年後の今、新しいアプローチは実際に人間よりも優れているようだね。

このアプローチは、すごく面白いゲームの花火（ハナビ）にも使えるよ。自分のカードは見えないけど、他のプレイヤーは見えるんだ。強化学習のポッドキャストで誰かが言ってたから、このゲームを買って、実際に何回もプレイしたよ。

ああ、やばい！ストラテジーゴは、勝てるボットを作るためにもっと頑張らなきゃいけないと思ってたんだ。2022年のDeepMindの取り組みも含めてね。最初のボットを作ろうと思ってたんだけど、リーマン予想を証明しようとするよりは、ちょっとマシかなと思ってた。でも最近は、クラウドに頼めば「1 + πiに反例がある」って教えてくれる時代だね。

└

最近、Starcraft 1のRLボットとAdvance Warsのボットを手に入れたんだけど、どちらも人間レベルの上位にいるよ。

└

リーマン予想がすでに解決されたかのように振る舞う人がいるのはなぜだろう？まだ人間には不可能で、AIのオーバーマインドには少し可能性があるかもしれないのに。（もちろん、明日Googleが解決したって発表するかもしれないけど。）

└

今はリーマン予想に取り組むのにいい時期だと思う。実際、たくさんのアイデアがあるけど、どれが進展するかは誰にもわからない。でも、新しいツールがあるから、進展するのは全く不可能じゃないと思うよ、ハハ。

現在のAIはストラテジーゴの「サイレントディフェンス」バリアントにどれくらい対応できるんだろう？記事によると、高い不確実性が課題になってるみたい。サイレントディフェンスだと、その不確実性はさらに高くなるよね。「攻撃が行われると、攻撃者だけが自分の駒の数を宣言しなければならない。防御者は自分の駒の数を明かさず、数が少ない駒をゲームボードから取り除いて攻撃を解決する。プレイヤーは自分の捕まえた駒を保持する。ただし、スカウトが攻撃する場合、防御者は自分の駒の数を明かさなければならない。」

└

子供の頃、友達が「エレクトロニックストラテジーゴ」を持ってたんだ。最大のゲームプレイの変更点は、相手に駒の強さを明かさずに戦闘を行えることだった。これのおかげで、もっと面白いゲームになったし、かなり楽しんでプレイしたよ。

これらのゲームが繰り返し勝てる理由は、静的だからだと思う。アルゴリズムがしっかりトレーニングされれば、MtGのようなゲームで平均的なプレイヤーよりも上手くプレイすることはあるだろうけど、もし新しい「カード」が定期的にリリースされる（例えば、週に1回や隔週で）なら、人間にとってはかなり公平なプレイ環境になると思う。新しい追加要素が、全く新しい「カード」によってトレーニングデータを無効化することもあるし、そのダイナミクスを完全に変えることができる。プレイヤーには理解しやすいけど、アルゴリズムには難しいかも（定期的に再トレーニングするための十分な計算能力があればできるかもしれないけど）。それに加えて、意思決定ツリーは囲碁やチェス、ストラテジーゴよりもはるかに深く、広く、条件が多いから、同じターンで同じカードが使える状態でも、計算に制約のあるアルゴリズムにはかなり難しい問題になると思う。

└

新しいカードが追加されることで、全体のトレーニングデータが無効になることがあるってこと？それはちょっとおかしいよ。要するに、新しいコンボデッキが常に追加されるべきだって言ってるようなもので、エージェントが新しいカードをスキャンして、流通している他の何千ものカードとの相互作用を探るのは、人間がそれらをすべて覚えるよりずっと簡単なんだ。君の例えは、常に新しいコードを投入し続けるだけでいいって言ってるようなもので、エージェントはそのコードでトレーニングされていないから、人間ほど早くセキュリティの脆弱性を特定したり対応したりできないってことになるけど、それは正しくないよ。

└

MTGのようなゲームに欠けている要素はほとんどないよ。MTGにStockfishがない主な理由は、ルールを実装するのが面倒くさいことと、誰も気にしていないから（少なくとも実現するほどは）。原則的に、MTGはポーカーやブリッジと何も違わないし、どちらにも超人的なエンジンがあるからね。

└

ルールセットの変更に対して正規化を試みることはできるよ。たくさんのカードを生成して、エージェントがそのカードのランダムなサブセットでプレイするようにするんだ。これに関する先行研究は見てないけど、静的なゲームに比べて追加のトレーニングはおそらく2〜3桁の範囲内だと思う。（それでもかなり多いけど！）

Hacker Newsで議論の続きを見る

同じ出典の記事