2011/02/26
■ 探索延長の制限(その2)
次の1手問題で、バランスを見ながら調整。PVノードで、
Iterationより6手深いときは1手延長を1/2手延長にする Iterationより10手深いときは延長なし
非PVノードで、
Iterationより4手深いときは1手延長を1/2手延長にする Iterationより8手深いときは延長なし
2011/02/09
■ 探索延長の制限
探索延長の制限をしないと、終盤の王手が多くかかる局面で、Iterationより10手も15手も深読みをしてしまい(しかもその先には静止探索もある)、Iterationが進まない。Iterationが進まないと探索打ち切り判定ができない...下記の探索時間管理の設計が進まないというジレンマ状態に陥ってしまった。CraftyもFruitもGlaurungも探索延長の制限などしていない。そもそもチェスでは王手応手が狭いのだ。というわけで、
Iterationより6手深いときは延長半分 Iterationより10手深いときは延長なし
を実装して様子をみよう。PVノード、非PVノード、進行度で違いを出すのも面白い。ちなみにbonanza_felizでは、shogi.hの中のLimitExtensionマクロで、
Iterationより2倍深いとき、 Iterationより4倍未満の深さなら、延長減 それより深いなら延長なし
と、なっている。bonanzaは1/8単位で手の延長をやっているので、細かい延長減をやっている。
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手目を返す
2011/02/03
■ 探索延長
・fruitの1手延長
SingleReply PVノードでSEEが正の同〜と取る手 PAWNが7段目 王手 静止探索内で王手
・graulungの延長
王手
SingleReply
Recapture(駒交換)
PAWNが7段目
null moveで負けを返したとき
if(pos.midgame_value_of_piece_on(move_to(m)) >= RookValueMidgame
&& (pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
- pos.midgame_value_of_piece_on(move_to(m)) == Value(0))
&& !move_promotion(m)) これはなんだ
...1手延長
PVノードでPAWN以上の駒を取ってSEEが負で無いとき半手延長
・craftyの1手延長
SEEが負で、王手をかけられたとき。 かってcraftyは1/60手単位で探索延長をやっていたが、今はこのようなシンプルなものになっている。
王手で１手延長は応手が限られるので、それほど計算量が増えないので順当。
とりあえずsingle reply、recaptureで半手延長を実装する。
single replyは１手延長が良いかも。非PVノードでのrecapture半手延長は要検討。
