やねうら王搭載の詰将棋ルーチンの千日手対応
Qhapaq アドベント将棋記事 14日目
やねうら王（tnk-）に搭載のdf-pnベースの詰将棋エンジンが図巧の1番を解けないことが発覚しました。時折聞かれる「コム将棋の開発ってどうやってやるの」という問への答えとして使えそう課題なので、図巧の1番の解決を目指したライブデバッギングをネタの水増しとしてやっていきたいと思います。
【1日目】
【まずどの局面で詰まないのかを二分探索する】
図巧の答えを見たい人はこちら。
図巧の１番は６９手目という超大作です。詰むはずの局面を詰まないと言われただけで問題が見えるレベルのサイズではありません。というわけで、まずは２分探索をして、何手目から読ませたら詰まなくなるのかを確かめます。
30手目から...詰む
16手目から...詰む
8手目から...詰まない
12手目から...詰まない
14手目から...詰む
ということで、どうやら１３手目に対して不詰の変化がある（模範解答は１４手目が正確ではない）と主張していることが解りました。
となると、１３手目の１５飛車打に対して、tnkの詰め将棋ルーチンはどんな手で詰まないと主張しているかを知るのが良さそうなことが解ります。打ち歩詰めや合法手生成が間違っているのか、はたまた本当に不詰なのか......
【2日目】
【詰まない変化を追いかける】
次にやねうら王を改造し、不詰の局面でどのような変化を提案するかを調べます。不詰の変化を全列挙するのは大変なので、特定の変化（手順をmove形式で与える）についてのみ、ハッシュテーブルに保存されたpn、dnをとりだせるようにした上で、詰みの場合は詰みの手を、不詰の場合は不詰の手を返すようにします。
その結果、13手目から探索をした場合▲15飛車打、14手目△25飛車打の手順が不詰である（▲15飛車打、14手目△25飛車打したあとの局面を初期局面にした場合は詰むにもかかわらず！）という出力が得られました。
となれば、何かしかの影響で、詰み手順の中の局面が不当に不詰に書き換えられていると予想できます。
【ハッシュの重複を探す】
局面の評価を書き換えうる要素としてまず浮かぶのが局面のハッシュ（キー）の重複です。この詰め将棋エンジンではキーは32bitであるため、億単位の局面を探索すれば重複がありえます。幸いにも、上述の「詰まない」と言われる局面で探索される局面の数は数千万オーダーなので、局面のsfen文字列を全て保持してもメモリは爆発しなさそうです。
そこで、局面が新しく探索されるたびに、その局面のハッシュとsfenのペアを保存し、異なる局面が同じハッシュを持っていないかをチェックしました（mapでデータを扱えば局面数をNとした場合の計算量はO(NlogN)なので全ての組み合わせについて検証が可能です）。ところが、局面のハッシュ衝突は見られませんでした。となると、少なくとも今回の問題ではハッシュ衝突は原因ではないようです。
【千日手の処理がどうやらおかしいようだ】
ハッシュが原因ではないということで、不詰にされた局面をよく眺めると、どうやら千日手周りの局面で評価がおかしいことに気付きました。tnkの詰め将棋エンジンでは千日手になった局面は不詰の評価を付けていますが間違いです。というのも、「千日手の変化は不詰」であっても「千日手の変化の途中で出てくる局面が不詰」とは限らないからです。例えば以下のような局面で千日手の筋が見つかったことを理由にこれらの局面を不詰にすると、本当は詰む問題について詰まないという結論が出てしまいます。
【問題の要件をまとめる】
千日手周りの問題を処理するには以下の要件を満たす必要があります。
・何らかの理由で千日手周りの変化の検討を打ち切る
・千日手を構成する局面のpn、dnを不当に不詰に変えてしまわない
【3日目】
【千日手処理を書き換える】
問題の要件と今回用いた解決方法を改めて図にまとめると以下のようになります。従来のルーチンでは千日手になった局面を詰まないとみなしていたため、左図のような変化で詰みを見つけることが出来ません。そこで、今回の改造では「千日手の変化で不詰とするのは千日手の変化の中でもっとも開始局面から遠い局面（末端局面）とする」、「末端局面が攻め手側の場合は、親局面に戻る手を違法とする」ことで今まで扱えなかった変化で詰み筋を見つけられるようにしました。
【以下、感想戦】
【原著論文の実装しょぼくね？】
原著論文の実装ではこんなありがちなケースも解けないのか、と思うかも知れませんが、通常の千日手の変化であれば、局面をそもそもループなどせず、攻め手側が別の手を探索してくれます。というのも、普通であれば局面を深く探索するほど局面のpn、dnは増えるため、ループをする時点で親局面や兄弟局面のpnを千日手の変化のpnが上回るからです。
今回の千日手で厄介だったのは受け手側に千日手を拒否する選択権がなかった（王手に対して合法手が１つしかなかった）ことです。これだと手を何度ループしてもpnは1から増えない（pn=1は詰みを除けば最も魅力的な変化）ため、攻め手側も千日手の変化を望んでしまうのです。
【問題は完全解決したのか】
ぶっちゃけしてないと思います。あくまで変な不詰が出る変化が少し減っただけと言えましょう。上記改造の脆弱性としては、例えば、千日手を構成する各々の局面の初期局面からの距離が探索の過程で変わる（より短い手数でその局面にたどり着く方法が見つかる）などがありえます。
【以下、個人的ポエム】
連休を詰将棋の改良に使った感想は「詰将棋の解析は1日でならない」というものでした。やねうら王に搭載されている詰将棋ルーチンの原著論文では、千日手周りの処理についての解説は殆どなく、千日手の処理は「不詰判定の一部」とみなしているようです（恐らく、論文通りの実装した結果が上記の脆弱性なので、解説を端折ってるか論文のやり方に不備があるかだと思います。正直な話、今回考えたハックを原著論文の技術を正しく実装しただけと言われたらちょっとムカつく）。
詰将棋界隈にはまだまだ上がおり、超難しい詰将棋を安定して解かせるという意味では、脊尾詰やなのは詰めのほうがまだまだ格上なのではと正直思います。とはいえ、やねうら王には詰将棋以外のルーチンも搭載されていること、ごく一部の難しい詰将棋でなければ現状の実装でも十分解けること、計算事態が高速であること、オープンソースであり様々な環境で動くこと（個人的にはこれが一番大事）などを考えれば不完全であっても十分な価値があり、一歩ずつでも品質を高めていくのは大事なのではないかなと思います。
今回作ったデバッグ用のコードの中では、詰め将棋探索後にユーザが特定の局面を指定することで、その局面のpn/dnを見られるルーチンは便利だなと思いました。詰将棋エンジンの隠しコマンドとしてコイツもプルリクしたいところです。
【おまけ】
なのは詰めなどの既存ルーチンがwindowsでしか動かないバイナリでしか配られていないと言った所、linuxで動かす方法を色々教えてもらいました。皆様ありがとうございます。
暫く日記の更新が滞ってましたが、手強い問題解決のコツの一つに、気がめいらないように休憩をちょくちょく入れるというのもありますのでそういうことで......
