探索と強化学習によるハイブリッドゲーム木探索の ゲームへの適用

A∗ 探索と強化学習によるハイブリッド ゲーム木探索の
ゲームへの適用
Hybrid Search Method of Game Tree by A∗ and Reinforcement Learning
1
栗田 翼
2 伊賀上 大輔，
市村 匠
1
2
1
Kurita Tsubasa Daisuke Igaue,
Takumi Ichimura
1
県立広島大学経営情報学部経営情報学科
1
Faculty of Management and Information Systems,
Prefectural University of Hiroshima
2
県立広島大学大学院総合学術研究科経営情報学専攻
2
Graduate School of Management and Information Systems,
1
Abstract: The 2012 Mario AI Competition runs in association with several major international conferences focusing on computational intelligence and games. In Japan, a special session related to AI video
games is held in FSS2012. The competition of this session focuses on the Learning track. Our team
becomes a participate in a session to verify the effectiveness of our proposed the hybrid search algorithm
of game tree, which realizes a good pruning by using A∗ search and the reinforcement learning method.
はじめに
1
agent が優勝している．
近時，学習・探索アルゴ リズムのベンチマークとし
2.2
ゲームの環境
てビデオゲームのスコアを評価することで，ゲームの
ビデオゲームであるエージェントには 3 つの状態が
スコアからアルゴ リズムの性能を競うコンペティショ
ンが国際的な学会において開催されている [1]．対象
となるビデオゲームでは，ゲームが速く進むことによ
り，高いスコアを獲得する評価基準があるため，たど
った経路を元に戻らないと次のステップに進めない，
いわゆる「 袋小路問題」が生じていた．本論文では，
MarioAICompetition におけるゲーム学習について，優
秀なスコアを収めているヒューリスティック経路探索
アルゴ リズムである A∗ と，階層型モジュラー強化学
習 [4][5] のハイブ リッド 型経路探索アルゴ リズムを提
あり，それらは下から一番小さな状態である “small”，
ジャンプでブロックを壊すことの出来る “big”，火の玉
を繰り出す “fire” である．ゲームの目的は，スタート
からゴ ールに到達することであり，ステージの長さは
一律で 4096phy，256cell である．エージェントは敵に
当たると一段階状態が下がり，もし “small” の状態で
敵にぶつかると “ライフ” を失う．またどの状態でも穴
に落ちると “ライフ” を失う．ステージには様々なアイ
テムがあり，“コイン ”，エージェントを大きくする “
キノコ”，“big” の状態から “fire” の状態にする “フラ
案し，問題の解決を図る．
ワー” が存在する．アイテムは，ステージ上に点在し
2
ていたり，ブロックの内側に隠されている．エージェ
MarioAICompetition
2.1
ントの行動選択は一つの動作に対して “ジャンプ ”，“
概要
MarioAICompetition では，ビデオゲームで AI の性
能を競っている [2]．ランダムに生成されるステージをク
リアすることにおいては，遺伝アルゴリズムやニューラ
∗
ルネットワークのような機械学習ではなく，A をはじ
めとするヒューリスティックな探索が優秀なスコアを収
めている [1]．2009 年の大会において GamePlayTrack
しゃがむ”，“右”，“左”，“ダッシュ” があり，組み合
わせてとして 32 通り存在する．
Game Play Track では，一つの行動を行うために
24fps，つまり 42ms 以内に行動をしなければならない．
3
A∗ アルゴリズム
というランダムに生成されたステージをいかに早くゴー
スタートノードから，任意のノード n を通ってゴー
ルできるかという部門では Robin 氏が作成した A∗ の
ルまでたどり着くときの最短経路を考える問題におい
て，最短経路のコストを f (n) とおくと，
ちそうになるか，もしくは場所を戻るという行動を取
り，結果として時間切れや穴に落ちてゲームオーバー
f (n) = g(n) + h(n)
になってしまう．A∗ では，ノード の探索条件を設けて
である．g(n) はスタートノードから n まで，h(n) は n
からゴールノード まで最小コストとする．この時 g(n)
と h(n) をあらかじめ与えることは出来ないので f (n)
を次のような推定値 f ∗ (n) に置き換え，以下のように
表す．
f ∗ (n) = g ∗ (n) + h∗ (n)
ここで g ∗ (n)，h∗ (n) はそれぞれ h(n)，f (n) の推定値
である．g ∗ (n) は，探索の過程で推定値を求めていく
ことができるが，n が決まらなければ h∗ (n) を推定す
ることはできない．そこで h∗ (n) には適当な推定値を
与え，g ∗ (n) は探索しながら適宜更新することで経路
図 1: 袋小路問題
を求めることを考える．このアルゴ リズムを A 探索ア
ルゴ リズムという．
このとき h∗ (n) のことをヒューリスティック関数と
いい，h∗ (n) が以下の条件
おり，探索木が増えすぎた場合に計算量が膨大となる
ことを防いでいる．しかしこの条件によって先の探索
を行えない，つまり短期的な探索しか出来ていないと
∗
∀n, 0 <
= h (n) <
= h(n)
いうことが分かる．そこで本論文では，A∗ の木構造を
抽出した．
を満たすとき，求まる経路がスタートからゴ ールまで
の最短経路であることが保証されている [3]．これが A∗
探索アルゴ リズムである．
まず初期のエージェントの動きを木構造で表す．こ
1 から順番に探索が行われており，こ
こでは，ノード ∗
ビデオゲームにおける A の適用
4
の探索においてコストが一番低い値が行動選択される．
次に袋小路での行動選択であるが，図 1 の赤い点が
ビデオゲームへの適用
4.1
木構造の分析
4.3
3 節で述べた考え方を利用して，ビデオゲームでは木
エージェントの位置である．その位置におけるエージェ
構造を元に最短経路の探索を行っている．ただしビデ
ントの行動選択は以下のようになる．コストが低いも
オゲームにおいて最短経路探索は，現在写っている画
s
面のみの探索であり，先の画面状態を予測して行って
1
いるものではない．現在見えている画面の右端をゴ ー
2
19
78
98
160
257
258
508
509
735
518
756
22
564
828
23
ルとして設定し，周囲の各ノードに対して環境からコ
2
スト計算し，行動を選択して，行動したノード の位置
3
4
5
8
7
からのコスト計算していく．これを繰り返して最短経
3
7
74
75
217
218
456
457
708
709
路を見つけ，その経路を選択して，エージェントが実際
9
に行動した際には，エージェントが存在しているノー
ドから再度コスト計算を行う [1]．
8
12
68
69
198
201
418
419
11
10
673 674
21
20
問題点
4.2
∗
9
11
43
46
163
164
368
369
A の探索を行うと，敵の数が少ないなど の単調な
ステージでは，A∗ は最短経路を簡単に発見し，ゴール
593 594
16
12
13
14
17
18
19
15
まで素早くたどり着いている．しかし，以下の図 1 の
ような袋小路問題に対応することが出来ていない．こ
図 3: 袋小路の木構造
の袋小路でエージェントは，行動選択を行っているが，
ジャンプを袋小路を越えるようなことは出来ず，穴に落
o のように
のを選択しており，行動選択は図の二重丸
s
2
3
14
4
20
5
21
22
24
23
16
6
10
40
41
17
7
1
30
25
8
46
59
9
66
11
75
76
26
12
47
28
13
29
15
42
54
31
48
43
33
18
69
35
32
36
49
44
88
45
19
63
27
64
37
74
78
79
91
87
80
51
38
34
50
52
65
89
66
39
57
53
58
55
90
67
56
68
71
83
84
72
73
85
図 2: 初期の木構造
なる．
行う教師なし学習の一手法である．強化学習アルゴ リ
木構造では，コストの低いものを選択するようになっ
ズムは一般に環境同定型と経験強化型の 2 つに大別さ
ているが，コスト計算に無駄がある．例えば，図 2 に
れる．環境同定型の Q 学習はマルコフ決定過程の環
9 と 11 のノード は行動が違うものの，その
おいて，
境で，ある条件下においての最適性が証明されており
行動を選択した時のコスト，行動したときの位置が全
[7]，学習精度が高いという特徴があり，経験強化型の
て一緒になる．つまり行動を探索しているが結果とし
Profit-Sharing は Q 学習と比較し，学習速度が速いと
いう特徴がある．本論文では，エージェントの学習に
上位階層にモジュラー Profit-Sharing を適用し，下位
て同じコストと場所になり，無駄な行動探索が多いと
いうことが言える．
A∗ では，一度訪れたノードに再度訪れる際にはペナ
ルティを与えており，その結果行動選択する場所を変
化させるようにしているが，コスト計算をしていくに
ジュラー強化学習を用いる．ハンターエージェント同
つれ，訪れる場所がなくなっている．つまり同じ行動
間を学習しなければならず，次元の呪いや学習速度低
選択の繰り返しになっている．
下の問題が顕著化する．階層型モジュラー強化学習は
階層に Q 学習を適用し，階層的に学習を行う階層型モ
士で協調して行動を学習するためには，膨大な状態空
また袋小路では，このような同じ行動の選択が増え， 状態空間とタスクを分割することで，次元の呪いの回
結果として行き来を繰り返したり，穴に落ちてしまう． 避と学習性能を向上させている．
また画面の右端をゴ ールとしているが，状態数の増加
により，計算量が増え，先を見通すことが出来なくなっ
ている．
ハイブリッド ゲーム木探索
5
A∗ のみの探索では，袋小路の問題において長期的な
目標を達成するための探索的行動選択が出来ないため
に，本論文では，A∗ と階層型モジュラー強化学習のハ
5.2
モデル構造
階層型モジュラー強化学習では，上位階層の Profit-
Sharing で，各エージェントがどこに向かえばよいか
のプランニングを行い，エージェントの目標位置策定
を学習する．下位階層の強化学習ではエージェントの
現在位置と上位階層で決定したエージェントの目標位
置の情報を元に Q 学習で行動選択を学習する．このよ
うに階層的に学習することで，目標達成のためのタス
イブリッド 型のゲーム木探索アルゴ リズムを提案する． クが分割され問題の複雑さが軽減できる．また，それ
図 4 のような強化学習システムの学習により，A∗ の袋 ぞれ上位階層では行動を，下位階層では他のエージェ
小路に陥るようなノード への探索時のコストに重み付
ントの状態を考慮しないことで，状態空間の次元数を
けすることで探索を抑制する．提案するハイブリッド
削減できる．
ゲーム木探索によって，制限された時間内での効率的
なゲーム木探索が出来ることを期待する [8]．
5.1
階層型モジュラー強化学習 [4][5]
強化学習 [6] は，エージェントが自身の環境の状態
(g1 , g2 , s1 , s2 , s3 , s4 ) = ∪e ∪l (e, gl , se , s )
(1)
(e, ∈ E, l ∈ L, e 6= )
を知覚し，その状態に対応して選択した行為の結果に
E はすべての子ノード の集合，L はすべてのエージェ
対して環境から報酬を得，その報酬を元に行動学習を
ントの集合を示す．g が子ノード の位置，s がエージェ
ントの位置を示す．
[4] 渡邊俊彦，和田竜也，
「 マルチエージェント追跡問
PS
全状態空間
(g 1 ,g2 ,s1 ,s 2 ,s 3 ,s 4 )
モジュラー構造
強化学習」，バイオメディカル・ファジィ・システ
ム，12(2)，pp.65-74，2010．
エージェント1の
部分木
エージェント2の
部分木
エージェント3の
部分木
エージェント4の
部分木
(1, g 1 ,s 1,s 2 )
(1, g 1 ,s 1,s 3 )
(1, g 1 ,s 1,s 4 )
(1, g 2 ,s 1,s 2 )
(1, g 2 ,s 1,s 3 )
(1, g 2 ,s 1,s 4 )
(2, g 1 ,s 2,s 1 )
(2, g 1 ,s 2,s 3 )
(2, g 1 ,s 2,s 4 )
(2, g 2 ,s 2,s 1 )
(2, g 2 ,s 2,s 3 )
(2, g 2 ,s 2,s 4 )
(3, g 1 ,s 3,s 1 )
(3, g 1 ,s 3,s 1 )
(3, g 1 ,s 3,s 4 )
(3, g 2 ,s 3,s 1 )
(3, g 2 ,s 3,s 2 )
(3, g 2 ,s 3,s 4 )
(4, g 1 ,s 4,s 1 )
(4, g 1 ,s 4,s 2 )
(4, g 1 ,s 4,s 3 )
(4, g 2 ,s 4,s 1 )
(4, g 2 ,s 4,s 2 )
(4, g 2 ,s 4,s 3 )
エージェント毎の現在位置・目標位置を下位階層へ
下位階層では，各エージェントの現在位置と
目標位置を元に実際の行動の学習をQ学習で行う
Q学習
図 4: 階層型モジュラー強化学習
6
題のための相対座標系に基づく階層型モジュラー
[5] 伊賀上大輔，市村匠「階層型モジュラー強化学習
による動的環境に適応した学習手法を用いる児童
見守りアプ リケーションの提案」，第 28 回ファ
ジィシステムシンポジウム予稿集， to appear in
2012．
[6] R.S.Sutton and A.G.Barto,“ Reinforcement
Learning”, MIT Press, 1998．
[7] C.J.Watkins, and P.Dayan, “Technical note:QLearning”, Machine Learning, Vol8, pp.58-68，
1992．
[8] 栗田翼，伊賀上大輔，市村匠，
「 A∗ 探索による木
構造の階層型モジュラー強化学習」，2012 IEEE
SMC Hiroshima Chapter 若手研究会，to appear
in 2012．
おわりに
本研究では，A∗ のビデオゲームへの適用例を示し ， 連絡先
〒 734-8558
木構造化から問題点をあげ，そこから問題点である袋
小路問題に対して強化学習を用いたハイブリッド 型の
広島市南区宇品東一丁目 1-71
アプローチを提案し，ビデオゲームの袋小路問題に適
県立広島大学 経営情報学部
用している．
市村 匠
問題点として，強化学習に関する計算時間が増加し
てしまったため，高スコアの獲得が望めないことがあ
る．リアルタイムに学習可能な手法の提案など 改良が
急がれるところである．
参考文献
[1] Julian Togelius and Sergey Karakovskiy and
Robin Baumgarten,“The 2009 Mario AI Competition”,Proc. of IEEE Symposium on Computational Intelligence and Games(CIG),2010
[2] Julian Togelius and Sergey Karakovskiy
and Noor Shaker,“ 2012 Mario AI Championship”,http://www.marioai.org/Support, July
21 2012
[3] Rina Dechter AND Judea Pearl,“Generalized
Best-First Seach Strategies and the Optimality
of A∗ ”, Journal of the Association for Computing
Machinery, Vol.32, No.3, pp.505-536, July 1985
E-mail: [email protected]