オーダリング

simkの飼い主のsuzume_rさんがsuzumer.web.fc2.com/simk.htmにて「オーダリングはかなり強力なようで、ここを良くすると格段に深く読めるようになった。しかし、先の教科書にはあまりオーダリングの重要性に触れられていない模様。SEEで並び変えるだけでもかなり違う」と書かれていた。

100Knps読めるプログラムを16秒走らせて160万局面を読ませたときに、局面あたりの平均読み手数によって、どれぐらい読める深さが違うかを計算してみた。
(floodgateで110手ぐらいで終わるとすると16秒ぐらい使えるかな、と)。

4手比は、同じ深さを分岐手数4のプログラムで達成する場合に必要な探索速度の向上率。

手数	深さ	4手比
3.0	13.00	42.13
3.1	12.63	24.98
3.2	12.28	15.49
3.3	11.97	9.99
3.4	11.67	6.66
3.5	11.40	4.58
3.6	11.15	3.23
3.7	10.92	2.34
3.8	10.70	1.73
3.9	10.50	1.30
4.0	10.30	1.00

分岐手数4のプログラムを30%高速化するのと、分岐数を0.1減らすのが同じぐらいの効果。高速化するのも大事だけど、オーダリングの方が重要なのだな。futility cutなどで枝をばっさり削っても読める深さがあまり変わらないのも納得がいく。もっとも、0.1減らすのはかなり大変そうだけど。特に終盤は。

いまの sakurapyon は終盤は100Kbpsどころか桁違いに遅いので、そこもなんとかせんといかんのだよなあ。