置換表から取り出してきた指し手がpseudo legal(指し手生成ルーチンが生成する指し手と同じレベルの仮の合法手)であるかを判定するの、マジで難しい。

やねうら王nano plusで長らく24時間に一度ぐらい落ちるバグがあって、各PCにVisual Studioをインストールして、トータル26コアで8時間ほど回したところようやく落ちたのでデバッガで見たところ、原因自体は5分でわかった。

非合法手のcounter moveがpseudo legalの判定をすり抜けていたのだ。

counter moveも置換表に登録されている指し手と同様、pseudo legalの判定をするので結局、pseudo legalの判定がおかしい。

具体的に書くとこうだ。(以下の例では「置換表」と書くが、counter moveでも同様である。)

後手が58の銀を59に移動させて、これが置換表に登録されたあと、58に歩がある局面でhash衝突するとこれが59歩不成という指し手に見えてpseudo legalの判定でこれをチェックしないと59に後手の歩が移動できてしまうのだ。(ちなみにこのあと59の歩の利きはpawnEffect[SQ_59]が0相当なので利きがないように見えるのだが、指し手生成でこの59の歩を一つ前に進める指し手は生成され、縦型Bitboardではこの歩は61に進める。そこで利きがないと思って61に来た玉を59の歩が捕獲できることになり、玉を捕獲する指し手としてassertに引っかかったという仕組みだ。)

counter moveの指し手や置換表の指し手として移動させる駒種も登録しておけば、pseudo legalの判定では、盤上のfromにある駒とその駒種が異なるなら非合法手と判定することも出来るのだが、置換表に移動させる駒を保存すると置換表のエントリーがもったいない。(置換表のエントリーはギリギリなのだ…)

counter moveのほうも、移動させる駒種を持とうとすると16bitで済んでいたものが32bit必要になって、テーブルサイズが2倍になる。結構大きめのテーブルなので、こんなところ2倍になられては(たぶん)困る。

そんなわけで結論的にはpseudo legalの判定では、不成での移動に関して、歩や香は、そこがいける升であることを判定しないといけないように思う。

Aperyどうやってるのかなと思って、Aperyのソースコードをちらっと見たら、Aperyはこの判定をやってなさそう。たぶんAperyのバグ。平岡さんにメールで確認中。

あとcounter moveの指し手をオーダリングに使うようにしていて気づいたのだが、58の龍を57に移動させる指し手がcounter moveとして登録されているときに、58に飛車が来ると、57飛不成という指し手がcounter moveに見えてしまう。こんな指し手が生成されてはまずいので、通常探索中のpseudo legalのチェックにおいては、この57飛不成を排除すべきである。

そう考えるとやはりcounter move、移動させる駒の駒種も持つべきなのかも知れないが…。

ちなみに置換表から取ってきた指し手についても同様ではあるが、置換表がhash衝突するのは極めて低い確率なのでcounter moveほど顕在化しない。Aperyはcounter moveがないようで、今回の問題は置換表をprobeするときにhash衝突しているときにしか顕在化しなくて、滅多に生じなかったために長年バグが誰にも発見されなかったのだと思う。

ともかく、pseudo legalの判定は(きちんと網羅するのは)すこぶる難しいということですな。

追記(2016/02/28 17:20)

平岡さんからメールの返信があったのでぺたぺた。GitHubのものはともかく、開発版のAperyのほうでは修正済みの問題のようです。

ご報告ありがとうございます。
https://twitter.com/HiraokaTakuya/status/699983959933882368
このとき気付いて、ついでに行きどころのない駒が合法手判定されるのも直しま
した。
ただ、公開しているAperyは置換表のエントリーに格納するhash keyに32bitつ
かっているので、
実用上バグることはほぼないです。普通に使って頂いている方々からのバグ報告
もなかったです。
http://woodyring.blog.so-net.ne.jp/2016-02-21-1
ここでも触れられていますね。

とりあえず選手権終われば一気にpushいたします。