GA将？開発日記～王理のその先へ～

ネタ勢最強を目指して絶賛開発中。

PGLeaf Drei全面的に書き直す事にした

開発日記

現状

　Policy Gradient Methods for Reinforcement Learning with Function Approximation

　まず、上記論文の関数近似器の導入は断念しました。何をどういじっても、素のPGLeaf以上の性能にはならなかったので。

　やった事は大体こんな感じ。

  1. 論文の手法をそのまま実装 → NG
  2. f_w \left( s, a \right) = \tanh( w^T \nabla \log\left( \pi \left( s, a \right) \right)と変形してみた → NG
  3. f_wの代わりに評価値を用いる → NG
  4. f_wの代わりに評価値から予測した報酬の期待値を用いる → NG

考察

　上記論文によると、まずf_wと評価関数の学習を並行して行うので、学習初期のf_wがあまり信用出来ないのでは？という疑問。

　この為、学習初期に変な方向にパラメータ更新してしまい、そのままズルズルとネガティブスパイラルに陥っているのでは、と考えています。

対案

　上記論文の手法をスッパリ諦めて、重点サンプリングを用いた方策勾配法を実装しようかと考えています。

　ベースはLearning to Explore via Meta-Policy Gradientですが、ほとんど原型を留めていません。

　アルゴリズムの擬似コードはこんな感じ。推定方策内の評価関数パラメータが、実戦（WCSC・UEC杯等）での対局用になります。

  1. 推定方策\pi_tと探査方策\pi_eを初期化。（推定方策は評価関数を内部に持つ。また、探査方策はそれとは独立した評価関数を内部に持つ。）
  2. エース評価関数を初期化。
  3. 以下、無限ループ
    1. M局*1探査方策を用いて自己対局する。
    2. M局分の棋譜を元に、推定方策のパラメータを更新する。更新後の方策は\pi_t'とする。
    3. エース評価関数と\pi_t'を用いて連続対局を行い、レーティング差⊿Rを求める。
      1. ⊿Rをメタ報酬として、探査方策のパラメータを更新する。（ここは上記論文の手法そのまま。）
      2. \pi_t'が優位に強くなっていれば、\pi_t \leftarrow \pi_t'と更新する。また、推定方策内の評価関数パラメータをエース評価関数にコピーする。

　評価関数の初期化は、極小さな乱数で初期化を行う予定です。

　ただ、\pi_tと\pi_eでは方策の分布に差異があるので、ここを補正してやる必要が有ります。有り難い事に、重点サンプリングという既存手法がありますので、これを用います。

　まず、推定方策内のパラメータベクトルを\theta_t、探査方策内のパラメータベクトルを\theta_eとします。また、P\left( d; \theta, \pi \right)を「パラメータ\theta、方策\piに従ってエピソードdが出現する確率、R_dをエピソードdの収益とします。

　この時、報酬の期待値J\left( \theta_t \right)を\theta_tで偏微分すると、下記の様になります。これは通常のREINFORCEアルゴリズムですね。

\nabla_{\theta_t} J \left( \theta_t \right) = \nabla_{\theta_t} \int R_d P \left( d; \theta_t, \pi_t \right) = \int R_d P \left( d; \theta_t, \pi_t \right) \nabla_{\theta_t} \log P \left( d; \theta_t, \pi_t \right)

　ここで、インポータンス・ウェイト \eta \left( d \right) = \frac{P \left( d; \theta_t, \pi_t \right) }{P \left( d; \theta_e, \pi_e \right)}とすると、上記の式はこう変形出来ます。

\nabla_{\theta_t} J \left( \theta_t \right) = \int R_d \eta \left( d \right) P \left( d; \theta_e, \pi_e \right) \nabla_{\theta_t} \log P \left( d; \theta_t, \pi_t \right)
　
　\etaがいきなり出てきましたが、\eta \left( d \right)の分母と上記の式のP \left( d; \theta_e, \pi_e \right)は打ち消し合うので、2つ上の式と同じになる事が確認出来ると思います。

　こうすると何が嬉しいかと言うと、「探査方策\pi_eを用いてサンプリングした結果から、推定方策\pi_tの勾配が計算出来る様になる」事です。

　実際にサンプリングした結果から勾配を求める式は、下記の通りとなります。なお、d_mはm局目のエピソード、T_mはm局目の総手数です。

\nabla_{\theta_t} J \left( \theta_t \right) = \frac{1}{M} \sum_{m=1}^M R_d \eta \left( d_m \right) \frac{1}{T_m} \sum_{t=1}^{T_m} \nabla_{\theta_t} \log \pi_t \left( s_t, a_t \right)

　重点サンプリングを用いたOff-Policy方策勾配法は、2年ほど前に動かしてそこそこちゃんと動いてたんで、今回も上手く行ってくれる事を期待しています。

*1:M=100～1000程度

PGLeaf Drei Phase1完成していなかった

開発日記

　え～、PGLeaf Dreiですが、三目並べモードではかなり良い感じだったんですが、5五将棋モードではてんでダメでした ＿|￣|○

　学習開始時*1からのレーティング上昇量が4300とかになってウハウハだったんですが、sspと対局させると勝率が3割前後。

　という訳で、もうちょっと頑張らないとだね。という感じです。

*1:全パラメータを微小な乱数で初期化した状態

PGLeaf Drei Phase1完成

現状

　素のPGLeafとの差分は以下の通りです。

  1. 関数近似の導入（参考論文はこちら）
  2. エントロピー正則化の導入（参考論文はこちら）
  3. 並列16連ガチャの導入

　まず、1.の導入により、エピソード終了時の収益を計算しなくても、方策勾配の計算が可能になりました。これにより、Phase2～3でExperience Replayを導入する目処がたちました。

　次に、2.で指し手の多様性を確保する事に成功し、三目並べモードでは収束速度が向上しました。5五将棋モード・本将棋モードでは未検証ですが、上手く動いてくれるのを期待しています。

　ただ、それでもまだ「正しく収束するかは運次第」という部分も有りますので、3.の並列ガチャを導入しました。結果的に、三目並べモードでは30秒*1かからずに正しく収束する様になりました。

　昨日の時点では並列16連ガチャは「適当なタイミングで全評価関数のパラメータの平均を計算し、それをベースに再度学習を開始する」というものでした。ただ、現在は少し修正して、GA*2の交叉処理っぽく「2つのパラメータ間の内分を、トータルでは評価関数の個数分だけ計算する」という処理に変更しました。これにより、評価関数パラメータの多様性を維持しつつ学習を進められる様になっているはずです。

考察

　並列16連ガチャに関して「ガチャ」とか言わずに真面目に考察してみます。

　前提として、自己対局による学習を行うものとします。また、三目並べモードでの動作について考えるものとします。

　この時、初手であれば角や中央は「その後の展開が間違えにくく、負けにくい」手であり、辺は「その後の展開が広いので、負ける可能性が高い」手です。

　つまり、学習初期に「角や中央に打てば負けにくい」と学習してしまうと、先手は初手辺に打つ手を自己対局の際にほとんど選択しなくなります。

　この結果どうなるかと言うと、「先手GA将 VS 後手完全読みプレイヤー」の場合は引き分け率が100％になるのですが、先後入れ替えると引き分け率が100％になりません。これは、先手が辺に打った後の展開を学習する機会がほとんど無いのが原因です。

　では並列16連ガチャを導入するとどうなるかと言うと、複数のエージェントが並行して学習しますので、多数のエージェントは初手角・中央を選択していても、一部のエージェントは初手辺を選択する確率が高くなります。

　並列16連ガチャでは「収束判定に使用するパラメータは、全評価関数のパラメータの平均値」です。また、パラメータは全て0で初期化しています。

　ですので、「初手角が得意なエージェント」と「初手中央が得意なエージェント」と「初手辺が得意なエージェント」（ただし、それぞれエージェントの個数は異なる）の平均値を取ると、どういう局面に関しても「そこそこ妥当なパラメータ」が得られます。

　ここからは将棋の場合の話になりますが、将棋モードでは線形の評価関数を使用しますので、「パラメータの平均値をとる」という処理が果たして正しいのか、という問題は残っています。

　例えば「居飛車が得意なパラメータ」と「振り飛車が得意なパラメータ」の平均値を取れば「オールラウンダーなパラメータ」になるのか、という疑問です。

　ひょっとしたら「捌く居飛車」とか「ゴリゴリ攻める振り飛車」っていう棋風になるかもしれません。が、まぁそれはそれで見ていて面白そうなんで、特に気にしなくて良いかなと感じています。

*1:ノートPCだと1万局程度

*2:遺伝的アルゴリズム

PGLeaf Drei Phase1 with 並列16連ガチャ、ほぼ完成

開発日記

　まず、先日書いたエントロピー正則化ですが、三目並べモード＋PGLeaf Dreiである程度ちゃんと動く様になりました。

　ただ、それでも乱数の偏りが原因（？）で、局所最適解にハマってしまう事もしばしば。ま、ソシャゲのガチャみたいな感じですね。

　んで、「ガチャになるなら当たるまで回せば良いじゃないか」と考えて、シングルスレッドの学習ルーチンを16並列で走らせて、最終結果*1を平均化したモノを完全読みプレイヤー相手に対局させてみました。

　したら、まーなんと、メタパラメータがテキトーでもちゃんと収束しました！ 学習率を1桁2桁変えてもOKですし、正則化係数も多少値を変えた位では最終結果に影響しませんでした。割と本気で、収束判定ルーチンのバグを疑った位です*2。

　そういう訳で、PALさんの「高回転並列学習」程ではないにせよ、学習ルーチンを並列で回して結果を統合するって線で何とか行けそうな雰囲気になって来ました。現時点では、ちゃんとコードをリファクタリングしてから将棋モードでも動く様に対応しました。

　ただ、単に並列ガチャだけだと面白くないので、途中で「並列に学習した評価関数パラメータ群の情報交換」を入れようかと思っています。GA*3の交叉みたいな処理ですね。

　本将棋モードで交叉処理無しの場合だと、学習用マシンの空きメモリが16GB程度*4しかありません。なんで、「省メモリで複数の評価関数を交差させる」処理をひねり出さないといけなさそうです。まぁ、最悪ストレージに書き出しておくって手も有るんで、何とかなるかと思いますが。

　ツー訳で、来年の選手権では「GA復活！！！」って事になるかもしれません。乞うご期待。

*1:1ステップ50局×50ステップ経過後のパラメータ

*2:学習率を5桁上げたら、流石に正しく収束しませんでしたが

*3:遺伝的アルゴリズム

*4:評価関数2～3個分

キーボード逝ったーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーッ！！！

　ThinkPadトラックポイントキーボードを愛用しているんですが、Ctrlキー*1が壊れましたｗ

　まぁ、xkeymacsでCtrlキーを酷使する設定にしてるから、しゃーないか。

　5年前の時点で4つあったストックが、現時点では残弾1。あと2年半か3年位で次のキーボード買わないといけないかな。

*1:配列入れ替えてるんで、刻印自体はCapsLockキー

現時点で確認している問題点＠三目並べモード

開発日記

　「初手の学習が上手く行かない」。これにつきます。

　対称形を考慮すると初手は三通りあるんですが、学習を進めていくとこの内どれか一手しかほとんど指さなくなります。

　で、これがどう困るかと言うと、先手に関しては対完全読みプレイヤーの引き分け率が1になるんですが、後手はなりません。先手が特定の手だけ指すので、それ以外の手の場合の展開を学習する機会がほとんど無いので。

　三目並べモードでこの状況ですから、例えば将棋モードでも「先手は居飛車しか指さない」ってなると、後手は「対居飛車の戦法しか知らない」って状況になりそうなんで、ちと困ります。

　今はエントロピー正則化を色々いじって試している所ですが、これで何とかなれば良いんですがねぇ…

今日の予定

開発日記

　MC Softmax 探索における局面評価関数の学習

　GPW 2018で五十嵐先生に発表してもらった上記論文（五十嵐先生・山本一将さんとの共著論文）ですが、理論の提案だけで学習実験がまだです。

　という訳で、実験用にプログラムの修正作業をするのが一つ。

　それから、エントロピー正則化が実装出来そうな感じなので、並行してそれもやっていきます。

　時間はたっぷり有るんで、両方完成すると嬉しいなぁ。