JAIST Repository
https://dspace.jaist.ac.jp/Title

横スクロールアクションゲームにおける多様なスピードランルートの自動提案

Author(s)原口, 海; 池田, 心Citation

ゲームプログラミングワークショップ2019論文集:
227‑234

Issue Date

2019‑11‑01

TypeConference Paper

Text version

publisher

URL

http://hdl.handle.net/10119/16693

Rights社団法人 情報処理学会, 原口 海, 池田 心,
ゲー
ムプログラミングワークショップ2019論文集, 2019,
pp.227‑234. ここに掲載した著作物の利用に関する注
意: 本著作物の著作権は（社）情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。 Notice for the use of thismaterial: The copyright of this material isretained by the Information Processing Society ofJapan (IPSJ). This material is published on thisweb site with the agreement of the author (s) andthe IPSJ. Please be complied with Copyright Law
of Japan and the Code of Ethics of the IPSJ if
any users wish to reproduce, make derivative
work, distribute or make available to the public
any part or whole thereof. All Rights Reserved,Copyright (C) Information Processing Society ofJapan.

Description

Japan Advanced Institute of Science and Technology

The 24th Game Programming Workshop 2019

横スクロールアクションゲームにおける多様なスピードランルートの自動提案
原口海†,1池田心†,2

概要：スピードランとは，主にアクションゲームをできるだけ短い時間でクリアする“遊び方”であり，日本ではタイムアタックなどとも呼ばれて親しまれている．スピードランをうまく行うためには，適切なルートつまりステージの進め方を設定したうえで，それを正確にこなす必要がある．上級者のルートは動画サイトなどで見つけられるが，それは初中級者には模倣が難しいものである．そこで本研究では，Marioについて初中級者でもプレイできるようなルートを自動的に提案するようなシステムを目指し，これをペナルティ付き遺伝的アルゴリズム(GA)で実現することを目指した．最速クリアのみを目指した GA では
12 回も敵キャラとニアミスをしたが，ニアミスにペナルティを加えた GA ではそれを 4 回に抑えることができた．面白い点として，後者のほうがクリアタイム自体も早くなったことも挙げられる．
キーワード：スピードラン，ルート生成，遺伝的アルゴリズム，ペナルティ

Evolution of Various Speedrun Routes
for Platform GamesKai HARAGUCHI†,1

Kokolo IKEDA†,2

Abstract: "Speedrun" (called "time attack" in Japan) is a way of playing action games, where each player
tries to clear the given stage/game as fast as possible. For this purpose, each player should optimize his routeto play from the start to the goal, and also should play the route accurately. Good routes optimized by experts
can be easily found from the Internet, but such routes will be too difficult for common players. So, thisresearch aims to generate and suggest good routes for common players, and proposes a way to realize thesuggestion system by using a genetic algorithm (GA) with penalties. We compared two routes, one by a GA
for fastest clear and the other by a GA for fast and safe clear. While 12 dangerous situations were found in theformer route, the number was successfully decreased to 4 in the latter route. One more interesting point is thatthe clear time of the latter route is faster than that of the former route.
Keywords: Speedrun, Route generation, Genetic Algorithm, Penalty

目標を達成する AI は完成しつつある．近年では，人間らし1. はじめにい動きを模倣したり [3]，教師となったりする研究が盛んに

近年，深層学習の登場や計算機技術の向上により，人工行われており，AI の役割は協力者や教育者へとシフトして知能を用いた研究は幅広い分野で行われている．ゲームのいる．しかし，これらの研究においても最終的な目標は人分野では，人間では困難なステージをクリアするアクショ間プレイヤーの“クリア”や“勝利”の補助である場合がンゲームの AI[1]や，人間チャンピオンに打ち勝つ囲碁 AI[2]多い．などが開発され，“クリア”や“勝利”といったゲームの主ら追加された目標”に着目する．具体的には，横スクロー† 北陸先端科学技術大学院大学

Japan Advanced Institute of Science and Technology, Nomi, Ishikawa,
923-1211, Japan
1 s1810149@jaist.ac.jp
2 kokolo@jaist.ac.jp© 2019 Information Processing Society of Japan

これらとは異なり本研究では，ユーザーによって“後かルアクションゲームにおいて，ただステージをクリアするのではなく，できるだけ素早くクリアすることを目標とする「スピードラン（タイムアタック）」という遊び方をとり- 227 -

The 24th Game Programming Workshop 2019あげる．詳細は次章で述べるが，この目標を AI がサポートするためには，プレイヤーの技術レベルに応じたスピードランルートの設定というものが必要であり，本研究では遺伝的アルゴリズム（GA）でこれを行う． 対象のゲームとしてはスーパーマリオを用いる．研究が盛んに行われている，評価が行いやすい，プラットフォーム[4]が公開されている，などの理由からである．詳細は 3 章で述べる．

2. スピードランについて
本研究で設定した“素早いステージクリア”という目標
は，スピードランやタイムアタックと呼ばれる，やりこみ

図 2

ギミックを無視した強行突破の例

要素の一種である．近年では動画投稿サイトなどで人気のプレイスタイルであり，e-sports として大会[5]も開催されてまた，図 2ギミックを無視した強行突破の例に示すよいる．やりこみ要素ではあるものの，超上級者でなければうな，本来であれば遠回りする場面を，敵と接触した際の挑戦できないようなものではなく，小学生であれ中高年で無敵時間を利用した強引な突破法も度々取られる．強行突

あれ自分が達成可能な目標を定めて，スキル向上や隣人と破自体は容易に行えることも多いが，これを実行する“ルの競争を楽しむことができる，懐の広い世界である．

ート”も同様に簡単とは限らない．このルートでは確実に競技会でのルールはさまざまで，対象となるゲームやス負傷するため，図 2 のポイントまで体力を温存して到着すテージはもとより，「最終ボスを倒すまで」や「隠しアイテる必要があるうえ，途中で無敵が解除されれば再度負傷すムを全回収するまで」などの達成すべき目標が定められてる．この前後にボス戦があれば，回避に専念することで短いる．また，バグ利用の可否なども定められることが多く，縮分以上の時間を失うこともある．

いずれにせよそれぞれのルールに沿った攻略法が必要とされている．

このようにスピードランでは，瞬間的に最善の手が長期的にも最善であるとは限らない．スピードラン上級者であスピードランにおける時間短縮を意識したクリアまでのれば自身のスキルとリスクを照らし合わせて選択できるが，道筋（ステージの進め方）は，“ルート”や“チャート”とスピードラン初級者にとっては自身に適切なルートの選択呼ばれ，良いルートの発見はタイム短縮の大きな役割を担は困難である．それにも関わらずルート探索には多くの経っている．自分に合った良いルートを発見することは簡単

験やゲームそのものに対する知識が必要であるため，多くではないため，それ自体が長期的な意味でのスピードランのプレイヤーは動画投稿サイトにアップロードされたものの楽しみ方のひとつでもある．

を模倣して獲得している．しかし，それらの動画はトッププレイヤーがプレイするものがほとんどであるため，初心者が自身に合ったルートを発見することは難しい．また，動画上では一見簡単そうに見えても，コンマ 1 秒以下の入力速度を要したり，小さなミスが大幅な遅滞に繋がるハイリスク・ハイリターンなものだったりする． このようなルートを初中級者が真似を試みても失敗ばかりで面白くなく，技術向上の妨げにすらなりかねない．
そこで本研究ではスピードランにおけるルート探索を AIに補助させ，より多くの選択肢の提供を試みる．通常の「強図 1

スキルによるルートの違いい AI」「人間らしい AI」では，“未知の”ステージに対して良いプレイを行う AI を，A*アルゴリズム・強化学習・入出例えば，図 1 に示したような横スクロールアクションゲ

力モデル＋遺伝的アルゴリズムで最適化することがよく見ームにおけるスピードランでは，プレイスキルに応じたルられる．しかし本研究の対象であるスピードランは，通常ートの選択が重要である．最も早いルートは青で示した，対象ステージが事前に公開されている．そのため，“１つの”敵キャラクターを足場にして対岸に渡るルートだが，失敗ステージに対する良いプレイを行えれば十分である．このした場合はリカバリーが効かないためリスクが非常に高い．

点を鑑みて，本研究では遺伝的アルゴリズムでルートを直一方，赤のルートは安全だが，その分時間がかかる．

接探索することを試みる．これにより，探索の際コマンドの入力速度や敵とすれ違う際の距離などに制限を加えることで，幅広いスキルレベルに対応した多様なルートの提案© 2019 Information Processing Society of Japan- 228 -

The 24th Game Programming Workshop 2019も期待できる．

ればよい」と割り切る．そして，（汎用的な戦略ではなく）ルート自体を直接的に最適化することを目指す．その場合

3. 関連研究でも，ルートをどのように表すかにはいくつかの可能性がスーパーマリオは極めて有名なゲームであり，一人ゲーあり，これは 4.1 節で述べる．4.2 節と 4.3 節ではルートのムで評価が行いやすいことや優れた研究用プラットフォー

通常の評価方法，4.4 節ではさらに“プレイしやすいルート”

ムが早くから公開されたことから，さまざまな研究が行わのための評価方法を述べる．実際にルートを最適化する方れている．高速なクリアを目指すもの，人間らしい動きを法については 5 章で述べる．

目指すもの，人間のレベルに合わせたステージを生成する

4.1 スピードランルートの直接探索ものなどであり，IEEE CIG などの国際会議でも多様な競技会が行われてきた．

本研究では，行動をルートを構成する要素と考えることで，スピードランルートの直接探索を試みる．

高速なクリアを目指すものとしては，A*アルゴリズムによるもの[1]がその動画のインパクトもあって有名である．
基本的には，右側に進めば進むほどゴールに近くなるというヒューリスティック関数を与えることによって探索を効率化しており，Ｓ字の動きなど迂回を要しないステージでは極めて高速なクリアが可能である．しかしながら，これをスピードランのルート設定に用いることは適切ではないだろう．1 ピクセルレベルでの敵とのすれ違いや，極めて厳密な操作が必要となるためである．なお A*はオンラインのアルゴリズムであり，オフラインでの学習は必要としない．
事前の学習を必要とするアプローチとしては，遺伝的ア

図 3

ルートの直接探索手法のイメージルゴリズムや強化学習がしばしば用いられる．Togelius らはNeuroevolution という枠組みを用いてマリオのプレイヤーを

図 3 のルートはジャンプで敵を踏んで対岸に渡るルート進化させている[6]．これはマリオの周辺状態を入力とし，を示している．このルートの達成には，右→右ジャンプ→行動を出力とするニューラルネットワークを最適化させる

右ジャンプ→右という入力を時系列順に行う必要である．

遺伝的アルゴリズムであるが，ポイントとしてネットワー

しかし，ルートを時系列に基づく行動の集合と捉えた場合，クの結合重みだけでなく構造も変化させる点がある．A*と探索が非常に困難となる．例えば，t0 の「右」という行動が同様この方法は未知のステージにも適用できるが，学習に「上」に更新された場合，いったんは梯子を登るが t1 で「右用いたステージでの性能よりも落ちるのは良く知られたこにジャンプ」してしまい落下してしまう．これを防ぐには，とである．

梯子を上がりきるまで「上」を押すなど，t1 以降の全ての要

藤井らは，人間らしいマリオの AI を学習させるための取素に大幅な変更が必要となる．

り組みを行った[3]．マリオに限らず多くのゲームに普遍的一方，ルートを座標に基づく行動の集合と捉えた場合，に登場する人間らしさである“身体的制約”に注目し，状場合，x0 が「上」に更新されても影響は小さく済む．x 座標

態認知に遅れやあいまいさを入れる，操作に疲れの要素をが変わらないため，梯子を登り終わった後も上を目指し続入れるなどの提案を行っている．強化学習および A*アルゴ

けるが，後ろの要素は影響を受けない．座標が固定されたリズムをベースとして，ここに提案手法を加えることで，場合への対処は必要となるが，更新が要素全体に及ぶこと人間よりも人間らしく見えるようなエージェントの獲得にと比較するとその労力は著しく減少する．

成功している．

本研究では以下の手法を用いてルートを行動に分解し，注意すべき点は，ここで用いられている手法または獲得行動の更新することでルートの探索を行っている．

された政策は基本的には「多くのステージで利用可能なもの」を目指しているということである．

⚫

表現することにする．

4. 提案手法⚫

前章で紹介した手法は基本的に全て未知の状況におけるAI エージェントの挙動を良くしようというものである．こことが多いことを踏まえ，本研究では「与えられたそのスx 座標は連続的であるため，全ステージをある程度幅の狭い N 個のブロックに分けることにする．

⚫

れに比べ，スピードランでは対象ステージが事前に分かる

1 つのブロックごとに 1 つの行動，全部で長さ N の行動の配列でルートが表現できる．

⚫

テージの中で，適切に行動する方法（良いルート）が分か© 2019 Information Processing Society of Japan

ルートを「この x 座標の範囲ではこの行動を取る」と- 229 -

エージェントによるテストプレイでルートの“良さ”を評価する．例えばステージのどこまで進めるかなど

The 24th Game Programming Workshop 2019

⚫

である．

し，本研究で利用するのはｘ座標のみであり，4.1 節で説明

長さ N の配列を 1 つの個体とした，遺伝的アルゴリした長さ N の配列を参照して行動が簡単に決まっていく．

ズムによって，評価値が高くなるようなルートを最適

具体的には，“x 座標を取得→当該インデックスの行動を 5化する．

フレーム実施”を繰り返すことが基本となっている．
行動を 5 フレーム連続して実施する理由は，“その行動をなお，ステージによっては右→上→左→上→右のようにプレイヤーが実施できるか”を考慮したものである．Mario「同じ x 座標でも違う行動を取らないといけない」ことがAI Benchmark の意思決定タイミングは 1 秒間に 24 回ありうる．この場合には，y 座標についても分割を行う必要（24FPS）であるが，0.04 秒ごとに行動を変えるなどというがあるだろう．

ことは普通の人間には不可能である．そこで，切り替え回4.2 エージェントによるテストプレイ数を軽減するためにこのような措置を取った．

上記の通り本研究では，ある座標 x における行動を更新

また，1 秒以上マリオの x 座標に変化がない場合は，強制してルートの探索を行っているため，評価にはエージェン

的に右＋ジャンプを実行することで行き詰まりを緩和して

ト に よ る テ ス ト プ レ イ が 不 可 欠 で あ る ． Mario AIいる．横スクロールアクションゲームでは左端にスタート

Benchmark[4]は，横スクロールアクションゲームを対象としがある場合がほとんどのため，スタートから遠ざかる右側

た AI のベンチマークソフトとしてしばしば用いられている．

を選択する．同時にジャンプを行うことで障害物に引っか図 4 に示したように，ステージ生成や，x 軸座標などの環かった場合の対処も兼ねる．このような処理を行わなくと境情報の習得が容易に行えるため，本研究でもこの環境をも綺麗にクリアできるルートは表現できるかもしれないが，利用してテストプレイを行う．

これがなければランダムに作った解はすぐに停止または障

このベンチマークソフトのエージェントの有効な行動は
表 1 に示す 12 種類である．

害物にひっかかってしまって探索効率が悪かったため，用いることにした．
4.3 生成されたルートの評価

表 1

エージェントが取り得る行動一覧

本研究において，生成されたルートの評価はエージェン
トを評価することで行う．
エージェントの評価には Mario AI

無操作

右＋ダッシュ

右左＋ダッシュ左右＋ジャンプ

るが， スピードランにおいてはこれらの値は（それが求めしゃがみ左＋ジャンプられる特殊な競技ルールの場合を除いて）不要である．しジャンプ

右＋ジャンプ＋ダッシュ

たがって，どれだけ進んだか，クリアできたか，クリア時

ダッシュ

左＋ジャンプ＋ダッシュ

Benchmark のスコアを利用する．デフォルトでは敵キャラク
ターのキル数や獲得したコインやアイテムの数で計算されにどれだけ時間が残っていたか，を主に参照することにする．
本実験ではエージェントがステージクリアに成功した場合（数式 1）と失敗した場合（数式 2）の 2 つに評価関数を分けて，評価値の計算を行った．

Eclear = distance + 1024 + 10 × leftTime- penalty (1)Efailed = distance- penalty (2)distance, leftTime はそれぞれで示したスコアの到達距離,残り時間が代入される．ゴールに到達できなかった場合には distance から penalty を差し引いた値のみが評価値として計算される．
4.4 penalty
単純に進んだ距離や残り時間を最大化した場合，得られたルートには「プレイしやすさ」といった本来欲しい特徴
図 4

Mario AI Benchmark の画面が考慮されていない可能性が高い．例えば，敵のぎりぎり近くをすり抜けるルート，足場があるぎりぎりでジャン

Mario AI Benchmark を用いる研究には，周辺の状況などの“入力”をもとにして次の行動を定めるものが多い．しか© 2019 Information Processing Society of Japan

プ・着地するようなルート，動作の切り替えが頻繁にあるルートなどは，一般的に初中級者向きとは言えない．

- 230 -

The 24th Game Programming Workshop 2019

こういった好ましくない特徴を，if-then ルールなどでハーり ， 世 代 交 代 モ デ ル と し ては 初 期 収 束 の 起 こ り に く い

ドに禁止することはできるだろうが，それでは今度は主た

Minimal Generation Gap [7] を採用した．具体的な手続きはる性能（クリアの速さ）が落ちてしまうこともありうる．

パラメータ込みで以下の通りである．

こういったときに，ペナルティという形でこれをソフトに抑制することができるのは GA などの直接探索法の利点の(1)一つである．具体的にはペナルティの与え方としては以下のようなものがありうるだろう．
(1)とする．
(2)

親世代から 2 個体非復元抽出し，50 組のペアを作る．

(3)

各ペアから 8 個体の子個体を作成し，評価する．詳し

敵のぎりぎり近くをすり抜ける回数を抑制するため，“自分と同じ高さの１マス前に敵がいる”状態に対し，い作成方法は次節で述べる．
(4)

1 フレームあたり 1 点減点する．
(2)

親子 10 個体の中から，評価値 1 位と 2 位を生存させる個体とする．

足場ぎりぎりでジャンプする回数を抑制するため，ジ(5)ャンプ時・着地時に，足場の端までの距離が 10 以下であれば，(10-距離)点減点する．
(3)

初期個体を 100 個体ランダムに生成・評価し，親世代全てのペアで生存個体を設定したら，次世代として（2）から（4）を繰り返す．

(6)

動作の切り替え回数を抑制するため，15 フレーム以内

400 世代終了後，最も評価値の高い個体のルートを確認する．に動作が切り替わるたびに 1 点減点する．
表 2

採用した行動一覧

これらはあくまで例であり，その閾値やペナルティの重左右さもチューニングされたものではない．将来的には，被験左＋ダッシュ

右＋ダッシュ

者実験で「どんなルートは模倣しにくいのか」を定量的に左＋ジャンプ＋ダッシュ

右＋ジャンプ＋ダッシュ計測し，また各プレイヤーの技量や傾向に合わせてこれらをチューニングすべきだと考えている．

5.1 交叉と突然変異
交叉と突然変異は，新しい良い解を作るための遺伝的ア5. 遺伝的アルゴリズムによる最適化

ルゴリズムの根幹操作である．交叉の場合は，両親の良い前章では，ルートの表現方法，評価方法について述べた．

部分をいいとこどりした子個体を生成することを期待し，本章では，これらを用いて実際にルートを最適化するため突然変異の場合は，（親が似通ってしまっているときに）悪の手続きについて述べる．どのようなステージに対してルい部分に良いものを導入することを期待している．この操ートを最適化するのかによって若干最適化手段も変わって作を不適切に定めると，良い親からも悪い子個体が頻繁にくるが，本論文では比較的シンプルな「道中に３つの穴（致生成されたり，突然変異によって良い解が壊されたりする死断崖）を持つ，部分的な後戻りの必要がないステージ」確率が高くなってしまう．

を対象に採用している．このステージはベンチマークソフ

本論文ではそもそも，（時刻ごとではなく）X 座標ごとにトがステージシード 0，ステージレベル 0 で生成するものに，行動を定めるということによって，交叉や突然変異が解の3 つの穴を追加して作成した．図 5 にステージの一部を撮質を落とすことを防ごうとしている．時刻ごとの行動系列影し，連結したものを示す．狭い穴への滑り込みのようなを持つのは表現としては自然に思えるが，１か所でも行動テクニックは必要としないステージであり，ルートを構成を変えればそれが以降の全ての場所に影響を与えるというする行動要素は表 1 から不要なものを削除して表 2 のよう業を持つことになる．実際我々は予備実験として時刻ごとに 6 つに減らした．ステージは 256 分割し，およそマス半の行動系列による遺伝的アルゴリズムも実行しているが，分ごとに行動を切り替えることができるようにした．従っクリアする解を見つけることすら困難であった．これを Xて，ルートのとり得る範囲は 6^256 である．

座標ごとにすることで，ある場所での変更が他の場所での挙動に大きな違いを与えないような工夫を行ったということである．
その上で，用いた交叉は一様交叉とした．すなわち，長さ 256 の配列 p1, p2 を親として，子の配列 c[i] は，p1[i]または p2[i]を i ごとにランダムに選ぶということである．
突然変異については，3 つの方法を試みた．1 つめは，「一図 5

本論文の対象となったステージの一部様に 10％の部位を変異させる」ものである．これだと解の破壊が頻発したため，2 つめとして「1 か所または 2 か所の最適化手法として採用するのは遺伝的アルゴリズムであ© 2019 Information Processing Society of Japan

み変異させる」ものも試みた．さらに，クリアができない- 231 -

The 24th Game Programming Workshop 2019

解の改善を狙って，3 つめとして「マリオが敵にやられた，また，A はクリアするルートの発生がかなり遅く，学習あるいは穴に落ちた場所の周囲 10 マスにだけ変異を起こ結果も不安定だったため，以後の実験では死亡箇所周辺にす」ものも試みた．これらをどのように組み合わせたかに強制的な変異を加える手法へと変更した． そのため，本論ついては 6 章で述べる．

文では B，C，D について比較する．

6. 性能評価
5 章では，遺伝的アルゴリズムの枠組みと，交叉・突然変異操作について述べた．本章では，突然変異に工夫を行う
場合と行わない場合でどのような差がでるか，さらに 4.4 節で述べたペナルティを加えるとどのような差がでるかについて比較実験を行う．
比較を行う設定は以下の 4 つである．
A)

ペナルティ・強制変異なし．変異発生時には全ての遺伝子がそれぞれ 10.0%の確率で変異する．

図 6

実験 B の最良評価値推移（200 世代）

図 7

実験 C の最良評価値推移（400 世代）

図 8

実験 D の最良評価値推移（400 世代）

ペナルティなし．両親個体が未クリアであれば，死亡B)箇所の周辺 10 マスで強制的に変異を発生させる．それ以外の変異発生時には全ての遺伝子がそれぞれ 10.0%の確率で変異する．
ペナルティなし．両親個体が未クリアであれば，死亡C)箇所到達点の周辺 10 マスで強制的に変異を発生させる．
変異発生時には 70.0%の確率でランダムな 1 カ所，30.0%の確率でランダムな連続した 2 カ所が変異する．
D)

自分と同じ高さの 1 マス前に敵がいる状態に対し，1フレームあたり 1 点の減点．両親個体が未クリアであれば，死亡箇所の周辺 10 マスで強制的に変異を発生させる．変異発生時には 70.0%の確率でランダムな 1 カ所，30.0%の確率でランダムな連続した 2 カ所が変異する．

なお， A・B・C は（数式３），D では（数式１）と異なる評価関数を用いて最適化を行った．よって D については（数式１）によって得られた最良個体で再度テストプレイし，（数式３）で再評価して同一の基準に合わせたうえで比較を行った．

E = distance + 1024 + 10 × leftTime(3)

B，C，D の手法はいずれもクリアするルートが安定的に生成されたため，全試行で最も高い評価値のルートについこれらの実験のうち，A と B は 20 試行の予備実験を行ってその性能を検証し，ステージクリアまでのゲーム内時間たが，図 6 に示した実験 B の最良評価値推移のようなグラである“クリアタイム”，敵と衝突した回数である“負傷数”，フの形状となった．最良値・平均値ともに，世代を重ねる評価値，同じ高さの 1 マス前の敵とすれ違った（ニアミス）

ことによる性能向上がほぼ期待できなかったため，200 世代回数である“ペナルティ”を表 3 にまとめた．

目で実験を打ち切っている．一方，C と D の実験では図 7（実験 C），図 8（実験 D）に示すように 400 世代目近くで表 3も評価値が増加している．これは，10％の部分を変異させ各実験の最良ルート性能一覧
クリアタイム 負傷数 評価値

ペナルティるという B の突然変異が破壊的であって殆ど良い解を作る

実験B

6126500

32のに寄与できないのに比べ，C では 1 または 2 か所に限定

実験C

462665013したために比較的高確率で改善解を得られているためだと

実験D3226790

4予想できる．

© 2019 Information Processing Society of Japan- 232 -The 24th Game Programming Workshop 2019

6.1 クリアタイム
3 実験のクリアタイムは意外なことに，行動に制約のない
実験 B や実験 C ではなく，ペナルティによる制約のあるはずの実験 D から最も良い記録が得られた．各世代最良評価
ルートのクリアタイム推移を全試行から取得し，図 9（実験 B）， 図 10（実験 C），図 11（実験 D）に示す．なお，スペースの都合上クリアタイム 110 以上のものは省略している．また，それぞれの図の最良値と平均値をまとめたものを図 12 に示す．
実験 D ルートの平均値は 200 世代目付近で実験 C の最良値とほぼ同タイムとなった．これはペナルティの導入で目の前に敵がいる状況が減り，通過するコースがずれても負傷しにくくなったためと考えられる．これにより交叉・変異の成功率が上がり，良い個体が誕生したと推測する．

図 11

各世代最良評価ルートのクリアタイム推移（実験 D）

図 12
図 9

各世代最良評価ルートのクリアタイム推移（実験 B）

各実験における各世代最良評価ルートのクリアタイムの最良値・平均値推移

6.2 ニアミス
各実験で得られたルートのプレイしやすさを検証するため，実験 B と実験 C でもテストプレイを行い，ペナルティが発生した回数を計測した．実験 D は評価関数にペナルティが含まれるため，3 実験の中では最も少ないが，実験 Bから実験 C でも大幅に減少している． 実際にプレイしやすいルートかを検証するため，x 軸の各 256 座標における最も近い敵の距離を計測した．この距離は，マリオがアクションを取る際に，マリオの x,y 座標と敵の x,y 座標の差を取得してユークリッド距離を計測したものである．この際の座標は，ステージを x 軸方向に 4096 分割，y 軸方向に 256 分割した場合のものであるため，敵との距離をより詳細に得ることができる．この距離が 23 以下の場合には，マリオの周辺 1 マス以内のどこかに敵がいることとなる． 図 13 に距離のヒストグラムを示す．
図 10

各世代最良評価ルートのクリアタイム推移（実験 C）© 2019 Information Processing Society of Japan- 233 -The 24th Game Programming Workshop 2019
参考文献
[1]

[2]
[3]

[4]

図 13

最も近い敵との距離ヒストグラム

実験 B のルートは，256 マス中 36 マスで敵が周囲 1 マス[5]以内にいる状況だった．実験 C で 1 マス以内に敵がいた回数は 26 回だったのに対し実験 D では 28 回と，ペナルティ[6]の無い実験 C のほうが少ない結果となった．一方，同じ高さの 1 マス前に限れば表 3 で示した通り実験 D が一番少な[7]い．これは，実験 D のルートが敵を踏みつけによって排除するため発生していると考えられる．図 13 の敵との距離は，踏みつけの直前にも計算されるためである．実験 C での踏みつけ回数は 12 回，実験 D では 16 回であり，これらの値を減算した場合には，実験 D の周囲一マスに敵がいた回数が最も少なくなる．
6.3 その他の観察
いずれの実験でもステージクリア時の状態はちびマリオであった．これは，いずれの実験でも評価値にマリオの状態を加えていないためであると考えられる．ただ，実験 Bのマリオが立ち往生している間に負傷している一方，
実験 Cと D ではダッシュでステージを進む最中に負傷するといった違いがみられた．負傷してでもクリアタイム短縮を図る
点はスピードランとしては非常に重要であり，この点から
実験 C・実験 D は本研究の目的に沿った動きをしていると評価できる．

7. おわりに本研究ではスピードランという，ユーザーによって“後から追加された目標”を達成する AI を，行動の最適化によって獲得できることが確認できた．今回は“素早いクリア”という目的に応じたスピードランルートの提案だけだが，評価値やペナルティを改良することで，“コインをすべて取る”や“負傷することなくクリア”などの目標にも対応できると考えられる．
今後の展望として，個人にとって最適なルートやスピードラン特有のテクニックを用いるルートの探索を行いたい．
本研究の手法は，交叉や突然変異手法やペナルティの与え方などでの改良の余地は大きいため，今後はこの点について研究したい．

© 2019 Information Processing Society of Japan- 234 -Julian Togelius, Sergey Karakovskiy and Robin Baumgarten,
The 2009 Mario AI Competition, Evolutionary Computation
pp.1-8, 2010-07
David Silver et al., Mastering the Game of Go without HumanKnowledge, Nature 550, pp.354-359, 2017-10
藤井叙人，佐藤祐一，中嶌洋輔，若間弘典，風井浩志，片寄 晴弘，生物学的制約の導入による「人間らしい」振る舞いを伴うゲーム AI の自律獲得，第 18 回 GPW，pp.73-80，
2013-11
Mario AI Championship, Mario AI Benchmark revision 762v.14, 入手先<
https://sites.google.com/a/marioai.com/www/marioai-benchmark/download >（アクセス 2019-10-8）
Games Done Quick, https://gamesdonequick.com（アクセス2019-10-8）
Julian Togelius, Sergey Karakovskiy, Jan Koutnik, Jurgen
Schmidhuber, Super Mario Evolution, 2009 IEEE Symposiumon Computational Intelligence and Games, pp.156-161, 2009-09
佐藤浩，小野功，小林重信，遺伝的アルゴリズムにおける世代交代モデルの提案と評価，人工知能学会誌 Vol.12 No.5,pp.734-744, 1997-09