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

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

明けましておめでとうございます

雑記

　既に2日になっていますが、本年も本ブログとGA将をよろしくお願いします。

　今年の目標ですが、当面は3月のUEC杯5五将棋大会と5月の世界コンピュータ将棋選手権への参加ですね。

　現在の学習ルーチンが割と良い感じなので、このまま学習を継続し、後は思考時間制御とかPonder周りのテストとか、その辺を2月中には終わらせようと思っています。

　本将棋モードの学習は3月に入ってから開始する事になるかと思いますが、まぁ2ヶ月あれば何とかなるでしょう、多分。

　そんなこんなで今年も行き当たりばったりになりそうですが、出来る限り頑張ろうと思います。

Optimizerの設定、間違ってた

開発日記 学習経過

　gasyou.hatenablog.jp

　昨日はRMSPropと書きましたが、設定を見直したらRMSProp＋慣性項になっていました。

　…まぁ、強くなってるから良いか。今の学習が頭打ちになったら、RMSPropのみに設定変更して、も一度学習しよう。

　ちなみに現在の棋力ですが、164万局経過後のパラメータで対ssp（ハンディキャップマッチ）が182勝71敗。勝率71.7％なので、このまま順調に行けば過去最高勝率を更新出来そうです。

　あ、そうそう。もう一つバグが。ログ出力のルーチンがバグってて、http://gasyou.is-mine.net/ura/の「KPP_v11玉_^33金_持ち駒^銀1」のグラフは、「KPP_v11玉_^33金_v22金」の値がプロットされていました。

　なんか、かなり良い形なのにパラメータがマイナスになってておかしいと思ってたんですよねぇ。

PGLeaf Dreiの現在の構成

開発日記 学習経過

　色々やって原型とどめ無くなってきたので、一旦整理。

  1. 勾配計算に用いるのはPGLeaf＋モンテカルロ法
    1. PGLeaf項はGPWの論文そのまま
    2. モンテカルロ項は評価値をシグモイド関数に通して予測勝率に変換し、交差エントロピーを最小化する
  2. Softmax方策＋αβ探索＋線形の評価関数（駒割・PPT・KKPT・KPPT・王将の移動可能範囲）
  3. Entropy Regularizationを係数*10.05で適用
  4. Noisy Networks風に、パラメータに平均と標準偏差を設定する
  5. 自己対局の棋譜を元に学習する
    1. 探索条件は、全幅3手（枝刈りはScoutのみ）＋静止探索1段目10手
  6. 自己対局500回を1エポックとし、1エポックごとにパラメータ更新
  7. OptimizerはRMSProp メタパラメータはα==0.0001, γ==0.9, ε==1e-08

　自己対局ですが、5五将棋モードでは大体24時間で90万局程度のスピードです。

　で、現状ですが72万5千局経過後のパラメータで対ssp（ハンディキャップマッチ）の勝率が 60.9％。PGLeaf Zweiで同等の勝率になるには800万局必要だったんで、収束速度はかなり高速化しています。

　問題は伸び代なんですが、こればっかりは実験を進めてみないとどうしようも判断つきません。

　今後の予定ですが、このままPGLeaf Dreiでの学習を継続し、3月のGAT杯コンピュータ5五将棋大会に参加予定。その後、本将棋の学習を開始して選手権に間に合わせるつもりです。

*1:A3Cの論文のβ

そう言えばちゃんと書いてなかったけど、レベルアップ判定のお話

開発日記

　現在のGA将は自己対局500回を1エポックとして、10エポックごとにレベルアップ判定をしています。

　レベルアップ判定は、現在の評価関数と「過去8代のエース評価関数」を相手に各50局、先後入れ替えて計400局実施し、勝率が55％超えたらレベルアップ、45％切ったらレベルダウンとします。

　レベルアップしたら過去のエースを順に後ろにずらして行き、最新のエースを現在のパラメータで上書きしています。

　何でこんな面倒な事を知ているかと言うと、「グーチョキパー問題」が発生していた可能性があるからです。

　以前にジャンケンの強化学習をした事があったんですが*1、「グーばかり出す方策が出来る」→「パーばかり出せば勝率上がるので、そういう方策に変化する」→「今度はチョキばかり出す様になる」という現象がありました。

　んで、将棋でも同様の現象が起こる可能性があると考え、現在の方式に変更しました。これなら、過去のエース達相手に勝率を出すので、どんな戦法相手でもある程度勝てないとレベルアップしないはずです。

　それから、レベルアップ時の勝率を元にレーティング上昇量を計算して、グラフにしてみました。

　…が、どうもこのレーティング、怪しいです。自己対局でRが100上昇しても、対sspのRは9前後しか上がりません。

　自己対局なんでちょっとしたパラメータの差が大きなレーティング差として表れている、という可能性はありますが、詳細は不明です。

　まぁ、レベルアップ判定で出したレーティングと、対sspのレーティングは綺麗に比例しているので、このまま気にせずに行きたいと思います。

*1:同じ方策を使って、自己対局で学習する方式

Noisy Networkを応用してみたら意外と良い感じになってきた

開発日記 学習経過

　Twitterで@mooopan氏に教えてもらった論文を参考にして、線形の評価関数にノイズを加えるのを試してみました。

　http://gasyou.is-mine.net/ura/ の上3つのグラフがパラメータの推移なんですが、線の上下の帯状の部分が標準偏差です。

　これを見ると、ある程度値が確定しているパラメータは標準偏差が小さく、未確定のは大きくなっている様です。

　現時点では、24万5千局自己対局後のパラメータで対ssp（ハンディキャップマッチ）の勝率が35％前後。まぁ、学習初期としては悪くない値です。

　前回PGLeaf Zweiで最高勝率69.3％を達成した時は1000万局学習したので、2週間程度放置すれば追い付けるかどうか判断出来そうです。

なんとなく、私がやりたいのは最終的にベイズ方策勾配法に落ち着く様な気がしてきた

後で読む

　http://papers.nips.cc/paper/2993-bayesian-policy-gradient-algorithms.pdf

　ただ、論文読んでも理論もアルゴリズムもサッパリ分からんｗ

「確率的パラメータを持つ方策関数に対する方策勾配法」読んだまとめ

開発日記

ci.nii.ac.jp

概要

　オープンアクセス不可の論文なんで、気になった所だけ書こうと思います。

  1. 通常の方策勾配法では、パラメータ\thetaは「確定的な」ベクトルである。これを、ハイパーパラメータ\nu*1から生成される「確率的な」ベクトルに拡張する。
    1. つまり、\thetaの値は（多分）エピソードごとにランダムに変化する。
    2. 学習の目的は、\nuを最適化する事。
  2. 方策\pi \left( a | s; \nu \right) = \int_\theta p \left( a | s ; \theta \right) p \left( \theta | \nu \right) d \thetaとする。
    1. p \left( a | s ; \theta \right)は、状態s・（ランダムに生成された）パラメータ\thetaのもとで行動aを選択する確率。
    2. p \left( \theta | \nu \right)は、ハイパーパラメータ\nuのもとでパラメータ\thetaが生成される確率。
  3. 後は、この方策を\nuに関して微分してやって、方策勾配法でよしなに最適化する。

　こうすると何が嬉しいかと言うと、探索・搾取のトレードオフを自動的に解決出来る事らしいです。学習初期は分散を大きめにとって探索重視、ある程度学習が進んだら自動的に分散が減少していって搾取重視にシフトしていく、と。

PGLeafへの適用

　原論文では\nuに含まれる分散は1つだけの様に読み取れました。つまり、「全てのパラメータ\theta_iに対して、共通の分散を用いる」らしいです。

　ただ、コンピュータ将棋に関しては個々のパラメータに対して分散があった方が良い様に思えます。例えば、「歩1枚の価値はだいたい推測出来ている*2が、持ち駒の6枚目の歩の価値は曖昧*3」という状況が起こり得ると思います。

　という訳で、ハイパーパラメータ\nuは「2（平均、分散）×パラメータの個数」分の要素を持つベクトルにしようと思います。

　後は方策勾配ですが、原論文では連続状態・連続行動問題を扱っているので解析的に求めていました。ただ、PGLeafではp \left( a | s ; \theta \right)はSoftmax関数とαβ探索・評価関数の組み合わせになるので、多分解析的には解けません。

　具体的には、p \left( a | s ; \theta \right)は下記の様になります。

\displaystyle p \left( a | s ; \theta \right) = \frac{\exp \left( evl \left( a, s', \theta) \right) \right)}{\sum_{x \in A \left( s \right)} \exp \left( evl \left( x, y', \theta) \right) \right)}

　s',y'はそれぞれ「状態（局面）sから行動（指し手）a,xを指した後の、αβ探索のPV Leafノード」になります。また、A\left(s\right)は局面sにおける合法手の集合です。αβ探索についてはアルファ・ベータ法 - Wikipedia等をご参照下さい。

　また、evl \left( a, s, \theta \right) = \sum_{i=1}^N \phi_i\left(s\right) \theta_iとなります。（\phi_i \left(s\right)は、局面sの特徴量*4）です。）

　これを解析的に解くのは難しそう（無理？）なので、\thetaに関するモンテカルロ積分をしてやって解く事にします。

　具体的にはM回*5のサンプリングを行い、

\pi \left( a | s; \nu \right) = \frac{1}{M} \sum_{m=1}^M p \left( a | s ; \theta \right)

とします。

　\nuが消えちゃったので微分しようが無いですね。困りました。

　かなり複雑な関数の積分をしたいのですが、自力では出来なくて質… - 人力検索はてなで質問しました。ベストな回答には1,000pt進呈しますので、分かる方がいらっしゃればご回答お願い致します。

*1:正規乱数の平均・分散。後、元の論文では別の字が使われてたけど、読み方が分からないので似た字をあてている。

*2:分散は小さくていい

*3:分散を大きくしたい

*4:駒割等

*5:M=100～1000程度