ボナンザを改造して強くする方法、どなたか教えて下さい。 [将棋]
たまにコンピュータ将棋スレみてたら面白い書き込みがあったのでメモ。
そんだけかよ！という感じだが、Bonanzaそのままだとそんな感じ。
３秒対戦ぐらいだと、深く読んでもあまり強くない。
あと毎回３秒対戦してるのは、時間制御アルゴリズムの影響を受けないようにするため。
＜追記＞
なのはの中の人によると２倍早くして+R150という噂があるらしい。
２割アップでもひーこらいってるのにこっから８割アップとか差分指し手生成とかやらんといかんのかという感じ。
ひよこ将棋の作者によればBonanzaでは２倍早くして６割程度らしいのでコンピュータ将棋界では常識的な数字なんだろう。
http://d.hatena.ne.jp/hiyokoshogi/20111208/1323329347
速くして強くするというのは、にわかはやめたほうが良い気がする。
これを書いた人はなかなか詳しいｗ
最近試したので覚えているうちにどれぐらい効果があるか私感をまとめてみる。
・３次元化
NDFが最初に取り組んだ内容。
また、FV38化をすると、FVIndexがソートされていないので、これをやりたくなる。
（Aperyの平岡さんもそんなことをつぶやいていたような記憶）
実際これをやると、１割アップする。
FV38化＋３次元化でNPS２割アップ。
しかしBonanzaの評価値のままだと勝率に影響はないという予測。（あってもR50程度）
＜追記＞
実際３秒１００戦で戦わせてみたところ、状況によってはNPSが３割アップぐらいの状況で、４３－８－４９と有意差はなかった。チョットは有意差ある気がするのだが、残り２０戦ぐらいのとこで、PC使い始めたため、NPS差があまりでなくなって急に五分五分になった感じ。そもそも速くしなくても遅くした方と戦わせるとか、３秒じゃなくて１秒にするとかいうほうがよほど差が出るし、検証としては確実だとは思う。
・ヒストリテーブルのグローバル化
よくわからん。
ハッシュテーブルについては、せっかくマルチスレッドになっているのに、キャッシュが32MB固定しか使ってないのを最近発見したが、これをZobristHashにして数Gとるだけで実は強くなると思ったが、よくみたら似たような実装になってた。
サイズが可変になってないのだけが問題っぽいし、対戦中は数％ぐらいしか使わない。
長時間でもないと意味が無いか？
・並列動作の効率向上
よくわからんが、プロファイラでみるとたしかに待ち時間が多い。
ただ、CPU使用率的には１００％に近いのであまり気にしてもしょうがない気がする。
・evaluate に SSE命令を適用する
適用できるところあるか？
と思ったが、値を全部ロードして加算はSSEにすると効果あるかもしれない。
・stockfish を参考にして探索部分を一部アップデート
Nanoha-miniの評価値の出方を見てると、これは効果あると思う。
というか、探索だけでなく、ヒストリー管理もセットで変更かけると効果がでるだけでなく、ソースも見やすいし管理しやすくなると思う。
Bonanzaの探索というかソースコードは結構テクニカルだと思う。（というかコメントが少なすぎる）
・三駒関係から利きや相対位置の同じものを共通化して,特徴ベクトルに加えて学習する
R3000超のために一番効くのがこれだと思われる。
やねうら王のやねうらおさんも「探索に時間をかけるなら評価関数」という趣旨のことを書かれていた。
FV38化にあたり、今更評価値を覗いてみると値がついてないように思われる項目がいっぱいある。
これもNDF由来。
＜追記＞
探索深さと一致率という面白いエントリがあり、具体的な数値が載っている。
http://yaneuraou.yaneu.com/2014/12/18/%E5%B0%86%E6%A3%8B%E3%81%AE%E6%8E%A2%E7%B4%A2%E7%A9%BA%E9%96%93%E3%81%AE%E5%BA%83%E3%81%95%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6/
GPSのGPWか何かの論文に６割ぐらいしか一致しないというのを見た気がするが、どういう条件かどうかは覚えていない。そもそも、GPSFishとBonanzaを戦わせると遅いGPSFishが勝ち越すし、BitboardやKPPにこだわらなくても成果は出せていた。実際、遅くてもより正確な評価関数があれば２倍遅くても勝ち越せる。（ただ、GPSとBonanzaのNPSが同一かどうかというのもLS3600さんが指摘していた）
しかし、NDFの相対化や、AwakeのKPAなど、いかに効率よくKPPに点をつけるかというのが去年ぐらいからの風潮で、速さと正確さを両立させたBitboard/KPP陣営が電王トーナメントで勝ち残った。
・手番考慮eval処理を実装
これは2014年の電王トーナメントの段階ではAperyの平岡さんは効果がなかったと諦めたはず。
しかし、NDFは２，３年前の段階で取り入れていた。
この違いは上記の学習方法と学習リソースの違いがあるかもしれない。
NDFの場合、先に手番＋強化学習に相対化したのに対して、
今相対化してから手番学習だと、やる意味があるのかどうかという話がある。
そもそもFV.binって後手玉中心の計算もしている以上、ある意味で手番考慮してると思われるのだが、勘違いだろうか。
同型で手番がある方が勝つというようなのを評価できるようになるが、そんなのはごく一部のような。矢倉や角換わりが強くなる一方で計算コストが増大するような。
やっぱりわからない。
あと、個人的に必要なのは定跡の整備。GPSなんかは明らかに悪くなる定跡がよく出てくる（笑）
思いついたらまた追記する
こんなしょっぱいBlogよりも成果を出されていてためになるやねうら王のサイトはこちら
http://yaneuraou.yaneu.com/
オチ
215 名前：名無し名人[sage] 投稿日：2014/12/29(月) 10:30:09.69 ID:7MBhfJLt
>>214
さっぱり分かりません。
＜追記＞
・BMI2を使う
LS3600ブログも更新されていて、BMI2を使うべきですね、と煽っていたが、コメント欄を読むと、やってもしかたないかぐらいのトーンダウン。理由は簡単でBMI2が128bitに対応していないため、81bit必要な将棋には使い方を工夫しないといけない。
そもそも、元のビットマップ、マスクデータ、結果を元に戻すテーブルかマスク、の３つのデータが必要だが
Bonanzaは回転ビットマップ、インデックステーブル、シフトテーブルで処理できてしまっているので、ぱっと見あまり効果がなさそう。
角や飛の縦横をまとめて処理すれば、仮に時間が同じだとしても２倍の効率化がされると思うが・・・
あとBonanzaは伝統的なC言語で書かれているため、改造がやりにくい（ということもLS3600さんのBlogにはかかれているが）
なので、もしBMI2化するのであれば、先にbitboardのクラス化でコードをクリーンアップする必要があるように思う。
206 名前：名無し名人[sage] 投稿日：2014/12/28(日) 22:36:32.04 ID:iVcex75m ボナンザを改造して強くする方法、どなたか教えて下さい。
208 名前：名無し名人[sage] 投稿日：2014/12/28(日) 22:58:27.39 ID:awd2iOZH >>206 速く動くように改造する。 R50は強くなる。
そんだけかよ！という感じだが、Bonanzaそのままだとそんな感じ。
３秒対戦ぐらいだと、深く読んでもあまり強くない。
あと毎回３秒対戦してるのは、時間制御アルゴリズムの影響を受けないようにするため。
＜追記＞
なのはの中の人によると２倍早くして+R150という噂があるらしい。
２割アップでもひーこらいってるのにこっから８割アップとか差分指し手生成とかやらんといかんのかという感じ。
ひよこ将棋の作者によればBonanzaでは２倍早くして６割程度らしいのでコンピュータ将棋界では常識的な数字なんだろう。
http://d.hatena.ne.jp/hiyokoshogi/20111208/1323329347
速くして強くするというのは、にわかはやめたほうが良い気がする。
214 名前：名無し名人[sage] 投稿日：2014/12/29(月) 01:29:12.84 ID:p3mWunby >>206 ・kpp テーブル配列の3次元化 ・kppテーブルインデックスリストの差分生成 ・ヒストリテーブルのglobal化 ・並列動作の効率向上 ・evaluate に SSE命令を適用する ・stockfish を参考にして探索部分を一部アップデート ・三駒関係から利きや相対位置の同じものを共通化して,特徴ベクトルに加えて学習する ・手番考慮eval処理を実装
これを書いた人はなかなか詳しいｗ
最近試したので覚えているうちにどれぐらい効果があるか私感をまとめてみる。
・３次元化
NDFが最初に取り組んだ内容。
また、FV38化をすると、FVIndexがソートされていないので、これをやりたくなる。
（Aperyの平岡さんもそんなことをつぶやいていたような記憶）
実際これをやると、１割アップする。
FV38化＋３次元化でNPS２割アップ。
しかしBonanzaの評価値のままだと勝率に影響はないという予測。（あってもR50程度）
＜追記＞
実際３秒１００戦で戦わせてみたところ、状況によってはNPSが３割アップぐらいの状況で、４３－８－４９と有意差はなかった。チョットは有意差ある気がするのだが、残り２０戦ぐらいのとこで、PC使い始めたため、NPS差があまりでなくなって急に五分五分になった感じ。そもそも速くしなくても遅くした方と戦わせるとか、３秒じゃなくて１秒にするとかいうほうがよほど差が出るし、検証としては確実だとは思う。
・ヒストリテーブルのグローバル化
よくわからん。
ハッシュテーブルについては、せっかくマルチスレッドになっているのに、キャッシュが32MB固定しか使ってないのを最近発見したが、これをZobristHashにして数Gとるだけで実は強くなると思ったが、よくみたら似たような実装になってた。
サイズが可変になってないのだけが問題っぽいし、対戦中は数％ぐらいしか使わない。
長時間でもないと意味が無いか？
・並列動作の効率向上
よくわからんが、プロファイラでみるとたしかに待ち時間が多い。
ただ、CPU使用率的には１００％に近いのであまり気にしてもしょうがない気がする。
・evaluate に SSE命令を適用する
適用できるところあるか？
と思ったが、値を全部ロードして加算はSSEにすると効果あるかもしれない。
・stockfish を参考にして探索部分を一部アップデート
Nanoha-miniの評価値の出方を見てると、これは効果あると思う。
というか、探索だけでなく、ヒストリー管理もセットで変更かけると効果がでるだけでなく、ソースも見やすいし管理しやすくなると思う。
Bonanzaの探索というかソースコードは結構テクニカルだと思う。（というかコメントが少なすぎる）
・三駒関係から利きや相対位置の同じものを共通化して,特徴ベクトルに加えて学習する
R3000超のために一番効くのがこれだと思われる。
やねうら王のやねうらおさんも「探索に時間をかけるなら評価関数」という趣旨のことを書かれていた。
FV38化にあたり、今更評価値を覗いてみると値がついてないように思われる項目がいっぱいある。
これもNDF由来。
＜追記＞
探索深さと一致率という面白いエントリがあり、具体的な数値が載っている。
http://yaneuraou.yaneu.com/2014/12/18/%E5%B0%86%E6%A3%8B%E3%81%AE%E6%8E%A2%E7%B4%A2%E7%A9%BA%E9%96%93%E3%81%AE%E5%BA%83%E3%81%95%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6/
GPSのGPWか何かの論文に６割ぐらいしか一致しないというのを見た気がするが、どういう条件かどうかは覚えていない。そもそも、GPSFishとBonanzaを戦わせると遅いGPSFishが勝ち越すし、BitboardやKPPにこだわらなくても成果は出せていた。実際、遅くてもより正確な評価関数があれば２倍遅くても勝ち越せる。（ただ、GPSとBonanzaのNPSが同一かどうかというのもLS3600さんが指摘していた）
しかし、NDFの相対化や、AwakeのKPAなど、いかに効率よくKPPに点をつけるかというのが去年ぐらいからの風潮で、速さと正確さを両立させたBitboard/KPP陣営が電王トーナメントで勝ち残った。
・手番考慮eval処理を実装
これは2014年の電王トーナメントの段階ではAperyの平岡さんは効果がなかったと諦めたはず。
しかし、NDFは２，３年前の段階で取り入れていた。
この違いは上記の学習方法と学習リソースの違いがあるかもしれない。
NDFの場合、先に手番＋強化学習に相対化したのに対して、
今相対化してから手番学習だと、やる意味があるのかどうかという話がある。
そもそもFV.binって後手玉中心の計算もしている以上、ある意味で手番考慮してると思われるのだが、勘違いだろうか。
同型で手番がある方が勝つというようなのを評価できるようになるが、そんなのはごく一部のような。矢倉や角換わりが強くなる一方で計算コストが増大するような。
やっぱりわからない。
あと、個人的に必要なのは定跡の整備。GPSなんかは明らかに悪くなる定跡がよく出てくる（笑）
思いついたらまた追記する
こんなしょっぱいBlogよりも成果を出されていてためになるやねうら王のサイトはこちら
http://yaneuraou.yaneu.com/
オチ
＜追記＞
・BMI2を使う
LS3600ブログも更新されていて、BMI2を使うべきですね、と煽っていたが、コメント欄を読むと、やってもしかたないかぐらいのトーンダウン。理由は簡単でBMI2が128bitに対応していないため、81bit必要な将棋には使い方を工夫しないといけない。
そもそも、元のビットマップ、マスクデータ、結果を元に戻すテーブルかマスク、の３つのデータが必要だが
Bonanzaは回転ビットマップ、インデックステーブル、シフトテーブルで処理できてしまっているので、ぱっと見あまり効果がなさそう。
角や飛の縦横をまとめて処理すれば、仮に時間が同じだとしても２倍の効率化がされると思うが・・・
あとBonanzaは伝統的なC言語で書かれているため、改造がやりにくい（ということもLS3600さんのBlogにはかかれているが）
なので、もしBMI2化するのであれば、先にbitboardのクラス化でコードをクリーンアップする必要があるように思う。
コメント 0