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%
© Copyright 2024 ExpyDoc