SSブログ

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なるものがコミットされていた(2015年9月コミット)。

 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自体は古くからある実装方法だが、2013年ぐらいでは採用が見送られていたらしい。ところが、今年2月ぐらいにCheng?というソフトが実装したところ、8コア以上でもスケールする(コアが増えるほどレーティングがあがる)ということで、Stockfishに採用してはどうかということで再び脚光が当たった。

 http://www.talkchess.com/forum/viewtopic.php?t=55170&start=11

 掲示板の議論を見てみると、「Stockfishで効果あるかどうかはわからない」的なことが書かれていたが、Lazy SMPの実装が容易であるのもあって速攻実装されて検証された。元々の実装であるYBWC(Splitpointのある実装)では4コアで頭打ちで、8コアではレーティングがむしろ下がったのが、8コアでも見事にスケールした(レーティングがあがった)ことで採用となった。(SplitPointの設定が悪いんじゃないか、とかいろいろあったようだが)

 Lazy SMPの動きそのもは単純で反復深化を行う際に、深さごとスレッドを割り当てることになる
 どの深さのスレッドを割り当てるかどうかは初期のコミットでは以下のようになっている。

 depth = Threads.main()->depth + Depth(int(3 * log(1 + this->idx)));

 関数にLogが入ってるのは深い探索ほど傾きが少なくなり、一つの深さを複数のスレッドで計算するようになる。
 親スレッドがDepth1を計算している時に、子スレッドは2~を計算するが、親スレッドがDepth10ぐらいあたりからは同じ深さを探索するようになる。

 評価した計算結果はメモリ上のTransposition Table(置換表)に入るので、親スレッドが、Depth2を計算したときに、子の計算結果が入っているため、メモリ参照だけで計算が終わるというのが、この方法がうまくいく理由らしい。
 
 このように置換表を前提とした誰でも思いつくような(怠惰な)並列探索にすることによって、コアが増えれば増えただけスケールしてくれるというメリットが出てくるらしい。

 やねうら王Blogで「(ほんのちょっとだけ)クラスタに効果がある」と書かれているのは、LazySMPは「置換表が十分大きく、他のスレッドの計算結果を参照するだけで自分がほとんど計算しないですむこと」がキモなので、置換表を共有できないクラスタでは大きい効果は望めないが、このような短絡的な探索の割り振り方によってクラスタでもスケールするのではないかという主張。(Bonanza Clusterは投機的実行なのでYBWCと意味合い的には同じだと思っている)

 また、ChengやStockfishでは4コアではYBWC版とは特にスコアが変わらなかった。あくまでも8コアで効果が出たというだけなので、無差別級であるコンピュータ将棋選手権ならともかく、去年から今年になって8コア=>4コアになってしまった電王トーナメントでは効果はあまり期待できない。(技巧が勝ちにくかったのはこのせいかも?)

 ただ、実装が比較的容易なのと、YBWC特有のチューニングをしなくてよいという点ではレーティングの底上げに寄与する可能性がある。習甦なんかは並列に苦労してそうなイメージがあるのでどうなのだろうか。

 Stockfish探索型のYBWCを実装してある場合は容易に実装できるので、自分が見ている範囲だけでも3人(やねうら王、shogi686、Ponanza)は実装が終わっているが、効果の程がどうだったのかわかるのは先の話になりそう。


<追記>

 Stockfish Blog — Stockfish 7 http://ow.ly/WCRd4

 Stockfish公式Blogにもちゃんと書かれていた

nice!(0)  コメント(0)  トラックバック(0) 
共通テーマ:パソコン・インターネット

nice! 0

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

トラックバック 0

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。