Bonanzaの疑問点の調査 その２ [将棋]
調査と言いつつ、単に英語読んでるだけなのでタイトルとやってることがイマイチあってない。
本当は軽くまとめようと思ったが、結構量があったので分けたエントリのその２
■４章 Experiments
Bonanzaについて書かれている
Bonanzaのソースのバージョンが論文中は2013とか書かれているが、公開されている6.0は2011更新となっている謎。
評価関数の重みは4000万（このカウント方法は後述）
あと、ほとんどのグラフとかはGPWのどっかにはあると思われる。
（どれも見た記憶はあるが、内容を覚えていない）
●4.1 Setup: Evaluation Functions, Features, and Game Records
・Bonanzaに取り入れられているテクニック
PVS
quience search
static exchange evaluation
killer and history heuristics
null move pruning
futility pruning
late mode reduction
全幅探索という言葉がひとり歩きしていたが、最初から枝刈りのテクニックを使っていた。（当然といえば当然なきもするが）。
枝刈りだけ抜き出して書いてある特集
「コンピュータ将棋における全幅探索とfutility pruningの応用」
Blunderも似たような感じ。
http://www.computer-shogi.org/wcsc21/appeal/Blunder/Blunder.pdf
余談だが、今はなきBlunder公式Blogでは、Blunderに実装した探索は
Stockfish探索よりも成果が良かったという結果を出していた。
・定跡ファイル
自己対戦の結果らしい
・学習に使った棋譜
48566、そのうちプロの棋譜は３万弱
具体的にどの棋譜を使ったかが、書かれている。
・評価関数の次元
A:駒割りのみ １３次元（駒の種類、成り駒が１３種類）
B:KP ６万ちょっと
C:KKP ２４２万
D:KPP ４４２２万
ソースコード上は、左右対称であっても、高速化を考慮して、KPPテーブルは２倍の80Mになっている。
・対称性
先手と後手を入れ替えると評価値がマイナスになる
左右入れ替えた評価値はおなじになる
・Pの取りうる値
状態数は1476であるとしている（shogi.hでenum定義されている値、これは非合法手を消してあるので、81*13*2より少ない）
・目的関数の値
ノーマライズのために、すべての合法手数で割った値を使う
（ただ、この値そのものは何かに使うわけではなくて学習効率を測る指標だと思われる）
・駒割りの制約
ラグランジュ未定乗数法として追加してある定数項は駒割りを一定の数にしている
fill_init_paramの中で初期値を決定している。
他の論文によると初期値はALL500でも収束してくれるらしいが、最初から近い値のほうがよい（当たり前にも思えるが）
・sigmoidの係数
0.0274 = 7/256 でソースに直打ちされている値
100点差があったときに大きく動くように調整したらしい
・正則化項
Jrの係数 0.00625は FV_PENALTY の値
calc_penaltyで計算した値は全く使っていないが、学習がうまくいってるかどうかの指標に使っているのだろう。
この正則化項によって、最大値が決定する。値が大きくなるほどペナルティが大きくなる。
1/160=0.00625
・FV_SCALE
Σ計算は32bitだが、wは16bitなので、2^5 = 32で割った値が格納されている
・更新量
整数の最小値である１に設定している
●4.2 Learning the Piece Values
駒の点数を計算するが、ここで、Tesauro(2001)のChessの論文の方法との対比になっている。
Chessの論文では、伝統的な勾配降下法(conventional gradient descent method？）を使っているが、それを将棋に適用したときに２つ問題がある
１．収束が遅い（１００回回しても収束しない）
２．定数倍で増えていってしまう
１と２は関係しているように思えるが、学習モデルに拘束条件が入っていないので収束しない
一方でボナメソ（の拘束条件）を使うと40回で収束する
Figure 5は別の論文の図にあったはずなので、そっち見たほうが（日本語なので）わかりやすい
Figure 6
拘束条件が無いと、MMTOよりも収束が遅くなる
2006論文などでは、収束させるには入れて当然、みたいにさらっと書いてあるが、裏付けとしてデータを載せている。
Figure 7
高次元ベクトルを評価関数に使う場合、オーバーフィッティングが発生している
正則化なしでは一致率が急激に上昇するので一見ようように見えるが、そのときの０になっている値は0.2%しかなく、正則化後では96.3%になっていることが、オーバーフィッティングであるとする理由。
●4.4 強さの改善
棋譜との一致率と強さの関係
ここでいきなり GPS将棋の紹介
まったく違う評価関数とのELOレーティングでの比較
Figure 8
GPS将棋と、KP、KKP、KPPの比較
これを見るとKKPはあまりレーティングに寄与していないように見える(R50ぐらい)
なのはminiはKP＋PPだったが、ここはKPPのみもしくはKPP＋PPPなんてやってみるとよいのではないか
あとKPPがまだ伸びしろがあるように思える。
NDFのように相対学習などを取り入れることによりR3000超えたりしているので、KPPはまだ点の付け方に工夫ができる余地があるということが、ここ最近の進展だろう。
●4.5 Numerical Stability and Convergence
数値的安定性と収束
早い話がちゃんと正しそうな値に収束するかどうかってことだと思うが、この章では駒の価値だけの評価関数を元に、連続性や、極小値に落ち込まないかどうかを検証している。
・4.5.1 Surface of the objective function
Figure 9
このグラフもGPWのどっかに書いてあった記憶。
極小値があって学習が難しいよという話
・4.5.2 Empirical Convergence and Local-Minima Properties
駒割りだけの学習だが、極小値に陥ってないかの検討
これも別の論文があったような
X5690で200回回すのに一週間
200回も回せば強さにはあまり影響がないらしい
初期値をランダムにして収束が違うか
ある程度まではよいが、４０回ぐらい回すと極小値に落ち込んでいる場合が多い
Bonanzaがクラスタ合議をやった際に、それで強くなるのか疑問だったが強くなったというようなことがあった気がする。クラスタ合議する際に、ランダムな初期値を与えて合議させていたので、極小値回避をしていたのだと思われる。
Figure 11
自分が回した時はサーチデプスが２だったのもあるが、目的関数が0.1程度だったが
0.165付近で止まってるので、これは調査用の学習だろう。
■4.6 Performance of MMTO under Tournament Conditions
世界コンピュータ将棋選手権でボナメソ使ってるソフトが活躍してるぜという紹介
ここにBonanzaの初期バージョンはL2正則化をしていると書いてある
2006論文ではL1だったような記憶が若干あるのだが。
あとNDFが古いタイプの学習になってるのだが、Bona6ベースだからAdvanced MMTOといってもいいのではないか。
もう一つ、Bonanzaのソースに入っているランダム性についてここに書かれている。
このランダム性をいれることことで評価関数の品質が上がるかどうかは不明であるとしている。（ちょ
だったら、自分みたいなニワカマンの場合、下手にランダム無い方が計算速くていいのではないか。
（実際は評価関数のほうが時間の比率は大きいから誤差みたいなもんだとは思うが）
■4.7 Preliminary Experiments on Chess
チェスのプログラムにMMTOを適用
チェスは凝ったプログラムが多いので比較が難しい的な話
■4.8 Data Quality Dependence
Table 5
強い棋譜を使うと強くなる的な話
これを推し進めると、コンピュータ同士の強い棋譜で学習したらつよくならんの？
と思ってちょっと走らせてみたが前々回ぐらいのエントリ
時間がかかりすぎたのでやめたが。
そもそも相対学習からの絶対学習で強くなるのがわかってるのだが、棋譜を用意がFloodgateのほうが１００倍楽なので、何か思いついたらまた試してみたい。
■5 Coclusion
まとめ
二人ゲームにおいてMMTOは有効
■Appendix
数式だらけなのでパス
■雑感
・KKPいらんのではないか
R50減ったとしても、その分速く読めればとんとんだったりしないのだろうか。
・棋譜
かなり正確に書かれていたので、同等の棋譜が用意できれば、同じぐらいの強さの評価関数は再現できるだろう
・実はもっとがっつり変化させられないか
この論文の主張では数値的に安定的にするために少しずつ学習する方法をとっているが、GPS優勝後のPPTによると、評価関数や学習方法を変えた時に、不連続性があってもうまく行ったようなのが書いてあった。ただ、GPW2008のものではイマイチっぽいかかれ方をしててよくわからず。
・GPSの学習方法との比較がなかった
GPSはGPSで式を変えていたが、どっちがよいかというような比較が無かった。
せっかく共著なのでそういうのも期待したかった。
Bonanzaについて一つにまとまっている論文を全部ひと通り読んでみたが、ソースコードだけから読み取ろうとした数字などについて解説があり、納得できた面もあるが、謎な部分もある。
まとめてたら、エントリも長すぎて途中で気力がつきかけたので、間違っている部分もあるかもしれない。
論文読んでたら、「Bonanzaよりは強くなるのではないか」という方法が４つぐらい思いついた気がするが、メモらなかったので忘れてしまった。
１個はKPP無しかな
思いついたら追記するかも。
そもそも、なんで読もうと思ったのかを忘れていたが、少し前にやった部分学習的なことの方針が合っているのかどうかを確認したかっただけだったが、論文のボリュームがあったのと英語の読解力不足で時間がかかった。
部分学習するときにいくつかの固定パラメータをうまく調整する必要があるはずで、カンで調整したところが、本当に調査どおりなのか確認してみたが、概ねあっていたように思う。
本当は軽くまとめようと思ったが、結構量があったので分けたエントリのその２
■４章 Experiments
Bonanzaについて書かれている
Bonanzaのソースのバージョンが論文中は2013とか書かれているが、公開されている6.0は2011更新となっている謎。
評価関数の重みは4000万（このカウント方法は後述）
あと、ほとんどのグラフとかはGPWのどっかにはあると思われる。
（どれも見た記憶はあるが、内容を覚えていない）
●4.1 Setup: Evaluation Functions, Features, and Game Records
・Bonanzaに取り入れられているテクニック
PVS
quience search
static exchange evaluation
killer and history heuristics
null move pruning
futility pruning
late mode reduction
全幅探索という言葉がひとり歩きしていたが、最初から枝刈りのテクニックを使っていた。（当然といえば当然なきもするが）。
枝刈りだけ抜き出して書いてある特集
「コンピュータ将棋における全幅探索とfutility pruningの応用」
Blunderも似たような感じ。
http://www.computer-shogi.org/wcsc21/appeal/Blunder/Blunder.pdf
余談だが、今はなきBlunder公式Blogでは、Blunderに実装した探索は
Stockfish探索よりも成果が良かったという結果を出していた。
・定跡ファイル
自己対戦の結果らしい
・学習に使った棋譜
48566、そのうちプロの棋譜は３万弱
具体的にどの棋譜を使ったかが、書かれている。
・評価関数の次元
A:駒割りのみ １３次元（駒の種類、成り駒が１３種類）
B:KP ６万ちょっと
C:KKP ２４２万
D:KPP ４４２２万
ソースコード上は、左右対称であっても、高速化を考慮して、KPPテーブルは２倍の80Mになっている。
・対称性
先手と後手を入れ替えると評価値がマイナスになる
左右入れ替えた評価値はおなじになる
・Pの取りうる値
状態数は1476であるとしている（shogi.hでenum定義されている値、これは非合法手を消してあるので、81*13*2より少ない）
・目的関数の値
ノーマライズのために、すべての合法手数で割った値を使う
（ただ、この値そのものは何かに使うわけではなくて学習効率を測る指標だと思われる）
・駒割りの制約
ラグランジュ未定乗数法として追加してある定数項は駒割りを一定の数にしている
fill_init_paramの中で初期値を決定している。
他の論文によると初期値はALL500でも収束してくれるらしいが、最初から近い値のほうがよい（当たり前にも思えるが）
・sigmoidの係数
0.0274 = 7/256 でソースに直打ちされている値
100点差があったときに大きく動くように調整したらしい
・正則化項
Jrの係数 0.00625は FV_PENALTY の値
calc_penaltyで計算した値は全く使っていないが、学習がうまくいってるかどうかの指標に使っているのだろう。
この正則化項によって、最大値が決定する。値が大きくなるほどペナルティが大きくなる。
1/160=0.00625
・FV_SCALE
Σ計算は32bitだが、wは16bitなので、2^5 = 32で割った値が格納されている
・更新量
整数の最小値である１に設定している
●4.2 Learning the Piece Values
駒の点数を計算するが、ここで、Tesauro(2001)のChessの論文の方法との対比になっている。
Chessの論文では、伝統的な勾配降下法(conventional gradient descent method？）を使っているが、それを将棋に適用したときに２つ問題がある
１．収束が遅い（１００回回しても収束しない）
２．定数倍で増えていってしまう
１と２は関係しているように思えるが、学習モデルに拘束条件が入っていないので収束しない
一方でボナメソ（の拘束条件）を使うと40回で収束する
Figure 5は別の論文の図にあったはずなので、そっち見たほうが（日本語なので）わかりやすい
Figure 6
拘束条件が無いと、MMTOよりも収束が遅くなる
2006論文などでは、収束させるには入れて当然、みたいにさらっと書いてあるが、裏付けとしてデータを載せている。
Figure 7
高次元ベクトルを評価関数に使う場合、オーバーフィッティングが発生している
正則化なしでは一致率が急激に上昇するので一見ようように見えるが、そのときの０になっている値は0.2%しかなく、正則化後では96.3%になっていることが、オーバーフィッティングであるとする理由。
●4.4 強さの改善
棋譜との一致率と強さの関係
ここでいきなり GPS将棋の紹介
まったく違う評価関数とのELOレーティングでの比較
Figure 8
GPS将棋と、KP、KKP、KPPの比較
これを見るとKKPはあまりレーティングに寄与していないように見える(R50ぐらい)
なのはminiはKP＋PPだったが、ここはKPPのみもしくはKPP＋PPPなんてやってみるとよいのではないか
あとKPPがまだ伸びしろがあるように思える。
NDFのように相対学習などを取り入れることによりR3000超えたりしているので、KPPはまだ点の付け方に工夫ができる余地があるということが、ここ最近の進展だろう。
●4.5 Numerical Stability and Convergence
数値的安定性と収束
早い話がちゃんと正しそうな値に収束するかどうかってことだと思うが、この章では駒の価値だけの評価関数を元に、連続性や、極小値に落ち込まないかどうかを検証している。
・4.5.1 Surface of the objective function
Figure 9
このグラフもGPWのどっかに書いてあった記憶。
極小値があって学習が難しいよという話
・4.5.2 Empirical Convergence and Local-Minima Properties
駒割りだけの学習だが、極小値に陥ってないかの検討
これも別の論文があったような
X5690で200回回すのに一週間
200回も回せば強さにはあまり影響がないらしい
初期値をランダムにして収束が違うか
ある程度まではよいが、４０回ぐらい回すと極小値に落ち込んでいる場合が多い
Bonanzaがクラスタ合議をやった際に、それで強くなるのか疑問だったが強くなったというようなことがあった気がする。クラスタ合議する際に、ランダムな初期値を与えて合議させていたので、極小値回避をしていたのだと思われる。
Figure 11
自分が回した時はサーチデプスが２だったのもあるが、目的関数が0.1程度だったが
0.165付近で止まってるので、これは調査用の学習だろう。
■4.6 Performance of MMTO under Tournament Conditions
世界コンピュータ将棋選手権でボナメソ使ってるソフトが活躍してるぜという紹介
ここにBonanzaの初期バージョンはL2正則化をしていると書いてある
2006論文ではL1だったような記憶が若干あるのだが。
あとNDFが古いタイプの学習になってるのだが、Bona6ベースだからAdvanced MMTOといってもいいのではないか。
もう一つ、Bonanzaのソースに入っているランダム性についてここに書かれている。
このランダム性をいれることことで評価関数の品質が上がるかどうかは不明であるとしている。（ちょ
だったら、自分みたいなニワカマンの場合、下手にランダム無い方が計算速くていいのではないか。
（実際は評価関数のほうが時間の比率は大きいから誤差みたいなもんだとは思うが）
■4.7 Preliminary Experiments on Chess
チェスのプログラムにMMTOを適用
チェスは凝ったプログラムが多いので比較が難しい的な話
■4.8 Data Quality Dependence
Table 5
強い棋譜を使うと強くなる的な話
これを推し進めると、コンピュータ同士の強い棋譜で学習したらつよくならんの？
と思ってちょっと走らせてみたが前々回ぐらいのエントリ
時間がかかりすぎたのでやめたが。
そもそも相対学習からの絶対学習で強くなるのがわかってるのだが、棋譜を用意がFloodgateのほうが１００倍楽なので、何か思いついたらまた試してみたい。
■5 Coclusion
まとめ
二人ゲームにおいてMMTOは有効
■Appendix
数式だらけなのでパス
■雑感
・KKPいらんのではないか
R50減ったとしても、その分速く読めればとんとんだったりしないのだろうか。
・棋譜
かなり正確に書かれていたので、同等の棋譜が用意できれば、同じぐらいの強さの評価関数は再現できるだろう
・実はもっとがっつり変化させられないか
この論文の主張では数値的に安定的にするために少しずつ学習する方法をとっているが、GPS優勝後のPPTによると、評価関数や学習方法を変えた時に、不連続性があってもうまく行ったようなのが書いてあった。ただ、GPW2008のものではイマイチっぽいかかれ方をしててよくわからず。
・GPSの学習方法との比較がなかった
GPSはGPSで式を変えていたが、どっちがよいかというような比較が無かった。
せっかく共著なのでそういうのも期待したかった。
Bonanzaについて一つにまとまっている論文を全部ひと通り読んでみたが、ソースコードだけから読み取ろうとした数字などについて解説があり、納得できた面もあるが、謎な部分もある。
まとめてたら、エントリも長すぎて途中で気力がつきかけたので、間違っている部分もあるかもしれない。
論文読んでたら、「Bonanzaよりは強くなるのではないか」という方法が４つぐらい思いついた気がするが、メモらなかったので忘れてしまった。
１個はKPP無しかな
思いついたら追記するかも。
そもそも、なんで読もうと思ったのかを忘れていたが、少し前にやった部分学習的なことの方針が合っているのかどうかを確認したかっただけだったが、論文のボリュームがあったのと英語の読解力不足で時間がかかった。
部分学習するときにいくつかの固定パラメータをうまく調整する必要があるはずで、カンで調整したところが、本当に調査どおりなのか確認してみたが、概ねあっていたように思う。
毎回興味深く読ませてもらっているど素人です。
この論文は読みましたか？
将棋での少数の棋譜からの評価関数の学習における 拘束条件
https://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=14&cad=rja&uact=8&ved=0CCwQFjADOAo&url=https%3A%2F%2Fipsj.ixsq.nii.ac.jp%2Fej%2Findex.php%3Faction%3Dpages_view_main%26active_action%3Drepository_action_common_download%26item_id%3D106496%26item_no%3D1%26attribute_id%3D1%26file_no%3D1%26page_id%3D13%26block_id%3D8&ei=rYncVLPjHou68gXlz4DgBA&usg=AFQjCNE42pihEiKlzzEPkkOFgVRkPUFjTw&sig2=1vwqGw38vsb4n7TqZKf2fQ
by 2ｃｈの508の中の人 (2015-02-13 10:04)
なかなかするどいところついてますね。
実は次のエントリはその論文について書こうと思ってます。
by woody (2015-02-13 20:16)