10月1日、Ars Technicaが「With most information hidden, the game Stratego had stumped AI」と題した記事を公開した。カーネギーメロン大学・MIT・ニューヨーク大学・スタンフォード大学の共同研究チームが開発したAI「Ataraxos」が、史上最強と目されるStrategoプレイヤーを圧倒した経緯と技術的背景について詳しく紹介している。
チェスでは1997年にIBMのDeep Blueがカスパロフを下し、囲碁では2016年にDeepMindのAlphaGoがイ・セドルを破った。ポーカーBotが人間プロを超えたのも数年前のことだ。しかしボードゲーム「Stratego」だけは長年AIの壁として残り続けた。2022年にDeepMindが発表したAI「DeepNash」でさえ、人間トップを安定して倒す水準には届かなかった。その壁を今回、潤沢なインフラを持たない大学の共同研究チームが打ち破った。
Strategoとは何か——なぜこれほど難しいのか
Strategoは各プレイヤーが40枚の駒を使う2人用ボードゲームだ。駒には元帥から間諜（スパイ）まで軍事階級が割り振られており、爆弾と旗も含まれる。勝利条件は相手の旗を取ること。日本では「ストラテゴ」として知られ、欧米では特に根強い人気を持つ。
最大の特徴は駒の「種類」が相手に見えない点だ。相手は駒の「位置」は把握できるが、それが元帥なのかスパイなのかは分からない。正体が明かされるのは、2枚がぶつかって戦闘が起きたときだけ——弱い方が除去され、勝った駒の正体が初めて開示される。
このような「不完全情報ゲーム」（imperfect-information game）はポーカーと同じカテゴリーに属する。しかしMITのコンピュータ科学者Gabriele Farinaは、ポーカーとの決定的な差をこう説明する。
「テキサスホールデムでは隠された情報はたった2枚のカードで、取りうる組み合わせは1,326通りしかない。Strategoでは40枚の駒が任意の順序で並ぶ。組み合わせ数は10の33乗を超える」
さらに問題はゲーム長だ。チェスの平均手数は約40手だが、Strategoは1ゲームで2,000手に達することも珍しくない。膨大な隠れ情報が長い時間軸にわたって累積していく構造が、チェスや囲碁とは質的に異なる難しさを生み出している。
「ブラフ」という追加の難題
NYU研究員のEugene Vinitskyは「Strategoで特に際立っているのは、膨大な隠れ情報が非常に長い時間スケールにわたって展開していく点だ」と述べている。
Strategoはさらにブラフのゲームでもある。弱い駒をまるで元帥のように動かして相手を牽制するという心理戦が存在する。ブラフが多すぎれば脅しに意味がなくなり、まったくブラフをしなければ動きが読まれる。DeepNashが突破できなかった壁のひとつが、この均衡点の制御だったと研究チームは説明している。
16台のGPUで史上最強プレイヤーを下す
共同研究チームが開発したAI「Ataraxos」は、この壁を越えた。対戦相手は、世界大会での実績を持つ史上最強のStrategoプレイヤーと目されるPim Niemeijer。結果は15勝1敗4引き分けという圧倒的なスコアだった。
Ataraxosのアプローチの核心は、反実仮想後悔最小化（counterfactual regret minimization、CFR）と呼ばれるアルゴリズムを長期・不完全情報環境に適応させた点にある。CFRはもともとポーカーAI研究で発展した手法で、「過去の選択をどれだけ後悔しているか」を繰り返し計算することで最適戦略に近づいていくアプローチだ。Ataraxosはこれを駒の正体に関する信念の確率的管理と組み合わせ、長期にわたる戦略的ブラフの均衡を学習させた。完全なゲーム木の探索が現実的でない規模であるため、情報集合をサンプリングしながら方策を近似する点が技術的な鍵とされる。
際立っているのがコストだ。訓練に使ったのは16台のGPUと数千ドルの計算コストのみ。DeepMindのような潤沢な予算なしに人類最強のプレイヤーを超えたことは、アルゴリズム効率の高さを端的に示している。
不完全情報AIの次のフロンティアへ
Strategoの攻略が持つ意味は、ゲームの勝敗にとどまらない。不完全情報・長期スパン・ブラフという3要素が絡み合う環境でAIが機能することは、現実世界の意思決定問題——交渉、競争戦略、サイバーセキュリティなど——への応用可能性を直接示唆する。チェスや囲碁が「完全情報ゲーム」であるのに対し、現実の多くの問題は不完全情報を前提とするからだ。
DeepNashの登場から3年、研究チームははるかに少ない計算資源でその壁を越えた。論文は現在査読中とされており、アルゴリズムの全貌が公開された際には改めて議論を呼ぶことになりそうだ。
詳細はWith most information hidden, the game Stratego had stumped AIを参照していただきたい。
