2010年12月01日

Mario AI Competition 解説

本解説は、 IEEE で実施された学術AIコンピティション Mari AI Competition とその優勝者のアルゴリズムの解説です。

昨年から、今年初めに話題になったMari AI Competition の優勝者のAI

IT Media
 http://gamez.itmedia.co.jp/games/articles/0908/18/news086.html

ですが、ようやく最近、技術解説
 http://julian.togelius.com/mariocompetition2009/GIC2009Competition.pdf
(1-15 ルール解説 16ページ以降、参加者の書くAIの技術解説。Robin 氏のものは16ページから)

を読んだので解説します。
このコンピティションは IEEE の 2つの SIG が合同で企画したものです。

IEEE SIG-Consumer Electronics Socity と
IEEE SIG-CIG (Computational Intelligence and games)
が開催した

Games Inovation Conference
 http://ice-gic.ieee-cesoc.org/2010/index.php

において実施されました。

Mario AI Competition
 http://julian.togelius.com/mariocompetition2009/

Infinite Mario Bros というフリーのスーパーマリオライクなゲームの
ソースを公開して(一部は隠蔽してあるはず)、AI用の環境認識インターフェース関数を
用意してあり、AIからは、アクションを定義する関数でアクションをゲーム側に返すことが出来ます。

AI である意義は何処に?と疑問に思われるかもしれませんが、
この競技では、マップは全て自動生成なので、単一の思考で、
自動生成された40マップをクリアすることが要求されており、
そこには、優秀なAIのアルゴリズムが必要とされます。
(上記 PDF 1−15ページ)

その優勝者は、Rockstar games (GTAとかRDR) のプログラマ Robin Baumgarden さん

Robin Baumagarden さんの GameAIdev におけるインタビュー
 http://aigamedev.com/open/interviews/mario-ai/

で、A* アルゴリズムを使った制御です。

以下は、
 http://julian.togelius.com/mariocompetition2009/GIC2009Competition.pdf
16-30ページの簡単なまとめです。

[概要] 

A* のゴールは画面右端の地面の上です。このゴールに対して、マリオの軌道をA* 検索でパス・プランニングします。
(A* アルゴリズムはヒューリスティックな検索法で、いろいろなAIの教科書やWEBを参照するとよいです)

スクロールすると、当然、ゴールが更新されますので、毎フレーム、パスプランニングをくり返し思考します。
つまり、プランしておいて、最初のアクションを行うと、またパス・プランニングし直します。

簡単に1フレームの中の思考を解説します。
※24FPS(一秒間に24回)センサー情報をアップデートして思考します。


(1) まず、周囲の各ノードに現在の環境からのコストを載せます。
    例えば、敵や通行不能なオブジェクトがあるノードはコストが高くなります。

(2) 周囲の各ノードにどのようなアクションを取れば行けるかを計算します。
     その中で最適なノードに移った場合を考えます。

    そこから、周囲のノードを同じように評価しますが、この時、
    まだ、ゲームは進行していないわけですから、
    敵の動きは、物理的に予測して、
   予測したゲーム状態をもとにノードを評価します。

  例えば、自分がジャンプした時間分、敵も動くわけですから、
  敵が動いた状態を加味して、ノードにコストを加算します。

(3) これをくり返しことで、経路を計算します。


動画の中にある、赤いたくさんの曲線は、A* 検索の結果、
候補として、作成された軌道です。

*  *  *

コンピティションの主催者は、マシンラーニングなどを期待したようですが、
ゲームAI思考的な方法が最もよいスコアを取りましたが、
もともとこれは、競技よりも、どのようなAIの成果があるかが問題なので、
上記の資料の他のAIのアプローチも見逃せませんね。

今年も開催されます。
 http://www.marioai.org/

posted by miyayou at 23:48| Comment(0) | TrackBack(0) | 日記
この記事へのコメント
コメントを書く
お名前: [必須入力]

メールアドレス: [必須入力]

ホームページアドレス: [必須入力]

コメント: [必須入力]

この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/41933731
※言及リンクのないトラックバックは受信されません。

この記事へのトラックバック