「戦略ゲームAI解体新書」読書会ログ 6 章

読書会

ようやく６章。一応２部までで区切りにするつもりなので、もしかすると最終回。

第６章 学習し、成長する人工知能

「キャラクターのコミュニティを育成する」ジャンルを題材にする章らしい。

  • プレイヤーがチームのリーダーやマネージャーとなって、AIキャラクターたちからなる集団を管理し、能力を向上させることを意味する
    • スポーツチームの監督となり優勝へ導く、歴史上の武将となって土地を治める
    • 指揮官ではなく全体をマネージメントする
  • 名前のないユニットではなく、一体一体のキャラクターへの思い入れがある
  • キャラクターにも個性があり、集団全体にも思い入れがある
  • このようなキャラクター性を利用したゲームの人工知能は、個性を出し、演技をする必要がある
  • 遺伝的アルゴリズム
    • 集団を進化させるために使う
  • ニューラルネットワーク
    • 個体を進化させるために使う

6.1 複数の役割のエージェントを組み合わせる

マルチエージェント技術

  • 以下でも登場
    • 2.5.7 決戦、ユニット間のコミュニケーション
    • 4.2 チームの階層化
  • それぞれのキャラクターに能力の個性を持たせて連携させる
  • エージェント同士のコミュニーケーション
    • エージェント間言語 (ACL) を使う (2.5.7 では「エージェントコミュニケーションランゲージ」)
    • オブジェクト間のシンプルなメッセージによって済ます (ゲームではこちらが使われる)
  • 連携の方法
    • ユーザーの指令によって全体のメンバーが連携する
    • キャラクター連携時にはリダーによる全体の制御方法をとる
    • キャラクター同士がコミュニケーションして連携する
    • これらの選択や組み合わせ

6.2 遺伝的アルゴリズムによるバランス調整

6.2.1 タワーディフェンス型ゲーム

タワーディフェンス型ゲーム

  • 経路に沿ってくる敵を経路の周辺に自動攻撃タワーを置くことで防衛
  • ゲームが始まると砲台はオートで動く
  • 敵がくる経路は決まっているため、経路上のどこにきたときに砲台がどのように動くか決めておく
  • 多くの場合、タワーを置くだけで攻撃範囲などは自動決定
  • 重要なのは「カバレッジ」
  • 経路の中でどれぐらいの領域をキャラクターの攻撃がカバーできているか

タワーディフェンス型ゲームの難しい点

  • ゲームデザインの検証が難しい
  • 具体的には、クリア可能かどうか、どの程度の難易度か
  • 人間での検証ではなく、人工知能の自動プレイで検証

6.2.2 遺伝的アルゴリズム (Genetic Algorithm, GA)

シティコンクエストの事例

  • タワーディフェンス型のゲームだが、タワーから構築されるシティ(街)同士が戦闘機を撃ち合う
  • 配置の種類を人間が調べ尽くすことは不可能なため「遺伝的アルゴリズム」を使う
  • 配置を行うコマンドを使う。１コマンド = 1建築。
  • コマンド１つ = 「遺伝子 (gene)」
  • コマンドの集合 = 「染色体 (chromosome)」
    • 一連のコマンド、つまり一連の街生成を示す
  • 染色体の交叉 (crossover)
    • 染色体をふたつに分けて、組み合わせ新しい染色体を作る (自然界と同じ）
  • 「突然変異 (mutation)」と「置換 (replacement)」
    • 突然変異：ある場所の遺伝子を有る確率で全く別なものにする
    • 置換：一定の領域の遺伝子を取り替える
    • いずれも、遺伝的アルゴリズムで現れる局所最適を回避し、大局的な最適解へ至る効果

実際の手順

  • ランダムにたくさんの染色体を作り出し（つまりはコマンド群 => 一連の街生成)
  • ２つの染色体を対戦させ、どのように勝利したか、また複数回の対戦によって、その平均を使って染色体の適応度を計測していく
  • そして適応度の高い染色体が親になりやすいように確率的に交叉させていく
  • 上記を「ルーレット方式」と呼ぶ
  • 多数かつ多様な遺伝子配置を持つ染色体を自動的に生成しながら、より強い遺伝子配置をもつ染色体を見つけ出していくことができる
  • シティコンクエストでは、「バランスの調整」「仕様のまずい点やバグ発見」で用いられた

交叉ではランダムに街の半分を入れ替えて行って、対戦を繰り返すということかぁ。

6.3 遺伝的アルゴリズムによるユーザー・マッチング

  • オンラインの集団戦においては、両チームの実力を近くしないと戦力差が出て面白くない。
  • 遺伝子 = 1ユーザー
  • 染色体 = 20 ユーザー
  • 上記から 10 体選出し、パラメータを計算し、残りの10体のチームとの戦力差が小さいほど、値が大きくなるフィットネス関数（適合度関数）でフィットネス値（適合度）を計算する
  • このような染色体 (20ユーザー1セット) をたくさん作った上で、遺伝的アルゴリズムを動かす
    • フィットネス値が大きいほど親になる確率が大きくなるルーレット方式を使いベストなチーム分けを見つける

こちらの場合は、さっきとは違い対戦は不要で各染色体のフィットネス値が一定に収束していけば終わりかな。パラメータの計算もむずかしそうに思う。

ゲームによっては戦績でレベル分けしすぎたり、強くなりすぎることでマッチしなかったり、そもそも自分がどこに所属するかを選択できるようなゲームもあるらしいと話題に上がった。

6.4 ニューロエヴォリューション - キャラクターを進化させる -

遺伝的アルゴリズムとニューラルネットワークを組み合わせた手法 (Neuroevolution)

6.4.1 NERO

  • 通常ニューラルネットワークは、ノードとコネクションからなる形状は変化せずコネクションの強さ（ウェイト）だけが変化する
  • ニューロエヴォリューションはその形状を学習と共に変化させていく手法
    • ドラスティックな変化では層が増えることもある

NERO (Neuro-Evolving Robotic Operatives)

  • 箱庭に閉じ込められた兵士たちがニューロエヴォリューションによって強くなる
  • 兵士たちは最初、入力層と出力層しかない簡単なニューラルネットワークを持つ
    • 入力層：「敵感知レーダー」「ターゲット感知」「オブジェクト感知」「最も近くの敵からの攻撃の方向の感知」「バイアス値」
    • 出力層：前後左右のベクトル、攻撃を行うかどうか
  • 兵士たちは FPS のように争い、あるタイミングごとに順位がつけられ下位２体が削除され、ランダムに作られた新しい２体が生み出されて入れ替えられ続ける
  • こうして全体が強くなる

4.11 で説明されたニューラルネットは、ゲーム性も違うが、ゲーム状態の統計情報を入力に、目標の選択を出力としていた。ここではベクトルが出力になるのでだいぶ違うなと。

6.4.2 NEAT (NeuroEvolution of Augmenting Topologies)

正直、理解が難しく詳細な説明は書籍見てくださいとしか・・・以下は、なんか読んでの感想。

  • ニューラルネットワークのノードではなく、コネクションを遺伝子として扱う
  • 染色体も遺伝子なので、コネクションの集合と言えるのかな
  • つまり、ニューラルネットワークのトポロジーに遺伝子たちは目に見えては現れない（コネクションは遺伝子だけど）
  • 一方で、トポロジーを決めるために遺伝子が存在する
  • 解説からは、この遺伝子の数値の決め方がわからないので、各パラメータがランダムなのか、ある時点でのニューラルネットワークをベースにして Weight 以外を決定するのかはわからない
  • ニューラルネットワークも詳しくないので、この処理の結果中間層のノードがコロコロ入れ替わってしまうことがどういうことかもよく分からない。。

6.4.3 rtNEAT (リアルタイム NEAT)

  • NERO で用いられている NEAT をリアルタイム化したもの
  • NEAT は世代を丸ごと入れ替えるのに対して、下位の一体を随時入れ替えて全体を進化させる

ここも難しい、、、以下は感想。

  • NEAT がニューラルネットワーク同士の交叉なので、下位の一体とはつまり一つのニューラルネットを入れ替えるってことか
  • 同じニューラルネットワーク構造を持つ集団を１つの「種」と捉え、種ごとの適合度（種に含まれる適合度の平均値）によって次の親となる確率を決定するとあるが
  • NERO において適合度は戦闘での順位であるのでそれで適合度が決まるのだろうか
  • 種と集団進化は話としてはわかるものの、実践してみないとイメージできない。最終的には一つの種が優勢になったところで終わるのだろうか。

6.5 ニューラルネットワーク - キャラクターを学習させる -

ゲームキャラクターの個性を、進化によって入れ替えるの絵はなく、無限とも言えるバリエーションで個性を与える場合には、ニューラルネットワークが使われているらしい。

がんばれ森川くん２号の紹介がほとんどなので詳細は省略。

6.6 パーセプトロンと決定木

6.6.1 ゴッドゲーム

  • プレイヤーがゲームを俯瞰的にみて、神の視点からゲームという箱庭世界に干渉するゲームジャンル

6.6.2 BDI アーキテクチャ (Belief-Desire-Intention Architecture)

  • 「Black & White」というゴッドゲームにおいて、ユーザーは島のオブジェクトを操作して、大型クリーチャーを教育して島を統治していく
    • 大型クリーチャーをユーザーが学習させていく（褒める、叱るなど）
  • クリーチャーたちはパーセプトロン、決定木を含む学習アーキテクチャを持つ

BDIアーキテクチャ

  • 心理学を起源とする意思決定アーキテクチャ
    • 信念 (Belief)、欲求 (Desire)、意志 (Intention) から知能を構築する
    • 心理学を起源とするので、ソフトウェアの構造は決まっておらず、事例ごとに設計する
  • 信念：認識対象のリスト（敵、体力、エネルギー etc）。しかし情報ではなく人工知能の思い込みを表現。
  • 欲求：パーセプトロン (0.0-1.0) で表現。食べたい、投げたい、眠りたい、など。
  • 提案：決定木で表現。それぞれの行動に対する評価値 (0.0-1.0) を計算。
  • 意志：全体プランであり、上記３つから決定される。敵の基地の攻撃など。
  • 特定のプラン：意志の全体プランから決定される。投石で攻撃など。
  • アクションリスト：具体的なアクションリスト。石を拾って、街に向かって、投石する、など。
  • 最終的な意思決定はユーティリティ・ベース（効用、評価値ベース) で行う。
  • ユーティリティ(欲求,　対象) = (欲求の強さ) x 提案 (欲求、対象)
  • 欲求、対象を入力にした関数。欲求はパーセプトロン、提案は決定木。

6.6.3 欲求のパーセプトロンの学習原理

  • 欲求はある行為に対する強さ。
  • 例えば「食べたい」であれば、「空腹度」「おいしさ」「寂しさ」からパーセプトロンで計算される
  • パーセプトロンの学習はウェイトの変化で行う。
  • パーセプトロンの変化に関しては簡単なので書籍の表 6.1 を参照。

6.6.4 提案の決定木、クイランのID3アルゴリズム

  • エントロピー、情報量についての説明。
  • 続いて ID3 アルゴリズムについて。
    • ID3 - Wikipedia

    • ID3は汎用目的で設計された教師あり学習アルゴリズムの一種である。その学習効率の高さと出力が決定的であることなどから、エキスパートシステムの知識獲得部分にしばしば用いられる。

    • この方法は各独立変数に対し変数の値を決定した場合における平均情報量の期待値を求め、その中で最大のものを選びそれを木のノードにする操作を再帰的に行うことで実装される。

ID3 アルゴリズムとこの Black & White の事例がどれぐらい合致するのかはよく分からない。

6.7 プランニング・アルゴリズム

スポーツゲームの自動の試合の進行に関するアルゴリズム

ここは図6.18 が無いと意味がわからないし、説明も結構難しく感じた。

  • 前提となる局面 (フリー、1対1、プレス etc) があり
  • そこでプレイセットが複数読み込まれ、プレイを選択する (パス、ドリブル、シュート etc)
  • 選択されたプレイセットが再生されるとともに、結果も判定される (成功、大成功、失敗、大失敗)
  • 結果がまた前提条件となる、局面が出てくる
  • 結果は結果判定式で確率テーブルとルーレット方式で判定される

みたいな感じだと思う。「完全オーサリング方式」や「完全リアルタイム方式」と比べて、どういう利点があるかはちょっとわからなかった。まあ、それぞれ利点があって、どれかを選ぶってことなんだろうか。

ということで 6 章終わり。第３部以降は、もっとわからないことが増えそうなので、読むかもしれないけど流し読みぐらいになりそう。