next.cについて保木さんとのメール

今回は、探索に深く関係すると思われる、指し手オーダリング(next.c)について保木さんと私がメールでやりとりした内容のうち、他の開発者の役に立ちそうな部分を保木さんの許可を得て、いくつか抜き出して紹介します。

私から保木さんへの質問。

if ( sortv > value_best )
{
// bestと、secondの指し手を格納。
move_second = move_best;
value_second = value_best;
value_best = sortv;
move_best = move;
}
else if ( sortv > value_second )
// 2番目のスコアの更新。
{
move_second = move;
value_second = sortv;
}

この比較の仕方は無駄で、sortvはvalue_secondとの比較を先にすべきです。
value_secondを超えなければvalue_bestを超えないことは確定するので
value_secondを超えない限りは比較回数は1回で済みます。

ところで、↑のようにすれば、上位5つぐらいならば、それほど
追加の計算コストなしに抽出できるのですが、それは探索結果には
あまり関係しないのでしょうか？(私のほうは指し手生成の高速化に
励んでいる状態でして、まだ探索関係の実験はほとんどしていないので
よくわかりません。)

保木さんから私への返信。

> value_secondを超えない限りは比較回数は1回で済みます。

確かにその通りですね。value_second を超えないケースの方が多そうです。

> ところで、↑のようにすれば、上位5つぐらいならば、それほど
> 追加の計算コストなしに抽出できるのですが、それは探索結果には
> あまり関係しないのでしょうか？(私のほうは指し手生成の高速化に
> 励んでいる状態でして、まだ探索関係の実験はほとんどしていないので
> よくわかりません。)

もしかすると強くなるかもしれませんね。最適な数は私も良く分からないのです。
この best と second の指し手は探索の延長 (recapture) に使用するのですが、
最近はあまりこれをしなくても良いかなという気がしています。

私から保木さんへの質問。

history変数ですが、これはHistoryHeuristics(?)なのだと理解していますが、
next_move_captureの末尾で生成された指し手のなかでhistoryのなかから
最大の手を選ぶコードがあり、next_move_history2のところでも同じ処理があります。

ここが、数%のCPU時間を消費しているのですが、next_move_history2は、
next_move_captureのときに2番目の指し手も求めておけば1度の指し手の
スキャンで済むと思います。

ただ、探索中にhistoryが書き換えらる影響は受けると思うのですが、
探索残り深さがそんなにないような状況では、更新される可能性が低いはずで
もし何でしたら残り探索深さが少ないときだけでも
next_move_captureのときに2番目の手も同時に求めて、それを使い回せば
いいように思うのですが、そうしない理由が何かあるのでしょうか？

保木さんからの返信。

> もし何でしたら残り探索深さが少ないときだけでも
> next_move_captureのときに2番目の手も同時に求めて、それを使い回せば
> いいように思うのですが、そうしない理由が何かあるのでしょうか？

そうですね、探索の末端付近ではそうした方が良いかもしれません。
ただ、探索の末端かどうかは、depth extension や reduction があるので判定
が難しいです。