2011/02/04
■ 探索時間管理の設計
深く読めるようになると探索時間管理が必須だが、このテーマは情報が少ない。コンピューター将棋の進歩5のYSSの改良点が詳しいぐらいか。
簡単なのは、ある時間が経過したら、次のIterationを実行しないというもの。さすがにそれでは荒っぽい。
ほとんどは探索中に時間を計算して打ち切り判定をするタイプ(GNU Shogi,Craftyなど)と、別スレッドで時間をポーリングして、探索打ち切りフラグを立てるタイプ(glaurung)であろう。探索の末端で時間計算ルーチンを呼ぶのは重いような気がするのと、将来、並列探索にしたときの見通しのよさで、別スレッドポーリング方式とする。
選手権は切れ負けルールなので、時間配分の調整も必要だ。深く読む/読まないを判断しないといけない。
・(参考)glaurungの探索打ち切り条件 (search.cpp)
・Iteration 内の判定
Iteration >= 6 で合法手が1手しかない
Iteration >= 6 でスコアがIteration連続で詰みに達したとき
Iteration >= 8 で最善手がEasyMoveで探索ノード数が全ノードの85%で探索時間が1手時間の1/16か,探索ノード数が全ノードの98%で探索時間が1手時間の1/32
Iteration >= 5 でExtraSearchTimeの計算をして、
ExtraSearchTime=BestMoveChangesByIteration[Iteration]*(MaxSearchTime/2) +BestMoveChangesByIteration[Iteration-1]*(MaxSearchTime/3);
探索時間が ((MaxSearchTime+ExtraSearchTime)*80)/128 =(MaxSearchTime+ExtraSearchTime)の62.5%以上なら
BestMoveChangesByIterationは最善手が変化した履歴
・poll() ポーリングルーチン
Iteration >= 2 で
( t > AbsoluteMaxSearchTime
|| (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime)
|| (!FailHigh && !fail_high_ply_1() && !Problem && t > 6*(MaxSearchTime + ExtraSearchTime)))))
AbortSearch = true;
MaxSearchTimeは持ち時間の1/40=1手当たりの持ち時間
AbsoluteMaxSearchTimeは持ち時間の1/8
EasyMoveの判定
2手目以降にEasyMoveMargin以上の手が無ければ1手目を返す
