GAとTD(λ)学習の組み合わせによる ゲーム局面評価パラメータの調整 近山・田浦研究室 70419 矢野友貴 1 本発表の流れ • 背景と目的 • 関連研究 • 提案手法 • 実験と結果 • まとめと今後の課題 2 本発表の流れ • 背景と目的 • 関連研究 • 提案手法 • 実験と結果 • まとめと今後の課題 3 背景 • ゲーム局面評価パラメータの調整において、遺伝的アル ゴリズム(GA)及びTD(λ)学習を単体で用いた例は数多く 存在する • ２つの手法は一長一短であり、組み合わせて用いること でよりよい結果が得られることが期待される • しかし、実際にこれらを組み合わせて用いたという事例 は極めて少ない 4 目的 • 本研究ではゲーム局面評価パラメータを調整する方法と して、GAとTD(λ)学習を組み合わせた手法を提案する • このとき、組み合わせる方法としてハイブリッドGAと いう従来とは異なったアプローチをすることで、より汎 用的な組み合わせ手法を構成する 5 本発表の流れ • 背景と目的 • 関連研究 • 提案手法 • 実験と結果 • まとめと今後の課題 6 TD(λ)学習とGA TD(λ)学習[R. S. Sutton 1988] GA[J. Holland 1975] • 行動によって得られる報酬を元 に状態の価値の推定値を学習す る強化学習の一種 • 素早く解を学習することができ るが、局所解に陥りやすい • TD-Gammon[G. Tesauro 1995] • 生物の進化を模したメタヒュー リスティックアルゴリズム • 大域的最適解を探す能力に長け ているが、解の収束が遅い • Chess Player [D. B. Fogel et al .2004] TD(λ)学習とGAには相反する特徴がある ２つを組み合わせることでより良い結果が期待できる 7 従来の組み合わせ手法 • 強化学習(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 8 ハイブリッドGA • GAと局所探索(LS)を組み合わせる手法はハイブリッド GAと呼ばれ、近年さまざまな分野で用いられている • ハイブリッドGAではGAとLSをうまく融合することで、 双方の欠点を補いつつ利点を生かす • しかし、LSを使うためGA単体よりも局所解に陥りやす く、GAとLSとのバランスをうまく調整する必要がある • バランス調整には主にLSを適用する確率が用いられる 大域探索 によって 解候補を 探す GA 切り替え LS 局所探索 によって 解候補を 精査する 9 本発表の流れ • 背景と目的 • 関連研究 • 提案手法 • 実験と結果 • まとめと今後の課題 10 設計方針 • TD(λ)学習の特徴は「素早く解を学習することができる が、局所解に陥りやすい」であったが、これは局所探索 の特徴とよく似ているため、TD(λ)学習は一種の局所探 索とみなすことができる • そのため、GAとTD(λ)学習を組み合わせる方法としてハ イブリッドGAのアプローチが可能 • 本手法ではTD(λ)学習を行う確率を用いることで、従来 手法にはなかったGAとTD(λ)学習のバランス調整という 考え方を導入する 11 本手法の概要 • 本手法はGAを行う部分(GAフェーズ)とTD(λ)学習を行う 部分(TDフェーズ)の２つから構成され、この２つを交互 に行うことでパラメータの調整を行う • TDフェーズではある一定の確率(TD確率)に従ってTD(λ) 学習を適用する個体が選択される 一部の個体にだけ TD(λ)学習を適用 yes GA 個体の集合 TD End? no result 12 Singerの手法との違い GA RL yes End? result no 個体の集合 • Singerの手法では強化学習をすべての個体に対して適用 しており、GAとのバランスが考慮されていない • そのため、局所解に陥りやすい GA 個体の集合 TD yes End? result no • 本手法ではTD(λ)学習を適用する個体数をTD確率で制御 することで、GAとのバランスを調整できる • 問題に応じてバランス調整ができ、より汎用的 13 Kim等の手法との違い TD GA yes End? result no 個体の集合 • Kim等の手法ではTD学習とGAが別々に用いられるため、 双方の結果を完全には活用できない GA 個体の集合 TD yes End? result no • 本手法ではTD(λ)学習をGAのフレームワークの中に組み 込こんでいるため、双方の結果を有効に活用できる 14 本発表の流れ • 背景と目的 • 関連研究 • 提案手法 • 実験と結果 • まとめと今後の課題 15 実験 • オセロの局面評価パラメータの調整を例に本手法と従来 手法との比較実験を行った • 調整するものはLogistelloで使われる113879パラメータ • 従来手法としてGAのみ、TD(λ)学習のみ、Singerの手法、 Kim等の手法を用意 • 評価にはZebraとの1000試合の対戦結果を用いた • ゲームでの行動は以下の通りとした(Zebraとの対戦では GAフェーズでの行動をとる) 進行度 石の数 GAフェーズでの行動 TDフェーズでの行動 序盤 4-13 決められた手を打つ ランダムな手に打つ 中盤 14-57 深さ1の探索 深さ1の探索+パラメータ調整 終盤 58-64 終局まで読み切る 終局まで読み切る 16 本手法の各種パラメータ GAフェーズのパラメータ TDフェーズのパラメータ パラメータ 値 パラメータ 値 個体数 128 トレース減衰パラメータ 0.7 交叉率 80% 割引率 1.0 突然変異率 1% TD確率 10% 選択・比較の試合数 1000試合 学習の試合数 1000試合 初期値の範囲 [-0.01,0.01] 学習率 下式参照 学習率は各パラメータで独立の ものを用いた。count[i]はi番目 のパラメータの出現回数 100.0 1.0 α[i ] 0.01 100.0 count[i ]1.1 ※初期値、TD確率、学習の試合数の値は予備実験によって決定した 17 実装と実験環境 • 本手法では一部の操作が各個体で独立に計算可能なため、 マスター・ワーカ方式を用いて並列化した • 実装にはC++とMPIを用い、実験では65並列計算をした • 本実験はネットワークに広域分散したクラスタ群である InTriggerで行った • なお、計算はInTrigger内のIntel Xeon E5410(2.33GHz) を搭載したクラスタであるhiro、kobe、keio、kyushu、 kyutech、tohoku、tsukubaを用いた 18 同一世代数での比較実験：概要 • 各手法で500世代の学習を行い、その結果を比較した • 比較対象の手法も本手法と同じ条件で実験を行った • ただし、TD(λ)学習のみを用いる手法では初期値を0.0と し、計算時間を合わせるために1世代での学習試合数を ２倍の2000試合とした • 実験は異なる初期値から10回行い、その結果得られた Zebraに対する勝率の平均及び標準誤差を求めた • 計算に要した平均時間は、本手法が5時間、GAのみ及び TD(λ)学習のみが4時間、Singerの手法が6時間、Kim等 の手法が3時間となった 19 同一世代数での比較実験：結果 本手法の勝率 が最も高い 本手法とTD onlyが 同じような挙動 すべての手法を同一世代数で 評価することは適切でない？ Singer’s methodで60世代 以降勝率が下降している 本手法とGA onlyが 同じような挙動 本手法はGAとTD(λ)学習の 特徴をうまく取り入れている 20 同一世代数での比較実験：結果 • 他の手法に比べて本手法が高い勝率を記録している • 本手法は初めの世代でTD onlyと同じような勝率の伸び を、その後はGA onlyと同じような勝率の伸びを示して おり、２つの手法の特徴をうまく取り入れられている • しかし、Singer’s methodは60世代あたりから勝率が降 下しており、すべての手法を同じ世代数で評価すること は適切でないと考えられる 21 最適停止世代での比較実験：概要 • GAでは長い世代数を1回やるよりも、同一の計算時間で 少ない世代数を複数回行い、その中から最も最適な結果 を選んだ方がいい場合がある • このように同一の計算時間で最も勝率の高くなる世代数 を最適停止世代という • 各手法で1024世代を1回、512世代を2回、…、16世代を 64回と実験を行い、各世代での勝率の期待値を求めた • 勝率の期待値は、各世代で得られた個体を使って50回 トーナメントを行い、トップとなった個体のZebraに対 する勝率の平均値として求めた 22 最適停止世代での比較実験：結果 本手法では勝率の降下が小さく、 安定して解が得られている すべての手法で途中から 勝率が降下している TD onlyで16,32,64世代の勝率 がぶれているが、原因は不明 23 最適停止世代での比較実験：結果 • 各手法とも途中から勝率が下降しており、特定の世代で 止めて反復回数を増やした方が良いことが分かる • しかし、本手法は256世代以降も勝率がほとんど下がっ ておらず、得られる解が反復回数に依らず安定している • TD onlyだけは16, 32, 64世代で勝率が大きくぶれている が、その原因は不明 24 各手法間の直接対決：概要 • 最適停止世代の比較実験より、下表のように各手法のお おまかな最適停止世代が分かった • 各手法の最適停止世代での局面評価パラメータ同士を対 戦させ、その強さを比較した • 対戦の方法はZebraの場合と同様とした 手法 最適停止世代 proposed method 256 GA only 512 TD only 256 Singer’s method 64 Kim’s method 512 25 各手法間での直接対決：結果 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での順位 26 各手法間での直接対決：結果 • 本手法はすべての対戦で勝ち越している • Zebraに対する勝率を用いた場合に比べて強さの順位が 異なるが、Zebraに対する勝率、直接対決のいずれの場 合も本手法が最も好成績をあげている 27 本発表の流れ • 背景と目的 • 関連研究 • 提案手法 • 実験と結果 • まとめと今後の課題 28 まとめ • 本研究ではGAとTD(λ)学習をハイブリッドGAの観点か ら組み合わせることで、従来よりも汎用性の高い手法を 提案した • 従来手法にはなかったTD(λ)学習を制御するパラメータ を導入することで、GAとTD(λ)学習の特徴をうまく融合 することができた • オセロの局面評価パラメータの調整を例に従来手法との 比較を行ったところ、従来手法に対して54.3～69.5%の 勝率を得た 29 今後の課題 • オセロ以外の問題を用いた実験 • TD確率を状況に応じて動的に変化させるような本手法 の拡張 • TDLeaf(λ)[J. Baxter et al. 2000]、TDMC(λ)[大崎泰寛 et al. 2008]、iLSTD(λ)[A. Geramifard et al. 2007]といった TD(λ)学習の拡張手法の本手法への適用 30 本研究は3/9の第21回ゲーム情報学研究会にて発表予定
© Copyright 2024 ExpyDoc
