詰め将棋の改良

コーディングの工夫で、わりと探索は早いと思うのですが
（1秒に300万手以上探索可能）
長手数の探索は限界があるようです。

謎電が約70秒かけて解いた日本チェスプロブレム協会のチャンピオン戦のひとつの
37手詰めの問題が解けません。

9番:37手詰 69.100秒 ５七金 127,707,259
http://ameblo.jp/professionalhearts/entry-10011162980.html
http://www.wombat.zaq.ne.jp/propara/solving/SS2006-5.htm

普通に探索してても20手ぐらいで進まなくなります。
そこで、王の可能な逃げられる手数の数を証明数として、
多い場合はあまり有効な手ではないので、探索を短縮、
逆に、逃げ場が少ない手は有効なので探索を延長する手法を使うと
（なんとなく共謀数？）
28手ぐらいまでは読みますが、それでもそのへんが限界のようです。

謎電あたりの高速なソフトだと、PN-DNをやってるんでしょうねえ。
PNはまだしもDNが難しいんですよねえ……
まあ、実戦で30手オーバーが詰められる必要は無いので、
15手ぐらいが高速に詰められれば良しとします……。今後の課題ということで。
「成って詰まないなら、成らない手も詰まないので指さない」とか柿木さんのアルゴリズムもあるのですが、それをやっても10%ぐらいしか高速にはならないという記事も本にあったので。
転置表にしても詰め将棋では有効だけど、平手の通常の探索は実はほとんど速くならないようですね。
これは実際に試してみるべきですが、詰め将棋は局所性があるから、重複する手が多くハッシュが合致するけれど、通常探索はそうでもないらしく。でも、反復進化で、前回の最善手を覚えておく意味では使えると思いますが。

持ち駒

 ９ ８ ７ ６ ５ ４ ３ ２ １ 　 ９８７６５４３２１

−-------------------------+　 ------------------+

 ・ ・ ・ ・ と ・v歩 ・ ・|一 　　　■■■■■■|一

 ・ ・ ・ ・ ・ ・ 歩 歩 と|二 　　　　■■★■★|二

 ・ ・ ・ ・ ・ ・ と ・ ・|三 　　　■■■□　■|三

 ・ ・ ・ ・ 龍 ・ ・v金 ・|四 ■■■■■　■■　|四

 ・ ・ 金 銀 ・ ・ ・ ・ ・|五 　■★■　■□　□|五

 ・ ・ ・v杏v桂 ・ ・ ・ ・|六 ■■　□■■■　　|六

 銀 ・ ・v玉 ・ 金 桂 ・ ・|七 ★■□□■■■　　|七

 ・ ・ ・ ・ 歩 ・ ・ ・ ・|八 □　　□■　　　　|八

v馬 ・ ・ 馬 ・ ・ ・ ・ ・|九 ☆□■★■　　　　|九

−-------------------------+　 ------------------+

持ち駒 桂

value=-4390 eval=-4220 悪形チェック=0
hash clear.

戦形=3
01歩 02香 03桂 04銀 05金 06角 07飛

# b5:可能手 b8:取る手 b3:次の一手 b4:１局 b6:詰将棋 b9:必至 b7:連続

b6

#10=0

#12=0

#14=0

#16=0

#18=0

#20=0

#22=0

#24=0

#26=0

#28=0