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

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

5五将棋用連続対局サーバの機能追加、ほぼ完了

　えー、まず以前の記事の訂正から。

　「Winboard」がShokidoki/Limaの使用しているプロトコル名だと思ってましたが、正式には「xboard」みたいです。もともとUNIX用のXBoardというチェスのGUIがあって、それが使用していたプロトコルが「xboard」。で、XBoardのWindows移植版がWinBoardという名称みたいですね。

　んで、そのxboardのエンジンを連続対局サーバから呼び出すのは、多分出来る様になりました。エンジンが異常な挙動をする*1事は無くなりましたし、GA将と連続対局させてもまぁ妥当な勝率になってます。

　現時点では、Fairy-Stockfish/Shokidoki/Limaをスパーリング相手にしています。エンジンのダウンロードは下記サイトから行いました。（Fairy-Stockfishのみ、少しソース修正して自前でビルド。）

github.com
hgm.nubati.net
sites.google.com

　Limaに関しては、おそらくUEC杯版とほぼ同じバージョンが公開されていると思われますので、まぁこっちは大丈夫でしょう。

　ただ、Shokidokiですが、公開版には定跡が入っていないのか、古い版なのかは分かりませんが、かなり弱いです。第11回UEC杯版とほぼ同じ棋力のGA将？が8割がた勝っちゃってます。

　それと、Shokidoki/Limaはスレッド数を指定しても無視してシングルスレッド探索になっているっポイんですが、これに関しては原因不明。現在調査中です。

　まぁ、スパーリング相手としてはシングルスレッドでも十分強いんで、このままでも良いかな、とは思っていますが。

*1:Illegal Moveを返すとか、反応しなくなるとか

VS Fairy-Stockfish勝率

　Ryzen 5 2400G搭載マシンでGA将と対局させた結果、勝率はこっちから見て15％前後でした。

　という事は、UEC杯で2局指して少なくとも1局勝つ確率は28％前後あった訳で…

　その28％を本番で引いてりゃUEC杯初優勝だったのに……

　まぁ、終わった事なんでそれはこっちに置いといて、来年に向けて開発再開しますかね。

5五将棋用連続対局サーバの改良中

　今まではGA将対ssp専用で実装していたのを、Winboardプロトコルのエンジン含む複数エンジン相手に対局可能な様にしようとしています。

　んで、現在はFairy-Stockfish3つ相手に対局してログ出力出来る様にまではなりました。

　後はWinboardプロトコルのエンジンへの対応ですが、これはもうちょっとかかりそうです。何しろUSIとは色々違うので、まずプロトコルの理解から始めないといけない状況です。

　それから、Fairy-StockfishをVC++2015でビルドして5五将棋モードで対局させるのはとりあえず成功しました。ソースの修正箇所としては、スレッド数・ハッシュサイズのデフォルト値を変更した位で、これはまぁ連続対局サーバの方で対応しても良かったんですが、楽したかったんでFairy-Stockfishのソースをチョロっと書き換えました。後、スタックサイズがデフォルト値だとStack-Overflowしたんで、64MBに増量してみました。

　今後の予定は、Winboardに対応させてShokidokiとLimaもスパーリング相手に加える事ですね。

多数決合議用の、複数の評価関数パラメータセットの学習

　久々の更新ですが、ちょっとだけ進展有りました。

　まず、以前から何回かトライしていた「複数の評価関数を生成し、それらのリーグ戦の結果から強化学習する」という手法ですが、ようやく成功したみたいです。

　以前は学習結果の各パラメータの平均値をファイルに保存しておき、実戦ではその（平均をとった）パラメータにDropoutをかけて対局していました。

　ただ、せっかく学習時に複数のパラメータセットを生成したんですから、それをそのまま使った方が良いんじゃないかと考えました。

　んで、現在の実装では「複数のパラメータセットをそれぞれ個別のファイルに保存しておき、実戦では各評価関数はそれぞれ異なるファイルのパラメータセットを使用する」となっています。

　肝心の棋力ですが、同じタイミングで保存しておいた、平均化したパラメータと生のパラメータ8個を使った場合を比較してみました。5五将棋モードで対局相手はssp、思考時間はGA将0.1秒・ssp1秒です。

　結果、平均化した場合は627勝131敗で勝率82.7％。生のパラメータの場合は988勝149敗で勝率86.9％。ほぼ確実に強くなっています。レーティングは50程度向上した様子。

　パラメータの推移を見た感じだとまだ収束していない様ですので、引き続き学習させてどこまで伸びるか見てみます。

「Combining policy gradient and Q-learning」を読んで、実装する為に最低限必要な知識をまとめてみた。

開発日記

arxiv.org

前提

　二人零和有限確定完全情報ゲームで、自己対局の結果からPGQ（論文の提案アルゴリズム）を用いて評価関数パラメータの学習を行う事を目的とします。

　報酬は「勝ち：+1、引き分け：0、負け：-1」と設定し、終局後に報酬を与えるものとします。

　方策勾配法やQ学習に関しては本エントリでは解説しませんので、適当なリソースに当たって下さい。

論文の重要な部分

　まず、エントロピー正則化ありの方策勾配法を考えます。方策π・状態sに対するエントロピーHは次式です。

　　H^\pi\left(s\right)=-\sum_a\pi\left(s,a\right)\log\pi\left(s,a\right)

　この時、方策勾配法の停留点*1における状況から、「方策π・エントロピーH・状態価値Vを元に行動価値Qを計算出来る」というのが最大のポイントです。

　具体的には、論文の式(5)です。（一部省略して記載します。）

　　\tilde{Q}^\pi\left(s,a\right)=\alpha\left(\log\pi\left(s,a\right)+H^\pi\left(s\right)\right)+V^\pi\left(s\right)

　なお、αはエントロピー正則化係数で、通常は0.01とか0.1が使用される様です。

パラメータ更新則

　方策πはパラメータθを、状態価値関数Vはパラメータwを持ちます。この時、パラメータ更新則は次式の通りです。（論文の式(14)。）

　　\Delta\theta \propto \left( 1 - \eta \right) E_{s,a} \left(Q^\pi-\tilde{Q}^\pi\right)\nabla_\theta\log\pi + \eta E_{s,a} \left(T^*\tilde{Q}^\pi-\tilde{Q}^\pi\right)\nabla_\theta\log\pi
　　\Delta w \propto \left( 1 - \eta \right) E_{s,a} \left(Q^\pi-\tilde{Q}^\pi\right)\nabla_w V + \eta E_{s,a} \left(T^*\tilde{Q}^\pi-\tilde{Q}^\pi\right) \nabla_w V

　ηは第一項と第二項のバランスを取る為のパラメータで、0～1の値を設定します。Q^\piは方策πに従って得られた報酬を用いれば良い様です。

　E_{s,a}で期待値を取る計算が出て来ますが、これはREINFORCEの様にサンプリング結果から計算すればOKかと。

　また、T^*は最適ベルマンオペレータで、論文中では3ページ目に記載があります。

　　T^*Q\left(s,a\right)=\underset{s',r'}{E}\left(r\left(s,a\right) + \gamma \underset{b}{max} Q\left(s', b\right)\right)

　まー要するに、通常のQ学習の目標値を求めるやり方ですね。

GA将？の実装にあたって

　ここからは論文に書いてない事で、「私はこうしました」って話です。

　まず、論文ではパラメータθとwは別個に持っている様でしたが、わざわざ2つに分ける必要性を感じませんでしたので、θのみにしてあります。

　具体的には、方策πと状態価値関数Vは下記の通りです。

　　\pi\left(s,a|\theta\right)=\frac{\exp\left(evl\left(s,a|\theta\right)/T\right)}{\sum_x\exp\left(evl\left(s,x|\theta\right)/T\right)}
　　V\left(s|\theta\right)=2 \cdot sigmoid\left(evl\_qui\left(s|\theta\right)\right) - 1

　evl(s,a|θ)は「パラメータθを用いて、局面sから手aを指した後の探索結果（評価値）」、evl_qui(s|θ)は「パラメータθを用いて、局面sから静止探索をして得られた探索結果（評価値）」です。Vに関しては、報酬が-1～+1なのでVの値もその範囲に収まる様にしています*2。

　メタパラメータですが、α=0.1・η=0.5が三目並べでの実験結果では最適でしたので、本将棋モードでも同様の値を使用しています。

実験結果

　5五将棋モードでの結果ですが、従来のGA将？の学習則（PGLeafとMCの勾配を個別に計算し、適当に加算して最終的な勾配とする）よりも、収束後のレーティングが60程度向上しました。やっぱり、理論的にきちんと考えられているアルゴリズムは優秀ですね。

*1:局所最適解…だと思います。間違っていたらご指摘お願いします。

*2:実験的に、この方が性能が良かった為。

まだまだ迷走中…

開発日記 学習経過

　Factorization Machineを使用した疑似四駒関係は結局上手く行きませんでした。

　という訳で、PPT＋αで何とか強くしようと色々いじってます。

　とりあえず、今までは割引率γを1に設定していましたが、これだとチョットぬるい手を指す事があるので、γ=0.99で学習させてみました。

　んで、途中経過。現在ssp相手に147勝27敗で勝率84.5％。結構強くなりました。

　ただ、角頭をちゃんと守らなかったり、飛車先の歩をなかなか突かなかったりと、見ていて何か変な感じ。まぁ、学習が足りていない可能性もあるので、もうちょっと様子見します。