もともと[*1]YSSの山下さんがコンピュータ将棋や囲碁の掲示板(04/02/17)で紹介されていた "Null-Move Forward Pruning" が事の起こりだ。そのページで示されているコードは、あくまで説明用のコードで、そのまま実装するとトンでもない目に遭うのだが[*2]それはともかく、更に追加の参考資料として、"Adaptive null move pruning" を挙げられており、この中の次の記述が巧いアイデアだと思ったことに始まる。
これを要約すると、「Null move pruning を行うノードからみて、それなりに深く読むのなら (depth が大きいのなら、それに合わせて) R が通常より少し大きくても、さほど問題を起こさずに探索効率を上げられる」という意味もあり、このまま指将棋の探索に適用するのは拙いとしても、巧く工夫すれば少なからず効率の向上を見込めるのではないか、と直感的に思ったわけだ。謎電では、とりあえず、
-- #define Radpt ( ( depth + N ) / D ) --
として、N,D の値を手動で調整し、謎電の探索アルゴリズムに合わせ込んで最適と思われる値にしている。これらの最適値を見つけ出すだけで、軽く１ランクはスピードグレイドの高いCPUを手に入れるのと同じくらいの効果がある[*3]。
現時点では実験的な実装にしかなってないのだが、このアイデアだけを追求しても相当面白いのではないかと思っている[*4]。少なくとも、PVS[*5] や MTD(f)よりも効果は大きいし、また、これは鶴岡法[*6]に対してもアイデア自体は流用できる。
[*1] Adaptive null move pruning の独断的和訳。
[*2] このコードを鵜呑みにすると、半無限再帰ループに陥ったり、効率が上がるどころか劇的に落ちたりするので、よく咀嚼してアイデアのみを活かせるように自分のプログラムに合わせて実装する必要がある。
[*3] 書くまでもないことだが、なるべくDの定数値は2nの値にした方がよい。その方が微妙に最適化が効く(コンパイラが算術右シフト命令に置き換えるので)。もし、どうしても精密な値で調整を行いたい場合は、( ( ( depth + N ) * M ) >> S ) とし、M,Sの定数値を含めて調整する方法を採った方がよい。
[*4] 簡単に言えば、Radpt の値は、局面状態(別の言葉を使えば進行度)によって微妙に最適値が異なると思われる。つまりは "Dynamic & Adaptive null move pruning" とでも呼べるような手法が考えられるわけだ。
[*5] 何故か謎電ではPVSの効果が小さい上に、閾値が同じであっても結果（探索値・最善手を含めて)が異なることが起きる。実装に問題があったのかもしれないが、そういう理由で現時点ではPVSを外している。
[*6] 「実現確率打ち切りによる探索アルゴリズム」とか「実現確率を閾値とした反復深化探索アルゴリズム」では文言として長いので、今後考案者に敬意を表して「鶴岡法」と呼ぶことにする。余談だが、鶴岡法は巧くアレンジすればTSPにも適用できる気がする。
(追補) 本稿で、やっと100個目となりました(ランキングチェックを除いて)。