POSTD PRODUCED BY NIJIBOX

POSTD PRODUCED BY NIJIBOX

ニジボックスが運営する
エンジニアに向けた
キュレーションメディア

Julian Togelius

本記事は、原著者の許諾のもとに翻訳・掲載しております。

この記事は当初、私たちの論文を紹介する簡単な投稿のつもりだったのですが、最終的に膨れ上がってしまいました。結果として、十分な内容が詰まったものになったと思います。

ビデオゲームは、人工知能アルゴリズムをテストする最良の方法ではないでしょうか。 少なくとも私は以前に、このことについて(ある程度の分量で)持論を展開しました。 ビデオゲームでは可能で、例えばロボットにおける問題などでは不可能なものの1つとして、同じアルゴリズムをたくさんのゲームで素早く簡単にテストできるということが挙げられます。ちなみにそのことは、 他のゲームベースのAIテストベッドに対して一定の優位性 を持つ The General Video Game AI Competition (GVG-AI)の指針となる原則の1つでもあります。


GVG-AIフレームワークに実装された数種類のゲーム。

現時点では、実質的にすべての種類のビデオゲームを十分にプレイできるアルゴリズムはありません(もしあれば、正直言ってAIについてはほとんどのことが解決できていると思います。しかし “ビデオゲーム” には倉庫番もゾークも、はたまたウィッチャー3も斑鳩も含まれており、そのカテゴリは非常に広範です)。あるゲームでは、満足に使えるアルゴリズムがまったくないこともあります。一方で別のゲームでは、人間レベル、時にはそれ以上でプレイできるアルゴリズムもあります。しかしスペースインベーダーをうまくプレイできるようなアルゴリズムは、恐らくBoulder Dashは苦手でしょうし、A Good Snowman Is Hard To Buildのようなパズルゲームに至ってはまったく歯が立たないでしょう。逆にスノーマンをうまく作れるようなAIが、スペースエイリアンからの攻撃をうまくかわせるかは疑問です。ゲームプレイのパフォーマンスというのは、ある意味で自動詞的だと言うことができると思います。

1つのアルゴリズムでどんなゲームでもうまくプレイできるようにさせたいというのは私たちの願いです。なぜなら知能というのは、単一のタスクだけでなく、(ある合理的な一般領域における)(ほぼ)すべてのタスクを十分に実行できるからです。しかし現状では、それぞれが部分的なタスクだけを実行できる別々のアルゴリズムしかありません。では、どうすればいいのでしょうか。

1つの答えとして、ゲームプレイ用の個別のアルゴリズム、言わば各種類のゲームにおける “チャンピオンたち” をまとめたアルゴリズムを作るということが考えられます。新しいゲームに出くわした時、そのアルゴリズムが自身の構成アルゴリズムの1つを選んでゲームをプレイするのです。大本のアルゴリズムが、それぞれのゲームに対して適切なサブアルゴリズムを選びさえすれば、個別のアルゴリズムを優に上回るパフォーマンスを実現できるでしょう。Ex pluribus unum(多数から1つへ)、三人寄れば文殊の知恵、全体はその各部の和よりも大きい、というわけです。しかし、それぞれのゲームに対して、どうやって適切なアルゴリズムを選べばいいのでしょうか。


GVG-AIフレームワークにおけるアルゴリズムのゲームへの対応力。薄い色ほど良好。アルゴリズムのパフォーマンスに基づいて、いくつかのカテゴリやゲーム群が見えてくる。

幸いなことに、 algorithm selection(アルゴリズムの選択) (分かりやすい)や hyper-heuristics(ハイパーヒューリスティクス) (多少、分かりにくい)という命題の下で、アルゴリズムを自動的に選択して問題を解決する方法の研究が以前から行われており、どのアルゴリズム(あるいはヒューリスティクス、この文脈では同じ意味です)を選択するかについて、いろいろな方法が模索されています。しかしこれらの研究はビデオゲーム向けではなく、もっと抽象的な…つまらないと言ってはさすがにダメですね。とにかくヒューリスティクスおよびアルゴリズムの選択の方法は、そのほとんどが、例えば充足可能性問題や組み合わせ最適化のような、より抽象的な(大抵の場合は退屈な)問題を対象としています。これらは確かに重要ですが、すべての問題を代表するようなものではありません。人間の知性により関連性の高いチャレンジという観点で考えれば、一般的なビデオゲームのプレイの方がより重要性が高いと言えると思います。

そんなわけで私は同僚と、ハイパーヒューリスティクスをビデオゲーム(具体的にはGVG-AIフレームワークのビデオゲーム)にどうやって適用させればいいかの調査を開始しました。その最初の成果が、この9月に開かれたIEEE Conference on Computational Intelligence and Gamesで発表した論文です。 こちらでご覧になれます。 エージェントに簡単に利用できるシンプルなフィーチャを使うことで、複数あるアルゴリズムのどれが、初めてのゲームに一番適しているかを比較的高い精度で予測できることを示しています。私たちは2014年および2015年のGVG-AIコンペティションでベストの結果を出したいくつかのエージェントを元にして、あるエージェントを作りました。そして、未訓練の状態において、どれが他よりも優れたエージェントで、それぞれの新しいゲームに対してどれを使うかを巧みに選ぶことによって、その効果を実証しました。このエージェントの中心にある分類器はシンプルな決定木なので、エージェントが選ばれる時の基準を検証することもできます。


私たちのハイパーヒューリスティクスエージェントの1つに使われる決定木。ゲームの特性に応じて、どのアルゴリズムをプレイ用に使うかを決定。

しかしながら、この結果だけではまだ十分ではありません。理想的なエージェントは、新しいゲームに対して “ほとんど” ではなく “毎回” 最良のパフォーマンスを実行するアルゴリズムを選択するべきです。もしかしたら、もっといいフィーチャがアルゴリズム選択アルゴリズムに必要なのかもしれません。あるいはもっと違う形で訓練させた方がいいのでしょうか。

人工知能とインタラクティブデジタルエンターテイメントに関するAAAI Conferenceで発表予定の次の論文で、私たちはこの問題についてより深く調査しています。 こちらをご覧ください。 まず、現時点で確認されているすべてのGVG-AIのゲームで、広範囲にわたるアルゴリズムのパフォーマンステストを実施しました。それを通じて、特定のアルゴリズムのパフォーマンスがよかったゲームをグループ別に識別しています。また、それぞれのタイプのゲームプレイ用アルゴリズムに影響を受けやすいゲームのクラスをより簡単に判別したいという思いから、アルゴリズムを選択するためのフィーチャセットについても幅広く調べています。ちなみに、このゲームのクラスは人間が識別するゲームのジャンルに何らかの形で対応すると私たちは想定しています(例えば、あるアルゴリズムはシューティングゲーム向きで、他のはパズルゲーム向きといったような具合です)。今のところ、人間によるジャンル分けに類似させるような十分なフィーチャは得られていませんが、一部の結果は上記の想定を裏付けています。特筆すべきは、ゲーム内でアバターが撃つことができるか、そして死ぬかという2つの特徴を見るだけで、それぞれのアルゴリズムがうまくプレイできるゲームを、4つのクラスに分類できることが分かったことです。


この決定木は、アバターが撃つことができるか、あるいは死ぬかのみを検索。

もちろん、まだまだ課題は山積みです。もっといいアルゴリズムを選択する方法が必要ですし、(自動的に?)フィーチャを構築できるようになることが最終的な方向かとも思っています。また、ゲームの途中でアルゴリズムを変更できるようになれば、さらに精度は上がるでしょう。ゲームの序盤と終盤では、適切なアルゴリズムが違う場合だってあるはずですからね。さらに、既存のアルゴリズムでは太刀打ちできないゲームが数多くあることも忘れてはいけません。