生物学的制約を導入した A*探索

有名な最短経路探索手法であるA*アルゴリズムにおいて，生物学的制約の導入 を試みる．1.1節で述べたとおり，A*アルゴリズムはアクションゲームにおいて，

ほぼ最適解を獲得した実績のある手法である．A*アルゴリズムでは，以下の式に よりゲーム木の経路のコストを算出する．

f^∗(n) =g^∗(n) +h^∗(n) (3.3) 数式3.3において, f^∗(n)はスタートノードから，あるノードnを経由して，ゴー ルノードに辿り着くまでの経路の推定コストを示す．f^∗(n)は二つの推定値の和に よって算出される．g^∗(n)はスタートノードから現在のノードnまでの既知のコス トである．h^∗(n)はヒューリスティック関数と呼ばれ，現在のノードnからゴール ノードまでのコストの推定値である．生物学的制約の導入に関して，「ゆらぎ」と

「遅れ」は，数百ミリ秒過去のキャラクタの位置情報に対してガウスノイズを付与 し，その座標をスタートノードとすることで実現する．「疲れ」は，極めて短時間 でのキー操作の変更を禁止することで再現する．「訓練と挑戦のバランス」は，学 習フェーズを持たないA*アルゴルズムでは実現不可能であるため対象外とする．

3.2.3 “Infinite Mario Bros.” の仕様

本研究では，“Infinite Mario Bros.”を対象とし，人間らしい振る舞いの自動獲得 と，その比較検証，主観評価実験を実施する．“Infinite Mario Bros.”は，世界的に 有名な2D横スクロール型アクションゲームである“スーパーマリオワールド”を 模したゲームであり，そのゲーム画面を図3.1に示す．“Infinite Mario Bros.”を対 象とした理由としては，以下の4つがあげられる．まず，1)ゲームの仕様やゲーム 環境パラメータが公開されている，かつ，2)「敵や穴を避けてできる限り先に進 む」という明確な目標が設定できるため，機械学習によるエージェントの振る舞 い獲得が可能である．次に，エージェントの振る舞いの人間らしさを評価するに あたり，3)当該ゲームは人間型キャラクタを操作可能であるため，評価者は人間 らしい振る舞いを想起しやすい．最後に，キャラクタの人間らしさを判断する際

3.2 振る舞いの獲得

図3.1: “Infinite Mario Bros.”のゲーム画面

の評価基準は，実際にそのゲームをプレイしたり，プレイ画面を見ているときに 形成されると考えられるため，4)世界的にきわめて有名なゲームジャンルである 2D横スクロール型アクションは最適である．2D横スクロール型アクションゲー ムは，複数人での協力プレイや敵対プレイが可能なタイトルも多数販売されてお り，人間の代替となるエージェントの自動獲得は有用である（マリオシリーズの ほかに，ソニックシリーズや星のカービィシリーズが世界的に有名）．

“Infinite Mario Bros.”における仕様は以下のとおりである．

• ステージの自動生成

事前に与えた疑似乱数のシード値に従って無限にステージが生成される．

• 操作キャラクタ（マリオ）

エージェントはマリオ（図3.1中央）を操作する．マリオの操作はコントロー ラのキー入力（LEFT, RIGHT, DOWN, SPEED, JUMP）により行う．毎フレー ムのキーの押下状態により，マリオは対応した行動を行う（毎秒24フレー ムで動作）．また，マリオには「スーパーマリオ」「ちびマリオ」という状態 が存在する．「スーパーマリオ」でダメージを受けた場合は「ちびマリオ」に 変化し，「ちびマリオ」でダメージを受けた場合は死亡する．ダメージについ ては，後述の接触判定において説明する．穴に落ちた場合は「スーパーマリ オ」「ちびマリオ」を問わず，死亡する．

• 敵キャラクタ

第3章 生物学的制約に基づく人間的なゲームAIの自律的構成

ステージには数種類の敵が登場し，敵はそれぞれ独自の動作をしている．エー ジェントは，これらの敵を避けて進むか，倒して進むかを決定しなければな らない．マリオは敵との接触判定によってダメージを受ける場合がある．踏 むことができる敵は，踏む以外の行動で接触した場合にダメージを受ける．

踏むことができない敵は，接触した場合にダメージを受ける．

• スコアの獲得

マリオが死亡する，または，設定された制限時間に達するとプレイは終了し，

スコアが表示される．スコアはMario AI Competition [17]で規定されている 評価関数で計算され，ステージを進んだ距離のみに応じてスコアが変動する

（右に1ピクセル進むごとに1.0加算される）．

• エージェントの観測情報

エージェントは，マリオの座標，マリオの状態（スーパーマリオかちびマリ オか），敵の座標および種類，地形の座標および種類を観測する．ただし，観 測可能な敵座標と地形座標は，マリオを中心に22×22ブロック（1ブロック は16×16ピクセル）の範囲内のみである．エージェントは毎フレーム観測 情報を受け取り，マリオの行動制御を行うためのキー入力を返す必要がある．

3.2.4 “Infinite Mario Bros.” での振る舞い獲得

“Infinite Mario Bros.”は，エージェントが観測可能な22×22ブロックの範囲内 に，4種類のブロック，11種類の敵キャラクタ，3種類のアイテムが配置される可 能性がある．そのため，全配置の組合せを考慮すると，現実的な時間で学習が収 束しない可能性が高い．そこで，エージェントが観測するゲーム局面sの次元を，

ゲームの攻略に重要でない情報を削減することで，以下のとおりに圧縮する．

• マリオを中心に7×7ブロックの敵と地形の情報

1フレームあたりのマリオの移動距離は小さく，画面内すべての敵座標や地 形座標がマリオの行動に影響することはない．そこで，学習に使用する敵座 標と地形座標は，マリオを中心に7×7ブロックの範囲内とする（図3.2：[16]

より引用）．また，ブロックの種類は通行不可能ブロックと上に飛び乗れる ブロックの2種類，敵の種類は踏める敵と踏めない敵の2種類，アイテムは 考慮しないこととする．これにより，ゲーム局面sの次元数は大幅に削減さ れる．

3.2 振る舞いの獲得

図3.2: 次元圧縮された観測情報

• マリオの進行方向

敵や地形との関係性を把握するための重要な要素であるため，エージェント は8方向＋停止の9次元としてマリオの進行方向を把握しておく必要がある．

• 「スーパーマリオ」か「ちびマリオ」か

「スーパーマリオ」でダメージを受けた場合は「ちびマリオ」に変化するだ けでプレイを続行できるが，「ちびマリオ」でダメージを受けた場合は死亡と なる．より長くプレイするうえで重要な要素であるため，エージェントはマ リオの状態を把握しておく必要がある．

• マリオが地上にいるか

マリオは，地上にいる場合はダッシュやジャンプができるが，空中にいる場合 はできない仕様である．マリオが地上にいるかどうかは，行動選択にあたっ て重要な要素であるため，エージェントはマリオが地上にいるかどうかを把 握しておく必要がある．

次に，Q学習における選択可能な行動aの設定方法について述べる．マリオの 行動は，コントローラのキー入力によって決定される．マリオの行動制御に影響 があるキー入力の組合せは11パターン存在する．そこで，選択可能な行動aとし て表3.1のとおり設定する．

最後に，Q学習における報酬rの設定方法について述べる．敵を可能な限り避 け，ステージをより早く，より遠くまで進むためには，ステージを早く進むこと

第3章 生物学的制約に基づく人間的なゲームAIの自律的構成

表3.1: 行動の種類とキー入力の組合せ

行動の種類 (LEFT, RIGHT, DOWN, JUMP, SPEED) 右に歩く (OFF,ON,OFF,OFF,OFF)

右に走る (OFF,ON,OFF,OFF,ON)

右に歩きジャンプ (OFF,ON,OFF,ON,OFF) 右に走りジャンプ (OFF,ON,OFF,ON,ON)

左に歩く (ON,OFF,OFF,OFF,OFF)

左に走る (ON,OFF,OFF,OFF,ON)

左に歩きジャンプ (ON,OFF,OFF,ON,OFF) 左に走りジャンプ (ON,OFF,OFF,ON,ON)

真上にジャンプ (OFF,OFF,OFF,ON,OFF) しゃがむ (OFF,OFF,ON,OFF,OFF) 静止 (OFF,OFF,OFF,OFF,OFF)

に対して正の報酬を与え，逆にダメージを受ける，死亡するといった，攻略を阻 害する要因に対して負の報酬を与えることが望ましい．また，キー操作変更によ る疲れを実現するため，キー操作を変更した場合は負の報酬を与える必要がある．

そこで，報酬rを以下のとおり設定する．

r =distance+damaged+death+keyP ress (3.4) 式(3.4)において，distanceは現フレームtから次フレームt+ 1の間に行動a_tに よって右に進んだ距離（pixel）であり，正の報酬として与える（ただし，左に進ん だ場合は負の報酬となる）．damagedは行動によってダメージを受けた場合に与え る負の報酬，deathは行動によって死亡した場合に与える負の報酬である．また，

keyP ressは前フレームから行動を変更した場合に与える負の報酬である．予備実

験の結果，distanceは右に進んだ距離（pixel）の2倍，damagedは−50.0，death は−100.0，keyP ressは−5.0とした．

最後に，A*アルゴリズムにおけるゲーム木の作成方法と，経路のコスト算出に ついて述べる．1.1節で述べたA*アルゴリズムに基づくエージェント[16]を参考 にする．スタートノードを現在のマリオの位置座標（ただし「ゆらぎ」や「遅れ」

が付与された座標），ゴールノードを画面の右端とし，マリオが取り得る行動に よってゲーム木を作成する．g^∗(n)としては，スタートノードから現在ノードまで の時間を，h^∗(n)としては，現在ノードから画面の右端に到達するまでの推定時間 を算出している．