2013/12/14
■ Stockfishの探索
PV search
ハッシュを見る スコアが使えるなら使う(真値のみ) ハッシュの手があり,王手がかかっていないなら現局面の評価値を求め,ハッシュに登録する...(1) Internal iterative deepening 手生成 for 手の数 Singular extension 手で局面更新 LMR判定...(2) 探索 局面戻す betaカット判定 ハッシュ登録
非PV search
ハッシュを見る スコアが使えるなら使う
ハッシュの手があり,王手がかかっていないなら現局面の評価値を求め,ハッシュに登録する
Razoring
Reverse Futility Pruning
Null move search
if (nullValue >= beta)
再探索してbetaを上回るならその値を返す
ProbCut
Internal iterative deepening
手生成
for 手の数
Singular extension
枝刈...(3)
Move count based pruning...(4)
Futility Pruning...(5)
残り深さが少なくSEEが負なら刈る
手で局面更新
LMR判定
探索
局面戻す
betaカット判定
ハッシュ登録
qsearch
ハッシュを見る スコアが使えるなら使う
ハッシュの手があり,王手がかかっていないなら現局面の評価値を求め,ハッシュに登録する
Stand pat Return
手生成
for 手の数
Futility Pruning
futilityBase+取った駒の価値 < beta なら刈る
futilityBase < beta かつ SEEが負なら刈る
王手を受けていない または 王手を受けていて駒を取らない手 ハッシュの手でなく SEE負なら枝刈
手で局面更新
qsearch
局面戻す
betaカット判定
ハッシュ登録
(1)ハッシュの手があるということはすでに探索済なのでこれはうまい工夫
(2)残り深さ,PV/非PV,improving,オーダリング順位で縮退する深さを変えている.improvingは3手前の局面より評価値が上がっている状態.
(3)王手がかかっている局面,重大な手,成る手取る手,threatMove,refutesは刈らない.
重大な手...王手,次にPAWNが成る手,キャスリング
threatMove...1手先のcurrentMoveがある...Null move searchで相手に有効な手があった
refutes...刈ってはならない手の判定.threatMoveですぐ取られる手.threatMoveで駒損.自分が動いた後に相手の駒が来る.利き変化.影利き変化.safe moves which block the threat path.
(4)残り深さ,PV/非PV,improving,オーダリング順で刈る数を変えている.
(5)残り深さでマージンを変えている.
