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

Title

人間らしさを考慮したテストプレイヤを用いる迷路の自動生成と難易度評価

Author(s)藤平, 啓汰; 池田, 心; シュエ, ジュウシュエン

Citation

ゲームプログラミングワークショップ2021論文集,
2021: 192‑199

Issue Date

2021‑11‑06

Type

Conference Paper

Text version

publisher

URL

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

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

Description

第26回ゲームプログラミングワークショップ(GPW‑21)，2021‑11，オンライン開催

Japan Advanced Institute of Science and Technology

The 26th Game Programming Workshop 2021

人間らしさを考慮したテストプレイヤを用いる
迷路の自動生成と難易度評価
藤平 啓汰1,a)

シュエ ジュウシュエン1,b)

池田 心1,c)

概要：ロールプレイングゲーム（RPG）のマップデザインにおいて，プレイヤの進行方向を適切に誘導す
ることは重要な課題のひとつである．プレイヤに対する誘導があまりに露骨なものだと，プレイヤに不快感を与えゲームの面白さを損ねてしまう可能性があるからである．そのため，RPG では，プレイヤの行動
傾向に応じて自然に誘導するマップが求められることが多い．本稿では，自然に誘導する RPG マップの自動生成に向けた研究の初期段階としてまず，人間プレイヤの分岐選択傾向に基づいた難易度の迷路を自動生成する．具体的には，分岐選択傾向を教師あり学習によって調査し，その傾向を模倣したテストプレ
イヤを作成，そのテストプレイヤを用いて「人間プレイヤだからこそ難しい迷路」を生成する．被験者実験の結果，テストプレイヤを用いて自動生成した難しい迷路は，実際の人間プレイヤに対しても難しい迷路であることが示された．
キーワード：自動生成，迷路，難易度，誘導，RPG

Procedural Maze Generation with Test Player
Considering Human-likeness
Keita Fujihira1,a)Chu-Hsuan Hsueh1,b)

Kokolo Ikeda1,c)

Abstract: In the design of maps for role-playing games (RPG), guiding players properly is one of the big
challenges. Too explicit guidance, such as simple single paths and ﬂashing marks, may harm players’ playexperience. Therefore, it is better to have maps that guide players according to their behavioral tendencies.
In this paper, as the ﬁrst step of our research, we aim to know the diﬃculty of mazes from human players’
tendencies and generate mazes accordingly. We investigate the tendencies by supervised learning and use
the learned model to create a test player considering human-likeness for maze generation. In evaluation experiments, the results show that our method succeeded in generating mazes with diﬃculty matching humanplayers’ tendencies.
Keywords: Procedural content generation, maze, diﬃculty, guidance, RPGAI が応用され，学術・産業界を問わず注目を集めている．

1. はじめに

PCG の研究は，横スクロールアクション [1] や ﬁrst-person

ゲーム分野ではこれまで，強いコンピュータプレイヤのshooter（FPS）[2] といった有名ジャンルを対象にするこ作成等に Artiﬁcial Intelligence（AI）が用いられてきた．

とが多い．一方，日本で親しまれているファイナルファン

さらに近年では，Procedural Content Generation（PCG）

タジーやドラゴンクエストに代表されるロールプレイングと呼ばれるゲームコンテンツの自動生成技術の研究にもゲーム（RPG）を対象とする研究は比較的少ない．

RPG においてプレイヤは，最後の大ボスを倒すなどス
1

a)
b)
c)

北陸先端科学技術大学院大学
Japan Advanced Institute of Science and Technology, Nomi,
Ishikawa 923-1211, Japankeita.fujihira@jaist.ac.jp
hsuehch@jaist.ac.jp
kokolo@jaist.ac.jp© 2021 Information Processing Society of Japan

トーリー上の最終目的以外にも，ダンジョン探索やアイテ
ム探しといった多様な目的を持つ．その目的を達成しようとするなかで，例えばダンジョン内で長時間迷ってしまったり，逆にレアアイテムが簡単に手に入ってしまったりす-192-

The 26th Game Programming Workshop 2021
ると，ゲームの面白さが損なわれる可能性がある．そのた

2.2 テストプレイヤを用いるコンテンツの自動生成

め，ゲームデザイナはプレイヤが迷いすぎないように助け

PCG には様々なアプローチが存在するが，一般的なアプ

たり，アイテムからあえて遠ざけたりするために，マップローチとして「生成したコンテンツを何らかの指標で評価

構造や敵・アイテムの配置方法によりプレイヤを誘導する

し，その中から評価値の高いものを選んだり，より評価値ことも多い．しかし，その誘導が一方的で露骨なものであが高くなるよう変化を加えたりする手法」がよく知られてれば，RPG の醍醐味である探索の高揚感を喪失させ，ゲーいる．このアプローチの評価部分では，2.1 節で紹介した

ムの面白さを損ねてしまう可能性がある．RPG では，プ研究のようにコンテンツの特徴から評価する方法のほか，

レイヤが「自分は能動的に行動している」と感じつつも，

テストプレイヤによるシミュレーション結果から評価す

実はゲームデザイナの意図に沿った行動をとる，つまりプる方法がある．テストプレイヤの実装方法は，ヒューリス

レイヤが自然に誘導されるマップがしばしば求められる．

ティック [9] やモンテカルロ法 [10]，A*アルゴリズム [11]，通常，そのような複雑な特性を持つマップの作成は，ゲー

強化学習 [12] など様々である
誤解を恐れずに言えば，PCG の主目標は「人間プレイ

ムデザイナによって手作業で行われるため，ゲーム開発にヤ」が楽しめるコンテンツを生成することであり，テスト

おける高コストな作業とされている．
本研究の主目標は，プレイヤを自然に誘導する RPG マッ

プレイヤが人間プレイヤからかけ離れた行動をとると，適プを自動生成することである．RPG マップの複雑さを考切な評価結果を得られない可能性が高くなる．そのため，

慮し，研究の初期段階では敵やアイテムを含まず，壁と通例えば，吉田ら [9] は「人間プレイヤは，正確で素早い操作

路のみで構成される 2 次元迷路マップを生成対象とする．

が苦手である代わりに，大局的な判断によって余裕を持っそのうえで，人間プレイヤの分岐選択傾向に基づいた難易

た回避を行うことが多い」という観点からいくつかの工夫

度の迷路を自動生成することを本稿の目的とする．まず，を施し，シューティングゲームのテストプレイヤに人間ら教師あり学習により分岐選択確率予測モデルを構築し，そしさを取り入れステージの自動生成に用いた．ただし，このモデルから人間プレイヤの傾向を調査する．次に，予測のように人間らしさを考慮したテストプレイヤを用いるモデルをベースとする人間らしさを考慮したテストプレイ

PCG の研究は，我々の知る限り比較的少ない．その理由

ヤを作成し，迷路の自動生成に用いる．最後に，自動生成として，（1）対象ゲームによっては単純なテストプレイヤ

した迷路を評価するために被験者実験を実施する．

でさえも作成が困難，（2）対象ゲームにおける人間らしさの抽出が困難であることが挙げられる．本稿の場合，詳細

2. 関連研究は 3 章で述べるが，対象ゲームがシンプルな迷路であるた

本章では，「迷路の自動生成」「テストプレイヤを用いる

め（1）については容易である．
（2）については，人間プレ

コンテンツの自動生成」に関する研究をいくつか紹介する．

イヤの分岐選択に着目し，教師あり学習によって人間らしさを抽出する．

2.1 迷路の自動生成
一般的な迷路生成アルゴリズムとして，穴掘り法 [3] や

3. 人間プレイヤの分岐選択傾向の調査

壁伸ばし法 [4]，棒倒し法 [5] などが挙げられる．難易度に迷路の種類は非常に多く，次元数や正解路の一意性，外焦点を当てた場合には，Genetic Algorithm（GA）などの観など様々な観点で分類できる．本稿では，N × N マスで

メタヒューリスティックが適用されることも多い [6][7]．

構成される 2 次元格子状の全域木型迷路を対象とする．本

Adams ら [6] は，Cellular Automaton（CA）を用いて迷路

章では，対象迷路の設定や教師あり学習用のデータを収集を自動生成し，CA のルールを進化させるために正解路長するため実施した被験者実験の概要について述べた後，学や行き止まりの数を評価値とする GA を適用した．また，習内容とその結果について報告する．

Kwiecień[7] は，正解路長や方向転換数，分岐点数などを評価値とする Cockroach Swarm Optimization を用いて，通3.1 学習データ収集のための被験者実験
本稿が対象とする迷路の特徴を以下にまとめる．図 1 は路構造が複雑な難しい迷路を自動生成した．
正解路長や分岐点数などの特徴が迷路の難易度に影響しその例である．

ていると報告する研究は少なくない [8]．例えば，分岐点が多いほどプレイヤの迷いが発生し得る地点が増えるため，難易度に関連すると報告されることは合理的であると考える．しかし，人間だからこそ迷ってしまう，あるいは迷うはずのない分岐点も迷路には存在するはずであり，その点を踏まえて難易度を調整すべきだと考える．本稿では，そのような人間らしさを考慮した難易度の迷路を生成する．

© 2021 Information Processing Society of Japan-193-• 迷路はディスプレイ上に映り，プレイヤはキーボード入力による操作を行う．

• プレイヤが辿ってきた道のりは，ディスプレイ上に可視化されない．

• 迷路サイズは，31 × 31（S），41 × 41（M），51 × 51
（L）のいずれかである．

• 制限時間があり，制限時間を過ぎてもゴールに辿り着The 26th Game Programming Workshop 2021

(a)

(b)

(a)

図 1 S サイズの迷路の例：（a）Wide 迷路，（b）Narrow 迷路．左(b)

図 2 分岐点となる通路マスとそうでない通路マスの例：（a）分岐点上隅の黄色マスはスタート，右下隅のピンク色マスはゴール，ではない，（b）分岐点

赤色マスはプレイヤの現在地をそれぞれ示す．

いていない場合，プレイヤはゲームオーバーとなる．
制限時間は迷路サイズによって異なる．S サイズは 80
秒，M は 100 秒，L は 150 秒である．

• 通行可能なマスと通行不可能なマスのみで構成され，それぞれを通路マス，壁マスと呼ぶ．

• 迷路の外周部分は，壁マスで構成される．

図 3 学習データの水増し方法• スタートは迷路の左上隅，ゴールは右下隅に設置する．
• プレイヤの目的は，スタートからゴールに辿り着くことである．

に到達可能な通路マスが，1 つでも Narrow 視界範囲外にある」ならば，その通路は「未確定」とする．例えば，図• プレイヤは 1 回の行動につき 1 マス分のみ，現在地の2(a) でプレイヤの右方向に注目すると，その先（緑斜線の上下左右に隣接するいずれかの通路マスに移動できる．

部分）が行き止まりなのか，ゴールへ続くのか判断できな• 迷路左上の頂点座標を（1, 1）とすると，通路マスのいため，右方向に続く通路は未確定となる．一方，左方向

配置候補となるのは，x 座標，y 座標，あるいはそのの先（青縦線の部分）は，その通路を構成する通路マスが両方が偶数となるマスである．言い換えれば，x，y 座

全て見えるため未確定ではない．なお，この「未確定」の標がどちらも奇数の場合，そこは必ず壁マスとなる．

判定は，現在の視界で得られる情報のみで行われることに• ループ（閉路）は存在しない．到達できない通路マス注意されたい．つまり，これまでのプレイヤの移動によっも存在しない．言い換えれば，プレイヤが同じ通路マて得られた情報を覚えていれば行き止まりと分かる場合でスを 2 回以上訪れない限り，スタートとゴールを結ぶも，上記条件を満たしていれば未確定として扱う．

経路（正解路）は必ず一意に定まる．

これを踏まえたうえで，「プレイヤが進行してきた方向• プレイヤは，以下のいずれかの視界状態を持つ．

の通路を除き，未確定な通路が 2 つ以上接続されている通- Wide：図 1(a) のように迷路全体が見える状態．

路マス」を「分岐点」と定義する．図 2(b) において，プレ- Narrow：図 1(b) のようにプレイヤを中心とする円のイヤの現在地は，2 つの未確定な通路と接続されているた内部のみ見える状態. 円の直径は，迷路の一辺の長さ

め分岐点となる．

の半分である．例えば，S サイズの場合，円の直径は3.2.1 学習内容

31/2 = 15.5 となる．

この教師あり学習では，人間プレイヤの分岐選択についこの設定のうえで，実験に使用する迷路は穴掘り法 [3]て予測する．目的変数となるのは，3.1 節の実験データからと壁伸ばし法 [4]，棒倒し法 [5] のいずれかを用いて生成し算出した被験者の分岐選択割合である．例えば，右と下方た．実験に参加した被験者は 20 人で，各被験者はサイズ向に進行可能な分岐点において，20 人中 16 人のプレイヤや視界状態を変更しながら計 21 個の迷路をプレイした．

が右方向を選んだ場合，右方向の選択割合は 16/20 = 0.8となる．この選択割合を学習するため，著者はこれまで 15

3.2 教師あり学習による分岐選択確率の予測個の特徴量を用いていた [13]．本稿では，新たに特徴量を

本節では，分岐点における人間プレイヤの分岐選択確率を予測する教師あり学習について述べる．学習内容を述べ追加することで予測精度の向上を図る．学習に用いる特徴
量の詳細については付録 A.1 を参照されたい．

る前に，本稿における「未確定」と「分岐点」を定義する．

実験データより，Wide 迷路は 147 個，Narrow 迷路は

この定義は Wide 迷路と Narrow 迷路に共通である．どち

197 個の学習データをそれぞれ得ることができた．これららの場合も，Narrow 迷路の視界状態を用いて定義する．

の学習データは，プレイヤが分岐点を初めて訪れたときプレイヤの現在地からある方向に注目したとき，「その先のデータのみを収集対象とした．さらに，図 3 のように x© 2021 Information Processing Society of Japan-194-

The 26th Game Programming Workshop 2021
表 1 旧特徴量 [13]，新特徴量を用いた各予測モデルの精度比較
視界状態

Wide

Narrow
(a)

予測モデル

RMSE

相関係数

旧特徴量・正規化なし

0.29

0.55

新特徴量・正規化なし

0.28

0.58

新特徴量・正規化あり

0.26

0.66

旧特徴量・正規化なし

0.27

0.53

新特徴量・正規化なし

0.23

0.70

新特徴量・正規化あり

0.21

0.74

(b)

図 4 予測モデルによる分岐選択確率の予測結果（横軸：正規化後のには（1）上や左方向よりも下や右方向を選ぶ傾向と（2）

予測値，縦軸：実測値）：（a）Wide 迷路，（b）Narrow 迷路

下と右の両方向が選択可能な場合，直進方向を選ぶ傾向が座標と y 座標を入れ替えたデータを作成することで学習データ数を 2 倍にした．学習には決定木ベースの勾配ブースティングモデルである LightGBM[14] を，精度検証にはleave-one-out 交差検証を用いた．
また，予測モデルは 1 つの分岐点に関する複数の選択割
合を別々に予測するため，予測値の和が 1.0 になるとは限らない点に注意されたい．本節と後述する 4.1 節では，1つの分岐点に関する予測対象が n 個あるとき，予測値の和が 1.0 になるように次式を用いて各予測値 pi を正規化し，確率分布へと変換している．

pi

f (pi ) = ∑nk=1 pkあると考える．図 5 は，形状の異なる分岐点ごとにまとめた，被験者たちの各方向の選択割合である．読みやすさの観点から割合が 0.5 未満のデータを，信頼性の観点からサンプル数が 20 未満のデータをそれぞれ除外している．
図 5 より，下や右方向の選択割合が高いことが分かるが，
これはゴールが迷路の右下隅に固定されているためだと推測できる．また，Narrow 迷路において最も重要度が高い

cos goal（重要度 0.35）は，予測方向が右や下であれば値が大きくなり，そうでなければ値が小さくなる特徴量である．つまり，cos goal が最も重要であるとする結果は，予測モデルが人間プレイヤの傾向（1）を十分に反映した結果であると言える．

(1)

さらに，図 5 において，下と右の両方向が選択可能な場

3.2.2 学習結果

合（赤矢印）に注目すると，いずれも直進方向の選択割合

図 4 は，横軸に予測モデルによる予測値を正規化した値，が高いことが分かる．Narrow 迷路で 2 番目に重要度が高

縦軸に実験データから得た実測値をとる散布図である．表

い特徴量は is straight（重要度 0.15）であり，これも予測

1 は，以前の結果 [13] も含めた，予測値と実測値の二乗平モデルが傾向（2）を十分反映した結果であると言える．

均平方根誤差（RMSE），相関係数をまとめたものである．

RMSE は小さいほど，相関係数は大きいほど予測精度が高

4. テストプレイヤによる迷路の難易度評価

いことを意味する．したがって，Wide，Narrow 迷路とも

迷路の生成・難易度評価には，人間らしさを考慮したテに，特徴量を追加したことによる改善，および予測値の正ストプレイヤを用いる．本章では，テストプレイヤの作成規化を行ったことによる改善が表 1 より確認できる．

方法と難易度の定義，難易度の評価方法について述べる．

人間プレイヤの分岐選択傾向を調査するため，予測モデ
ルから特徴量重要度を算出した．特徴量重要度とは，学習

また，テストプレイヤの作成について，視界状態を Narrowと仮定していることに注意されたい．

に用いた特徴量が予測にどの程度貢献しているのか数値化したものである．

4.1 人間らしさを考慮したテストプレイヤ

Wide 迷路すなわち視界制限のない迷路において，最も重要度が高い特徴量は area（重要度 0.5）であった．特徴

テストプレイヤの行動は，その現在地となる通路マスが分岐点（3.2 節で定義）であるかどうかで異なる．

量の詳細は付録 A.1 で述べているため省略するが，area は

通路マスが分岐点ではない場合の行動をアルゴリズム 1「視界範囲に関係なく，予測方向の先にある到達可能な全てに示す．アルゴリズム 1 では迷路を，スタートを根とするの通路マスの個数」を示す特徴量である．area の値が小さ木に見立てたとき，テストプレイヤの現在地の親ノードをければ，続く通路が行き止まりであるか，ゴールに繋がっ「前のマス」，子ノードを「次のマス」と呼ぶ．また，テスているのか判断しやすくなる．一方，area の値が大きい

トプレイヤは，図 6(a) のようにゴールが見えている場合をと，特に制限時間がある中では，その判断が比較的難しく除き，図 2(a) の青縦線部分のような未確定でない通路に含なるはずである．そのため，area の値が小さい不正解路にまれる通路マスには移動しない．アルゴリズム 1 において続く方向は選択確率が低く，値が大きい方向は正解・不正

特に重要なのが 8・9 行目であり，条件（1）と（2）に該当

解にかかわらず選択確率が高くなるといった理由により，する状況の例を図 6(b) と 6(c) にそれぞれ示す．これは人area が重要視されたと推測する．

間プレイヤの行動により近づけるため導入したヒューリス

Narrow 迷路について結論から述べると，人間プレイヤ© 2021 Information Processing Society of Japan-195-

The 26th Game Programming Workshop 2021

図 5

Narrow 迷路を対象とし，形状の異なる分岐点ごとにまとめた被験者の分岐選択割合

アルゴリズム 1 分岐点ではない通路マスにおける行動
Input: state : テストプレイヤの状態
1: if state = 通路を進む then2:
次のマスに移動する
3: else if state = 最後に通過した分岐点まで戻る then
4:
前のマスに移動する
5: end if
6: if （未確定でない通路を除いたうえでの）分岐点に着いた then7:
state ← 分岐点にいる
8: else if （1）外周に隣接するマスをゴールとは逆方向に進んだ
or（2）続く通路の先が全て行き止まりであることが，視界範囲内で判明した then9:state ← 最後に通過した分岐点まで戻る
10: else
11:
state ← 通路を進む
12: end if

(a)

(b)

(c)

図 6 テストプレイヤの行動と状況の例：（a）ゴールが見えている
状況，（b）右側の外周に隣接する通路を上方向に動いた状況，（c）続く通路の先にある全ての行き止まりが見えた状況することがあるのではないかと推測した結果，この条件を適用することとした．また，この条件を正解路上の分岐点に適用すると，テストプレイヤがゴールに辿り着かない可能性があるため，不正解路上の分岐点のみに適用した．

ティックである．例えば，条件（1）について，対象迷路はゴールが迷路の右下隅に設置されループも含まないため，

4.2 迷路の難易度とその評価方法

外周に隣接する通路上で上や左方向に進むことはその通路

迷路の難易度は，4.1 節のテストプレイヤが迷路を解いが不正解路であることを意味する．被験者実験でも，そのたときの歩数をもとに評価する．ある迷路のスタートからような通路を突き進む被験者はあまり見られなかった．

ゴールに到達するまでに必要な最短歩数を nshortest ，テス

分岐点におけるテストプレイヤの行動は，その分岐点を

トプレイヤがその迷路を解いたときの歩数を ntotal ，その初めて訪れたかどうかで異なる．ある分岐点を初めて訪れ差を nextra = ntotal − nshortest としたとき，nextra が大きた場合，3.2 節の予測モデルを用いて全ての未確定な通路

いほど難しい迷路であると定義する．また，テストプレイの選択確率を予測し*1 *2 ，その確率分布に従い進む先をラヤの行動にはランダム性があるため，1 試行ではなく複数

ンダムに選択する．その分岐点を訪れるのが 2 回目以降の回試行したときの nextra の平均値と標準偏差をもとに難易場合には，未訪問かつ未確定の通路のみを予測対象とした度を評価する．本稿では，以下の 5 つの難易度を用意した．

うえで選択確率を予測し進む．

• easylowSD (nextra の平均値：小，標準偏差：小)ただし，不正解路上*3 のある分岐点で 2 回目以降の予測• moderatelowSD (nextra の平均値：中，標準偏差：小)を行う場合に限り，「3.2.1 項で述べた正規化処理前の予測• moderatehighSD (nextra の平均値：中，標準偏差：大)値が 0.5 未満ならば，その予測値を 0.0 に変換する」とい• diﬃcultlowSD (nextra の平均値：大，標準偏差：小)う条件を加える．この理由について，例えば人間プレイヤ• diﬃculthighSD (nextra の平均値：大，標準偏差：大)は，もし不正解の方向に進んだとしても，その探索結果から迷路構造の一部を把握することができる．そのため，次5. 迷路評価の被験者実験

回以降の分岐選択時，人間プレイヤなら「こちらは不正解

テストプレイヤの評価した難易度が，人間プレイヤが実路っぽい」など見当をつけ，未訪問の通路であっても無視際に解いたときの結果に適合するのか検証するため被験者

*1
*2
*3

図 6(a) のようにゴールが見えている場合には，予測ステップを省きゴールへ続く通路を進む．
分岐点進入前にテストプレイヤがいた方向は予測対象から除く．
正解路か不正解路であるかは本来プレイヤには区別できないが，本稿で用いたテストプレイヤにはこの情報を与えている．

© 2021 Information Processing Society of Japan

実験を実施した．本章では，その実験結果を報告する．

5.1 実験内容-196-

本実験に参加した被験者は 10 人である．公正な評価のThe 26th Game Programming Workshop 2021
表 2

easylowSD
順番

mean

迷路を解いた順番と被験者による nextra の平均値と標準偏差（SD）
moderatelowSD
moderatehighSD
diﬃcultlowSD

SD

順番

diﬃculthighSD

mean

SD

順番

mean

SD

順番

mean

SD

順番

mean

SD

5

200

194

1

71

43

3

53

113

4

299

173

2

257

180

9

72

131

10

241

197

6

243

206

7

364

123

8

231

162

14

69

44

12

285

114

11

195

209

13

371

121

17

447

162

18

77

116

19

220

137

15

135

214

16

406

150

20

368

200

21

175

151

23

228

140

24

232

201

22

262

133

25

265

234

26

48

47

29

178

152

27

228

180

28

517

159

30

104

173

33

27

25

32

235

42

31

314

291

34

374

77

35

140

184

Avg.

95

101

Avg.

208

118

Avg.

200

202

Avg.

307

134

Avg.

259

185

もあり，easylowSD の平均値は区間 [0, 50) より 45 程度大きく，diﬃcultlowSD と diﬃculthighSD の平均値は区間 [350, )より 43，91 程度それぞれ小さくなった．この理由は 5.3 節にて考察する．
次に，lowSD と highSD 迷路の nextra の標準偏差の差
(a)

(b)

に注目する．lowSD と highSD 迷路の標準偏差の平均値(c)（b）diﬃcultlowSD ，
図 7 自動生成した迷路の例：（a）easylowSD ，（c）ある被験者が（b）の迷路を解いたときの軌跡について Student の t 検定（p < 0.05）を行った結果，moderatehighSD は moderatelowSD よりも標準偏差の平均値が大きく（p = 0.0142），diﬃculthighSD は diﬃcultlowSD よため，3.1 節の被験者とは異なる被験者を採用した．本実

りも標準偏差の平均値が大きく（p = 0.0057），いずれも統験で使用する迷路は，サイズを L，視界状態を Narrow に計的に有意差があることが示された．

設定し，穴掘り法 [3] を用いて自動生成した．実験の準備段階で 3 万個の迷路を生成し，各迷路を 10 回ずつテストプ

5.3 実験結果の考察

レイヤが解いた．その結果，nextra の平均値が [0, 50) であ

5.2 節の結果より，テストプレイヤの行動は人間プレイ

れば難易度を easy，[150, 250) であれば moderate，[350, )ヤの傾向を十分に反映し，その傾向に基づく難易度の迷路であれば diﬃcult とした．さらに，それらの中で標準偏差を生成できていることが分かる．また，標準偏差が大きい

が上位 7 個を highSD，下位 7 個を lowSD とした．

迷路を複数の人間プレイヤが解いた場合，同じ迷路であっ実験で使用した easylowSD と diﬃcultlowSD の迷路を図ても各プレイヤは全く異なる難易度を体験してしまう可能

7(a)，7(b) にそれぞれ示す．色付きの通路マスはテストプ性が高くなる．そのため，多くの場合において，標準偏差

レイヤの軌跡を示しており，灰色マスは正解路中の軌跡，は小さいほうが望ましいと考える．テストプレイヤによる

赤斜線マスは不正解路中の軌跡である．被験者は計 35 個

標準偏差の評価と人間プレイヤが解いた結果が大まかに適の迷路を表 2 に記す順番で解いた．図 7(c) は，図 7(b) の合したことは良い結果と言える．

迷路をある被験者が解いたときの軌跡である．これは実験

しかし，人間プレイヤの結果に反して，テストプレイヤ

結果の中でも，テストプレイヤと人間プレイヤの軌跡が特が難しさを（1）過大評価していた，あるいは（2）過小評価に一致した例である．

していた迷路もいくつか見られた．まず，（1）と（2）に共通する理由として，予測モデルに改善の余地があることが5.2 実験結果

挙げられる．次に（1）について，これは制限時間に起因し被験者による nextra の平均値と標準偏差を表 2 の mean，ていると考える．被験者実験では，制限時間を設けていたSD の列にそれぞれ示す．まず平均値について，おおよそため，特に難しい迷路の場合，ゴールまで辿り着けずゲー

easy < moderate < diﬃcult となり，テストプレイヤの評価

ムオーバーになる被験者も少なからず見られた．一方，テと人間プレイヤが解いた結果は適合することが示唆された．

ストプレイヤが迷路を解く際には制限時間を設けず，必ずまた，lowSD 迷路について Student の t 検定（p < 0.05）

ゴールまで辿り着くという条件のもと nextra を計算していを行った結果，moderatelowSD は easylowSD よりも平均値

た．被験者とは異なり，テストプレイヤは際限なく迷路内が大きく（p = 0.0016），diﬃcultlowSD は moderatelowSD よを探索できてしまったことで，（1）が生じたと推測する．

りも平均値が大きく（p = 0.0083），いずれも統計的に有（2）については，人間プレイヤの「思い込み」「勘違い」

意差があることが示された．ただし，これらの平均値の中といった部分がテストプレイヤに十分反映されていないこには，テストプレイヤによる評価区間から外れているものとが理由であると考える．例えば，非常に長い正解路を持© 2021 Information Processing Society of Japan-197-

The 26th Game Programming Workshop 2021
つ迷路を人間プレイヤが解いているとする．プレイヤは正[8]解路を進んでいる最中，長時間ゴールに辿り着けなければ「これは不正解路なのだろうか」と考え通路を引き返し，そ[9]の分 nextra が増加する可能性がある．一方，テストプレ
イヤにはそういった迷いがないため，（2）のような食い違いが生じたと推測する．分岐選択のほかにも，「思い込み」[10]「勘違い」といった人間らしさを取り入れることが（2）の解消に繋がると期待できる．

[11]

6. おわりに
本稿では，プレイヤを自然に誘導する RPG マップの自[12]

動生成に向けた研究の初期段階としてまず，人間プレイヤの分岐選択傾向に基づいた難易度の迷路を自動生成した．
人間プレイヤの傾向は教師あり学習を用いて調査し，その[13]傾向を取り入れたテストプレイヤを作成，迷路の自動生成に用いた．迷路評価の被験者実験では，テストプレイヤが[14]評価した難易度と実際に人間プレイヤが解いた結果は適合することが示唆された．
提案手法は，特定の難易度の迷路が生成されるまでに多横田和幸, 船瀬新王, 藤原清悦, 内匠逸: ヒトを対象にした迷路課題の難易度を定量的に決定するパラメータの検討.
生体医工学, 57(2-3), pp. 58-67 (2019).
吉田友太, 池田心: 遺伝的アルゴリズムと人間らしい AI
プレイヤを用いた 2D シューティングゲームのステージ
生成. 研究報告ゲーム情報学（GI）, 2020-GI-43(23), pp.
1-8 (2020).
森永剛志, 池田心: 上海ゲームにおける面白いインスタ
ンス生成. 研究報告ゲーム情報学（GI）, 2020-GI-43(21),pp. 1-8 (2020).
Shu, T., Liu, J., and Yannakakis, G. N.: ExperienceDriven PCG via Reinforcement Learning: A Super MarioBros Study. In 2021 IEEE Conference on Games (CoG
2021), (2021).
Gisslen, L., Eakins, Andy., Gordillo, C., Bergdahl, J.,
and Tollmar, K.: Adversarial Reinforcement Learning
for Procedural Content Generation. In 2021 IEEE Conference on Games (CoG 2021), (2021).
藤平啓汰, 池田心: 2D 迷路における行動選択の予測と自然なプレイヤ誘導への応用. 研究報告ゲーム情報学（GI）,
2021-GI-46(4), pp. 1-6 (2021).
Ke, G., Meng, Q., Finley, T., Wang, T., Chen, W., Ma,
W., Ye, Q., and Liu, T. Y.: LightGBM: A Highly Efﬁcient Gradient Boosting Decision Tree. In Advances in
Neural Information Processing Systems (NIPS 2017), pp.
3147-3155 (2017).

くの時間を要してしまう可能性があり，その点が課題として残る．今後は特定の難易度の迷路を適時生成できるよう，生成効率の改善を目指す．また，既存の難しい迷路生成手法との比較も行う予定である．さらに，今回得た知見付録

A.1 教師あり学習に用いた特徴量をもとに，敵やアイテムなどを含むより複雑なゲームに提教師あり学習に用いた特徴量を以下に記す．著者の以前

案手法を適用していきたい．

の論文 [13] から新たに追加された特徴量には下線を引く．

謝辞

方向を表す特徴量は，右なら 0，下なら 1，左なら 2，上なら 3 に変換し，数値化している．

本研究は JSPS 科研費 JP18H03347，JP20K12121 の助• maze size：迷路のサイズ（S，M，または L）．S な成を受けたものです．

ら 0，M なら 1，L なら 2 に変換し，数値化している．

• x, y：分岐点の x，y 座標．
参考文献
[1]

[2]

[3]
[4]
[5]
[6]

[7]

• ent：分岐点へ進入する前にプレイヤがいた通路マス

Volz, V., Schrum, J., Liu, J., Lucas, S. M., Smith, A.,
and Risi, S.: Evolving Mario Levels in the Latent Spaceof a Deep Convolutional Generative Adversarial Network. In 2018 Genetic and Evolutionary Computation
Conference (GECCO 2018), pp. 221-228 (2018).
Cardamone, L., Yannakakis, G. N., Togelius, J., andLanzi, P. L.: Evolving Interesting Maps for a First Person Shooter. In 2011 European Conference on the Applications of Evolutionary Computation (EvoApplications2011), pp. 63-72 (2011).
Algoful, 迷路生成法（穴掘り法）, https://algoful.com/
Archive/Algorithm/MazeDig (accessed 2021-10-01).
Algoful, 迷路生成法（壁伸ばし法）, https://algoful.com/
Archive/Algorithm/MazeExtend (accessed 2021-10-01).
Algoful, 迷路生成法（棒倒し法）, https://algoful.com/
Archive/Algorithm/MazeBar (accessed 2021-10-01).
Adams, C., and Louis, S.: Procedural Maze Level Generation with Evolutionary Cellular Automata. In 2017
IEEE Symposium Series on Computational Intelligence(SSCI 2017), pp. 1-8 (2017).
Kwiecień, J.: A Swarm-Based Approach to Generate
Challenging Mazes. Entropy, 20(10), 762 (2018).

© 2021 Information Processing Society of Japanの方向．

• exit：予測対象となる通路マスの方向．
• exit up, exit down, exit left, exit right: 分岐点
から見たとき，ent を除く各方向に未確定な通路があるかどうか．ある方向が True で，その方向を 1 回以
上訪れた場合でも，その方向は True のままとする．

• dist edge up, dist edge down, dist edge left,
dist edge right：分岐点と各方向にある外周との直線距離．ただし，dist edge up と dist edge left は，特徴量 x，y と同じ値をそれぞれ持つため，あまり意味のない特徴量である．

• is straight：ent と exit が直進方向にあるかどうか．
• straight depth：is straight が True の場合，視界範
囲に関係なく*4 ，exit の先で直進できなくなるまでの
*4

-198-

Narrow 迷路では，本来プレイヤは視界範囲外の情報を取得できないが，straight depth と area，area sum を計算する際には視界範囲外の情報も用いている．

The 26th Game Programming Workshop 2021
通路マスの個数．is straight が False なら 0 となる．

• area：視界範囲に関係なく，exit の先にある到達可能な全ての通路マスの個数．例えば，図 A·1 中の B を分岐点とし，下方向の選択確率を予測する場合，緑斜線
で塗りつぶされた通路マス（ゴールを含む）の個数がarea の値となる．
• area sum：分岐点から見たとき，ent を除く各方向の先に続く通路マスの個数．例えば，図 A·1 中の B を分

図 A·1 特徴量 area と area sum の例

岐点とし，それに関連する選択確率を予測する場合，
緑斜線と青縦線で塗りつぶされた通路マス（ゴールを含む）の個数が area sum の値となる．

• num branch：視界状態を Narrow と仮定し，視界範囲内にある分岐点の個数（現在いる分岐点は除く）．

• dist start：スタートから分岐点までの最短歩数．

図 A·2 特徴量 cos goal の例• avg step：全被験者の分岐点到達時点の歩数の平均値．テストプレイヤが迷路をプレイする場合，分岐点
到達時点の合計歩数を avg step の値とする．迷路や分岐点の情報から作成される他の特徴量とは異なり，本特徴量はプレイヤの歩数をもとに作成される．歩数が多いほど迷路内を探索し，その構造を把握している可能性が高くなる．それが分岐選択に影響するだろうという観点から，本特徴量を用いることとした．
図 A·3 特徴量 general direction の例• cos goal：分岐点から見たゴールの方向と予測対象通路マスの方向のなす角度に対する cosθ．図 A·2 に例を示す．図 A·2 中の B を分岐点，G をゴールとし，exitが右方向なら cos goal の値は cos30◦ ≈ 0.86，下方向なら cos300◦ = 0.50，左方向なら cos210◦ ≈ −0.86，上方向なら cos120◦ = −0.50 となる．

• cos start：分岐点から見たスタートの方向と予測対
象通路マスの方向のなす角度に対する cosθ．

• general direction：視界状態を Narrow と仮定し，exit の先に続く通路の大まかな方向．この特徴量を計算するうえで，分岐点を根，exit の先に続く視界範囲内の通路マスを節や葉とする迷路の部分木を考える．また，特徴量の候補値を決めるための変数 DLR と DU Dを導入し，アルゴリズム 2 を用いて DLR と DU D を計算する．DLR が正数であれば右方向を，負数であれば左方向を候補値とする．また，DU D が正数であれば下方向を，負数であれば上方向を候補値に追加する．

DLR と DU D の絶対値同士を比較し，値の大きい変数に由来する候補値を general direction の値とする．
例えば，図 A·3 中の B を分岐点とし，下方向の選択確率を予測する場合，DLR = −1 − 1 = −2，

DU D = 1 + 1 + 1 + 1 = 4 となり，| − 2| < |4| となるた

アルゴリズム 2 DLR と DU D の計算
1: DU D ← 0
2: DLR ← 0
3: S ← {} // 空のスタック
4: v ← ルートノード // 分岐点
5: r ← 1
6: S.push((v, r))
7: while S が空ではない do
8:(node, r) ← S.pop()
9:
for all c ← node の子ノード do10:d ← 迷路上で node から c を見たときの方向
11:
if d = 上 then12:
DU D ← DU D − 1 × r
13:else if d = 下 then14:
DU D ← DU D + 1 × r
15:else if d = 左 then16:
DLR ← DLR − 1 × r
17:else if d = 右 then18:
DLR ← DLR + 1 × r
19:
end if20:
if c = 十字路または丁字路の中心地点 then21:
S.push((c, r/2))
22:
else
23:
S.push((c, r))24:
end if
25:
end for
26: end while

め，general direction は下方向となる．また，右方向の選択確率を予測する場合，DLR = 1 + 1 + 21 (1 + 1) = 3，

DU D = 12 (1 + 1 − 1 − 1) = 0 となり，|3| > |0| となるため，general direction は右方向となる．

© 2021 Information Processing Society of Japan-199-