証明駒

詰み探索に証明駒を実装した。

証明駒は以下の論文の説明の通り実装した。
詰将棋を解くアルゴリズムにおける優越関係の効率的な利用について

速度比較

証明駒の実装前後で速度は以下の通りとなった。
実装前の状態は、前回の日記に書いた先端ノードで2手詰めと3手詰めを行い、優越関係の反証への利用を行ったものと比較している（前回の実装に一部バグがあったので修正している）。

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

	探索ノード数	処理時間
実装前	19504	71ms
実装後	20652	73ms

わずかに遅くなってしまった。

速くなる局面もあった。
sfen 7n1/+R5glK/n4s1p1/p4pkl1/2s3n2/P3PP2P/1P+pG5/2P6/9 b R2B2G2S2L8Pn 1

	探索ノード数	処理時間
実装前	476743	1076ms
実装後	215831	517ms

他にもテスト用の37局面で比較したが、平均して改善はわずか(0.8%)であった。

実装の変更

論文では、詰みの局面と後手の局面で、後手が1枚も持っていない種類の先手の駒を証明駒に加えるとなっているが、近接王手の場合は不要なため、近接王手以外の場合のみその処理を行うようにした。

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

	探索ノード数	処理時間
変更前	20652	73ms
変更後	28433	106ms

sfen 7n1/+R5glK/n4s1p1/p4pkl1/2s3n2/P3PP2P/1P+pG5/2P6/9 b R2B2G2S2L8Pn 1

	探索ノード数	処理時間
変更前	215831	517ms
変更後	187811	443ms

遅くなる局面と速くなる局面がある、37局面の合計では、6%ほどの改善であった。

考察

証明駒を実装してもそれほど改善されなかった。
証明駒にはどれくらい効果があるものかデータがあれば調べたい。もっと効果があるものであれば、どこかで実装が誤っているかもしれない。
反証駒も同様に実装できるので、試したい。

github.com

優越関係の反証への利用

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

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

前回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手詰めのみの場合より探索ノード数は減っているが、処理時間は少し遅くなっている。詰み局面での改善を考慮すると許容範囲だろう。

2手詰めルーチン

前回詰み探索に3手詰みルーチンを入れると遅くなったと書いたが、先端ノード以外でも3手詰めルーチンを呼び出していたことが原因だった。

3手詰めを行うのは先端ノードのみとして、15手詰めの局面で速度を比較しなおした。
position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

	探索ノード数	処理時間
1手詰めルーチン	100591	330ms
3手詰めルーチン	104886	357ms

前回より改善されたが、それでも1手詰めルーチンより遅くなっている。
探索ノード数が増えているのは探索順が変わったためと思われる。

次に、3手詰めチェックを行う際に、1手詰めのチェックを行った結果をハッシュに残すように修正した。

	探索ノード数	処理時間
1手詰めルーチン	100591	330ms
3手詰めルーチン	160249	523ms

これも探索順が変わったことで探索ノードが増えてしまった。
3手詰めは近接王手しか生成していないので、ゲーム木のバランスが崩れてしまうのかもしれない。

2手詰めルーチン

以下の論文で、ANDノードで2手読みをすると効果があるという記述があったので、ANDノードでの2手詰めを試してみた。
新規節点で固定深さの探索を併用するdf-pn アルゴリズム
論文では、証明数の先読みを行っているが、証明数の先読みは行わず、1手詰めの結果をハッシュに残すのみとした。

	探索ノード数	処理時間
1手詰めのみ	100591	330ms
2手詰めルーチン	24146	92ms

探索ノード数は、24%になり、処理時間は27.8%になった。
先端ノードでの2手詰めチェックは効果があることがわかった。

3手詰めと組み合わせ

2手詰めに加えて、3手詰めも行うようにした。3手詰めでは1手詰めの結果をハッシュに残さない。

	探索ノード数	処理時間
1手詰めのみ	100591	330ms
2手詰め+3手詰め	19497	71ms

2手詰めと3手詰めの両方を行うことで、さらに処理速度が改善された。

不詰みの局面

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

	探索ノード数	処理時間
1手詰めのみ	395634	645ms
2手詰め	391476	669ms
2手詰め+3手詰め	381496	724ms

不詰めの局面では1手詰めが一番早いという結果になった。
探索ノード数は、減っているため、2手詰め、3手詰めの処理に時間がかかることによって処理時間が伸びている。
実戦のモンテカルロ木探索の末端で使用する場合は、不詰みの方が多いため、2手詰め、3手詰め行わない方がよさそうだ。

github.com

バグ修正

王手生成にバグがあったので修正した。開き王手で直線上に移動する場合に直接王手にならない手も生成していた。

3手詰めルーチン

詰み探索に近接王手からの3手詰めルーチンを実装した。
近接王手の手を生成することで、3手で詰む場合無駄合いを省くことができる。

近接王手の生成は、敵玉の8近傍に移動または持駒から打つ手と、桂馬で王手する手を生成する。
王手の指し手生成を変更することで作成した。
3手詰めルーチン · TadaoYamaoka/ElmoTeacherDecoder@4b331e0 · GitHub

3手詰めのルーチンはやねうら王のmate_n_ply.cppを参考に実装した。
3手詰めルーチン · TadaoYamaoka/ElmoTeacherDecoder@4b331e0 · GitHub

生成した近接王手に、自分の駒からの利きがない場合と、敵の王以外の駒からの利きがある場合、移動により自玉が詰む場合は除外する。
残った手について、1手指して、敵玉の王手回避後、1手詰めルーチンですべての手が詰むか調べる。
2手指して、戻す処理が入るため、それなりに計算コストが高い。

速度比較

詰み探索に1手詰めルーチンを使った場合と3手詰めルーチンを使った場合で、前回と同様の15手詰めの局面で速度を比較した。
position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

1手詰めルーチン	330ms
3手詰めルーチン	366ms

3手詰めルーチンを使うと10%程遅くなってしまった。

25手詰めの局面では、
position sfen lnl5l/2b6/ppk6/3p1p2p/Ps2p1bP1/1NP3g1K/LP6P/9/1N6+p b R3G2SN2Prs4p 1

1手詰めルーチン	4677ms
3手詰めルーチン	6135ms

34%程遅くなった。

まとめ

3手詰めルーチンは指して戻す処理が必要なため計算コストが高い。3手で詰む場合は無駄合いを省くことができるが、3手で詰まない局面でも呼び出すと探索速度が落ちてしまう。
1手詰めルーチンを使って、無駄合いは優越関係を使って省略した方が良い。

近接王手の生成を実装しているときに、王手生成で歩を必ず成るようにしていた問題に気づいた。
打ち歩詰めが関係するので、歩は成らない手も生成する必要があるので修正しておいた。

詰み探索のループ対策

やねうら王から移植した詰み探索では、以下の後手3手詰めの局面を不詰みと判定してしまう。
position sfen +B+R5n1/5gk2/p1pps1gp1/4ppnsK/6pP1/1PPSP3L/PR1P1PP2/6S2/L2G1G3 w B2N2LP2p 1

原因を調べたところ、探索にループが発生し、深さが4で始めと同じ局面になり、pnとdnが誤ってカウントされてしまうことで、後手の2五銀のループが検出できずに最大深さまでループして探索が打ち切られてその結果が置換表に登録されてしまっていた。
やねうら王の詰み探索では、無限ループの対策としてThreshold Controlling Algorithm (TCA)が実装されているが、置換表がループ後に現れた局面を同一と判定してしまっているため誤動作していた。
対策として、探索の深さが異なる局面は別の局面として置換表に登録することにした。
深さが同じでも別の経路から同じ局面に至る場合があるが、それはまた別の対策が必要になる。

対策を入れた後に、前回と同様の15手詰めの局面で速度を比較した。

対策前	176ms
対策後	380ms

2.15倍遅くなってしまったが、対策前はたまたま正しく動いていたものと思われる。

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

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

局面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

やねうら王の詰み探索をAperyに移植

Aperyの初期局面集には、詰みの局面を数%含んでいるので、これを除きたい。
詰みの局面で自己対局を行い教師局面を生成すると終盤局面に偏りが生じると考えるためである。
なお、初期局面集に詰みの局面を含めることがマイナスか判断するには実験が必要だが、確かめてはいない。

詰みの局面を除くために初期局面集の各局面に対して詰み探索が必要になる。
以前にdf-pnを実装したことがあるので、それを使って試そうと思ったが、証明ノードが多い不詰みの局面でうまく動かなかったためバグ取りをするより、やねうら王の詰み探索を移植することにした。

やねうら王の詰み探索をAperyに移植

やねうら王のmate-engineのソースコードをほぼそのまま流用して、Aperyに移植を行った。
ElmoTeacherDecoder/dfpn.cpp at master · TadaoYamaoka/ElmoTeacherDecoder · GitHub

基本的にPositionクラスのメソッド名を変えるだけで対応できたが、やねうら王にあってAperyにない機能については、それらも移植した。
王手の生成については、以前に移植したことがあるのでそれを利用した。
また、Positionから1手指した後のハッシュキーを取得するメソッドがなかったので、AperyのPositionクラスに追加した。
ElmoTeacherDecoder/position.cpp at master · TadaoYamaoka/ElmoTeacherDecoder · GitHub

移植した詰み探索を使って、以前に試した15手詰めの局面の詰み探索を行い探索速度を調査した。
position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

結果、1625msと以前に自作したdf-pnと同じくらいの速度だった。
それほど早くないが、バグなく安定して使えるのでこれを使用することにする。

探索速度

20手以上の長手数の詰みや、証明ノード数が多い不詰みの局面だと非常に探索に時間がかかるので、探索の深さと探索局面数に制限を設けて時間がかかる局面は不詰みとして扱うことにした。
探索の深さ＝20
探索局面上限＝1048576

これで、シングルプロセスで平均33局面/秒の速度で探索できるようになった。

分割処理

詰み探索の置換表はStockfish風になっているが参照、更新する際に特別な考慮をしないとlock lessでは使用できなそうである。
Stockfishがグローバルな置換表をマルチスレッドで使用できる仕組みがどうなっているかはあまり理解できていない。
詰み探索の置換表はマルチスレッドでは使えなそうである。
そこで、初期局面集を分割してマルチプロセスで処理するようにした。

10コアのPCで初期局面集を10分割して、各プロセスで約500万局面ずつ探索して、1.75日くらいで完了する見込みである。
副産物で大量の詰み局面集ができあがるので、何かの用途があるかもしれない。

なお、自玉が王手の場合は、ANDノードから探索を行い詰みの場合はそれも除くようにした。

モンテカルロ木探索での利用

dlshogiではモンテカルロ木探索の末端ノードで7手の詰み探索を行っているが、7手であればAND/OR木を全て探索しても早いので、df-pnは使っていない。
df-pnを使えばもう少し探索手数を増やせるので、置き換えることも検討したい。
置換表がマルチスレッドに対応していないので、スレッドごとに置換表を分けることになると思う（もしくはロックを実装する）。
以前は探索スレッド数が多いこともあったdf-pnはあきらめていたが、探索と評価の直列化をしたことでスレッドごとに置換表を割り当てても問題なさそうである。
スレッドごとに置換表を分ける場合、サイズはあまり大きくできないので、探索ノード数を制限することになりそうである。