TadaoYamaokaの日記

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

反証駒

前回までに実装した詰み探索では、ループの対策を行っておらず、最大深さまでループする局面があった。
ほとんどの局面では閾値がうまく働いて無限ループにならないが、以下の19手詰めの局面で最大深さまでループが発生していたため、優越関係を反証に利用すると、最大深さに達した局面が不詰み扱いになるため、誤って不詰みと判定されていた。
sfen ln6K/1ksPg1sG1/5s2p/ppp3p2/9/P1P3P2/4+p3P/1+r7/LN3L2L w RBSb2g2n7p 1

完全なループの対策をする方法もあるようだが、とりあえず簡易な実装として千日手チェックを行い千日手となった局面にはハッシュに印をつけて、優越関係では利用しないようにした(親のノードにも影響するので完全な対策にはなっていない)。
判定が誤ることなくても、ある程度ループしている局面があったようで、千日手チェックを入れるとテスト用の37局面の合計で3%程速くなった。

反証駒

前回証明駒を実装したが、反証駒も実装した。
反証駒は、証明駒とは逆に不詰みを証明するための後手の最小の持ち駒のことを示す。

ハッシュは、すべて先手の駒で保持しているため、後手の駒を先手の駒に読み替えて実装する必要があった。

不詰みの局面では、後手側では、反証駒を0にして、先手が1枚も持っていない種類の駒を反証駒に加える。
これを先手の持ち駒で表現すると、先手が持っている種類の持ち駒に後手の持ち駒を加える(後手の持ち駒を0にすると同義)。
先手が1枚も持っていない種類の駒を反証駒に加える部分は、もとから先手の持ち駒は0なので処理は不要となる。

ANDノードでは、後手が駒を打った場合は反証駒を減らし、後手が駒を取った場合は反証駒に加える。

ORノードでは、子局面の反証駒の積集合とする。また、先手が一枚も持っていない種類の駒の反証駒を0にする。

速度比較

反証駒を実装する前後で速度を比較した。

15手詰みの局面

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

探索ノード数 処理時間
証明駒のみ 28372 108ms
証明駒+反証駒 28372 110ms

探索ノード数は変わっておらず、処理時間も誤差の範囲である。

不詰み局面

sfen +B2B1n2K/7+R1/p2p1p1ps/3g2+r1k/1p3n3/4n1P+s1/PP7/1S6p/L7L b 3GS7Pn2l2p 1

探索ノード数 処理時間
証明駒のみ 952464 2158ms
証明駒+反証駒 910453 2062ms

探索ノード数が減っており、4.4%程処理時間が速くなっている。

テスト用の37局面の合計では、4.9%程速くなった。

考察

反証駒の実装前後で、処理速度の改善は5%以下であった。
証明駒の効果と同程度である。両方組み合わせると局面に依存するがテストした局面の合計では10%程改善した。
探索ノード数が多い局面ほど、効果があるようである。

証明駒も反証駒も参考にできるオープンソースがないため、実装があっているかあまり自信がない。
github.com

証明駒

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

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

速度比較

証明駒の実装前後で速度は以下の通りとなった。
実装前の状態は、前回の日記に書いた先端ノードで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
f:id:TadaoYamaoka:20180521223401p:plain

原因を調べたところ、探索にループが発生し、深さが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