IGDA ゲームAI連続セミナー「ゲームAIを読み解く」第四回

IGDA主催の、ゲームAI連続セミナー「ゲームAIを読み解く」第四回「Halo2におけるHFSM(階層型有限状態マシン)」に参加してきました。

場所は、前回と同じ東京大学で行われました。

全体の構成は、二部構成になっており、第一部はフロムソフトウェアの三宅陽一郎さんによる技術解説、第二部はグループ討論という形になっていました。

第一部は、四章構成になっていて、

第一章 FSM
第二章 Halo
第三章 Halo2
第四章発展

といった流れで、(Halo/Halo2で用いられているAI技術としての)FSMの紹介が行われました。

FSMとは、Finite State Machineを略したもので、日本語で用いられる場合、「有限状態マシン」等とよばれます。
有限状態マシンとは、「有限個の状態が、遷移条件によって結ばれているシステム」で、AI技術だけに用いられる技術ではなく、状態と遷移条件だけで成り立つシステムですから、プログラムを打っていればどこにでも出てくるような技術(概念)だったりします。

HFSMとは、Hierarchical Finite State Machineを略したもので、今回のセミナーのタイトルにあるように「階層型有限状態マシン」とよばれます。
階層型有限状態マシンは、普通の(?)有限状態マシンの一つの状態の中に、(小さな)有限状態マシンがあり、階層構造を作っているような状態になります。

...プログラマの人は、関数を使って、また新たな関数を作るようなイメージで捉えてしまえばよいかと思います

状態を階層化することで、状態と状態の相関関係が把握しやすくなり、階層化されている状態を一つの大きな状態として捕らえることで、より抽象的に状態を捕らえることが出来ることになります。

階層型有限状態マシンの一つの形式として、DAG(有効非環)形式のHFSMというものがあります。

DAG形式とは、一方向にノードが伸びて、ノードが環を為すことがないグラフ構造で、例えば、ルートの下には、「攻撃」と「防御」といった状態を示す階層、「防御」の下には、「盾で防御」/「剣で受け流し」/「一歩下がる」といったより具体的な行動の種別の階層があり、同じように「攻撃」の下には、「魔法」/「剣」といった階層があるような、グラフ構造を示します。
このグラフがキャラクタの振る舞いを決定する場合には、グラフを「振る舞いツリー」とよびます。

(ここまでが、FSMの基礎解説)

Halo2では、前作の複雑な状況に対応するように作っていった結果、個体とAIの関連性が強くなりすぎてしまいスケーラビリティをなくしてしまったという反省から、スケーラブルAI(柔軟な拡張性を持つAI)が目指され、その仕組みとしてDGA形式のHFSMが採用されていたようです。
Halo2でのHFSMの話は、そのうちIGDAで公開される(と思う)セミナー資料と、GDCで発表されたHalo2の資料の方を参考にしていただいたほうが良さそうなので、参考資料だけ挙げておきます。

参考資料:
(1) Damian Isla (2005), Managing Complexity in the Halo2 AI,Game Developer's Conference Proceedings.
　 (DOC) https://www.cmpevents.com/Sessions/GD/HandlingComplexityInTheHalo2AI.doc
(2) Damian Isla (2005), “Dude, where’s my Warthog? From Pathfinding to General Spatial Competence".
(PPT) http://www.aiide.org/aiide2005/talks/isla.ppt

グループワークでは、メタルギアソリッドをお題にして、実際に状態遷移図を書いてみようといったことが行われました。
私のグループでは、索敵時のFSMとして、「巡回」という状態を中心として、「ロッカーを発見する」と「調べる」、「仲間を発見する」と「無駄話」を始める、「調べる」間は、物音がすると「調べる」から「音のほうへ向かう」状態に遷移するが、「無駄話」の間は物音がしても気付かず、一定時間経過後に「巡回」状態に戻るか、「プレイヤー発見」によって「通信機器まで移動」といった状態になるとしました。

第三回のグループワークと比較して、スムーズにグループワークが進行していったと思います。

グループワークでやるべきことがはっきりしていた点と、三宅さんの技術解説の最後に、どのように状態遷移図を作っていくのかという解説があった点から、参加者はやりやすかったんじゃないかと思います。

ただ、与えられた時間で「全体FSM」「索敵FSM」「追跡FSM」「警戒FSM」「FSM全体図詳細」を書き上げるのには時間が短すぎだと思いました。
一時間のグループワークで５つのFSM書くのには、せいぜい一枚あたり12分しか時間が取れないわけですし、運営スタッフの方もその辺りは把握していて、できる所まで進めてくれれば良いって心構えで居たんだと思いますが、グループワークが終わった後に空欄が大きく残ってしまうのは、参加者に「何も出来なかった」って印象を与えてしまうんじゃないかと思いました。

グループワーク後に、コーディネーターの長久さんから、AI技術以外でのFSMの解説がありました。
箇条書きや、フローチャートで仕様を伝えた場合の欠点から、FSMを導入した場合にはどのようになるのかといった話をしていただきました。

こうやってAIセミナーの一環として、取り上げられるとFSMってAI用途の技術なんだと誤解されがちですが、そんなことは全然無くて、状態遷移を書き起こすための手法(概念)の一つにしか過ぎないんですよね。

私も以前に、企画職の方から中途半端なフローチャートを渡されたり、箇条書きで仕様を伝えられたりしましたが、その度に「状態遷移図ぐらい描いてくれないかなぁ...」なんてことを思っていたものです。
そんなに厳密なものを期待しているわけじゃないし、企画職の方達にも有用なツールだと思うんで、長久さんのプレゼン(?)には非常に好感が持てました。

一度、社内でFSMについての勉強会でもやってみようかな...