Bonanzaの疑問点の調査 その１ [将棋]
ソースだけ見ててもコメントが入ってないので、
その数値はどうやって決めたのかというのがよくわからなかったが
そもそもほとんど解説してる論文の存在を忘れていた。
Kunihito Hoki and Tomoyuki Kaneko, Large-Scale Optimization for Evaluation Functions with Minmax Search, Journal of Artificial Intelligence Research, 49, 527-568, 2014.
電子書籍の悪いところとして、タブレットに突っ込んでおいて忘れるという、未だ生活スタイルに馴染んでいないのだが、これもまさにそのパターンでつい最近まで完璧に忘れていた。
この論文は、将棋を知らない外国人が読んでもわかるように書いてあるため、いまさらBonanza 6.0のソース読んでる自分が完全に欲しかったものであり、疑問点はほぼすべて書いてあった。
2006年のGPWの発表論文などでは、Bonanza 1あたりについて書かれているため、パラメータが１万とか書いてあって、今と同じなのかという疑問があったが、この論文でも学習方法の大筋は変わっていないようであった。なので、英語はチョットと言う人は、日本語の発表論文のほうを読んでからのほうがわかりやすいと思う。
■１章 序章
Chessにおける機械学習の歴史と、この論文のポジション。
世界的にはChessのほうが研究が盛んなので、それらの成果との対比という書き方になる。
この論文ではBonanzaメソッドはMinmax Tree Optimization(MMTO)と書かれている。
余談だが、小保方問題のときに、序章は先人の積み上げた歴史なかでこの論文でどういう発見があったかを書くものなのでコピペはありえないと、どこぞの研究者がキレていたのを思い出した。
■２章 関連事項
他の方法の紹介とその方法ではダメでMMTOならいけるというような話
2.1 チェスにおける学習の枠組み
2.2 他の評価関数学習方法
2.3 学習とnumerical optimization
numerical optimizationの訳語がわからない。数値最適化だろうか
■３章 Minmax Tree Optimization
ボナメソの説明
3.1 目的関数の最小化
これは2006の論文などにも書かれている内容をより正確に書いてある（と思う）
英語で分からない人は先に2006のほうを見ておくとすんなりわかる（はず）
疑問点：sigmoidのaの符号が-になっていない理由
微分するからどうでもいいっちゃーどうでもいいような？
Figure 2の説明と、該当ソースコード
1. Phase 1のmake_pvあたり
2. Phase 2の前半、calc_derivあたり
3. Phase 2の後半、renovate_paramあたり
チェスの学習方式との違い
Heaviside関数 => sigmoid関数
評価値の差 => 探索結果の評価値の差
目的関数に拘束条件が入っているのが重要
最後のセンテンスは不明（学習を進めるとPVノードが固定化されるような意味合いだろうか）
3.2 定数項と一般項
目的関数にあった拘束条件？の部分の説明
チェスでは一般的にSinged 16bit Integerが使われる。(KKP/KPPとかもShort）
置換表に格納するのに丁度よいためらしい
チェスにスケール合わせる
拘束条件とかL1正則化について書かれているがよくわからん
3.3 偏導関数近似？
3.2の考えに沿って導関数を偏微分して拘束条件などを考える
探索結果は微分可能であるとは限らないため、近似を行う
近似によってエラーは出るが影響は小さい（らしい、別の論文がある）
3.4 格子隣接アップデート
評価関数のアップデートのこと
今のBonanzaのように符号の向きだけを使うようにすることで、目的関数を最小化させて、近似によるエラーも無視できる
がっつり移動しない理由
（超訳）本来であれば微分であるので浮動小数点を使って調整するべきであるが、最終的な結果は整数で扱うので調整方法を十分に小さい整数にする。
3.5 実践的な事項やテクニックの組み合わせ
実装されているパラメータなどの説明
3.5.1 ラグランジュ乗数
ラグランジュ未定乗数項をどう設定するかという話だろうがよくわからん。
話としては、駒割りの総計を一定数（変化量を０）にすることで、望ましい結果を得ようという拘束条件について書かれているはず。具体例は４章。
3.5.2 探索深さ
make_pvで探索を行うため、MMTOで一番時間がかかる処理である
静止探索を使うとよい＝より深く探索するほどよい
現実的な問題として一手探索＋一手静止探索
学習が進んで探索の幅？が狭くなっても深く探索するのは効果がある（4.4）
3.5.3 効果的な学習のためのPVの再使用
イテレーション３２は経験的に決めた。多くのPVが変わらないように十分小さい値にするべき。
個人的には32は固定小数点の数と一致させたのかなと思っている
3.5.4 枝刈り
枝刈りによって学習に必要な探索が劇的に削減される
αβ探索では枝刈りによって不連続になることはないが、Futility Pruningでは不連続性が発生しうる
Futility Pruningを使った時にも評価関数が強靭であるか評価するべきである
経験的には問題がない
3.5.5 収束の判定
収束の判定は難しいのでレーティングで判断する？
3.5.6 重複する局面と代替手？
同じ局面が何回も出てきても１回にカウントする（実装にはZobristHashを使う）？
同じ局面で複数の手が指された場合には、互いの学習が打ち消し合ってしまう。
経験的にはそれでもうまく動いているが、他の種類のゲームではうまくいかないかもしれない。
（MMTOは将棋だけでないという主張なのでこういう書き方になっていると思われる）
4. Experiments(やったこと？）
ソースや学習などを実際にやる人はここからが本題
細かいパラメータや評価関数の形式など、ソースにある不明な点はここからが本題なのだが、その２の予定。
元々Bonanzaのソースは個別の話題があったときに流し見してた程度だったので、一般的に言われているようなことしか知らなかったが、今回学習とか高速化を少しやった上で、疑問点がいつくかあった状態で読んだのでかなり理解できた（気がする）。
GPSの金子さんとの共著になっているので、元の論文があるのではないかと思ったが、GPW2008で方法論の整理だったりとか、GPW2010でチェスとの比較だったりとか、理論的な体系を確立するのに必要そうな論文を複数だしていて、そういうのを全部まとめたのが今回の論文だったようだ。
■現状のまとめ
シグモイド関数の正負が逆なのだけは理解できない。
文章中に「in our experiments」みたいなことが結構多いが、過去のGPWの論文では、そのへんを考察しているようだ。
「がっつり変化させる」ということに対しては、この論文からは否定的な結論になっている。GPSのソースのコメントにも、ボナメソのほうが結果が良い的なことが書かれていた。
その数値はどうやって決めたのかというのがよくわからなかったが
そもそもほとんど解説してる論文の存在を忘れていた。
Kunihito Hoki and Tomoyuki Kaneko, Large-Scale Optimization for Evaluation Functions with Minmax Search, Journal of Artificial Intelligence Research, 49, 527-568, 2014.
電子書籍の悪いところとして、タブレットに突っ込んでおいて忘れるという、未だ生活スタイルに馴染んでいないのだが、これもまさにそのパターンでつい最近まで完璧に忘れていた。
この論文は、将棋を知らない外国人が読んでもわかるように書いてあるため、いまさらBonanza 6.0のソース読んでる自分が完全に欲しかったものであり、疑問点はほぼすべて書いてあった。
2006年のGPWの発表論文などでは、Bonanza 1あたりについて書かれているため、パラメータが１万とか書いてあって、今と同じなのかという疑問があったが、この論文でも学習方法の大筋は変わっていないようであった。なので、英語はチョットと言う人は、日本語の発表論文のほうを読んでからのほうがわかりやすいと思う。
■１章 序章
Chessにおける機械学習の歴史と、この論文のポジション。
世界的にはChessのほうが研究が盛んなので、それらの成果との対比という書き方になる。
この論文ではBonanzaメソッドはMinmax Tree Optimization(MMTO)と書かれている。
余談だが、小保方問題のときに、序章は先人の積み上げた歴史なかでこの論文でどういう発見があったかを書くものなのでコピペはありえないと、どこぞの研究者がキレていたのを思い出した。
■２章 関連事項
他の方法の紹介とその方法ではダメでMMTOならいけるというような話
2.1 チェスにおける学習の枠組み
2.2 他の評価関数学習方法
2.3 学習とnumerical optimization
numerical optimizationの訳語がわからない。数値最適化だろうか
■３章 Minmax Tree Optimization
ボナメソの説明
3.1 目的関数の最小化
これは2006の論文などにも書かれている内容をより正確に書いてある（と思う）
英語で分からない人は先に2006のほうを見ておくとすんなりわかる（はず）
疑問点：sigmoidのaの符号が-になっていない理由
微分するからどうでもいいっちゃーどうでもいいような？
Figure 2の説明と、該当ソースコード
1. Phase 1のmake_pvあたり
2. Phase 2の前半、calc_derivあたり
3. Phase 2の後半、renovate_paramあたり
チェスの学習方式との違い
Heaviside関数 => sigmoid関数
評価値の差 => 探索結果の評価値の差
目的関数に拘束条件が入っているのが重要
最後のセンテンスは不明（学習を進めるとPVノードが固定化されるような意味合いだろうか）
3.2 定数項と一般項
目的関数にあった拘束条件？の部分の説明
チェスでは一般的にSinged 16bit Integerが使われる。(KKP/KPPとかもShort）
置換表に格納するのに丁度よいためらしい
チェスにスケール合わせる
拘束条件とかL1正則化について書かれているがよくわからん
3.3 偏導関数近似？
3.2の考えに沿って導関数を偏微分して拘束条件などを考える
探索結果は微分可能であるとは限らないため、近似を行う
近似によってエラーは出るが影響は小さい（らしい、別の論文がある）
3.4 格子隣接アップデート
評価関数のアップデートのこと
今のBonanzaのように符号の向きだけを使うようにすることで、目的関数を最小化させて、近似によるエラーも無視できる
がっつり移動しない理由
Although MMTO focuses on optimization of weight vectors represented by integers, it should be noted that the gradient descent update is not suitable even when one uses oatingpoint feature weights
（超訳）本来であれば微分であるので浮動小数点を使って調整するべきであるが、最終的な結果は整数で扱うので調整方法を十分に小さい整数にする。
3.5 実践的な事項やテクニックの組み合わせ
実装されているパラメータなどの説明
3.5.1 ラグランジュ乗数
ラグランジュ未定乗数項をどう設定するかという話だろうがよくわからん。
話としては、駒割りの総計を一定数（変化量を０）にすることで、望ましい結果を得ようという拘束条件について書かれているはず。具体例は４章。
3.5.2 探索深さ
make_pvで探索を行うため、MMTOで一番時間がかかる処理である
静止探索を使うとよい＝より深く探索するほどよい
現実的な問題として一手探索＋一手静止探索
学習が進んで探索の幅？が狭くなっても深く探索するのは効果がある（4.4）
3.5.3 効果的な学習のためのPVの再使用
イテレーション３２は経験的に決めた。多くのPVが変わらないように十分小さい値にするべき。
個人的には32は固定小数点の数と一致させたのかなと思っている
3.5.4 枝刈り
枝刈りによって学習に必要な探索が劇的に削減される
αβ探索では枝刈りによって不連続になることはないが、Futility Pruningでは不連続性が発生しうる
Futility Pruningを使った時にも評価関数が強靭であるか評価するべきである
経験的には問題がない
3.5.5 収束の判定
収束の判定は難しいのでレーティングで判断する？
3.5.6 重複する局面と代替手？
同じ局面が何回も出てきても１回にカウントする（実装にはZobristHashを使う）？
同じ局面で複数の手が指された場合には、互いの学習が打ち消し合ってしまう。
経験的にはそれでもうまく動いているが、他の種類のゲームではうまくいかないかもしれない。
（MMTOは将棋だけでないという主張なのでこういう書き方になっていると思われる）
4. Experiments(やったこと？）
ソースや学習などを実際にやる人はここからが本題
細かいパラメータや評価関数の形式など、ソースにある不明な点はここからが本題なのだが、その２の予定。
元々Bonanzaのソースは個別の話題があったときに流し見してた程度だったので、一般的に言われているようなことしか知らなかったが、今回学習とか高速化を少しやった上で、疑問点がいつくかあった状態で読んだのでかなり理解できた（気がする）。
GPSの金子さんとの共著になっているので、元の論文があるのではないかと思ったが、GPW2008で方法論の整理だったりとか、GPW2010でチェスとの比較だったりとか、理論的な体系を確立するのに必要そうな論文を複数だしていて、そういうのを全部まとめたのが今回の論文だったようだ。
■現状のまとめ
シグモイド関数の正負が逆なのだけは理解できない。
文章中に「in our experiments」みたいなことが結構多いが、過去のGPWの論文では、そのへんを考察しているようだ。
「がっつり変化させる」ということに対しては、この論文からは否定的な結論になっている。GPSのソースのコメントにも、ボナメソのほうが結果が良い的なことが書かれていた。
コメント 0