［CEDEC 2008＃08］生き物を相手にするようなゲームを作る〜遺伝的アルゴリズム

進化を利用する遺伝的アルゴリズム

セッションが始まる前に長い列ができた

　CEDEC 2008では，2日目から「AI Day」と題される，AIをテーマにした一連のセッションが設定されている。AIはゲームに欠かせない要素であるためか，いずれのセッションも大盛況だった。今回はそのAI Dayの中から「遺伝的アルゴリズム」に関するセッションを紹介しつつ，ゲームとAIの関係を見ていこう。

　セッションを担当したのは，ムームー取締役社長の森川幸人氏で，読者の中には同氏の名前を知っている人も多いだろう。カリスマ番組とされる「ウゴウゴルーガ」に携わったCGクリエイターであり，オリジナリティあふれるゲームを作り続けているゲーム制作者でもあるからだ。
　そんな森川氏のセッションということもあり，会場に入りきれないほど参加者が集まっていた。筆者もなんとか潜り込めたという状況で，写真などを撮る余裕がなく，そのためここでは，会場で配付された資料を基に紹介を進めていきたい。
　ところでこのセッション，「ゲームとAIはホントに相性がいいのか？」と題されており，前半は森川氏が手がけたゲームに使用された遺伝的アルゴリズムの解説，そして後半はタイトル通り「AIに適したゲームはどのようなゲームなのか」，といった話がQ&A形式で行われた。本稿ではその中から“遺伝的アルゴリズム”（Genetic Algorithm，以降GA）を重点的に紹介していこう。

GAは生物進化を真似たアルゴリズムで，優秀な親の性質を受け継ぐ子を繰り返し作ることで，ある種の方向に特化したプログラムを作成する

リンゴを上手に集めたキャラクターから2個体を選び出し親にする。その両親の遺伝子を受け継ぐ子を作成して2世代目を作る

　GAというのは，生物の進化を真似たアルゴリズムの一種だ。森川氏によると1975年頃には研究が始まっていたというから，AIのアルゴリズムとしては古い部類に入るだろう。進化を真似るアルゴリズムはいくつかあるのだが，遺伝的アルゴリズムはその中でも比較的シンプルで作りやすい部類に属する。だが，ゲームへの応用は決して盛んとはいえないようだ。

　森川氏は，キャラクターがリンゴを集めるという分かりやすいゲームを例に挙げた。フィールドに落ちているリンゴを複数のキャラクターが拾い集め，一定の時間内に多く拾ったキャラクターほど「優秀」――GA風に言えばより適応している個体とする。リンゴを集めさせたあとでキャラクターに順位を付け，優秀な二つのキャラクターを「両親」として選び，その性質を表す「遺伝子」を混ぜ合わせて次の世代（子）を作る。また，あまり得点が高くなかったキャラクターは削除する。そしてまた集団でリンゴを集めさせる……というゲームを繰り返していく。何世代かが経過すると，リンゴを効率的に集める能力に秀でたキャラクターが勝手に生まれてくる，というシカケだ。

　では遺伝子とはどのようなものなのだろうか。GAでは，普通は1本の2進数の列を使う。ご存じのように生物は複数の対になった遺伝子を持つが「そういう遺伝子を使う研究も行われているが，今のところあまり使われていない」（森川氏）とのこと。
　両親の遺伝子を混ぜ合わせて子を作る方法としては，2進数の列を適当な場所で切って入れ替える「交叉」が使われる。

2点交叉の例。遺伝子を交叉ポイントで切って入れ替え子を作る。交叉するポイントの数（例は2点）や交叉させる場所は恣意的に決めるしかない

　交叉ポイントの数や，交叉させる場所は最終的な結果に大きな違いをもたらすのだが，「ルールはない」（森川氏）そうだ。ただ，交叉ポイントを多くすれば，変化がよりダイナミックになるが，交叉ポイントをやたらに増やせばいいかといえば，そういうわけでもない。
　「動的に交叉ポイントを変える方法もあるが収束しないことが分かっている」（森川氏）ため，現場で決めるしかないのだという。このあたりがGAの難しさだろう。
　もう一つ，GAの重要な要素が「突然変異」である。ある確率でランダムに遺伝子のビットを反転させ突然変異を起こす必要があるのだ。突然変異の必要性についてはあとで触れることにしよう。

GAでは突然変異も重要な要素。当然変異を加えないと進化がうまく進まない

もっとも簡単な遺伝子。飛行機を構成する要素に重みを付けてビット列にする

　ところで，そもそも遺伝子はどうやって作ればいいのだろうか？　これにもいろいろな方法があるのだが，森川氏が示した最も簡単な例は上のスライド（右）のようなものだ。
　この飛行機の例では，羽の形やエンジンといった各パーツに重みを付けてビット列にする。この遺伝子を使って進化させて「よりよく飛ぶ飛行機を作る」といったことが出来るのだ。

GAは職人技が必要なAI技法

　具体的な例として，初代プレイステーションのゲーム「アストロノーカ」のAIに，GAを利用したと森川氏は続けた。

森川氏が手がけた「アストロノーカ」。GAとプレイヤーが対決するゲームだ

　プレイしたことがある読者も多いかもしれないが簡単に内容を紹介しておこう。プレイヤーは宇宙の農家（アストロノーカ）になり，毎日おいしくて栄養豊富な野菜を育てているのだが，宇宙の害獣「バブー」が農場にやってきて野菜を荒らすのが悩みの種。プレイヤーは農場にトラップを作って作物をバブーから守らなければならない，というのがゲームの骨子。バブーはトラップにチャレンジするたびにそれをクリアする能力を付けていくのだが，その進化にGAを利用しているという。

　アストロノーカを作るに当たり，もっとも苦労した点として森川氏が繰り返していたのが「パラメータの決め方」である。森川氏が触れていた難しさの一つに「初期収束」の問題がある。

アストロノーカにおける最終に的なGAパラメータ。このパラメータを決めるのにかなり苦労したという

　初期収束というのは早い段階で進化が止まってしまう現象のことだ。他より優れたバブーがたまたま生まれ，わずか数世代でそれと同じ優れたバブーだらけになってしまい，それ以上の進化が止まるというものだが，これではゲームとしてあまり面白くない。
　初期収束でどういうことが起きているのか筆者なりに説明してみよう。GAではより適応したもの（優れたものと言い換えてもよい）が生き残るのが原則だが，優れているといっても，あるトラップだけにめっぽう強いとか，すべてのトラップに無難に対応できるなどいろいろなパターンがあり得る。適応の度合いはバブーの敵であるプレイヤーによっても変わってくるだろう。
　適応度を土地の高低に例えると，鋭いピークやゆるやかな丘がある地形ができあがる（これを適応地形などという）。最も適応した個体は地形の中で最も高い山に到達したものだが，たまたま周囲より少し高い程度の，手近な丘に到達してしまう個体もいる。丘の頂上からは，どの方向に進化しても丘より少し低いため，結果的に丘の上に安住してしまい，何世代後かには丘に個体が集まってしまうわけだ。これが初期収束である。

　こうした現象を避けるには，評価関数（優れているかどうかを決める関数）を変えたり，交叉ポイントを変えたりする方法もあるが，より重要な決め手が突然変異だ。突然変異によって，妙なところで安住してハマってしまったGAを，より適応度の高い方向へと飛躍させられるからで，先にGAで突然変異が重要と述べたのは，こういった理由による。
　GAのパラメータの決め方，評価関数の調整などは非常に難しく，デバッグも大変なのだという。「何が原因でトラブルを起こしているのか，パラメータを全部ダンプして追いかけた」（森川氏）とのことで，その場その場での勘や経験が必要なことから，「GAは職人芸的アルゴリズム」だとも述べていた。こうした難しさが，簡単なようでいてゲームに応用されづらい理由の一つになっているのだろう。

　本稿でGAに興味を持った方はアストロノーカをプレイしてみることをお勧めしたい。アストロノーカはストレートな形でGAを応用したゲームであり，現在でもPLAYSTATION Storeから入手できるとのことなので，環境がある人はチェックして欲しい。