SIGSAI30 1 Recent site activity jsaisigsai

(1)

遺伝的アルゴリズムを用いたプレイヤーエージェントによる

デジタルゲームのバランス調整

Balancing digital game by using player agents

generated by Genetic Algorithm

眞鍋和子

¹^∗

三宅陽一郎

¹

Kazuko Manabe

¹

Yoichiro Miyake

¹

1

株式会社スクウェア・エニックス

1

SQUARE ENIX CO., LTD.

Abstract:

The research theme of this project is cost reduction of Quarity Assurance(QA) for digital game. Focusing on QA dealing with ensuring game balance. In this research, we create player agents for the game by Genetic Algorithm and systems to support QA’s work using statistics of agents’ data. Agents behave like real players in eyes of developers of the game. Agents’ data can provide us statistics regarding strength of various items.

1 _はじめに

デジタルゲームは年々, その複雑さを増している. それに伴い, 不具合修正やゲームバランス調整などの品質保証 (Quarity Assurance, QA) にかかる負担も増大してきた. 特に近年大きく市場を広げたモバイル端末向けゲームでは, 従来まで主流だった, 発売した時点で開発が終了する形のゲームは減少している一方で, 発売後も随時新しいアイテムを追加を行うなど, 定期的にアップデートを行う形が主流となっている. この場合には開発サイクルは非常に短いものとなり, QA にかけられる時間が数日という短期間となることも, 一般的に起こり得る.

QAは通常, テスターと呼ばれる人間がプレイヤーの代わりとなってプレイし, 不具合やゲームバランスが崩壊している部分を発見する. しかしこの方法は, 人的資源を用いている以上, 開発プロジェクトに与える負担が大きい. とは言え, 単純にその QA の作業量を減らすことはできない. ただ 1 つの不具合やバランス崩壊がプレイヤーの興を削ぎ, ゲームから離れさせる致命的な要因となることも, 決して珍しいことでない. ごく最近に, 自動 QA の試みも行われるようになってきた [1][2][3]が, まだその数は少ない. ゲームにはそれぞれ固有の特徴があるため, これらの手法をそのまま他のゲームに適用するのは難しい. ゲーム産業界全体で共

∗連絡先：株式会社スクウェア・エニックステクノロジー推進部

〒 160-843 東京都新宿区新宿 6 丁目 27 番 30 号新宿イーストサイドスクエア

E-mail: [email protected]

有できる, 様々な種類のゲームに対する事例が必要とされている.

本研究では, プレイヤーの代わりとなるボットを遺伝的アルゴリズムによって作成し, そのデータの統計を取ることにより, QA 作業の効率化を目指した. 特に今回は, モバイル端末向けゲームにおいて, 短期的な開発サイクル中でのゲームバランス崩壊の発見をゴールとした. 本稿では以降, プレイヤーと同等の行動を取るボットのことを, プレイヤーエージェント, または単にエージェントと呼ぶ.

2 _{題材「グリムノーツ」}

本研究では, グリムノーツ (スクウェア・エニックス, 2016)[5]というモバイル端末向けゲームを研究の題材とした. ここでは, グリムノーツの基本的な知識と用語を説明する. なお, 本稿で説明するグリムノーツは, 2017年 7 月 26 日時点のバージョンである.

グリムノーツは, ゲームの入手や継続にかかる料金は無料で, 特定のゲーム内アイテムの購入にのみ課金される, Free to Play(F2P) と呼ばれるカテゴリに属する. バトルを行い, バトル報酬を元に自己強化するサイクルを回すのが, 基本的なプレイスタイルとなる. バトルはアクションバトル (バトルシーン例: 図 1) であり, プレイヤーがタップ・ワイプなどで操作を行うが, 操作せずにオートバトルを行わせることもできる.

以下に簡単な用語の説明をする.

(2)

図 1: バトルシーン例

ヒーローバトルで戦うキャラクター. ヒーローはそれぞれ, 「アタッカー」(近接攻撃特化), 「シューター」(遠距離攻撃特化), 「ディフェンダー」(防御特化), 「ヒーラー」(回復支援特化) のいずれかの職種カテゴリーに属する. 全部で 300 を超える種類があり, プレイヤーは 1 種類につき最大 1 人までしか所持することはできない. ヒーローにはレアリティレベルが設定されており, 基本的にレアリティが高いほど強い.

主人公バトルには直接参加しないキャラクターで, 1 人の主人公につき, 2 人のヒーローをセットすることができる. バトル中はどちらか 1 人のみが戦い, どちらが参加するかは, プレイヤーはバトル中の任意のタイミングで切り替えることができる. セットできるヒーローの職種は, それぞれ予め決められており, プレイヤーは変更することはできない. なお, 一般的な本やゲームで言う用語と異なり, グリムノーツには主人公と称されるキャラクターが複数おり, 2017 年 7 月時点で 8 人登場する.

リーダープレイヤーが任意で 1 人選ぶ主人公. リーダーとなった主人公は, それぞれが持つリーダー専用スキル (特定の職種の攻撃力アップなど) を発動する. また, プレイヤーがバトル中操作するヒーローは, リーダーにセットされているもののみとなる.

装備ヒーローを強化するアイテムの総称. 直接ヒーローを強化する, 「武器」, 「アクセサリー」, 「衣装」の他 (ヒーロー 1 人につき, 各 1 つ), 武器を強化する「スキルコア」(武器 1 つにつき, 各最大 5 つ. 上限数は, 武器の種類により異なる) がある. 武器とスキルコアにはヒーローと同様, レアリティレベルが設定されており, 基本的にレアリティレベルが高いほど強い.

サポートキャラクターバトルの時のみ, 他のプレイヤーから 1 人だけ借りる主人公. パーティ内の主人公 4 人は全て違うキャラクターでなければならないが, サポートキャラクターは他プレイヤーの主人公であるため, セットされているヒーローは, 自キャラクターのヒーローと同じものになる可能性がある.

パーティリーダー, サポートキャラクターを含む, ヒーローや装備をセットした主人公 4 人のチーム. バトルはこのパーティ単位で行う. サポートキャラクターを除くパーティ編成は, バトル中以外であればプレイヤーが変更できる.

パーティの階層構造を以下に示す. なお, ヒーローより下位の要素については, 2 度目以降は省略している.

パーティ

主人公 1(リーダー) ヒーロー 1

衣装 1

アクセサリー 1 武器 1

スキルコア 1 スキルコア 2 スキルコア 3 スキルコア 4 スキルコア 5 ヒーロー 2

主人公 2 ヒーロー 3 ヒーロー 4 主人公 3

ヒーロー 5 ヒーロー 6

主人公 4(サポートキャラクター) ヒーロー 7

ヒーロー 8

バトルは, リアルタイムで進行する. ヒーローと敵キャラクターは, 攻撃をすることによって相手の体力の数値を減らす (ダメージを与える) ことができる. ダ

(3)

メージの数値は, お互いの攻撃力・防御力等のパラメータによって計算される. 体力が 0 になると戦闘不能状態になり, 以後は戦闘に参加することはできない. バトルの勝利/敗北条件は, バトルの種類によって異なる.

ヒーローは固有の必殺技を持っており, 特定の条件下で発動させることができる. 敵への範囲攻撃や全体回復等, その効果は大きい. ヒーローやスキルコア等が持つパラメータの一つに, 火や氷と言った属性値がある. ダメージ値を上昇させる効果を持つが, 特定の組み合わせはその効果が打ち消しあってしまう. 属性を持つ必殺技との組み合わせや, 敵の弱点属性など, 考慮すべき点は多い.

グリムノーツでは, 新しい装備やヒーローは 1-2 週間に 1 回程のペースで追加される. それらはプレイヤーにとって, 手に入れたいと思う程強くなければならない. しかし強すぎると, プレイヤー全員がそれを使うようになり, ゲームの面白さが失われてしまう. このバランス調整は微妙なものであり, かつゲームのエンターテインメント性に関わる, 非常に重要な点である. この調整を短期間のうちに行わなければならないが, 武器やヒーローにはそれぞれ数百の種類があり, その組み合わせ数は概算で 10⁹⁰程となる. 全ての組み合わせを限られた時間の中で試すことはできず, 開発者の蓄積した経験を基に, バランス調整は行われている.

本研究は, 最終的には様々なゲームに適用することを目標としている. グリムノーツには, 固有のダメージ計算式や特徴があるものの, パーティ編成とバトルがゲームの核であるという点において, 他の多くのゲームと共通する.

3 遺伝的アルゴリズムによるグリム

ノーツのプレイヤーエージェント

の成長

本研究では, プレイヤーエージェントのパーティ編成を改善していくのに, 遺伝的アルゴリズム (Genetic Algorithm, GA)[4]を用いた. パーティ編成の遷移状況の可視化が可能なこと, GA が組み合わせ最適化に適していること, 実装が容易であることがその理由である.

GAは, 生物の進化のメカニズムを模倣したモデルである. 本稿で用いられる GA の基本用語について説明する.

個体 1 つ以上の染色体によって特徴づけられた, 解の候補

遺伝子個体の形質を規定するもの染色体遺伝子の集合

適応度個体の環境に対する適応の度合い

GAについては様々なアイディアが議論されており, そのアルゴリズムは一意に決まってはいない. ここでは, 本研究で用いた GA の処理フローについて説明する. 1. 染色体を無作為に生成し, 現世代に初期個体群を

作成する

2. 現世代の各個体の適応度を計算

3. 現世代の中で最も高い適応度を持つ個体を, 次世代にコピー (エリート保存)

4. 一定確率で個体を抽出し, 遺伝子を無作為に変化させた個体を次世代に作成 (突然変異)

5. 適応度に応じて現世代から個体を選択し, それらの遺伝子を組み替えた, 新しい個体群を次世代に作成 (交叉)

6. もし指定した世代数に到達したら → 終了それ以外 → 次世代を現世代として, 2 に戻るこの手順に沿って, グリムノーツのパーティ編成の改良を行った.

遺伝子には, パーティ編成の要素, 即ち下記を用いた.

• 主人公

• ヒーロー

• 衣装

• アクセサリー

• 武器

• スキルコア

遺伝子の候補 (対立遺伝子) は, プレイヤーの所持しているもの全てとし, 実際には, それらを表す ID である整数を用いた. この実験では, プレイヤーはどの装備も無限に持っているという設定にしたが, 現実には染色体の長さは有限である. そこで, 同じ種類の装備は 1 つしか持てないユニークカテゴリと, 複数持てるノンユニークカテゴリに分けて扱った.

• ユニークカテゴリ - 主人公, 自プレイヤーヒーロー, 他プレイヤーヒーロー, 衣装

遺伝子長: カテゴリ内の種類数

初期個体群の染色体: 全種類の装備を 1 つずつ遺伝子に設定し, 無作為にシャッフル交叉: 切断点ごとに, 「一方の親の遺伝子のコ

ピー」, 「一方の親の遺伝子のコピー後に, 他方の親の染色体内での出現順に並び替え」の操作を交互に行う (順序交叉) 突然変異: ランダムに遺伝子を 2 つ選択し, 交換する (転座)

(4)

• ノンユニークカテゴリ - アクセサリー, 武器, スキルコア

遺伝子長: 1 パーティの編成に同一の装備を使用できる個数の最大値

初期個体群の染色体: 対立遺伝子の中から無作為に設定

交叉: 切断点ごとに, 交互に親から遺伝子を受け継ぐ (一般的な多点交叉)

突然変異: ランダムに選択した遺伝子を, 対立遺伝子のいずれかに変更する (一般的な突然変異)

全カテゴリの遺伝子を繋げて 1 つの染色体とし, 交叉は切断点を無作為に 5 つ決定して行った.

染色体からパーティ編成へのデコードは, 2 章のパーティ構造のルートを始点に, 深さ優先の順で行った. 各カテゴリにおいて, 対象バトルで指定されている編成条件 (特定の主人公の使用禁止等), 及び上位レイヤーの装備との適合条件を満たしている装備を探索し, 発見次第パーティにセットするという手順とした.

本研究の染色体の構造は, ゲーム固有の要素が GA に極力影響しないようにしている. そのため, パーティ編成から染色体へコード化した後, デコード化で戻すまでの GA の処理は, ゲームのパラメータ仕様変更 (新しいヒーローの追加, 武器の攻撃力変更など) への対応は基本的に必要ない. ゲームデータの更新と, GA の再実行のみで事足りる. また, グリムノーツに限らず, パーティ編成を行ってバトルを行うような, 他のゲームにも適用可能である.

適応度を求めるためには, 個体のパーティ編成を使ってバトルを行い, その結果を利用した. 対象としたバトルは, ゲーム内名称で言う白雪姫想区の「追憶の洞窟」を用いた. このバトルは特別に強い敵 (ボス) は出現しないが, 敵の総数が多い. 勝利条件は全ての敵の討伐, 敗北条件はリーダーの戦闘不能である.

適応度はバトルの勝敗別に, 以下のような方針とした. 敗北時: 味方から敵に与えたダメージの多さ

勝利時: バトルに勝利するのにかかった時間の短さこれらは値の単位が違い, また適応度の高さを示す方向の正負も異なるため, そのままの値では比較ができない. また, 対象とするバトルによって, 敵の数や強さが違うため, ダメージやバトル時間のスケールも異なってくる. そのままの値をルーレット選択に用いた場合, スケールによって選択確率の変化勾配に差が出てしまい, それぞれに合った GA のパラメータ調整が必要になってしまうが, グリムノーツにはバトルが数百種類あるため, そういった各個の調整は現実的には不可能である. そこで, それぞれのダメージと時間を, その世代

の全個体のバトル終了後, 指定した範囲にマッピングを行ったものを適応度とする. 勝利した個体 i = 1..m のバトル時間を, tⁱ,その中で最小値と最大値を持つ個体をそれぞれ m1, m2 とし, マップ先の値の範囲を [c¹, c²](t^m1̸= t^m2, c¹ ̸= c²)とした時, 個体の適応度 fⁱは, c1, c2からの位置関係 (値の差分の比率) が, tⁱの t1, t2

に対する位置関係と等しくなるような値が適応度であると定義した. 式は以下のようになる.

ti== tm1の時, fi = c1

tⁱ== t^m2の時, fⁱ = c² それ以外の時,

c²−fⁱ fi−c1

= ^t^m2⁻^tⁱ ti−tm1

fⁱ = ^(t^m2⁻^tⁱ^)c¹^{+ (t}ⁱ⁻^t^m1^)c² t^m2−t^m1

敗北時についても, バトル時間をダメージに置き換え, 範囲 [d¹, d²]を指定して同様のマッピングを行う. バトル時間に関わらず, 常に勝利は敗北より大きな差をつけて適応しているという考えの元, c1 = 1.0, c2= 0.3, d1= 0.04, d2= 0.2とした. ここで, c1≥c2となっているのは, 勝利時のバトル時間が, 短いほど高い値にマッピングされるようにするためである.

前述のように定義した適応度を用い, 次世代に保存するエリートの選択や, 交叉を行う. 交叉に関しては, 適応度の高い個体ほど親として選ばれやすくなる手法 (ルーレット選択) を用いた. 現世代の中の各個体 i = 1..n に関して, 適応度がそれぞれ fⁱである時, 個体 k(1 ≤ k ≤ n) が親として選ばれる確率は,

P^k = f^k/Σⁿi=1fⁱ となる.

適応度を求めるために行うバトルは, 実際のバトルではなく, 敵や味方の攻撃力や防御力などを基にして計算を行うシミュレーションを用いた. シミュレーションバトルでは, 必殺技とヒーローの切り替え機能は省略しており, 空間・移動の概念は, 攻撃頻度や被ターゲット率などのパラメータに置換している. これらのパラメータは, バトルについての知識が深い, グリムノーツ開発者が調整した. 実際のバトルと同様, 確率的要素が含まれるため, 全く同じパーティ編成でも結果が異なることがある. シミュレーションバトルの最大のメリットは実行時間であり, 実際のバトルが数分かかるのに対し, 実験で用いた下記の計算機において, シミュレーションバトルは 1-2 秒 (バトルの種類や進行具合, パーティ編成等によって, おおよそこの範囲内で変動する) で実行することができる (シングルスレッド. 本実験では並列処理は行なっていない).

• OS: Windows⃝^R 10 (64bit)

(5)

• CPU: Intel Core⃝^R i7-4790K (4.00GHz)

• Memory: 32GB

この計算機を用い, 1 世代の個体数 50, 最大世代数 500とし, GA を用いてプレイヤーエージェントのパーティ編成改善を行った. ここで設定した最大世代数は, 上記計算機で 10 時間程度で到達できる世代数とした. GAを用いた実験は, プレイヤーのヒーロー・装備の所持状況を変えて 2 種類行った. また, GA を用いずに, 無作為の組み合わせでパーティを編成し, それらのバトル時間の計測を行った.

実験 1

プレイヤーは全ての主人公・ヒーロー・装備を無限に所持しているとし, パーティ編成の組み換えを行った. 図 3 に, バトル結果の遷移を示す. 勝利した個体のうち, 各世代において最短のバトル時間の遷移を実線, 敗北した個体のうち, 各世代において最大の与ダメージの遷移を破線で表している. 横軸が世代, 左縦軸がバトル時間, 右縦軸が敵に与えた総ダメージとした. 無作為に個体生成された第 1 世代は全て敗北しているが, 第 17世代で初めて勝利する個体が出現するまで, 急激にその与ダメージを伸ばした. それからほとんど変化がないのは, 敵の総体力は約 28 万であり, それ以上のダメージを与えた個体は勝利するためである. 勝利個体のバトル時間は, 第 17 世代での出現時 816.5 秒であったが, 以降継続的に改善され, 最短時間を記録した 494 世代目の 571 秒まで, 約 3 割バトル時間を短縮することに成功した.

図 2: プレイヤーエージェントが行ったシミュレーションバトルの結果遷移 (対立遺伝子に全レアリティのものを使用)

実験 2

実験 1 の初期世代のパーティ編成を確認すると, レアリティの低いヒーローや装備が混じっていることがわかった. 基本的にレアリティの低い装備は高い装備に比べて弱いため, これらを対立遺伝子から除外して実験を行なった. 図 3 に, バトル結果の推移を示す. 横軸, 縦軸, 線種は, 全て実験 1 と同様である. 敗北個体の与

ダメージは, 第 1 世代から実験 1 より高い値を示し, 勝利個体の最短バトル時間は 359 世代目の 467.75 秒と, 実験 1 の最短時間から更に 2 割弱の改善ができた.

図 3: プレイヤーエージェントが行ったシミュレーションバトルの結果遷移 (対立遺伝子から低レアリティのものを除外)

実験 3

GAを用いず, 無作為に 25000(実験 1, 2 で生成した個体数: 50 個体 x500 世代と同数) のパーティを生成して, バトルを行わせた. そのうち最もバトル時間が短いものは 600.5 秒, 次いで 644.25 秒, 671 秒であった. この結果から, GA を用いた実験 1, 2 は, 効率的に探索を行えていることがわかる.

以上のようにして得られた, バトル時間が最短のパーティの編成を見ることで, ゲーム開発者は予想外の結果になるパーティの組み合わせが存在しないか, リリース前に確認することができる. これは, 場合によっては強いと言うような, 例外的なパーティを発見するのに役に立つ.

GAは適応度の高い個体の遺伝子を次世代に引き継がせるため, 自然, 適応度の高い個体に含まれる遺伝子がパーティに用いられる確率が高くなる. そこで, 利用頻度がその遺伝子の価値であるとし, 1 パーティ内に含まれる回数を頻度として統計を取った. 利用頻度が高い遺伝子は, 他の遺伝子に依存しない, 総合的に強い遺伝子であると言える. 統計を取るためのプレイヤーエージェントを 9 体作成し, それらに含まれる全ての勝利個体を対象データとした. 独立したエージェントを複数用いることで, 局所解に陥るエージェントが現れたとしても, 総合的にその利用頻度を集計することができる. ヒーローに関して利用頻度の高かった上位 10 位を表 1 に示す. なお, 整数以外は小数点 2 位までとしている.

利用頻度に有意な差が現れているため, 遺伝子として用いられたヒーローの強さには, 偏りがあることを示している. ただしゲームバランスとしては, パーティにヒーローを用いるためのゲーム内コストも考慮しなければならない. コストはゲームによって様々だが, グリムノーツではヒーローを得るためには貴重なアイテ

(6)

表 1: 勝利個体に含まれるヒーロー遺伝子の利用頻度 Rank Frequency Count Battle time average

1 0.71 138407 533.47 2 0.58 114426 536.66 3 0.45 87945 498.04 4 0.32 62871 517.22 5 0.32 61894 577.96 6 0.24 47642 501.91 7 0.23 46063 539.18 8 0.20 39933 502.56 9 0.20 39411 521.92 10 0.20 39135 505.16

ムが必要になったり, また, 入手時期が限られていたりすることがコストだと言える. コストが高いヒーローや装備は強力であることは, ゲームバランスとしては自然である. したがって, 実際のゲームバランス調整作業は, 開発者が強さとコストを比較しながら行う必要がある. なお, 表のデータ全体をバトル時間昇順で並び替えると, 利用頻度が低いもののバトル結果に大きい影響を与える可能性があるヒーローが, 上位に来ることになる. これらもまた, バランス調整の対象となる可能性が高い.

4 _むすび

遺伝的アルゴリズムを用い, グリムノーツにおいてプレイヤーエージェントのパーティ編成を効率的に探索することができた. また, そのパーティ編成の試行ログを元に, 価値の高いパーティの要素を探し出すことができた. ただしシミュレーションバトルを用いているため, 省略やパラメータでの置き換えがされている要素が, 程度は不明だが結果の正確さに影響を及ぼしていることは確かである. 実際のバトルの高速化を行うことで, シミュレーション精度の測定, 更には GA の成長そのものを実際のバトルを使って行うことが可能になる. 実際のバトルの実行速度向上, 及び GA プロセスの実行時間の短縮が今後の目標となる.

謝辞

本研究を行うに当たり, 元気株式会社の皆様より, 技術的支援や貴重なご意見を賜りました. 心より感謝致します.

また, 本研究に多大なるご協力をいただきました, グリムノーツ開発・運営の皆様に, 感謝を申し上げます.

商標

Windowsは, 米国 Microsoft Corporation の米国およびその他の国における登録商標です.

Intel Coreは, アメリカ合衆国および / またはその他の国における Intel Corporation またはその子会社の商標です.

その他掲載されている会社名, 商品名は, 各社の商標または登録商標です.

参考文献

[1] AiGameDev.com: Making Designers Ob- solete? Evolution in Game Design, http://aigamedev.com/open/interview/evolution- in-cityconquest/ (2017-11-13参照)

[2] 友部博教, 半田豊和: AI によるゲームアプリ運用の課題解決へのアプローチ, CEDEC2016(2016), http://cedil.cesa.or.jp/cedil sessions/view/1511 (2017-11-13参照)

[3] 折田武己: ゲーム開発におけるデバッグ作業の自動化 ∼ OpenCV の「眼」で捉え、Python の「脳」が思考し、Appium の「指」で動かす, CEDEC2016 (2016), https://cedil.cesa.or.jp/cedil sessions/view/1575 (2017-11-13参照)

[4] Stuart Russell, Peter Norvig: エージェントアプローチ人工知能第 2 版, 共立出版 (古川康一監訳), pp.117-119(2008)

[5] SQUARE ENIX CO., LTD.: グリムノーツ — SQUARE ENIX, http://www.grimmsnotes.jp/ (2017-11-13参照)