IBM東京基礎研究所「NeurIPS 2018」のAIゲームコンペティション、圧勝の秘密

記事をシェアする:

自律型エージェントによるリアルタイムの逐次的意思決定

自動運転車やドローンをはじめとする自律型エージェントは、環境や他のエージェントの動きの変化に即座に対応できるよう、リアルタイムで逐次的な意思決定を行わなければなりません。衝突を避け、安全な状態に復帰する必要があるのならなおさらです。現在のAIでは、他のエージェントの動きを考慮しなければならない場合や必要な情報を直接観測できない場合、このようなリアルタイムの意思決定は非常に困難です。AI Researchのコミュニティーはこれらの課題に対処すべく、具体的なコンペティションを企画し、互いに競い合うことでこの分野を発展させてきました。

2018年12月8日にカナダ・モントリオールで開催されたAI国際会議「第32回Conference on Neural Information Processing Systems」（NeurIPS 2018）で行われたPommermanコンペティションにおいて、IBM東京基礎研究所からの参加勢が1位と3位を獲得しました。IBMチームの成功の鍵は、自律型エージェントによるリアルタイムの逐次的意思決定を実現させるためにIBMが開発した最新のテクノロジーにありました。

Pommermanコンペティションでは、2つのエージェントで構成されたチームが11×11の碁盤目状のボード上で別のチームと対戦します（図1参照）。各エージェントが観測できるのはボード上の限られた範囲だけで（図1の小さいパネルを参照）、エージェントどうしが通信することはできません。各チームの目標は対戦相手を全滅させることです。この目標を達成すべく、エージェントは爆弾を仕掛けて木製の壁を破壊し、それらの壁から現れてくることがあるパワーアップ・アイテムを集め、爆炎を避けながら対戦相手を攻撃します。詳しくは、PommermanのGitHubリポジトリーをご覧ください。

図1. 100手後のPommermanボード

Pommermanの難しさは、リアルタイムの意思決定を下さなければならないという制約にあります。つまり、エージェントは100ミリ秒以内にアクションを選択しなければならないのです。こうした制約があるために、チェスや囲碁のようなゲームでは有効であったモンテカルロ木探索の適用が難しくなります（例えば、囲碁のプレイヤーには持ち時間を使い切った後でも、通常1手ごとに30秒が与えられます）。

Pommermanの場合、4つのエージェントが1手ごとに同時にアクションを起こし、エージェントごとに6通りのアクションが考えられることから、場合によっては分岐因子（次の可能手の数）が64=1,296通りにもなります。分岐因子が多くても192=361通りしかない囲碁と比べてみるとわかりやすいかもしれません。各エージェントは、爆弾の爆発を考慮に入れ、先を見越してアクションを選択する必要があります。爆弾のライフタイムは10手です。

木探索の深さが不十分（10未満）だと、爆弾の爆発が無視されるため、エージェントが爆炎に巻き込まれやすくなります。一方、十分に深く（10以上）探索しようとすると、分岐因子が大きくなる（11手以降の可能な手の数が1031通りを超える）ため、リアルタイムに最善手を選ぶことが実質的に不可能になります。

IBMが開発した新手法では、限られた深さでしか木探索は行われませんが、探索木の葉が決定的かつ悲観的シナリオに基づいて評価されます（図2参照）。この新手法では限られた深さまでしか分岐がないため、探索木のサイズを抑えられると同時に、分岐を考慮した場合に可能な長さよりもはるかに長いシナリオで葉を評価できるため、遠い将来に発生する可能性のある重大なイベントをも考慮することができます。

図2. 決定的かつ悲観的シナリオに基づく新しい木探索

この新手法で悲観的シナリオを用いる理由は、特に安全が優先される状況での優れたアクションとは、悲観的シナリオでうまくいったものであることが多いためです。環境の状況を物体の位置によって表すことができる場合、悲観的シナリオを体系的に生成することが可能です。Pommermanでは、エージェント、爆炎、パワーアップ・アイテム、壁がそれらの物体に相当します。エージェントのアクションによって位置が変わる物体があるので、必然的に木探索の分岐が発生します。新手法では、たとえ非現実的であったり、ルールに適合しないとしても、複数の位置に１つの物体が配置されることを許容することによって、悲観的シナリオを生成します。

新手法の有効性は悲観度のレベルによって決まるため、（悲観レベルを変えながらエージェントに自己対戦を繰り返させる）セルフプレイによってそのレベルを調整することで、IBMエージェントの全体的なパフォーマンスを最大化できます。図3は、新手法における「悲観」の有効性を示しています。各パネルはベースラインに対するIBMエージェントの勝ち数、引き分け数、敗け数を示しており、IBMエージェントの悲観レベルは横軸に沿って変化させています。左側パネルのベースラインは、初期設定エージェントのチーム（SimpleAgents）であり、右側パネルのベースラインは、悲観レベルが0に設定されている以外はIBMエージェントと同一のエージェントのチームです。悲観レベルが最適化されたIBMエージェントのチームは、SimpleAgentsとの対戦で99.7%の確率で勝っています（残り0.3%は引き分け）。

図3. 新手法における「悲観」の有効性

 
新手法の詳細については、最近発表した研究報告書[1]でご確認いただけます。IBMエージェントのDockerイメージも、multiagentlearning/{hakozakijunctions, dypm.1, dypm.2}として提供されています。IBMの手法は、きわめて重要な意思決定をリアルタイムで行うことができる自律型エージェントの実現に向け、リアルタイムの逐次的意思決定の分野を発展させるものです。例えば、この新手法を自律走行車に採用すれば、さまざまな潜在的リスクに対処し、危険な状況でも安全に運転することのできる、人間のベテラン・ドライバーさながらの走行を実現できる可能性があります。

※この記事は米国時間2019年3月6日に掲載したブログ（英語）の抄訳です。

[1]恐神 貴行・高橋 俊博 共著、Real-time tree search with pessimistic scenarios（悲観的シナリオに基づくリアルタイムの木探索）、arXiv:1902.10870、2019年2月 , arXiv:1902.10870, February 2019.

著者：恐神 貴行 IBM東京基礎研究所、研究員

著者：高橋 俊博 IBM東京基礎研究所、研究員