dlshogiは、モンテカルロ木探索とは別に、詰み専用のアルゴリズム(df-pn)で長手数の詰み探索を行っている。
df-pnで詰みが見つかった場合、すぐにその手を返している。
df-pnは、詰みがあるかどうかを見つけるアルゴリズムのため、見つかる手順が最短手順とは限らない。
実戦上は詰ませればよいため、最短になることは考慮していない。
そのため、読み筋は(最短の)手順の参考にならないため表示していなかった。
しかし、issueを頂いたため、最短でなくても表示した方がよいかもしれないので、読み筋表示に対応した。
検討時のMateで読み筋が出ない · Issue #62 · TadaoYamaoka/DeepLearningShogi · GitHub
実装方法
df-pnで詰みが見つかった後に、ルートからゲーム木を辿り、
ORノードでは最初にpn=0になる手を選択し、
ANDノードでは手順が最大になる手を選択する。
先端ノードでは、1手詰めを行っているため、1手詰めで詰みになったノードのdnの値を他と区別するようにしておき、1手詰めのノードで再度1手詰めを行って読み筋に追加する。
テスト
やねうらお氏が公開してくれている詰将棋500万問を使ってテストした。
やねうら王公式からクリスマスプレゼントに詰将棋500万問を謹呈 | やねうら王 公式サイト
3手詰めは、深さ制限を3して、すべて正しく表示できた。ただし、1手詰めの局面が1214件含まれていた。
5手詰めは、深さ制限を5にすると、1件不詰めになる局面があった。
df-pnのANDノードでは、すべて5手以内で詰んでいないと不詰みになることによる。
深さ制限を大きくすると詰みになるが、最短手順ではなくなる。
7手詰めでは、深さ制限を7にすると、同様に不詰みになる局面が13件あった。
深さ制限を大きくすると詰みになるが、手順が17手や19手になるものがあったため、原因を調べたところ、飛車と角の不成を生成していないことで手順が長くなっていることがわかった。
不成の方が手順が短くなる局面
今まで、実戦上は問題ないだろうと思って、王手の指し手に飛車と角の不成は生成していなかった。
しかし、少数だが詰みの手順が10手以上伸びる局面があることがわかった。
いずれも、飛車と角を成ったことで、打ち歩詰めになるため手順が長くなっていた。
飛車の不成の方が良い例
+LR2R2n1/3g1lg2/3N2kp1/p2pp4/5S1Sp/1PP3SP1/P2PP2B1/1G1S2G2/LN2K4 b N6Pblp 121 l4p2l/7g1/6n1b/P2g1kS1p/3p2p2/2S2N1p1/1PKP1S1NP/4g1G2/L1+B1+p1S1L b RN5Pr3p 171 lkB1s3+N/4bs3/2RL2pp1/p1pGpp2p/1n1p5/8P/PP1PPPP1N/1G1S2S+R1/LN2KG2L b Pg2p 89 l8/2+P2+N1k1/4G2p1/2p2ps1G/p3s4/1pP1S4/PlN1gP+p2/1bGp5/L3K4 b R4Prbs2nl3p 193 l4ksRl/3+S5/p4pngp/2pp1bp2/9/P1PP1PP1P/1PNG1K3/1G4r2/L5bNL w G2SN2P3p 78 lR3p2l/2g1k1s2/ps1ppPn2/2pg2p1p/9/2PB1NP2/P1NPP1N1P/2S1KGS2/L2G4L b RPb3p 83
角の不成の方が良い例
9/3S1k3/3pg2+R1/4spP2/1p1PN3L/PP1nPP3/3l1SN2/K1g2G3/L3b+b3 w RGSL7Pn2p 126
不成も生成することで、全体的な探索時間への影響を調べた上で不成も生成するか検討したい。
まとめ
dlshogiのmateの読み筋表示に対応した。
テストしている中で、王手の指し手に不成を生成していないことで手順が10手以上伸びる局面があることがわかった。
今後、不成を生成するか検討したい。
