計算機科学実験及演習2ソフトウェア (Mario AI) 遺伝的アルゴリズムによる解法

Mario AI とは?

Mario AI とは、スーパーマリオブラザーズのステージを、あらかじめ動きがプログラムされたマリオを用いてクリアしていく競技会のことで、2009 ~ 2012 年の間行われていたものです。マリオを動作させるためのプログラムは、何らかのプログラミング言語で自分で設計することになっています。
自分が大学で所属しているコースでは、このプログラムを設計・動作させるためのソースコードが配布され、自分たちでマリオの動きをプログラムしていくという課題を行います。ソースコードについては、こちらからダウンロードすることも可能なようです。

マリオAIのプレイ画面。画像中のマリオが、自分で設計したプログラムに従って動きます

Mario AI の基本的な実装法

マリオの各個体は、アニメーションの原理と同じような原理で動作します。短い時間間隔ごとにフレームが区切られて、各フレームごとにマリオの次動作 (右に動く、ジャンプするなど) をプログラムにより決定します。
具体的には、true か false が格納される 6 要素の配列 (action という名前がついています) を「マリオの動作」とします。
配列の

  • 0 番目を true にすると左移動
  • 1 番目を true にすると右移動
  • 2 番目を true にするとしゃがむ
  • 3 番目を true にするとジャンプ
  • 4 番目を true にするとダッシュ & ファイヤ
  • 5 番目を true にすると上移動 (自分の環境では動作しませんでした)

となっていて、この配列の要素を適宜決めたのち返してあげると、次のフレームの行動が決定されることになります*1
下の画像は実際のプログラム中の「毎フレームの動きを決定する」部分です。action という配列の 1 番目のみを true にしているので、「毎フレームで右移動」をするマリオができあがります。目の前に落とし穴があってもジャンプはしませんし、敵がいても突進してしまうお茶目な子です。
「お茶目な子なんです!てへ」などと言ってこのプログラムを提出してしまうと留年しますので、何とかしてもう少し良いものを作らないといけません。

ただ右方向に進むだけのマリオ

シンプルなルールベースによる解法

まず考えられるのは、「目の前に落とし穴があったらジャンプする」「上に敵がいたらしゃがむ」などといった、特定の条件に対して特定の動きを割り当てるようなマリオを作ることです。
「1 マス前に障害物があるかどうか」「1 マス上、1 マス前に敵がいるかどうか」といった、周囲の環境情報を取得するための関数は、既にソースコードに用意されています。なので、実はこれを使ってあげるだけで、先ほどの右移動しかしないマリオよりもかなり良いものを作ることができます。このようなルール決めを、自分の周囲の各マスに対して行うことを考えます。

マリオの周囲 8 マスについて、障害物があるか・敵がいるかを調べ、適切な行動を割り当てる

マリオの周囲 8 マスについて、障害物や敵があるかどうかの組み合わせは、4^8 = 65536 通りあります。この 65536 通りの場合*2に対して、どのように動けばよいかを考えれば良いです。
さらに、前述の 6 種類の動き方の組み合わせを考えると、ナイーブには 2^6 = 64 通りあります。したがって、周囲 1 マスの情報を全て取得し、その情報に応じて行動するマリオは、全部で 65536 * 64 = 4194304 体存在することになります。これらを 1 体ずつ試してみて、指定されたコースをクリアできるマリオを見つけようという作戦です。

しかし、このプログラムをそのまま用いようとすると、終了までにかなり時間がかかってしまうおそれがあります。例えば、上の例ですと周囲 8 マスについて調べましたが、「周囲 8 マスだけでは足りない!」と思って、さらに 3 マス分追加で調べるとすると、なんと 268435456 体のマリオを作らなければいけなくなります。このように、周囲の情報を手に入れようとすればするだけ、指数的に手数が増えていってしまいます。

サンプルコードの遺伝的アルゴリズムによる解法

解の候補となるマリオを全て作って試す、ということが難しい場合でも、「さっき作ったマリオよりも改善された (と思われる) マリオを作り続ける」という方針を取った場合、調べるマリオの個体数が大きく減少することがあります。これを実現するための 1 つの方法として、「遺伝的アルゴリズム」というものがあります (遺伝的アルゴリズムの簡単な説明としては、このサイトが分かりやすいです) 。


各マリオは「どういった周囲の情報に対し、どのように行動するか」という対応付けを持っています。この対応付けは、マリオの各個体によって異なることから、「遺伝子」と呼ばれ、配列で実現できます。サンプルコードでも、(先ほどの解法とは少し異なりますが) 周囲の環境情報に行動を対応付ける解法を取っています。

サンプルコードの解法。周囲の環境情報を bit 列と見て 10 進数に変換し、その 10 進数から取るべき行動への対応付けを定める。

遺伝的アルゴリズムを用いると、例えば以下のようにしてコースをクリア可能なマリオを見つけることができます。

  1. まず、ランダムに 100 体ほどマリオを作る。この 100 体を「1 世代目」とする。
  2. 次に、現世代の 100 体それぞれにコースを走らせてみて、最も良い成績であった上位 2 体を選出する。
  3. 上位 2 体については、次世代に引き継ぐ。それ以外の個体については、以下の方法で遺伝子を「組み換え」する。
    1. 選択: そのまま次世代に引き継ぐ。
    2. 交叉: 個体を 2 つ選び、遺伝子の一部を交換して次世代の個体とする。
    3. 突然変異: 個体を 1 つ選び、ランダムに遺伝子を異なるものにする。
  4. 次世代を次の現世代とする。コースをクリアできる個体が見つかるまで、2. 3. 4. を繰り返す。見つかれば終了。

上位の数個体はそのまま次世代に引き継いでいることから、解は単調非減少となり、選択・交叉・突然変異により、条件を満たす解に近づいていく方法です。

サンプルコードの問題点

このようにすると無事解が求まるように思われますが、そのままサンプルコードを動かしても、うまく行きません。理由として、周囲の 1 マス単位でしか環境情報を取得していないため、情報の粒度が粗いから、というのがありそうです*3。また、シンプルに探索するマスを増加させてみたりしましたが、解の更新が低速になるだけで、あまり改善しませんでした。そこで、少し異なる方法を採用してみることにしました。

愚直解の構成

各フレームごとに取る行動は、action という 6 要素の true または false が入っている配列で表現しますが、これを 2 進数で表し、10 進数に変換することを考えます。

action の中身を 2 進数で表し、10 進数に変換する

すると、各フレームでの action は自然数で表されるので、マリオが 1 フレーム目から N フレーム目までで取る行動は、要素数 N の (0 から 63 までの) 数列で表現することができます。
すると、コースをクリアできるマリオの個体を探すという問題は、数列を探し当てる問題にすり替えることができるようになります。

次に、この数列の要素を全探索してみることを考えます。行動パターンは 2^6 = 64 通りですから、仮にフレーム数を 2000 とすると、64^2000 通りという膨大な数を全探索することになります。全探索により必ず解が見つかることは保証されますが、実験期間内にプログラムが終了せず、確実に留年します

愚直解の改善 (1)

そこで、先ほど見た「遺伝的アルゴリズム」で、効率よく解を探索することを考えます。先ほどは「周囲の環境情報→取るべき行動」の対応付けを遺伝子としましたが、今回は「何フレーム目か→取るべき行動」の対応付けを遺伝子とします。
これによる最大の違いは、全体的な問題を部分問題に落とし込むことで、解の逐次改善が可能となることです。
例えば、m 世代目の最優秀個体が 150 フレーム目まで順調にコースを進んでいて、その後すぐに落とし穴に落ちてゲームオーバーとなっていた場合を考えます。このとき、150 フレーム目までの行動はおおむね正しいと判断して、m + 1 世代目の全個体は、その最優秀個体の 150 フレーム目までと全く同じ行動を取るように初期設定してあげれば良いということになります*4
次に、続く 200 フレーム分の行動の改善を目指すとすると、遺伝的アルゴリズムの「交叉・突然変異」について、およそ 150 フレーム目 ~ 350 フレーム目のみで起こるとして良いです*5。このようにすると、まるで尺取り虫が進むように少しずつ解が改善されていき、解の 1 つを探し当てることができます。

愚直解を改善したプログラム

愚直解の改善 (2)

しかし、これだけではあまり高速化しません。さらに 2 つほどルールを加えてあげることを考えます。
まず 1 つ目のルールは、初期状態での動き方についてです。当初、初期状態ではランダムな動き方をするように設計していたため、同じところを行ったり来たりうろちょろし、そもそも難所にたどり着かないということがありました。これを受けて、初期状態で取れる動きは「右方向の移動・ジャンプ・およびこれらの組み合わせのみ」とします。このようにすることで、1 世代目で猪突猛進なマリオを構成し、その後少しずつ行動を改善していけるようになります。

猪突猛進に進む人

2 つ目のルールは、落とし穴のかわし方についてです。落とし穴に関しては飛び越えるの一択なのですが、これは右方向への移動とジャンプを常に行った状態にするという単調な行動です。一方で、飛び越し中はこれを行っていないと失速し、落とし穴に簡単に落ちてしまいます。この部分は遺伝的アルゴリズムを用いるまでもなく、ルールベースで行動を上書きしてあげることで、より解の探索が高速になります。

サンプルとの性能比較

サンプルのプログラムでは 20,000 世代ほど繰り返しても解が見つかりませんでした (やりすぎ) が、改善したプログラムでは 10 ~ 700 世代ほどで解が見つかりました。もっとちゃんとデータ取ればよかったかも……

*1:もちろん、右移動と左移動を同時に true するなどの無効な動きは存在します

*2:例えば、「周囲 8 マスに障害物も敵もない」という場合や、「1 マス前方に障害物があり、1 マス前方・1 マス上方に敵がいる」という場合があります

*3:例えば、0.8 マス先に敵がいる場合と、1.2 マス先に敵がいる場合では取る行動を変えた方が良いかもしれませんが、そのような調整はできません

*4:実際は、局所最適に陥っている可能性を考えて、もう 100 フレームほど戻ったところまでをコピーしています

*5:こちらでも、さらに 100 フレームほど戻ったところから交叉と突然変異を行っています