search

yaneurao / YaneuraOu

YaneuraOu is the World's Strongest Shogi engine(AI player) , WCSC29 1st winner , educational and USI compliant engine.
GNU General Public License v3.0
525 stars 140 forks source link

df-pnベースの詰将棋の品質をもう少しあげたい #116

Closed qhapaq-49 closed 3 years ago

qhapaq-49 commented 4 years ago

現状の問題

詰まない局面の例

barcodehair様より

解けない詰将棋はいろいろありそうです。少し試しただけですが、以下の２つは解けませんでした。
（本当は詰むのに短時間で不詰を返す）
馬鋸の例題
sfen 7k1/5+Bp2/7Ss/9/9/9/1n7/9/9 b 2rb4g2s3n4l17p 1
使用駒9枚長手数 (https://www.ne.jp/asahi/tetsu/toybox/challenge/c1056.htm)
sfen 1+P2l4/2P6/9/p5+R2/2k6/B3+P3B/9/9/9 b r4g4s4n3l14p 1

また、以下の問題は明らかにおかしな手順を解答します。玉方がループを避けているように見えます。
以前のバージョンでは正しく解答するようなので、デグレかもしれません。
sfen 4+P+P+P+P1/+P1+P5+P/7kP/PP5pp/1+P2+P1pP1/6+P1+P/9/9/9 b 2r2b4g4s4n4l 1

今後作りたいもの（上にあるものほど先に作る？）

詰み局面、不詰局面の検証エンジン

局面合流に強いというWPNS

https://www.researchgate.net/publication/220962458_Weak_Proof-Number_Search

劣等局面を使った高速化

https://tadaoyamaoka.hatenablog.com/entry/2018/05/20/150355

yaneurao commented 4 years ago
  1. どの問題も時間をかければ詰むようになる

ハッシュ衝突やメモリ不足で詰まないのはまあ、GC導入したり、Hashを64bit+αにするなどしてある程度回避はできると思いますので、アルゴリズム的に誤判定してしまうことさえなければ、あとは何とかなります。

  1. 詰む問題に対して不詰と返すのはまずい(その結果を利用するのに困るので..)　本当に不詰の問題に対してのみ不詰と返すようにする

詰みが発見できず、不詰かどうかわからない場合は、探索がいつまでも終わらないほうがまだマシと言えます。

Qhapaqさん、頑張ってくだされ…。

yaneurao commented 4 years ago

dlshogiの詰将棋ルーチン、置換表サイズの問題で解けない問題があるだけなのでしたら、これ移植してきて(元はtanuki-詰将棋エンジンを参考に書かれたそうですけども)、詰将棋エンジン対応をしたあと、置換表にGCつけるのがよろしいのかも…。

https://twitter.com/TadaoYamaoka/status/1290613879475560448

dlshogiに解けない問題があるのは、置換表サイズの問題だけであるのか否か…。

qhapaq-49 commented 4 years ago

https://github.com/yaneurao/YaneuraOu/pull/118 にて barcodehair様 が提案してくれた局面については詰み筋が出るようになりました。ただし「攻め側が手数を最短にするように最善を尽くさないことに起因して、本来早詰めの変化が想定解よりも長い詰み手数になる」問題は解決していません。

次のタスク案

dlshogiに解けない問題があるのは、置換表サイズの問題だけであるのか否か…。 少なくとも、今回修正したbugfixは挟まなければ動かないと見ています。この他にも千日手周りの処理は少し怪しいと思います（何も書いていないのですが、これはこれで受け手側が拒否できない千日手とかでおかしなことが起こりうる）。劣等局面の応用は素晴らしいので、参考にする価値は大いにありますが。

barcodehair commented 4 years ago

新しいバージョンで確認してみました。残念ながら課題は多そうです。 今までに発見した問題を報告しておきます。まだ本気は出していないのですがw

(1) 詰みがあるのに不詰を返す 今回のバージョンでも詰まない問題です。本当は詰むのに「詰みません」と言われます。 sfen 3l5/2b1+P2g1/2p1+R2l1/6kn1/2nN3p1/4Sg+n2/5S1Gb/4Pr3/9 b SPgs2l13p 1 出典：http://sleepingfrog.air-nifty.com/diary/2005/05/post_7bc5.html

(2) マスターブランチのバイナリでは詰むのに今回のバージョンで詰まなくなった問題 次の問題は、masterブランチでは詰みますが、今回のものでは詰みません。 不詰の解答にはなりませんが、ノード数が増えてもハッシュの使用率が途中から全く増えなくなって終了する気配がないので動作が怪しいと思います。 sfen 9/9/5PLpk/6G2/6S+pl/9/9/9/9 b 2R2P2b3g3s4n2l13p 1 SOTA先生の色紙の詰将棋（53手詰） 出典：https://book.mynavi.jp/shogi/detail/id=114072

(3) 正解より短い手数の解答を出す問題 正解より短い手数を解答する場合があります。前回報告したものは sfen 4+P+P+P+P1/+P1+P5+P/7kP/PP5pp/1+P2+P1pP1/6+P1+P/9/9/9 b 2r2b4g4s4n4l 1 http://www.ne.jp/asahi/tetsu/toybox/challenge/c1020.htm 71手詰なのに15手の解答を返します。最後に1手で詰む方に逃げます。

次のものも同じような結果でした。 sfen 2pnb2lR/1P2s1p2/Sn1+P1+Ps1p/2l6/lp1P1k3/pN1p+p+plNG/2P+r5/1G7/2+p2+b3 b 2GS4p 1 将棋妙案 第69番 金知恵の輪 http://park6.wakwak.com/~k-oohasi/shougi/html/myouan/myouan07.html 最後に1手で詰む方に逃げる手順を解答します。

qhapaq-49 commented 4 years ago

（おお、sota先生という文言が使われとる、嬉しい......） ありがとうございます。引き続き検討します。

本来の詰手数よりも長い詰み筋を提案する場合はともかく、短い手数を提案する場合は間違っているというのは真なので、今回提案していただいた局面は全て現状のルーチンのバグと言えると思います。

課題は（先人が課題を解決したと論文中で言い張ってるのを疑いたくなるレベルで）多いですが、今後ともアドバイスいただけると嬉しいです。少なくともクレジット的には各種論文より上に来てもいいと思えるレベルの貢献です。本当にありがとうございます。

yaneurao commented 4 years ago

barcodehair様が何者かは存じませんが、凄い活躍ですねｗ

qhapaq-49 commented 4 years ago

現在投稿中のプルリクでは幾つかの問題について改善がされていると思います。というか、前のプルリクが致命的にバグっていました、あまりテストせずに出して申し訳ないです（汗

https://github.com/yaneurao/YaneuraOu/pull/120 現状マージはされていないので、試すには自前でビルドする必要があります。

(2) の回答

R*1a P*1b P*1d 1c1d 1a1b+ G*1c 1b1c 1d1c 3d2c 1c2c G*3d 2c2b R*4b P*3b 4b3b 2b2a 3b3a+ 2a1b P*1c 1b1c 3a1a P*1b P*1d 1c1d 1a1b R*1c 1b1c 1d1c P*1d 1c1b 1d1c 1b1c P*1d 1c2b P*2c 2b1a R*3a B*2a 3a2a 1a2a B*3b 2a1a 2c2b+ 1a2b 1d1c+ 2b1a 1c1b 1a1b 3d2c 1b1a 3b2a+ 1a2a 3c3b+ 2a1a 2c2b

(3) の回答

2a2b 2c3c 3a3b 3c4c 4a4b 4c5c 5a5b 5c6c 5b6b 6c5c 4b5b 5c4c 3b4b 4c3c 2b3b 3c2c 2e2d 2c2d 3f2e 2d2c 3b2b 2c3c 4b3b 3c4c 5b4b 4c5c 6b5b 5c6c 7b6b 6c7c 8d8c+ 7c8c 9d9c+ 8c7c 6b7b 7c7b 9b8b 7b7c 9c8c 7c6c 5b6b 6c6b 8b7b 6b6c 8c7c 6c5c 4b5b 5c5b 7b6b 5b5c 7c6c 5c4c 3b4b 4c4b 6b5b 4b4c 6c5c 4c3c 2b3b 3c3b 5b4b 3b3c 4b4c 3c2c 2e3d 2c3d 5e4d 3d2c 4c3c 2c2d 3c3d

1と4については今回のプルリクでは不詰とでてきてしまいます。１は長時間の探索になっているのでハッシュをうっかり上書きしたなどの可能性がまだありえますが、４は超短時間で不詰を返してるのでどこかバグってます。

（barcodehair様が実は先行研究の論文の著者で本実装が終わったあたりで「この詰将棋はわしが育てた」とかいい出したら私の心は多分千日手をひいてクラッシュします。

qhapaq-49 commented 4 years ago

あれ、githubにあがってるコードと手元の実験結果が一致しない。アーキテクチャ依存のバグをひいてるかも。ちょっとベンチコマンド先に作ったほうがいいですねこれ。

yaneurao commented 4 years ago

とりま、プルリク、マージはしときましたので、引き続き調査してくだされ…。> Qhapaqさん

qhapaq-49 commented 4 years ago

（白目）

qhapaq-49 commented 4 years ago

とりあえず次はベンチコマンドを作って、過去の作品で何が解けて何が解けてないのかを確認する所に戻るべきな気がしてきました。詰将棋の実装、途中で嫌になって逃げても化けてでてこないでくだしあ

yaneurao commented 4 years ago

アーキテクチャ依存のバグ

現状のコード、依存しているところが思いつかないので、未初期化のメモリアクセスか(Hashはゼロ初期化しているのであればこれは考えにくい)、Hashサイズの違いの二択かと…。

qhapaq-49 commented 4 years ago

アドバイスありがとうございます。

sota先生の詰将棋が解けない問題、最新のやねうら王のmasterをマージしたことで発生しているみたいです。

こちらのブランチで言えば masterをマージする前のコミットである https://github.com/qhapaq-49/YaneuraOu/commit/7ed0b90cd91b8ce9bfab300af455a3b42e2265d0

では解けてるのに masterをマージした後(mate-engine.cppは特に変更されてない？) https://github.com/qhapaq-49/YaneuraOu/commit/562aed7be47fcfe6811f59aaf6759c8b6bb35a9c では解けなくなってます。

最新のやねうら王のコミットを受け入れたことによる差分は https://github.com/qhapaq-49/YaneuraOu/commit/562aed7be47fcfe6811f59aaf6759c8b6bb35a9c に記載されているのですが、これで詰将棋エンジンの挙動が変わるってのが私にはよく解りません。何か心当たりがあったりしませんか？

qhapaq-49 commented 4 years ago

より厳密に実験環境を記載すると、

yaneurao commented 4 years ago

これで詰将棋エンジンの挙動が変わるってのが私にはよく解りません。何か心当たりがあったりしませんか？

Magic Bitboardによる利きは以前のものと等価なのでそこは関係ないですね。benchコマンドでのnode数も変化ないですし。 やはり、未初期化メモリの挙動が疑わしい気がします。

yaneurao commented 4 years ago

Qhapaqさん、本件、どんな感じでしょう？

詰将棋うまく解けるバージョンのソースコード一式と、解けなくなったソースコード一式、そして問題局面の3つをセットにしてメールか何かでいただければ私のほうで調査してみますよ(｀･ω･´)ｂ

yaneurao commented 3 years ago

やねうら王の新しい詰将棋ルーチンで何でも解けるようになったのでこのissueはcloseしますです。