今の実装よりもうちょっと賢い並列化方式
「今の」というか、GA将のVer.1で実装したやつですが、単純なPVS*1でした。ハッシュの手はシングルスレッドで読んで、それでカットしなかったら残りを並列化ってやり方です。
これは要するに「ハッシュの手でカットしなかったら、Cut Nodeの可能性が高い。だから並列化しよう。」って考えてやってたんですが、いくつか問題があります。
- ハッシュの手が無いと無条件に並列化する → Cut Node誤認の可能性大
- ハッシュの手の次やその次の手でカットが起きると、無駄な探索が必要 → 遅くなる
んで、例えば「カットノードの場合、上位n手でカットが起きる可能性がm%」ってデータをとっといて、それをもとに適当な閾値（例えばm=95%）までの手はシングルスレッドで探索*2、その後からは並列探索ってのを検討中。
実装は少し面倒ですが、閾値固定ならそれほど複雑にはならないはず。
もしくは、探索中に実際のCut Nodeの探索結果からm=95%になるnの値を調べれば、さらに効率上がるかも。「ムーブオーダリングが信用出来る状態なら1〜2手読んだ後に並列化。信用出来ないなら10手くらい読んでから並列化。」とかって動作になるはずです。
…ただこれ、絶対どこかの誰かが既にやってるネタですよねぇ。論文でも見つかりゃ楽なんですが、どうやって検索すれば良いのか… 良いキーワードが思いつかないです ＿|￣|○
