Lazy SMPのまとめ [コンピュータ将棋]
仕事が始まったら完全に忘れると思うのでまとめ
やねうら王Blogに「Stockfishの探索方法が新しくなった」というようなことが書かれていた。
http://yaneuraou.yaneu.com/2015/12/20/%E9%80%A3%E8%BC%89%E3%82%84%E3%81%AD%E3%81%86%E3%82%89%E7%8E%8Bmini%E3%81%A7%E9%81%8A%E3%81%BC%E3%81%86%EF%BC%8110%E6%97%A5%E7%9B%AE/
Stockfishがそんな大胆なことをやったのかと確認したところ、ごく最近Lazy SMPなるものがコミットされていた（２０１５年９月コミット）。
https://github.com/official-stockfish/Stockfish/commit/ecc5ff6693f116f4a8ae5f5080252f29b279c0a1
で、どんなものかと調べて（ぐぐって）みたが、いまいちよくわからない
いつものチェスプログラミングWikiを見ると以下の説明のみ
https://chessprogramming.wikispaces.com/Parallel+Search
Lazy SMP
Recent improvements by Dan Homan [2] , Martin Sedlak [3] and others on Lazy SMP indicate that the algorithm scales quite well up to 8 cores and beyond [4] .
上の[2][3[4]あたりを見てみると、Lazy SMP自体は古くからある実装方法だが、２０１３年ぐらいでは採用が見送られていたらしい。ところが、今年２月ぐらいにCheng？というソフトが実装したところ、８コア以上でもスケールする（コアが増えるほどレーティングがあがる）ということで、Stockfishに採用してはどうかということで再び脚光が当たった。
http://www.talkchess.com/forum/viewtopic.php?t=55170&start=11
掲示板の議論を見てみると、「Stockfishで効果あるかどうかはわからない」的なことが書かれていたが、Lazy SMPの実装が容易であるのもあって速攻実装されて検証された。元々の実装であるYBWC（Splitpointのある実装）では４コアで頭打ちで、８コアではレーティングがむしろ下がったのが、８コアでも見事にスケールした（レーティングがあがった）ことで採用となった。（SplitPointの設定が悪いんじゃないか、とかいろいろあったようだが）
Lazy SMPの動きそのもは単純で反復深化を行う際に、深さごとスレッドを割り当てることになる
どの深さのスレッドを割り当てるかどうかは初期のコミットでは以下のようになっている。
depth = Threads.main()->depth + Depth(int(3 * log(1 + this->idx)));
関数にLogが入ってるのは深い探索ほど傾きが少なくなり、一つの深さを複数のスレッドで計算するようになる。
親スレッドがDepth1を計算している時に、子スレッドは２～を計算するが、親スレッドがDepth１０ぐらいあたりからは同じ深さを探索するようになる。
評価した計算結果はメモリ上のTransposition Table（置換表）に入るので、親スレッドが、Depth2を計算したときに、子の計算結果が入っているため、メモリ参照だけで計算が終わるというのが、この方法がうまくいく理由らしい。
このように置換表を前提とした誰でも思いつくような（怠惰な）並列探索にすることによって、コアが増えれば増えただけスケールしてくれるというメリットが出てくるらしい。
やねうら王Blogで「（ほんのちょっとだけ）クラスタに効果がある」と書かれているのは、LazySMPは「置換表が十分大きく、他のスレッドの計算結果を参照するだけで自分がほとんど計算しないですむこと」がキモなので、置換表を共有できないクラスタでは大きい効果は望めないが、このような短絡的な探索の割り振り方によってクラスタでもスケールするのではないかという主張。（Bonanza Clusterは投機的実行なのでYBWCと意味合い的には同じだと思っている）
また、ChengやStockfishでは４コアではYBWC版とは特にスコアが変わらなかった。あくまでも８コアで効果が出たというだけなので、無差別級であるコンピュータ将棋選手権ならともかく、去年から今年になって８コア=>4コアになってしまった電王トーナメントでは効果はあまり期待できない。（技巧が勝ちにくかったのはこのせいかも？）
ただ、実装が比較的容易なのと、YBWC特有のチューニングをしなくてよいという点ではレーティングの底上げに寄与する可能性がある。習甦なんかは並列に苦労してそうなイメージがあるのでどうなのだろうか。
Stockfish探索型のYBWCを実装してある場合は容易に実装できるので、自分が見ている範囲だけでも３人（やねうら王、shogi686、Ponanza）は実装が終わっているが、効果の程がどうだったのかわかるのは先の話になりそう。
＜追記＞
Stockfish Blog — Stockfish 7 http://ow.ly/WCRd4
Stockfish公式Blogにもちゃんと書かれていた
やねうら王Blogに「Stockfishの探索方法が新しくなった」というようなことが書かれていた。
http://yaneuraou.yaneu.com/2015/12/20/%E9%80%A3%E8%BC%89%E3%82%84%E3%81%AD%E3%81%86%E3%82%89%E7%8E%8Bmini%E3%81%A7%E9%81%8A%E3%81%BC%E3%81%86%EF%BC%8110%E6%97%A5%E7%9B%AE/
Stockfishがそんな大胆なことをやったのかと確認したところ、ごく最近Lazy SMPなるものがコミットされていた（２０１５年９月コミット）。
https://github.com/official-stockfish/Stockfish/commit/ecc5ff6693f116f4a8ae5f5080252f29b279c0a1
で、どんなものかと調べて（ぐぐって）みたが、いまいちよくわからない
いつものチェスプログラミングWikiを見ると以下の説明のみ
https://chessprogramming.wikispaces.com/Parallel+Search
Lazy SMP
Recent improvements by Dan Homan [2] , Martin Sedlak [3] and others on Lazy SMP indicate that the algorithm scales quite well up to 8 cores and beyond [4] .
上の[2][3[4]あたりを見てみると、Lazy SMP自体は古くからある実装方法だが、２０１３年ぐらいでは採用が見送られていたらしい。ところが、今年２月ぐらいにCheng？というソフトが実装したところ、８コア以上でもスケールする（コアが増えるほどレーティングがあがる）ということで、Stockfishに採用してはどうかということで再び脚光が当たった。
http://www.talkchess.com/forum/viewtopic.php?t=55170&start=11
掲示板の議論を見てみると、「Stockfishで効果あるかどうかはわからない」的なことが書かれていたが、Lazy SMPの実装が容易であるのもあって速攻実装されて検証された。元々の実装であるYBWC（Splitpointのある実装）では４コアで頭打ちで、８コアではレーティングがむしろ下がったのが、８コアでも見事にスケールした（レーティングがあがった）ことで採用となった。（SplitPointの設定が悪いんじゃないか、とかいろいろあったようだが）
Lazy SMPの動きそのもは単純で反復深化を行う際に、深さごとスレッドを割り当てることになる
どの深さのスレッドを割り当てるかどうかは初期のコミットでは以下のようになっている。
depth = Threads.main()->depth + Depth(int(3 * log(1 + this->idx)));
関数にLogが入ってるのは深い探索ほど傾きが少なくなり、一つの深さを複数のスレッドで計算するようになる。
親スレッドがDepth1を計算している時に、子スレッドは２～を計算するが、親スレッドがDepth１０ぐらいあたりからは同じ深さを探索するようになる。
評価した計算結果はメモリ上のTransposition Table（置換表）に入るので、親スレッドが、Depth2を計算したときに、子の計算結果が入っているため、メモリ参照だけで計算が終わるというのが、この方法がうまくいく理由らしい。
このように置換表を前提とした誰でも思いつくような（怠惰な）並列探索にすることによって、コアが増えれば増えただけスケールしてくれるというメリットが出てくるらしい。
やねうら王Blogで「（ほんのちょっとだけ）クラスタに効果がある」と書かれているのは、LazySMPは「置換表が十分大きく、他のスレッドの計算結果を参照するだけで自分がほとんど計算しないですむこと」がキモなので、置換表を共有できないクラスタでは大きい効果は望めないが、このような短絡的な探索の割り振り方によってクラスタでもスケールするのではないかという主張。（Bonanza Clusterは投機的実行なのでYBWCと意味合い的には同じだと思っている）
また、ChengやStockfishでは４コアではYBWC版とは特にスコアが変わらなかった。あくまでも８コアで効果が出たというだけなので、無差別級であるコンピュータ将棋選手権ならともかく、去年から今年になって８コア=>4コアになってしまった電王トーナメントでは効果はあまり期待できない。（技巧が勝ちにくかったのはこのせいかも？）
ただ、実装が比較的容易なのと、YBWC特有のチューニングをしなくてよいという点ではレーティングの底上げに寄与する可能性がある。習甦なんかは並列に苦労してそうなイメージがあるのでどうなのだろうか。
Stockfish探索型のYBWCを実装してある場合は容易に実装できるので、自分が見ている範囲だけでも３人（やねうら王、shogi686、Ponanza）は実装が終わっているが、効果の程がどうだったのかわかるのは先の話になりそう。
＜追記＞
Stockfish Blog — Stockfish 7 http://ow.ly/WCRd4
Stockfish公式Blogにもちゃんと書かれていた
AperyのPGOビルド [コンピュータ将棋]
今更pgoビルドが出来なかった理由がわかったのでメモ
■要因
・合成済み評価値ファイルが読み込めていないと０メモリの合成を始めようとする
・-jオプションをつけてパフォーマンス測定を行うと参照カウンタがぶっ壊れる
■詳細
・Aperyでリリース版相当の最適化を掛けるにはpgoを行う必要がある
「make pgo」でやってくれる（はず）
・PGOビルドが何をやっているか
プロファイルありでビルドする
benchコマンドを実行する
PGOビルドを行う
・aperyのベースディレクトリがsrcのため、bench実行時に行われる評価値ファイルが読み込まれない
binの下で動かす前提になっている
・評価値ファイルが読み込まれない時の処理
ファイルを開く
読み込めなかったらメモリを０クリアする
評価値ファイルを合成する
これは評価値ファイルがない場合の処理なので、使うだけのときはむしろエラーになってほしい
・一般的にはエラーが起きたらboolでfalseでも返せばいいのだが、
この部分の処理がUSIOptionのコールバックで戻り値無し（void）になっている
そのため、評価値ファイルが見つからない場合の処理が入っていない
（もしかすると学習時にはこれでもよいので気にしていないのかもしれない）
一般ユーザー的にはゼロメモリの合成処理をしようとしてしまって意味が無い。
・解決方法はsrcの下に評価値ファイルを用意する
mingw環境ではシンボリックリンクで解決できる
ln -s ../bin/20151105 20151105
確か、Apery初配布ぐらいのときは読み込まれなくてちゃんと動いていない人が続出したような記憶があるが、この部分を直そうとすると上記のように結構面倒で諦めた記憶がある
あと学習時は０メモリににしたいと思われるので、LEARNとかMINIMALあたりで切り替わるようにするのが良さそう。
・無事成功すると配布版と同等の速度（NPS）になる
■要因
・合成済み評価値ファイルが読み込めていないと０メモリの合成を始めようとする
・-jオプションをつけてパフォーマンス測定を行うと参照カウンタがぶっ壊れる
■詳細
・Aperyでリリース版相当の最適化を掛けるにはpgoを行う必要がある
「make pgo」でやってくれる（はず）
・PGOビルドが何をやっているか
プロファイルありでビルドする
benchコマンドを実行する
PGOビルドを行う
・aperyのベースディレクトリがsrcのため、bench実行時に行われる評価値ファイルが読み込まれない
binの下で動かす前提になっている
・評価値ファイルが読み込まれない時の処理
ファイルを開く
読み込めなかったらメモリを０クリアする
評価値ファイルを合成する
これは評価値ファイルがない場合の処理なので、使うだけのときはむしろエラーになってほしい
・一般的にはエラーが起きたらboolでfalseでも返せばいいのだが、
この部分の処理がUSIOptionのコールバックで戻り値無し（void）になっている
そのため、評価値ファイルが見つからない場合の処理が入っていない
（もしかすると学習時にはこれでもよいので気にしていないのかもしれない）
一般ユーザー的にはゼロメモリの合成処理をしようとしてしまって意味が無い。
・解決方法はsrcの下に評価値ファイルを用意する
mingw環境ではシンボリックリンクで解決できる
ln -s ../bin/20151105 20151105
確か、Apery初配布ぐらいのときは読み込まれなくてちゃんと動いていない人が続出したような記憶があるが、この部分を直そうとすると上記のように結構面倒で諦めた記憶がある
あと学習時は０メモリににしたいと思われるので、LEARNとかMINIMALあたりで切り替わるようにするのが良さそう。
・無事成功すると配布版と同等の速度（NPS）になる
