やねうら王搭載の詰将棋ルーチンの改造中継(ver 2)

Qhapaq アドベント将棋記事 13日目

前回の記事もマージしています。

やねうら王(tnk-)に搭載のdf-pnベースの詰将棋エンジンが図巧の1番を解けないことが発覚しました。時折聞かれる「コム将棋の開発ってどうやってやるの」という問への答えとして使えそう課題なので、図巧の1番の解決を目指したライブデバッギングをネタの水増しとしてやっていきたいと思います。

 

【1日目】

【まずどの局面で詰まないのかを二分探索する】

図巧の答えを見たい人はこちら。

park6.wakwak.com

図巧の1番は69手目という超大作です。詰むはずの局面を詰まないと言われただけで問題が見えるレベルのサイズではありません。というわけで、まずは2分探索をして、何手目から読ませたら詰まなくなるのかを確かめます。

 

30手目から...詰む

16手目から...詰む

8手目から...詰まない

12手目から...詰まない

14手目から...詰む

ということで、どうやら13手目に対して不詰の変化がある(模範解答は14手目が正確ではない)と主張していることが解りました。

f:id:qhapaq:20200722093426p:plain

この局面は意図したとおりに詰む

 

f:id:qhapaq:20200722093558p:plain

この局面は詰まない(と主張している)

 

となると、13手目の15飛車打に対して、tnkの詰め将棋ルーチンはどんな手で詰まないと主張しているかを知るのが良さそうなことが解ります。打ち歩詰めや合法手生成が間違っているのか、はたまた本当に不詰なのか......

 

【2日目】 

【詰まない変化を追いかける】

次にやねうら王を改造し、不詰の局面でどのような変化を提案するかを調べます。不詰の変化を全列挙するのは大変なので、特定の変化(手順をmove形式で与える)についてのみ、ハッシュテーブルに保存されたpn、dnをとりだせるようにした上で、詰みの場合は詰みの手を、不詰の場合は不詰の手を返すようにします。

 

その結果、13手目から探索をした場合▲15飛車打、14手目△25飛車打の手順が不詰である(▲15飛車打、14手目△25飛車打したあとの局面を初期局面にした場合は詰むにもかかわらず!)という出力が得られました。

 

となれば、何かしかの影響で、詰み手順の中の局面が不当に不詰に書き換えられていると予想できます。

 

【ハッシュの重複を探す】

局面の評価を書き換えうる要素としてまず浮かぶのが局面のハッシュ(キー)の重複です。この詰め将棋エンジンではキーは32bitであるため、億単位の局面を探索すれば重複がありえます。幸いにも、上述の「詰まない」と言われる局面で探索される局面の数は数千万オーダーなので、局面のsfen文字列を全て保持してもメモリは爆発しなさそうです。

そこで、局面が新しく探索されるたびに、その局面のハッシュとsfenのペアを保存し、異なる局面が同じハッシュを持っていないかをチェックしました(mapでデータを扱えば局面数をNとした場合の計算量はO(NlogN)なので全ての組み合わせについて検証が可能です)。ところが、局面のハッシュ衝突は見られませんでした。となると、少なくとも今回の問題ではハッシュ衝突は原因ではないようです。

 

 

千日手の処理がどうやらおかしいようだ】

ハッシュが原因ではないということで、不詰にされた局面をよく眺めると、どうやら千日手周りの局面で評価がおかしいことに気付きました。tnkの詰め将棋エンジンでは千日手になった局面は不詰の評価を付けていますが間違いです。というのも、千日手の変化は不詰」であっても「千日手の変化の途中で出てくる局面が不詰」とは限らないからです。例えば以下のような局面で千日手の筋が見つかったことを理由にこれらの局面を不詰にすると、本当は詰む問題について詰まないという結論が出てしまいます。

f:id:qhapaq:20200725164719p:plain

図巧1番の詰手順の中には千日手可能な局面がある

 

【問題の要件をまとめる】

千日手周りの問題を処理するには以下の要件を満たす必要があります。

 

・何らかの理由で千日手周りの変化の検討を打ち切る

千日手を構成する局面のpn、dnを不当に不詰に変えてしまわない

 

今回は此処まで。

次回はこれらの要件を満たす千日手の処理方法を考えます(次回が最終回です。問題は(多分)解けます)

 

【おまけ】

なのは詰めなどの既存ルーチンがwindowsでしか動かないバイナリでしか配られていないと言った所、linuxで動かす方法を色々教えてもらいました。皆様ありがとうございます。

暫く日記の更新が滞ってましたが、手強い問題解決のコツの一つに、気がめいらないように休憩をちょくちょく入れるというのもありますのでそういうことで......