TadaoYamaokaの日記

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

詰み探索で優越関係の利用

やねうら王から移植した詰み探索の速度を上げるために優越関係の実装を行った。

局面Aが局面Bを優越するとは、AとBの盤上の駒の配置が同一で持駒のみが異なっており、Bの持駒がAの持駒の部分集合になっている場合を示す。
参考:
詰将棋を解くアルゴリズムにおける優越関係の効率的な利用について

言い換えると、盤面が同じで持駒が多い局面のことを指す。
詰み探索では、ある局面と盤面が同じで持駒がより少ない局面で詰みが証明できるならば、その局面も詰みであることを利用すると、探索ノード数を減らすことができる。

置換表

優越関係を利用するには、盤面が同じ局面を効率的に置換表から検索できる必要があるため、通常の探索では置換表のキーは、盤面と持駒を合わせたハッシュ値になるが、優越関係を利用する場合、置換表のキーは、盤面のみのハッシュ値とする。
局面を区別するため、持駒も置換表のエントリに保持しておく。

持駒の表現

持駒は、各駒の枚数に必要なビット数を割り当て、32bitに詰め込む。
AperyではHand型で実装されているので、そのまま利用した。
Aperyには優越関係を調べるためのisEqualOrSuperiorメソッドも用意されている。

置換表のエントリ数

ハッシュキーを盤面のみとするため、持駒のみが異なる複数局面のハッシューが同一となる。
そのため、同一のハッシュキーに対して十分なエントリ数を用意しておく必要がある。
256エントリあれば、ほとんどの場合でエントリが不足することはない。
エントリが不足したらどれかのエントリを上書きすることになる。
(情報量が少ないエントリを上書きするのがよいが実装していない。)

優越関係の利用

詰み探索中に置換表を検索する際に、優越関係を満たす局面に詰み(証明数が0)があれば、そのエントリを返すようにする。
ここで、ORノードとANDノードで優越関係が逆になるので注意する。
ORノードでは、持駒の少ない局面を調べるが、ANDノードでは、相手側の持駒になるので相手の持駒が多くても詰むか調べる必要がある。

速度比較

以下の15手詰めの局面で速度を比較した。
position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

優越関係利用なし 1625ms
優越関係利用あり 176ms

9.23倍高速になった。

まとめ

優越関係の実装は、ハッシュキーの仕組みを変更するだけで実装することができ実装は難しくないが、効果が大きい。
優越関係を利用することで無駄合いの判定などの特別な処理を行うことなく、無駄合いの局面の探索を省略できる。

なお、優越関係を満たす局面の不詰みも利用することが可能だが、かえって遅くなる場合があったので利用しないことにした。

優越関係の利用は、詰みの局面のみではなく、優越関係を満たす局面のpnの値も利用できる。
そちらについても実装する予定である。

優越関係を実装したソースコードはこちら。
github.com