なのは詰(アピール文章)

アピール文章というよりアピールプログラムかもしれませんが、なのはの詰ルーチンのバイナリを公開します。
(ソースは恥ずかしいので非公開)
ダウンロード(zip; 233KB)

こんな問題も解けないのかよ、とか指摘いただけると幸いです(短いほうがうれしい)。

なのはの詰ルーチン(アピール文章)

なのはの詰ルーチンは証明数と反証数を使用した WPNS を基本にし、
・優越関係
・最小距離法
・証明駒、反証駒
を実装している。実戦では必要ないだろうとの判断で探索中のハッシュのクリアは行っていない。
また、なるべく歩角飛の不成を読まないようにして、かつ打ち歩詰めが絡む局面で詰みを発見できるように以下のようにしている。
(1) 王手生成では歩角飛の不成も含めて全ての王手を生成する。
(2) 証明数・反証数の計算のときに、打ち歩詰めが絡まないときは歩角飛の不成を無視する。
(3) 証明数・反証数の計算のときに、打ち歩詰めが絡むときは歩角飛の不成も含めて計算する。
したがって、不成を生成しないプログラムが詰みを発見できない以下の局面でも詰みを発見する。



現在は歩角飛の成りによる打ち歩詰めかどうかに関係なく探索中に打ち歩詰めが発生したときは打ち歩詰めが絡むと判断しているため、非効率になっている場合がある。

今週のバグ

単に昔のプログラムから新しいプログラムに持ってきて少し変更しただけなのになんでこんなにバグが出るかなぁ～

1. 王手の重複生成
王手の生成順を旧では「駒を打つ手」⇒「駒を動かす手」としていたのを、新では「駒を動かす手」⇒「駒を打つ手」の順に変更しています。
で、重複する王手を削除する処理を少し変更したら、削除できていませんでした…。

ということで、生成する手を間違っているわけではないので直接的な不具合はないのですが、王手を余分に計上するため重複する手が生成される局面で反証数を多めに見積もってしまうことになります。

このことが影響を与えるかというと・・・直したプログラムでは問題によってノードが増えたり減ったりするのでよくわからない、ということになりました。
ひょっとしたら不詰の証明が遅くなるかも?(未確認)

2. df-pnの最小距離法の異常な節点の更新
異常な子節点を持つ局面の証明数の計算は普通は正しくしている(はず?)ですが、証明されたときに最小距離を更新する処理で局面ハッシュの計算を間違えて最小距離の更新が出来ていなかった。
そのためGHIにより「わからない」という回答が多発した。

これは直すことで、正解が増え効果がありました。

これらを直しても、旧で解けていた問題が新で解けなかったりするので、まだ別のバグを仕込んでしまっているかも??

来月くらいには Bonanza の fv.bin を組み込んで、nabona で floodgate に参加するかも？！
「ナボナはお菓子のホームラン王です！」とかｗ ← ふるっ！

※ナボナは Navona と書くらしいので、間違ってますｗｗｗ

df-pn起動

df-pnの詰ルーチンが動いてきました。ときどき間違った答を返すので、移植するときにバグを仕込んだと思われます…。

今回も対象は「羽生の将棋 実戦[詰め＆必死]200」の最初の10問。
これらの回答はとりあえず正解でした。df-pnは反復深化詰ルーチンに比べてノード数が少ない領域でのオーバーヘッドが多いですね～。
とりあえず、黄色地は反復深化より性能が低下しているところです。

	新 なのは(反復深化)		新 なのは(df-pn)
	時間(s)	ノード数	時間(s)	ノード数
第1問	0.005	4,137	0.051	230
第2問	0.001	700	0.056	637
第3問	0.003	2,539	0.061	1,983
第4問	8.978	7,780,882	0.166	32,012
第5問	0.006	6,477	0.207	43,350
第6問	0.371	368,785	0.091	11,927
第7問	1.095	1,097,943	0.061	3,335
第8問	0.325	338,387	0.062	2,161
第9問	178.604	160,426,279	0.485	98,322
第10問	3.229	2,671,302	0.057	1,749

新たなる力、起動なの！

ようやく新なのはで反復深化の詰ルーチンが動いてきました。
起動というよりようやく始動という気がしないでもないｗ

ピンを考慮した打ち歩詰め判断がないとか機能的に欠けている部分やバグの関係でまだちゃんと動いてなさそうな気がしているのですが、それなりに動いているので結果を。

対象は「羽生の将棋 実戦[詰め＆必死]200」の最初の10問。
回答はとりあえず正解ですが、従来のなのはの反復深化詰ルーチンに比べて劣化(黄色地)が見られます…。
※df-pnは参考値。100msでループしてるので結果が少し変ですが。

今気づいたけど、王手の生成を従来は「打つ手」⇒「盤上の駒を動かす手」をしていたのを新では「盤上の駒を動かす手」⇒「打つ手」の順に変更したからか?
証明駒を考慮すると新の生成順のほうがいいらしいが、反復深化は証明駒を使っていないので意味なしですね。

	旧 なのは(df-pn)		旧 なのは(反復深化)		新 なのは(反復深化)
	時間(s)	ノード数	時間(s)	ノード数	時間(s)	ノード数
第1問	0.101	252	0.006	2,885	0.005	4,137
第2問	0.101	732	0.001	166	0.001	700
第3問	0.101	1,582	0.009	5,458	0.003	2,539
第4問	0.202	33,577	2.209	1,458,396	8.978	7,780,882
第5問	0.402	69,115	0.010	6,587	0.006	6,477
第6問	0.101	11,105	0.682	471,854	0.371	368,785
第7問	0.101	2,703	1.086	731,204	1.095	1,097,943
第8問	0.101	2,140	0.608	448,992	0.325	338,387
第9問	0.705	105,382	64.840	41,601,448	178.604	160,426,279
第10問	0.101	1,946	1.920	1,170,853	3.229	2,671,302

※Athlon64X2 4600+(2.4GHz)、WindowsXP(32bit)

やねうら王の詰ルーチンには時間で2桁以上負けそうな気がする…。