詰み探索のMovePickerには最大合法手分の配列を確保していたが、王手生成に限れば最大合法手分よりもサイズを減らすことができる。
そこで、スタックサイズを節約するため、配列のサイズを王手生成の最大数に合わせることにした。
合法手の最大数
合法手の最大数は、以下のページで593であることが証明されている。
http://www.nara-wu.ac.jp/math/personal/shinoda/bunki.html
王手生成の最大数
王手生成の最大数は、上記のページのような証明が考え付かなかったので、自分で最大ではないかという局面を作成した。
sfen 9/R1S1k1S1R/2+P3G2/2G3G2/9/B1NL1LN1B/9/4K4/4L4 b G2S2NL17P 1
この局面で王手の数は65になる。
もしかしたら、これ以上の局面があるかもしれない。
見つけた方がいたら教えてもらえると助かります。
こんな局面になる前に詰んでいるので65あれば大丈夫だとは思いますが。
バグ修正
自作の王手生成ルーチンを使用して王手の数をカウントしていたところ、またしてもバグを見つけた。
王手生成ルーチンは、やねうら王のコードを元にしていたが、やねうら王で、
(pos.pieces(GOLDS) & check_candidate_bb(Us, GOLD , themKing))
となっていたところを、Aperyをベースに作成したコードで、誤って、
(pos.bbOf(Gold) & goldCheckTable(US, ksq)) |
としていた。
やねうら王の、GOLDSは、と金なども含むので、と金などの手が生成されていなかった。
Aperyでは、
(pos.bbOf(Gold, ProPawn, ProLance, ProKnight, ProSilver) & goldCheckTable(US, ksq))
とする必要があった。
追記
さっそくTwitterで65以上の局面を教えていただきました。
sfen 5S1S1/RS5k1/5G3/9/5NL1L/9/9/1K7/B8 b RB3GS3N2L18P 1
これで、67手です。
さらに、
sfen B7B/1R7/6R2/9/4k4/9/9/9/K1N6 b 4G4S3N4L18P 1
飛車で開き王手して、飛車が成らない場合と成る場合がある方が多くなります。
ただし、私の王手生成では実戦の速度重視で打ち歩詰めの考慮をしていないので、飛車は必ず成るようにしており、上の67手が最大になりそうです。
追記その2
さらに、情報をいただきました。
不成りも含めると、
91が最大になりそうです。
大駒の不成りを除く条件では、
4S4/R1S3k1S/4+P3+P/9/8N/4N3N/1L7/B8/5L1LK b RB4GSNL16P 1
74になりそうです。
(私の王手生成では香車の2段目不成も除いたので73になりました。)
教えていただきありがとうございました!