TadaoYamaokaの日記

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

優越関係の反証への利用

先日の記事で、優越関係を反証に利用するとかえって遅くなるということを書いたが、遅くなる原因は、探索を深さで打ち切りにしていることが原因だった。

作成している詰み探索は、長手数の詰将棋を解くプログラムを開発するというより、実戦の詰み探索を短時間で行いたいという動機で作成している。
そのため、探索の深さに制限を設けていたが、最大の深さに達したときに不詰みとして扱っていたため、その局面が優越関係に利用されると不詰みでない局面が誤って不詰みとされていた。
そこで、探索の制限はノード数のみとし、深さは十分に大きい値とした。

前回2手詰め、3手詰めを行うと、不詰みの局面の探索速度が落ちることを確かめたが、優越関係を反証にも利用した場合に改善するか測定した。

不詰みの局面での速度比較

前回同様、以下の不詰みの局面での速度を比較した。
sfen position l2+S1p2K/1B4G2/p4+N1p1/3+B3sk/5P1s1/P1G3p1p/2P1Pr1+n1/9/LNS5L b R2GL8Pnp 1

探索ノード数 処理時間
1手詰めのみ(優越関係の反証への利用なし) 395634 645ms
1手詰めのみ(優越関係の反証への利用あり) 67406 88ms
2手詰め+3手詰め(優越関係の反証への利用なし) 381496 724ms
2手詰め+3手詰め(優越関係の反証への利用あり) 77426 127ms

優越関係を反証に利用することで、不詰みの局面で速度が改善している。
2手詰め+3手詰めを行うと、不詰みの局面で遅くなるのは同じ傾向だが、影響は少なくなっている。

詰み局面での速度比較

position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

探索ノード数 処理時間
1手詰めのみ(優越関係の反証への利用なし) 100591 330ms
1手詰めのみ(優越関係の反証への利用あり) 97599 322ms
2手詰め+3手詰め(優越関係の反証への利用なし) 19497 70ms
2手詰め+3手詰め(優越関係の反証への利用あり) 19497 70ms

詰み局面では、優越関係を反証に利用しても影響はほとんどない。

まとめ

優越関係を反証にも利用することで不詰みの局面での速度が改善することが確かめられた。
不詰みの局面で2手詰め+3手詰めを行うと速度が低下するが影響は小さくなった。
2手詰め、3手詰めで、不詰みのチェックも行うことで改善できそうなので次に試したい。

追記

2手詰めで不詰みチェックを行うようにした。
不詰みチェックは、1手詰めで詰まない場合に、王手の手がないことチェックする。
王手の手がないことは、王手生成のロジックを流用して、王手の手が1手以上ある場合に直ちにfalseを返し、王手が1手もない場合にtrueを返す。

上記の不詰みの局面で探索速度は以下の通りとなった。

探索ノード数 処理時間
1手詰めのみ(優越関係の反証への利用あり) 67406 88ms
2手詰め+3手詰め(優越関係の反証への利用あり) 77426 127ms
2手詰め+3手詰め(優越関係の反証への利用あり+不詰みチェックあり) 57130 94ms

2手詰めで不詰みチェックを行うことで、不詰みの局面での速度が改善した。
それでも、1手詰めのみの場合より探索ノード数は減っているが、処理時間は少し遅くなっている。詰み局面での改善を考慮すると許容範囲だろう。