GAとTD(λ)学習の組み合わせによるゲーム局面評価パラ

GAとTD(λ)学習の組み合わせによる
ゲーム局面評価パラメータの調整
東京大学
工学部電子情報工学科
矢野友貴
1
本発表の構成
• 背景と目的
• 関連研究
• 提案手法
• 実験と結果
• まとめと今後の課題
2
本発表の構成
• 背景と目的
• 関連研究
• 提案手法
• 実験と結果
• まとめと今後の課題
3
背景
• ゲーム局面評価パラメータの調整において、遺
伝的アルゴリズム(GA)及びTD(λ)学習を単体で
用いた例は数多く存在する
• ２つの手法は一長一短であり、組み合わせて用
いることでよりよい結果が得られることが期待
される
• しかし、実際に組み合わせて用いたという事例
は極めて少ない
4
目的
• 本研究では、ゲーム局面評価パラメータを調整
する方法として、GAとTD(λ)学習を組み合わせ
た手法を提案する
• このとき、ハイブリッドGAの考え方を導入する
ことで従来手法よりも汎用性の高い手法を構築
する
5
本発表の構成
• 背景と目的
• 関連研究
• 提案手法
• 実験と結果
• まとめと今後の課題
6
TD(λ)学習[R. S. Sutton 1988]
TD誤差の伝搬
λδ
  r   V(st 1 )  V( st )

r
δ  ,  ,  [0.0,1.0]
 ：TD誤差
 
2
V( st 2 )
V( st 1 )
V( st )
V( st 1 )
st  2
st 1
st
st 1
※この図では
  1.0
行動
r：報酬
V( st )：状態 s t の価値の推定値
 ：学習率
状態
 ：割引率
：トレース減衰パラメータ
• TD(λ)学習は行動によって得られる報酬を元に
状態の価値の推定値を学習する強化学習の一種
7
Genetic Algorithm[J. Holland 1975]
選択
集団内から相対的に
「よい」個体を選ぶ操作
選択
v.s
交叉
交叉
複数個体間で
部分列を交換する操作
突然変異
個体を構成する要素
の一部を変更する操作
突然変異
swap
no
End?
yes
result
• GAは生物の進化を模したメタヒューリスティッ
クアルゴリズム
8
TD(λ)学習とGAの特徴
• TD(λ)学習
▫ 利点：素早く学習ができる
▫ 欠点：大域最適解を得ることが困難
• GA
▫ 利点：大域探索により広く解の探索を行える
▫ 欠点：計算コストが大きい
２つの手法には相反する特徴があり、
組み合わせることでよりよい結果が期待できる
9
従来の組み合わせ手法
• 強化学習(RL)+GA [J. A. Singer 2001]
▫ 強化学習とGAを交互に行う手法でオセロの局面評価パラメータを調整
▫ 最終的に中級者程度の強さとなった
GA
RL
yes
End?
result
no
個体の集合
• TD学習+GA [K. J. Kim et al. 2007]
▫ TD学習によって初期集団を作成したのちGAを施す手法でオセロの局面
評価パラメータを調整
▫ 最終的にCEC 2006 Othello competitionにおいて優勝した
TD
個体の集合
GA
yes
End?
no
result
10
ハイブリッドGA
GA
大域探索によって
解候補を開拓
LS
局所探索によって
解候補を調査
• GAと局所探索(LS)を
組み合わせる手法は
ハイブリッドGAと呼
ばれ様々な分野で用
いられている
大域探索
no
end?
fitness
局所探索
yes
result
solution space
11
ハイブリッドGAの特徴
• 局所探索を組み込むことでGA単体よりも少ない
個体数、世代数での探索が可能となる
• しかし、局所探索による解の補正がかかるため
GA単体よりも局所解に陥りやすい
GAと局所探索のバランスを調整することが重要
12
NAHGA[K. E. Mathias et al. 1994]
GA
no
do
LS?
yes
LS
no
end?
頻度・確率・期間で
GAとLSのバランスを調整する
• 頻度
LS間に挟むGAの回数
• 確率
LSを行う個体の割合
• 期間
LSを行う長さ
result
頻度
ratio
1.0
yes
0.4
• NAHGAでは頻度・確率・
期間を固定の値とする
• ３つのパラメータを状況
に応じて変えるNAHGAの
拡張手法として
SAHGA[F. P. Espinoza et
al. 2001]がある
期間
赤:GA
緑:LS
確率
time
13
本発表の構成
• 背景と目的
• 関連研究
• 提案手法
• 実験と結果
• まとめと今後の課題
14
方針
• TD(λ)学習の特徴は「素早く学習できるが、局
所解に陥りやすい」というものだった
• これは局所探索の特徴によく似ている
• TD(λ)学習は一種の局所探索とみなせる
• GA+TD(λ)学習をハイブリッドGAとして考える
15
概要
• NAHGAをベースに
GAとTD(λ)学習を組み
合わせる
• 頻度を1に固定して、
確率及び期間を用いて
TD(λ)学習を制御する
• 本手法はGAの操作を
行うGAフェーズ及び
TD(λ)学習を行うTD
フェーズで構成させる
GAフェーズ
選択により親候補を作成
親候補に対して
交叉・突然変異を適用し
子世代を作成
親子世代間で比較
設定された確率・期間で
TD(λ)学習を適用
no
TDフェーズ
終了条件を
満たした？
yes
終了
16
個体の定義
 
V( s)   wi vi (s)     (s)
i
これを調整する
wi ：i番目の特徴の局面評価パラメータ(重み)
vi (s) ：局面sでのi番目の特徴の出現数
• 本手法では上式のような線形和で表される局面
評価関数を対象とし、その局面評価パラメータ
のベクトルをGAの個体とする
17
GAフェーズ：選択
個体１
集
団
個体１
win_rate1
対戦
抽出
個体２
個体１
勝率を
求める
個体２
勝率に
応じて選択
個体１
win_rate2
個体を集団に戻す
勝率がwin_rateの場合に選択される確率prob
1
prob 
1  exp(a( win_rate 0.5))
※実験的に a  12 とした
18
GAフェーズ：交叉
個体１
集
団
抽出
個体２
個体１’
一様交叉
一様交叉
個体２’
個体を集団に戻す
• 交叉は集団の一定の割合
(交叉率)の個体間で行う
個体の対応する要素を
ランダムに交換する
19
GAフェーズ：突然変異
集団全体での
標準偏差σ[i]
を求める
i番目
…
+mutate
mutate[ [i], [i]]
要素に一定の確率(突然変
異率)で標準偏差の幅を持
つ一様乱数を加える
M個
2
(

[
i
]

avg
)
 j 0 j
i
M
 [i] 
j
M 1
：集団内のj番目の個体
avgi ：i番目の要素の集団全体での平均
 [i]   [i]  RND(1.0,1.0)   [i]
RND(1.0,1.0)：[-1.0,1.0]の一様乱数
• 突然変異はすべての要素
に対して行う
20
GAフェーズ：比較
…
…
親個体i
親個体i
子個体i
対戦
親世代
…
親世代と子世代
の対応する個体
を選択
…
…
子個体i
強い方を
次世代に
残す
次世代
子個体i
…
子世代
• 子世代は親世代に選択・交叉・
突然変異を行ったもの
21
TDフェーズ
個体１
集
団
一定の確率
(TD確率)に
従って抽出
個体２
個体１’
一定の試合数
(TD期間)の間
TD(λ)学習
個体２’
個体を集団に戻す
• 本手法ではTDフェーズをTD(λ)学習を行う確率
(TD確率)と試合数(TD期間)の二つのパラメータ
によって制御する
22
Singerの手法との違い
GA
RL
yes
End?
result
no
個体の集合
• Singerの手法では強化学習をすべての個体に対して適用
しており、GAとのバランスが考慮されていない
• そのため、局所解に陥りやすい
GA
個体の集合
TD
yes
End?
result
no
• 本手法ではTD(λ)学習をTD確率・TD期間で制御するこ
とで、GAとのバランスを調整できる
• 問題に応じてバランス調整ができ、より汎用的
23
Kim等の手法との違い
TD
GA
yes
End?
result
no
個体の集合
• Kim等の手法ではTD学習とGAが別々に用いられるため、
各手法単体での特徴がそのまま使える
• しかし一方で双方の結果を完全には活用できない
GA
個体の集合
TD
yes
End?
result
no
• 本手法ではTD(λ)学習をGAのフレームワークの中に組み
込こんでいるため、双方の結果を有効に活用できる
24
本発表の構成
• 背景と目的
• 関連研究
• 提案手法
• 実験と結果
• まとめと今後の課題
25
実験
• オセロの局面評価パラメータを用いて、本手法
の評価を行った
• オセロの局面評価パラメータを学習する際、下
記のようにオセロを序盤・中盤・終盤に分け、
行動を決定した
進行度石の数
GAフェーズでの行動
TDフェーズでの行動
序盤
4-13
決められた手を打つ
ランダムな手に打つ
中盤
14-57
深さ1の探索
深さ1の探索or５%でランダム
+パラメータ調整
終盤
58-64
終局まで読み切る
終局まで読み切る
26
局面評価パラメータ
• 本実験ではLogistelloで用いられる局面評価パラ
メータを用いて学習を行った
• Logistelloで用いられる局面評価パラメータは上
記の11パターン+Parity(空マスの偶奇)
• 対称性を考慮すると計113879パラメータとなる
• 評価値はシグモイド関数で(0.0,1.0)に正規化し
て求めた
27
評価方法
• 局面評価パラメータはZebraのパラメータに対す
る1000試合での勝率を用いて評価した
• 集団から代表する個体をトーナメントで選び、
それを用いて集団の評価を行う
• Zebraのパラメータは中盤での行動で用いた
Zebra
集
団
トーナメント
で選出
代表
1000試合の対戦
得られた勝率に
よって集団を評価
28
実装と実験環境
• 本手法では選択、比較、TD(λ)学習で行われる
対戦が各個体で独立に計算可能なため、３つの
操作をマスター・ワーカ方式で並列化した
• 実装にはC++とMPIを用い、マスター１個、
ワーカ64個をした
• 本実験はネットワークに広域分散したクラスタ
群であるInTriggerで行った
• なお、計算にはIntel Xeon E5410(2.33GHz)を搭
載したクラスタを用いた
29
並列化による実装
タスクを
ばらまく
※マスター１個、ワーカ64個なので注意
ここは
64並列
ここは
64並列
タスクを
ばらまく
比較 … 比較 … 比較
選択 … 選択 … 選択
結果を
集計
結果を
集計
交叉
突然変異
タスクを
ばらまく
TD
…
TD
結果を
集計
…
ここは
最大64並列
TD
30
本手法の各種パラメータ
GAフェーズのパラメータ
TDフェーズのパラメータ
パラメータ
値
パラメータ
値
個体数
128
トレース減衰パラメータ
0.7
交叉率
80%
割引率
1.0
突然変異率
1%
TD確率
後述
選択・比較の試合数
1000試合
TD期間
1000試合
初期値の範囲
[-0.01,0.01]
学習率
下式参照
学習率は各パラメータで独立の
ものを用いた。count[i]はi番目
のパラメータの出現回数
100.0  1.0
α[i ]  0.01
100.0  count[i ]1.1
※初期値、TD期間の値は実験によって決定した
31
TD確率に関する実験：概要
• TD確率を0%,5%,10%,20%,50%,100%と変化さ
せ、それぞれの勝率の推移を調べた
• 学習は500世代、異なる初期値から10回行い、
得られたZebraに対する勝率の平均及び標準誤差
を求めた
• 計算時間はTD確率が増えるに従い増加し、0%
で4時間、100%で6時間を要した
32
TD確率に関する実験：結果
後半では
50%,100%の
勝率が頭打ち
になっている
0%で序盤に勝率が伸びない
性能としては
のは、TD(λ)学習によるパラ
10%  5%  20%
メータの補正がないため
本実験ではTD確率として
序盤では0%だけ勝率
TD確率が大きい場合には、
10%を用いることとした
が伸びていない
解が局所最適解に落ち込む
ために勝率が伸びない
33
従来手法との比較実験
• 本手法と従来手法との比較実験を行った
• 従来手法としては次の4つを用いる
▫
▫
▫
▫
GAのみ
TD(λ)学習のみ
Singerの手法
Kim等の手法
• 従来手法の実装は本手法を拡張することで行う
34
従来手法の実装方法１
GAのみ
TD(λ)学習のみ
GAフェーズ
TDフェーズ
no
end?
TD確率=0%
で通らない
no
GAフェーズ
GAフェーズは
行わない
TDフェーズ
TD確率=100%
ペアは固定
end?
35
従来手法の実装方法２
Singerの手法
Kim等の手法
GAフェーズ
TDフェーズ
TD確率=100%
no
TDフェーズ
TD確率=100%
10世代?
10世代までは
TDフェーズ
のみ行う
yes
GAフェーズ
no
end?
no
end?
36
同一世代数での比較実験：概要
• TD確率での実験と同じ方法で実験を行った
• 比較対象の手法も本手法と同じ条件
• ただし、TD(λ)学習のみを用いる手法では初期
値を0.0とし、計算時間を合わせるために1世代
の学習試合数(TD期間)を２倍の2000試合とした
• 計算に要した時間は、本手法が5時間、GAのみ
及びTD(λ)学習のみが4時間、Singerの手法が6時
間、Kim等の手法が3時間となった
37
同一世代数での比較実験：結果
本手法の勝率
が最も高い
本手法とTD onlyが
同じような挙動
すべての手法を同一世代数で
評価することは適切でない？
Singer’s methodで60世代
以降勝率が下降している
本手法とGA onlyが
同じような挙動
本手法はGAとTD(λ)学習の
特徴をうまく取り入れている
38
最適停止世代
optimum fitness
1024世代
512世代
256
256
max
512世代
256
256
max generation/try
time
各世代数での試行のうち最もよい結果を選ぶ
最適停止世代
同一の計算時間で最も適応度の高くなる世代数
を最適停止世代という
39
最適停止世代での比較実験：概要
• 1024世代を1回、512世代を2回、…、16世代を
64回と各手法で実験を行い、各世代での勝率の
期待値を求めた
• 勝率の期待値は、各世代で得られた個体を使っ
て50回トーナメントを行い、トップとなった個
体のZebraに対する勝率の平均値として求めた
集団１
代表１
集団２
代表２
集団３
代表３
集団４
代表４
Zebra
代表２
トーナメント
対戦
ここで得られる
勝率の50回での
平均を求める
40
最適停止世代での比較実験：結果
本手法では勝率の降下が小さく、
安定して解が得られている
すべての手法で途中から
勝率が降下している
TD onlyで16,32,64世代の勝率
がぶれているが、原因は不明
41
各手法間の直接対決：概要
• 最適停止世代の比較実験より、下表のように各
手法のおおまかな最適停止世代が分かった
• 各手法の最適停止世代での局面評価パラメータ
同士を対戦させ、その強さを比較した
• 対戦の方法はZebraの場合と同様とした
手法
最適停止世代
proposed method
256
GA only
512
TD only
256
Singer’s method
64
Kim’s method
512
42
各手法間での直接対決：結果
GA only
TD only
Singer’s
method
Kim’s
method
58.0
69.4
69.5
54.3
１
１
３
５
５
４
Singer’s
method
57.4 46.6
30.6 いずれの場合でも本手法が
43.3
49.6 29.4
30.5 最もよい成績をあげている
42.6 50.4
33.6
４
３
Kim’s
method
45.7
２
２
自分＼相
手
proposed
method
直接対決での順位
proposed
method
GA only
本手法はすべての
42.0
対戦で勝ち越している
TD only
56.7
53.4
70.6
66.4
※(自分)の(相手)に対する勝率、単位は%
赤文字は勝ち越しを、青文字は負け越しを表す
v.s Zebraでの順位
43
本発表の構成
• 背景と目的
• 関連研究
• 提案手法
• 実験と結果
• まとめと今後の課題
44
まとめ
• 本研究ではGAとTD(λ)学習をハイブリッドGAの
観点から組み合わせることで、従来よりも汎用
性の高い手法を提案した
• 従来手法にはなかったTD(λ)学習を制御するパ
ラメータを導入することで、GAとTD(λ)学習の
特徴をうまく融合することができた
• オセロの局面評価パラメータの調整を例に従来
手法との比較を行ったところ、従来手法に対し
て54.3～69.5%の勝率を得た
45
今後の課題
• オセロ以外の問題を用いた実験
• NAHGAではなくSAHGAによる本手法の拡張
• TDLeaf(λ)[J. Baxter et al. 2000]、TDMC(λ)[大
崎泰寛 et al. 2008]、iLSTD(λ)[A. Geramifard et
al. 2007]といったTD(λ)学習の拡張手法の本手法
への適用
46
47
スパースな特徴に対する学習率
• スパースな特徴では
各特徴の出現確率に
偏りが生じ、統一の
学習率ではうまく学
習できない
• そこで、学習率を各
特徴ごとに独立に用
意することで偏りの
問題を緩和する
N0  1
  0
N 0  # episode1.1
N0  1
 [i]   0
1.1
N 0  count[i ]
48
学習率の比較実験
49
初期値の比較実験
50
TD期間の比較実験：勝率
51
TD期間の実験：時間
52
Zebraを用いた絶対的な適応度
• 本手法では選択・比較で２個体間の相対的な適
応度を用いていたが、これをZebraに対する絶対
的な適応度に置き換える
• 対戦結果を用いて次のように適応度を計算
fitness  win 1.0  draw 0.5
• なお、実装には各世代で最も強い個体を次世代
に残すエリート戦略を用いる
53
絶対的な適応度：結果１
54
絶対的な適応度：結果２
Z10% vs
Zebra
初期局面１
初期局面２
初期局面３
初期局面４
初期局面５
75.3
46.7
44.8
45.9
45.6
ZGA vs
Zebra
80.4
41.6
38.7
42.2
39.7
Z10%：絶対的な適応度でTD確率10%
ZGA：絶対的な適応度でGAのみ
prop_m
vs Zebra
Z10% vs
prop_m
ZGA vs
prop_m
35.4
35.7
33.6
34.4
32.9
35.0
34.0
37.4
34.2
32.2
26.9
29.3
24.1
23.1
22.5
prop_m：最適停止世代での本手法で
TD確率10%

Download Report