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

GAとTD(λ)学習の組み合わせによる
ゲーム局面評価パラメータの調整
東京大学
工学部電子情報工学科
矢野友貴
1
本発表の構成
• 背景と目的
• 関連研究
• 提案手法
• 実験と結果
• まとめと今後の課題
2
本発表の構成
• 背景と目的
• 関連研究
• 提案手法
• 実験と結果
• まとめと今後の課題
3
背景
• ゲーム局面評価パラメータの調整において、遺
伝的アルゴリズム(GA)及びTD(λ)学習を単体で
用いた例は数多く存在する
• 2つの手法は一長一短であり、組み合わせて用
いることでよりよい結果が得られることが期待
される
• しかし、実際に組み合わせて用いたという事例
は極めて少ない
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
▫ 利点:大域探索により広く解の探索を行える
▫ 欠点:計算コストが大きい
2つの手法には相反する特徴があり、
組み合わせることでよりよい結果が期待できる
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では頻度・確率・
期間を固定の値とする
• 3つのパラメータを状況
に応じて変える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フェーズ:選択
個体1
集
団
個体1
win_rate1
対戦
抽出
個体2
個体1
勝率を
求める
個体2
勝率に
応じて選択
個体1
win_rate2
個体を集団に戻す
勝率がwin_rateの場合に選択される確率prob
1
prob 
1  exp(a( win_rate 0.5))
※実験的に a  12 とした
18
GAフェーズ:交叉
個体1
集
団
抽出
個体2
個体1’
一様交叉
一様交叉
個体2’
個体を集団に戻す
• 交叉は集団の一定の割合
(交叉率)の個体間で行う
個体の対応する要素を
ランダムに交換する
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フェーズ
個体1
集
団
一定の確率
(TD確率)に
従って抽出
個体2
個体1’
一定の試合数
(TD期間)の間
TD(λ)学習
個体2’
個体を集団に戻す
• 本手法では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の探索or5%でランダム
+パラメータ調整
終盤
58-64
終局まで読み切る
終局まで読み切る
26
局面評価パラメータ
• 本実験ではLogistelloで用いられる局面評価パラ
メータを用いて学習を行った
• Logistelloで用いられる局面評価パラメータは上
記の11パターン+Parity(空マスの偶奇)
• 対称性を考慮すると計113879パラメータとなる
• 評価値はシグモイド関数で(0.0,1.0)に正規化し
て求めた
27
評価方法
• 局面評価パラメータはZebraのパラメータに対す
る1000試合での勝率を用いて評価した
• 集団から代表する個体をトーナメントで選び、
それを用いて集団の評価を行う
• Zebraのパラメータは中盤での行動で用いた
Zebra
集
団
トーナメント
で選出
代表
1000試合の対戦
得られた勝率に
よって集団を評価
28
実装と実験環境
• 本手法では選択、比較、TD(λ)学習で行われる
対戦が各個体で独立に計算可能なため、3つの
操作をマスター・ワーカ方式で並列化した
• 実装にはC++とMPIを用い、マスター1個、
ワーカ64個をした
• 本実験はネットワークに広域分散したクラスタ
群であるInTriggerで行った
• なお、計算にはIntel Xeon E5410(2.33GHz)を搭
載したクラスタを用いた
29
並列化による実装
タスクを
ばらまく
※マスター1個、ワーカ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
従来手法の実装方法1
GAのみ
TD(λ)学習のみ
GAフェーズ
TDフェーズ
no
end?
TD確率=0%
で通らない
no
GAフェーズ
GAフェーズは
行わない
TDフェーズ
TD確率=100%
ペアは固定
end?
35
従来手法の実装方法2
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期間)を2倍の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に対する勝率の平均値として求めた
集団1
代表1
集団2
代表2
集団3
代表3
集団4
代表4
Zebra
代表2
トーナメント
対戦
ここで得られる
勝率の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
1
1
3
5
5
4
Singer’s
method
57.4 46.6
30.6 いずれの場合でも本手法が
43.3
49.6 29.4
30.5 最もよい成績をあげている
42.6 50.4
33.6
4
3
Kim’s
method
45.7
2
2
自分\相
手
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を用いた絶対的な適応度
• 本手法では選択・比較で2個体間の相対的な適
応度を用いていたが、これをZebraに対する絶対
的な適応度に置き換える
• 対戦結果を用いて次のように適応度を計算
fitness  win 1.0  draw 0.5
• なお、実装には各世代で最も強い個体を次世代
に残すエリート戦略を用いる
53
絶対的な適応度:結果1
54
絶対的な適応度:結果2
Z10% vs
Zebra
初期局面1
初期局面2
初期局面3
初期局面4
初期局面5
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%