TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

詰み探索の高速化

前回までに作成したdf-pnによる詰み探索を自己対局に組み込んでみたが、探索速度が遅くあまり実用にならなかった。

これまでは、モンテカルロ木探索の先端ノードで全探索の7手詰めを行っていたが、それと同じ時間になるようにdf-pnの探索ノード数を調整すると、150ノードしか探索できない。

150ノードでは、7手詰め以上の詰みを見つけられるときもあるが、7手詰めを見逃すことがあり、単純には置き換えることができない。
インライン化やテンプレート化をして高速化を行ったが、改善は数%程度で、なかなか高速化できずに困っている。

ハッシュのサイズを小さくするほど探索速度が上がるので、CPUのキャッシュヒット率が関係していそうだが、df-pnで優越関係を使用しているため、ハッシュエントリサイズが大きく、キャッシュに載せるのが難しい。
詰み探索に特化したハッシュ構造を考える必要がありそうだが、今のところ良い案が浮かばないので、詰み探索を組み込むのは宿題としておく。

github.com

バグ修正

テストしているときに、また王手のバグ修正が見つかった。
玉で開き王手する場合に、玉の自殺手を除外していなかった。