第3章 遺伝的アルゴリズムの応用

NPC動作アルゴリズムの自動生成

　GAを実際の問題解決に利用する実例として、コンピュータゲーム制作の過程において利用する事が可能である事を示します。アイデア自体は他の分野にも適用可能と考えられますので、ゲームに興味のない方は、何か置き換え可能な身近な問題を念頭に、読んで頂ければ幸いです。
　「アルゴリズム＋データ構造＝プログラム」の金科玉条の通り、プログラムとは突き詰めていえば、データ操作そのものと考えられます。ゲームプログラムの場合、操作対象となるデータは、画像、音楽、文章などをはじめ、ゲーム中に登場するキャラクタに関する攻撃力や当たり判定など多岐にわたります。ゲームプログラムに必要となるこのようなデータの多くは、普通、人間が作ります。例えば、画像は絵描きさんが、音楽は作曲家さんが、文章はシナリオライタさんが作ります。同じように、ゲーム中のキャラクタを表現するのに必要な攻撃力や当たり判定などの各種情報も、普通は人間が作っています。実際、こうしたデータ作成作業は、プログラミング作業と同程度かそれ以上に手間のかかる作業なのです。「あー、誰か代わりにやってくれへんかなあ……」と現場の人たちは、特に納期が近づくと、しばしば考えるのですが、なかなかそうもいきません。それじゃあ、ここは一発、人間の代わりにコンピュータに作業をお願いできないか考えてみましょう。例えば、ゲーム中の10人のキャラクタの攻撃力をバランス良く設定したいとします。値を埋める事自体は簡単で、決められた値の範囲で10個の値を用意すれば良いだけです。乱数を使えば簡単に値を埋められます。次に、実際にその値が設定された状態で、ゲームが面白く遊べるかどうかを検証し、問題があれば値の設定をやり直さなければなりません。「ん、この手順はどこかで……」どうやらGAが使えそうですね。ゲームプログラム本体をシミュレータとして用い、ゲームプログラムの動作状態を何らかの指標で評価する事が出来れば、GAを適用して最適な値のセットを得る事ができそうです。このように、ゲーム上で必要なデータの中には、GAで求められる可能性のあるものがあり、人間はより複雑でコンピュータにできない仕事に労力を割く事ができます。


Fig.25 コンピュータはかわいい女の子を判断できるか?

　データをGAで自動生成するとはいっても、画像、音楽、文章を実用に足るレベルで自動生成する事は困難です。何故なら、GAの適用の為には、評価されるべきデータを作成可能で、コンピュータが自動的に評価できるような明確な評価基準が必要になるからです。コンピュータに画像を解析させて、かわいい女の子の画像かそうでないか判断させようとしても、「かわいい」という概念を明示的にコンピュータに与える事ができなければならないのです。せいぜい、輪郭抽出後にメガネをかけていると判断できた場合は「かわいい」といえるのが限界ではないかと思います。(Fig.25参照)
　それでは実際に例を挙げて考えていく事にします。今回、対象とするゲーム上のデータは「ノンプレイヤーキャラクタ(以下、NPCと表記)動作アルゴリズム」です。正確には「NPC動作アルゴリズムを表現したデータ」になります。ゲーム中では、プレイヤーの操作するキャラクタ以外にも、コンピュータが操作を行うキャラクタ、NPCが登場します。ゲームが成立する為には、このNPCの存在がかかせません。NPCを上手く動かすアルゴリズムを如何に実装するかが、ゲーム性を大きく左右するともいえます。例えば、シューティングゲームと呼ばれるタイプのゲームでは、NPCとして多数の敵機が登場しますが、この敵機の動きや攻撃パターンが、ゲームが面白いかどうかを決める重要な要因になっています。現在、コンピュータゲームは様々なジャンル分けがされています。有名なインベーダゲームにはじまるシューティングゲーム、近年コンピュータゲームの社会的認知度を飛躍的に高めたFF7のようなロールプレイングゲーム、他にもテトリスなどのパズルゲーム、アクションゲームなどのジャンルがあります。こうしたジャンル分けを考える場合、主にゲームのシステムによって分類されているのですが、ゲームのシステムが違えば扱うデータも変わってきますし、NPCの果たす役割も変わってきます。そこで、ここでは特に、対戦型格闘ゲームと呼ばれるタイプのゲームにおけるNPC動作アルゴリズムを扱う事にします。


Fig.26 対戦型格闘ゲーム

　対戦型格闘ゲームのゲームシステムを要約すると、ほぼ同等の性質を持ったキャラクタが、１対１で戦い優劣を競う、というものです。格闘の名が示す通り、格闘技の試合をそのままゲームにしたものと考えていただければ良いでしょう。ゲームシステム上、重要な状態を表す値の1つが、キャラクタの残り体力（Fig.26、画面上部左右の横棒状の表示）です。通常、ゲーム開始時の両者の体力は同じ量ですが、相手の攻撃を受ける事で減少してしまいます。このゲームの目的は、闘いに勝つ事ですから、プレイヤーは一方のキャラクタを操作し、もう一方のキャラクタを倒す事を目指します。具体的には、相手の攻撃を受けないように、相手を攻撃する操作を行い

のいずれかであれば、目的達成すなわち「勝ち」となります。このタイプのゲームでは、2人のプレイヤーが対戦する場合と、動作アルゴリズムに基づいてコンピュータの操作するキャラクタと1人のプレイヤーが対戦する場合がありますが、ここでは、後者の場合における、コンピュータが操作するキャラクタの動作アルゴリズムを自動生成する事について考えようというわけです。


Fig.27 NPC動作アルゴリズムのモデル化

　まず、対戦型格闘ゲームにおけるNPC動作アルゴリズムを、どのように捉えれば良いか考える事にします。このタイプのゲームにおいては、NPCもプレイヤー・キャラクタと同様の動作を行いますから、人間のプレイヤーがどの様に状況を判断して操作を行うのかを参考にします。ゲーム内で操作によって行える動作は、数種類の攻撃、移動など限られています。人間のプレイヤーは、可能な選択肢の中から、状況によって最適なものを選ぶわけですが、ここでいう状況とは、次のようなものから表現されると考えらます。

例えば、敵キャラクタが何らかの理由で無防備な状態であれば、チャンスと見て攻撃するでしょう。また、残時間が少なく、敵キャラクタの残体力の方が多い場合、一発逆転の大技をねらうでしょう。こうした状況の各要素、状況変数を参考にして、どういった操作、キャラクタの動作を行うか決める事が、NPC動作アルゴリズムに要求される能力といえそうです。これは倒立振子の例と同様に、NPC動作アルゴリズムが状況(状況変数群)を入力、操作を出力とする関数の形式で表現出来る事を示しています。(Fig.27参照)
　NPC動作アルゴリズムは、書き下された手順、つまりプログラムコードとして実装される場合もありますが、そうした実装形態を取った場合、

といった問題があります。そこで、アルゴリズムをデータ列で表現し、安全で扱い易い実装形態を目指す事にします。
　ゲームの状況を規定する各種状況変数について、詳細な検討を加えます。まず、敵キャラクタの動作状態などの状況変数は、定義された数個の値しか取りません。例えば、キャラクタの動作状態では、移動中=1、攻撃動作中=2、ジャンプ中=3と定義されていれば、変数の値は1、2、3のいずれかの値しかとりません。次に、コンピュータゲーム上で、整数で表現される敵キャラクタとの水平距離などの状況変数も、倒立振子の例で行ったように、区間分割で表現すれば、やはり定義された数個の値しか取りません。例えば、敵キャラクタとの水平距離では、自分の攻撃の当たる距離内と、それより遠い距離では、明らかに違う操作を行うべきだと考えられますから、その距離を境界にして区間分割を行えばよいと考えられます。つまり、攻撃の当たる距離であれば、実際の距離が1でも2でも同じとみなせるわけです。こう考えると、各種状況変数は、それぞれ有限個の離散値で表現可能になります。
　一方、プレイヤーが選択可能な操作も、キャラクタの動作自体が予め決められたバリエーションしかとらない事から、状況変数と同じように、有限個の離散値しかとりません。
　このように考えれば、状況(状況変数群)を入力、操作を出力とする関数で表現されるNPC動作アルゴリズムは、全状況変数によって張られる空間、状態空間上で、各状況変数の区間分割によっての得られる各領域に、操作を離散値表現した値をマッピングしたもので表現できる事になります。この表現方法はFig.23と同じ手法ですから、NPC動作アルゴリズムは多次元配列で表現できる事になります。各状況変数によっては、正の領域しか持たないものや、負の領域に関しては正の領域の反転で良いものも考えられますから、多次元配列とはいっても、かなり大きさをコンパクトに抑えられる事が期待できます。
　因みに、ここでは、NPC動作アルゴリズムの多次元配列による表現を提案していますが、対戦型格闘ゲームをはじめ多くのゲームにおいて、プログラムがリアルタイムに動作する事が求められる為、区間分割の場合分けの後はテーブル参照で済むこの表現は、動作速度を保証し易い点で優れています。各種演算を大量に含むような表現方法は、スペックに比べて高速な動作を要求されるコンピュータゲームの分野においては、かなり閾値が高く感じられるのです。コンピュータゲームにおける動作速度は、他の分野のソフトウェアに比べて重要度が高くなる傾向があります。この為、それを考慮したモデルを作成する事が必要です。
　NPC動作アルゴリズムを多次元配列で表現可能という結論を基に、この多次元配列を染色体として、GAによって最適なNPC動作アルゴリズムを獲得する事を考えます。染色体構造が決まったので、次はその評価方法を考えてみます。


Fig.28 NPC動作アルゴリズムとゲーム本体のプログラムの関係

　まず最初に、NPC動作アルゴリズムとゲーム本体のプログラムの関係について整理する事にしましょう。プレイヤーとNPCが闘う場合、以下の通りです。(Fig.28参照)

  1. プレイヤーの操作（動作選択）とNPC動作アルゴリズムの動作選択が発生する。

  2. 選択された動作は、ゲーム本体のプログラム内部に新しい状況を作り出す。

  3. 新しい状況に応じて、再び、プレイヤーとＮＰＣの動作選択が行われる。 

  4. 勝敗が判定されるまで、この繰り返しによってゲームの処理は進む事になる。

　ここで、NPC動作アルゴリズムの目的は、ゲームの枠組み内での十分な強さによって、プレイヤーの相手を務める事になります。また、不自然な動きが目立つと、プレイヤーに対して心理的なストレスを与える場合が多いので、極力、人間が操作している様に感じさせるアルゴリズムである事が求められます。この評価基準について、実際にはかなりの複雑さを伴う事になります。例えば、不自然な動きを定式化し、評価方法に加える事は極めて難しいでしょう。そこで、評価方法を単純化する為、プレイヤーがゲームを遊んで上達した結果、非効率な不自然な動きは淘汰されているだろうと考え、同様に、十分に強いNPC動作アルゴリズムは、自然な動きを行うだろうと考える事にします。したがってここでは、強いNPC動作アルゴリズムを評価する方法を考えます。
　強いNPC動作アルゴリズムを相対的に評価する方法は至極簡単です。2つのNPC動作アルゴリズムの優劣を付けたければ、実際に戦わせれば評価できます。この評価を行うには、ゲームプログラムをそのまま流用して利用する事が可能です。つまり、Fig.28のプレイヤーの部分をNPC動作アルゴリズムに差し替えた状態で、先ほどの1〜4の手順を踏み、結果として勝った方が優秀だとみなすわけです。また、特定のグループ内で順列が必要なら、リーグ戦によるポイント計算で決める事が可能でしょう。したがって、GAにおける集団内部で、個体同士のリーグ戦を行い、獲得したポイントに応じて順位付けを行えばよいのです。例えば、総当たり戦だと評価時間がかかるので、前の世代の上位陣と闘うなどとし、勝ち星のみをポイントとして計算するなどと考える事ができます。
　こうして、染色体の順列付け、世代交代を繰り返す事で、優秀な染色体の獲得が可能と考えるのですが、1つ問題が残ります。先ほど述べた評価方法は、絶対的な指標ではなく、集団内での相対的な地位を得るものでしかありません。確かに、世代が進むことで、優秀なものが生き残り、より勝つ事が難しくなっていく為、集団全体の絶対的な能力が向上していくと考えられます。しかし、全勝する個体が現れたとしても、その個体が本当にどれだけ優秀なのかが分からないのです。つまり、1世代目の集団における全勝と100世代目の集団における全勝では、絶対的な強さという意味で同じではないのです。GAは、漸近的に良い近似解を真の解を求めようとする枠組みです。したがって、性能的に十分な近似解を得られた時点で操作を終了しなければ、無限ループに陥ってしまいます。通常、評価が絶対的な値で行われる場合、操作を打ち切る判断は容易で、実用上問題ないと考えられる評価値を持つものが現れた段階で終了すれば良いのですが、今回のように、評価を相対的に行わざるを得ない場合には、そうした終了条件の設定が難しくなってしまうのです。
　何らかの形でGAの操作を終了する条件を設定しなければなりませんが、最も単純な判断方法としては、適当な世代毎に優秀なNPC動作アルゴリズムを取り出し、実際に人間がテストする事が考えられます。しかし、これでは自動生成による作業の効率化といった観点からは好ましいとはいえないので、次の様なアイデアを紹介しておきます。
　GAにおいて、各世代の探索空間上での分布を考えてみます。山登りの話を思い出して下さい。優秀な解、すなわち山は複数存在する可能性がありますが、世代が進めば、生き残る優秀な染色体の分布はそれらの山の近傍に集中すると考えられます。したがって、十分な世代を経た後、生き残る優秀な個体の集団は、極めて似通った構造を持つ複数の染色体のグループから構成されると予測されます。つまり、いくつかの山に登っている個体だけが優秀な評価を得られるので、逆に登っている山によってグループ分けが可能とみるわけです。こう考えると、この染色体によるグループ分けを監視し、複数グループの寡占状態が何世代にもわたって続くようであれば、十分優秀な染色体が得られたものとして、GAの操作を終了する事ができます。染色体の似通り具合を調べる方法は、何通りか考えられますが、例えば、染色体の各遺伝子座のうち何%が同じであったかで調べる事ができます。80%以上が同じなら同一グループとみなすなどと考え、まず、最も優秀な個体のグループを取り出し、次に、残ったものの中で最も優秀な個体のグループを取り出し、と調べていけば、グループに分割する事が可能です。
　また別のアイデアとして、強すぎないNPC動作アルゴリズムを得る為の終了条件を考えてみましょう。先ほどの方法だと、群雄割拠の状態から、生き残ったグループが凌ぎを削る状態になったかどうかを見るので、かなり強いNPC動作アルゴリズムを得られると期待できます。しかし、勝ち目のない相手と試合をして面白いと感じられる人は少ないので、弱いプレイヤーの相手をできるNPC動作アルゴリズムも必要になります。そこで、ゲームのヘタクソなプレイヤー(例えば、私)を用意し、実際にゲームをプレイさせます。この時、プレイヤーの操作とその時の状況を、履歴として残すようにします。この履歴を基に、NPC動作アルゴリズムを表現する多次元配列の値を埋めれば、ヘタクソなプレイヤーのクローンが作れるわけです。ここでGAの終了条件として、最優秀個体がプレイヤーのクローンに勝てるようになったら終了とすれば、ヘタクソなプレイヤーより少し強いNPC動作アルゴリズムを得る事が可能になると考える事ができます。

遺伝的アルゴリズム+ニューラルネットワーク

　恐らくGAよりも良く知られており、GAと同様の問題解決に用いられる手法として、ニューラルネットワーク(Neural Networks：以下、本文中では"NN"と表記)があります。NNと一口にいっても、さまざまなバリエーションがありますが、最も良く知られているのがパーセプトロン(Perceptron)型NN+誤差逆伝播学習法(Back-Propagation：以下、本文中では"BP法"と表記)のモデルです。
　実はNNとは、いわばハードウェアの事を指しており、問題解決の為にはNN上で適用するアルゴリズムが別途必要になります。BP法はパーセプトロン型NN上で最も一般的に使われているアルゴリズムですが、その中身は既に述べた山登り法そのものなのです。したがってBP法にも、たくさん山があるような状況下で、小さい山に登って満足してしまう癖があります。実際、BP法のこの癖を直す為の研究が、多く試みられています。


Fig.29 3層からなるパーセプトロン型NN

　BP法にそうした問題がある一方、3層からなるパーセプトロン型NN(Fig.29参照)には、大変有効な性質がある事が知られています。その性質とは、3層式パーセプトロン型NNでは、中間層を十分にとれば、その表現力の範囲内で、あらゆる関数を近似可能であるというものです。
　倒立振子や対戦型格闘ゲームの例でみてきたように、GAの適用範囲の中に、関数を染色体で表現し、最適な関数を探索するタイプの問題があります。しかし、ここまでの例で行ってきた、区間分割による関数の近似は、複雑な構造の関数を近似するのに向いているとはいえません。複雑な構造の関数を近似しようとすると、どうしても区間の分割数を増やす事になり、染色体のバリエーションが大きくなってしまいます。染色体のバリエーションが大きくなってしまうと、GAにおける探索空間が大きくなってしまうので、解を見つける為にかかる時間が大きくなってしまうのです。
　そこで、3層式パーセプトロン型NNの関数近似能力と、GAの最適解探索能力を合体させれば、かなり強力なモデルになるのではないかというアイデアが生まれてきました。この手法を「遺伝的山登り法(Genetic hill-climber：以下、本文中では"GHC法"と表記)」と呼びます。
　NNは、各ノードを結ぶ枝の太さによって挙動が決定付けられます。GHC法では、この枝の太さの集合を染色体とし、GAを適用するわけです。枝の太さは実数範囲ですから、染色体は実数の配列で表現される事になります。
　BP法を理解しようとすると、それなりに数学の知識が必要なので、NNを使ってみようとしたけれども、BP法でつまずいた方もたくさんおられると思います。しかし、NNの動作原理自体は、それほど難しくありません。そこで、3層式パーセプトロン型NN+GHC法というモデルは、実際に多くの人が利用し易い選択肢だと思います。

人工生命

　本特集では、GAによる問題解決とその実装に焦点を当ててきました。しかし、GA周辺で最も話題性があり、一般の人たちの興味を引くのは、なんといっても「人工生命(Artificial Life：以下、本文中では"AL"と表記)」でしょう。
　GAが、生物の進化の過程と遺伝子の関係にヒントを得て考えられたのは、既に述べた通りですが、これを逆に利用して、コンピュータ上で生物を規定し、その種が進化していく過程をシミュレーションしようとしたのがALです。


Fig.30 遺伝情報の発現

　例えば、染色体をビット列とし、この染色体で個体の形質が決定付けられるとします。各遺伝子座に、角がある/ない、体毛が長い/短い、といった具合に意味付けを行い、GAを適用するとします。(Fig.30参照)
　この時、個体の評価方法を次のように考えます。まず、その生物集団の住んでいる環境を設定できるようにします。餌が豊富にあるかないか、暑いか寒いか、などを設定できるようにします。そうして設定した環境下で、例えば、餌をめぐって争いが起き易いので、角があった方が生存に有利などと考え、個体のそれぞれの形質が、どの程度生存に有利かを評価していきます。
　こうしてGAを生物進化シミュレータとして動作させると、世代を経ると、有利な形質を持つ個体が増加していく事が観察できます。途中で環境を変化させると、有利な形質が変化するので、また新しい形質を持つ個体のグループが台頭してきます。
　ALは、基本的にGAによる結果を求める事を目的とはしていません。プロセスの過程にこそ着目点が置かれています。ALの研究を行っている人にはさまざまな人がいます。純粋にALが楽しいので取り組んでいる人もいれば、GAの可能性を検証する為に取り組んでいる人もいます。ALをアートにしている人もいます。そう考えると不思議な分野ですが、その不思議さがALの魅力なのかも知れません。

さいごに

　GAについて、かなり大雑把な感は否めませんが、一通り筆を進めてまいりました。GAをまったく知らなかった方が、本稿によって興味を持たれて、GAの勉強をはじめるきっかけになれば良いと思います。
　また、まだまだ距離のある研究の現場と開発の現場ですが、それが少しでも近づく事を願って、本特集の締めとさせて頂きます。