局面Aが局面Bを優越する場合、Aの証明数はBの証明数以上になる性質がある。
そのことを利用すると、Aの証明数は、AとAに優越されるすべての局面の証明数の最大値をAの証明数とすることができる。
反証数についても同様に優越関係を利用できる。
これをそのまま詰み探索に適用すると、かなりの局面で探索ノードが増えて遅くなってしまった。
原因は追究できていないが、探索ノードが多い局面ほど遅くなる傾向があるため、サイクルとDAGが関係していると疑っている。
そこで、先端ノードのみでこの性質を利用して証明数と反証数を初期化するようにした。
速度比較
優越関係を利用して証明数と反証数の初期化を実装する前後で探索速度は以下のようになった。
15手詰みの局面
sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161
| 探索ノード数 | 処理時間 | |
|---|---|---|
| 優越関係利用なし | 28372 | 108ms |
| 優越関係利用あり | 7200 | 31ms |
探索ノード数が25.3%になり、処理時間は28.7%になり、大幅に速くなった。
テスト用局面のほとんどの局面で改善しており、テスト用の37局面の合計で、処理時間が85%になった。
まとめ
優越関係を証明済、反証済局面以外の局面にも利用することで、探索速度を改善できた。
はじめ先端ノード以外でも利用していて効果がなかったため採用を見送っていたが、先端ノードのみに適用してみたら効果あった。
先端ノード以外に適用できない件はできれば原因を調べたい。
上記の15手詰みの局面で探索ノード数は、なのは詰め64bit版の16929よりも少なくなっている。
しかし、処理時間はなのは詰めは19msで、まだ及んでいない。
持ち駒の実装を詰み探索に特化すればもう少し改善できそうであるが、詰み探索の改良は一旦保留して、自己対局による強化学習の方に現状の詰み探索を組み込む予定。
