Bonanza6.0の棋譜からの学習 ～左右対称はありまぁす～ [将棋]
去年レーティングがすごい伸びたのは
以下がきっかけだったのかなと予想している。
http://www.computer-shogi.org/wcsc24/appeal/NineDayFever/NDF.txt
相対化を学習に取り込んだところ良かったらしい
（複数の変更があるのでどの程度良くなったかどうかは不明）
では、Bonanzaはまったく相対を考慮していないのかというとそんなことはなかった。
Phase1
・棋譜を今の評価関数で評価する
・指し手の中である程度有望そうな手を更新予定として保存する
（ここはあまり自信がない）
・Phase2
Phase1の結果から、評価関数の更新量を計算する
ここがちょっと特殊
・終了処理
左右対称の更新量を合算する
駒割りが発散しないように調整する
L1正則化っぽいことを行う
学習元のfvテーブルを更新する
評価関数に使う駒割りの差分を更新する
となっている。
ここでの合算というのが、計算をし終わった上で合算しているので
本当にそれでいいのかは理解できていない。
数をこなしているうちに収束するから大丈夫だろうということだろうか。
また、Bonanzaの更新量はシグモイド関数とみせかけて違うのは
合算しても問題ないようにしたのかもしれない
（あと仮定として学習によって更新しても指し手が変わらないので
あんまり急激な変更は入れたく無いというのがある気はする）
＜下記に追記しました＞
それはともかく、最終的な結果として左右対称の場合は値が同じになるように調整されている。
これをさらに一般化して完全に縦方向も相対化したというのがNDFのアピール文章で
相対化の後絶対学習をさせ、そのときに相対化された項目の値が残るように
目的関数を設計しているようである。
また、少ない棋譜での学習については以下の様な書き込みが２ｃｈにあった。
自分も追加で学習を繰り返していけば強くなるのではないかと思ったが
それこそ素人の浅はかさで、すべての学習に使った棋譜＋問題の棋譜のようにしないとうまくいかないし
部分的に追加された項目が指し手に現れるかというとまず現れない。
これは、今のBonanzaの学習ルーチンの設計がそうなっているからで
具体的にはPhase2が終わって最後の計算をする前に
ペナルティ（ノイズを消す）がかかっていて、そこで消されているからであると思われる。
（具体的にはrparam)
大雑把に書くと
・数万局の棋譜で指し手の頻度を調べる
・指し手の頻度に応じてパラメータを更新する
・ノイズを消す（ペナルティ＝少し減衰させる）
となっているので、今の関数に部分的に学習したいと思っても
最後のノイズを消す作業によって、微妙についていた値が全部消されてしまって
のっぺりした評価関数になっていると思われる。
やねうら王Blogでペナルティを何とかしたいようなエントリがあった。
http://yaneuraou.yaneu.com/2015/01/08/%E3%81%9D%E3%82%8C%E6%9C%AC%E5%BD%93%E3%81%AB%E9%81%8E%E5%AD%A6%E7%BF%92%EF%BC%9F/
少ない棋譜から学習したり、効率をあげるには何かしらのアルゴリズム的な変更が求められる。
＝＞もしかして：オンライン学習
＜追記＞
妙にRTされたので少し補足
局面評価の学習を目指した 探索結果の最適制御
http://www.geocities.jp/bonanza_shogi/gpw2006.pdf
変化量はsign関数なので一定量しか動かないようになっている
http://ja.wikipedia.org/wiki/%E7%AC%A6%E5%8F%B7%E9%96%A2%E6%95%B0
将棋の棋譜を利用した，大規模な評価関数の調整
http://www.graco.c.u-tokyo.ac.jp/~kaneko/papers/gpw08.pdf
軽くBonanzaの学習方法について触れられているが、考え方は概ねあっているようだ。
ただ、基本的な考え方は同じではあるが、
この当時のBonanzaは1.0ぐらいだと思われるので、いまのとは当然形が違う。
PPTによれば変化量は一定のように書かれているが、
Bonanza 6.0の最終的に値を更新していると思われるrparam場所では
乱数を利用して学習している。（RはRandomの略だろうか）
これは合議などを行う際に、全く同じ結果で合議しても意味が無いことから入っている乱雑さだと思われる。
更新量は変化の度合いに関わらず、正負だけで
0 : 25%
1 : 50%
2 : 25%
の範囲で更新するようになっている。後手番だと負の値になる。
なので、この部分を合議するつもりがなかったり、さっさと収束させたい場合は
のようにしてしまえば、あっという間に過学習気味に終息すると思う。
元々のdvがシグモイド関数の微分値から求められているので、
これでも案外いい線いくのではないかと予想している。
（GPSの学習も微分不可能なのに微分可能であるとして
大胆に学習させてそこそこうまくいったような論文があった）
そして、このような学習方法であることと、先日やねうら王Blogが書いてあったコードを見ると、やねうら王の学習パラメータの一部を勝手に推測できる。
http://yaneuraou.yaneu.com/2014/12/30/stockfish-dd-bitcount-h/
この表現こそまさに今のrparamの中でやっていることだと思われる。
& 7となっているので、０～２５５の値で中央値は１２８ぐらい。
FV_SCALEをそのままだとすると４点ぐらい一気に動かすようにしていたりするのだろうか。
＜追記の追記＞
ビット数えてるので、０～３でした、Bonanzaよりも１点だけ多く変動するだけでした。orz
＜追記の追記終わり＞
＜追記終わり＞
以下がきっかけだったのかなと予想している。
http://www.computer-shogi.org/wcsc24/appeal/NineDayFever/NDF.txt
相対化を学習に取り込んだところ良かったらしい
（複数の変更があるのでどの程度良くなったかどうかは不明）
では、Bonanzaはまったく相対を考慮していないのかというとそんなことはなかった。
Phase1
・棋譜を今の評価関数で評価する
・指し手の中である程度有望そうな手を更新予定として保存する
（ここはあまり自信がない）
・Phase2
Phase1の結果から、評価関数の更新量を計算する
ここがちょっと特殊
・終了処理
左右対称の更新量を合算する
駒割りが発散しないように調整する
L1正則化っぽいことを行う
学習元のfvテーブルを更新する
評価関数に使う駒割りの差分を更新する
となっている。
ここでの合算というのが、計算をし終わった上で合算しているので
本当にそれでいいのかは理解できていない。
数をこなしているうちに収束するから大丈夫だろうということだろうか。
また、Bonanzaの更新量はシグモイド関数とみせかけて違うのは
合算しても問題ないようにしたのかもしれない
（あと仮定として学習によって更新しても指し手が変わらないので
あんまり急激な変更は入れたく無いというのがある気はする）
＜下記に追記しました＞
それはともかく、最終的な結果として左右対称の場合は値が同じになるように調整されている。
これをさらに一般化して完全に縦方向も相対化したというのがNDFのアピール文章で
相対化の後絶対学習をさせ、そのときに相対化された項目の値が残るように
目的関数を設計しているようである。
また、少ない棋譜での学習については以下の様な書き込みが２ｃｈにあった。
508 名前：名無し名人[sage] 投稿日：2015/01/12(月) 07:22:18.60 ID:xPf01yZ4 [1/2] 棋譜はとにかく数が多くないとダメっぽいね 2000局位(羽生さん多め)を追加学習させてノーマルbonanzaと100局対戦させてみたら勝率４割程度しかなかった
自分も追加で学習を繰り返していけば強くなるのではないかと思ったが
それこそ素人の浅はかさで、すべての学習に使った棋譜＋問題の棋譜のようにしないとうまくいかないし
部分的に追加された項目が指し手に現れるかというとまず現れない。
これは、今のBonanzaの学習ルーチンの設計がそうなっているからで
具体的にはPhase2が終わって最後の計算をする前に
ペナルティ（ノイズを消す）がかかっていて、そこで消されているからであると思われる。
（具体的にはrparam)
大雑把に書くと
・数万局の棋譜で指し手の頻度を調べる
・指し手の頻度に応じてパラメータを更新する
・ノイズを消す（ペナルティ＝少し減衰させる）
となっているので、今の関数に部分的に学習したいと思っても
最後のノイズを消す作業によって、微妙についていた値が全部消されてしまって
のっぺりした評価関数になっていると思われる。
やねうら王Blogでペナルティを何とかしたいようなエントリがあった。
http://yaneuraou.yaneu.com/2015/01/08/%E3%81%9D%E3%82%8C%E6%9C%AC%E5%BD%93%E3%81%AB%E9%81%8E%E5%AD%A6%E7%BF%92%EF%BC%9F/
ボナメソでは出現しなかった特徴因子の値はゼロに収束するようにしてあります。ところが、iterationをある程度回すと、それぞれの棋譜のそれぞれの局面のPVは固定化してきてしまい、いままで出現していて、きちんと値がついていた特徴因子も出現しなくなるので、これらがすべてゼロに収束していく現象が起きます。
少ない棋譜から学習したり、効率をあげるには何かしらのアルゴリズム的な変更が求められる。
＝＞もしかして：オンライン学習
＜追記＞
妙にRTされたので少し補足
局面評価の学習を目指した 探索結果の最適制御
http://www.geocities.jp/bonanza_shogi/gpw2006.pdf
変化量はsign関数なので一定量しか動かないようになっている
http://ja.wikipedia.org/wiki/%E7%AC%A6%E5%8F%B7%E9%96%A2%E6%95%B0
将棋の棋譜を利用した，大規模な評価関数の調整
http://www.graco.c.u-tokyo.ac.jp/~kaneko/papers/gpw08.pdf
軽くBonanzaの学習方法について触れられているが、考え方は概ねあっているようだ。
ただ、基本的な考え方は同じではあるが、
この当時のBonanzaは1.0ぐらいだと思われるので、いまのとは当然形が違う。
PPTによれば変化量は一定のように書かれているが、
Bonanza 6.0の最終的に値を更新していると思われるrparam場所では
乱数を利用して学習している。（RはRandomの略だろうか）
これは合議などを行う際に、全く同じ結果で合議しても意味が無いことから入っている乱雑さだと思われる。
更新量は変化の度合いに関わらず、正負だけで
0 : 25%
1 : 50%
2 : 25%
の範囲で更新するようになっている。後手番だと負の値になる。
なので、この部分を合議するつもりがなかったり、さっさと収束させたい場合は
*pv += dv;
のようにしてしまえば、あっという間に過学習気味に終息すると思う。
元々のdvがシグモイド関数の微分値から求められているので、
これでも案外いい線いくのではないかと予想している。
（GPSの学習も微分不可能なのに微分可能であるとして
大胆に学習させてそこそこうまくいったような論文があった）
そして、このような学習方法であることと、先日やねうら王Blogが書いてあったコードを見ると、やねうら王の学習パラメータの一部を勝手に推測できる。
http://yaneuraou.yaneu.com/2014/12/30/stockfish-dd-bitcount-h/
私は棋譜からの学習のときに評価因子に正規分布っぽい乱数を加算するのに、popcount(rand() & 7) とかやってますが(二項分布≒正規分布なので)…まあ、こんなところはたいした問題ではないですね。
この表現こそまさに今のrparamの中でやっていることだと思われる。
＜追記の追記＞
ビット数えてるので、０～３でした、Bonanzaよりも１点だけ多く変動するだけでした。orz
＜追記の追記終わり＞
＜追記終わり＞
追記の最後、&7は0から7で、さらにpop countしてるので0から3なのでは？
by かず@なのは (2015-01-15 09:48)