if (depth < OnePly)
return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
- // Initialize, and make an early exit in case of an aborted search,
- // an instant draw, maximum ply reached, etc.
+ // Step 1. Initialize node and poll
+ // Polling can abort search.
init_node(ss, ply, threadID);
- // After init_node() that calls poll()
+ // Step 2. Check for aborted search and immediate draw
if (AbortSearch || TM.thread_should_stop(threadID))
return Value(0);
if (pos.is_draw() || ply >= PLY_MAX - 1)
return VALUE_DRAW;
- // Mate distance pruning
+ // Step 3. Mate distance pruning
oldAlpha = alpha;
alpha = Max(value_mated_in(ply), alpha);
beta = Min(value_mate_in(ply+1), beta);
if (alpha >= beta)
return alpha;
- // Transposition table lookup. At PV nodes, we don't use the TT for
- // pruning, but only for move ordering. This is to avoid problems in
- // the following areas:
+ // Step 4. Transposition table lookup
+ // At PV nodes, we don't use the TT for pruning, but only for move ordering.
+ // This is to avoid problems in the following areas:
//
// * Repetition draw detection
// * Fifty move rule detection
// * Searching for a mate
// * Printing of full PV line
- //
tte = TT.retrieve(pos.get_key());
ttMove = (tte ? tte->move() : MOVE_NONE);
- // Go with internal iterative deepening if we don't have a TT move
+ // Step 5. Evaluate the position statically
+ // At PV nodes we do this only to update gain statistics
+ isCheck = pos.is_check();
+ if (!isCheck)
+ {
+ EvalInfo ei;
+ ss[ply].eval = evaluate(pos, ei, threadID);
+ update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
+ }
+
+ // Step 6. Razoring (is omitted in PV nodes)
+ // Step 7. Static null move pruning (is omitted in PV nodes)
+ // Step 8. Null move search with verification search (is omitted in PV nodes)
+
+ // Step 9. Internal iterative deepening
if ( UseIIDAtPVNodes
&& depth >= 5*OnePly
&& ttMove == MOVE_NONE)
tte = TT.retrieve(pos.get_key());
}
- isCheck = pos.is_check();
- if (!isCheck)
- {
- // Update gain statistics of the previous move that lead
- // us in this position.
- EvalInfo ei;
- ss[ply].eval = evaluate(pos, ei, threadID);
- update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
- }
+ // Step 10. Loop through moves
+ // Loop through all legal moves until no moves remain or a beta cutoff occurs
- // Initialize a MovePicker object for the current position, and prepare
- // to search all moves
+ // Initialize a MovePicker object for the current position
mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move()));
- CheckInfo ci(pos);
MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
+ CheckInfo ci(pos);
- // Loop through all legal moves until no moves remain or a beta cutoff
- // occurs.
while ( alpha < beta
&& (move = mp.get_next_move()) != MOVE_NONE
&& !TM.thread_should_stop(threadID))
moveIsCheck = pos.move_is_check(move, ci);
captureOrPromotion = pos.move_is_capture_or_promotion(move);
- // Decide the new search depth
+ // Step 11. Decide the new search depth
ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
// Singular extension search. We extend the TT move if its value is much better than
newDepth = depth - OnePly + ext;
- // Update current move
+ // Update current move (this must be done after singular extension search)
movesSearched[moveCount++] = ss[ply].currentMove = move;
- // Make and search the move
+ // Step 12. Futility pruning (is omitted in PV nodes)
+
+ // Step 13. Make the move
pos.do_move(move, st, ci, moveIsCheck);
- if (moveCount == 1) // The first move in list is the PV
+ // Step extra. pv search (only in PV nodes)
+ // The first move in list is the expected PV
+ if (moveCount == 1)
value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
else
{
- // Try to reduce non-pv search depth by one ply if move seems not problematic,
+ // Step 14. Reduced search
// if the move fails high will be re-searched at full depth.
bool doFullDepthSearch = true;
}
}
- if (doFullDepthSearch) // Go with full depth non-pv search
+ // Step 15. Full depth search
+ if (doFullDepthSearch)
{
ss[ply].reduction = Depth(0);
value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
+
+ // Step extra. pv search (only in PV nodes)
if (value > alpha && value < beta)
value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
}
}
+
+ // Step 16. Undo move
pos.undo_move(move);
assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
- // New best move?
+ // Step 17. Check for new best move
if (value > bestValue)
{
bestValue = value;
}
}
- // Split?
+ // Step 18. Check for split
if ( TM.active_threads() > 1
&& bestValue < beta
&& depth >= MinimumSplitDepth
break;
}
- // All legal moves have been searched. A special case: If there were
+ // Step 19. Check for mate and stalemate
+ // All legal moves have been searched and if there were
// no legal moves, it must be mate or stalemate.
if (moveCount == 0)
return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
+ // Step 20. Update tables
// If the search is not aborted, update the transposition table,
// history counters, and killer moves.
if (AbortSearch || TM.thread_should_stop(threadID))
Position pos(*sp->pos);
CheckInfo ci(pos);
SearchStack* ss = sp->sstack[threadID];
+ StateInfo st;
Value value = -VALUE_INFINITE;
Move move;
int moveCount;
bool useFutilityPruning = sp->depth < 7 * OnePly //FIXME: sync with search
&& !isCheck;
- while ( lock_grab_bool(&(sp->lock))
- && sp->bestValue < sp->beta
+ lock_grab(&(sp->lock));
+
+ while ( sp->bestValue < sp->beta
&& !TM.thread_should_stop(threadID)
&& (move = sp->mp->get_next_move()) != MOVE_NONE)
{
if ( moveCount >= futility_move_count(sp->depth)
&& ok_to_prune(pos, move, ss[sp->ply].threatMove)
&& sp->bestValue > value_mated_in(PLY_MAX))
+ {
+ lock_grab(&(sp->lock));
continue;
+ }
// Value based pruning
Value futilityValueScaled = sp->futilityValue - moveCount * 8; //FIXME: sync with search
if (futilityValueScaled < sp->beta)
{
- if (futilityValueScaled > sp->bestValue) // Less then 1% of cases
- {
- lock_grab(&(sp->lock));
- if (futilityValueScaled > sp->bestValue)
- sp->bestValue = futilityValueScaled;
- lock_release(&(sp->lock));
- }
+ lock_grab(&(sp->lock));
+
+ if (futilityValueScaled > sp->bestValue)
+ sp->bestValue = futilityValueScaled;
continue;
}
}
- // Make and search the move.
- StateInfo st;
+ // Step 13. Make the move
pos.do_move(move, st, ci, moveIsCheck);
- // Try to reduce non-pv search depth by one ply if move seems not problematic,
+ // Step 14. Reduced search
// if the move fails high will be re-searched at full depth.
bool doFullDepthSearch = true;
}
}
- if (doFullDepthSearch) // Go with full depth non-pv search
+ // Step 15. Full depth search
+ if (doFullDepthSearch)
{
ss[sp->ply].reduction = Depth(0);
value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
}
+
+ // Step 16. Undo move
pos.undo_move(move);
assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
- // New best move?
- if (value > sp->bestValue) // Less then 2% of cases
+ // Step 17. Check for new best move
+ lock_grab(&(sp->lock));
+
+ if (value > sp->bestValue && !TM.thread_should_stop(threadID))
{
- lock_grab(&(sp->lock));
- if (value > sp->bestValue && !TM.thread_should_stop(threadID))
+ sp->bestValue = value;
+ if (sp->bestValue >= sp->beta)
{
- sp->bestValue = value;
- if (sp->bestValue >= sp->beta)
- {
- sp->stopRequest = true;
- sp_update_pv(sp->parentSstack, ss, sp->ply);
- }
+ sp->stopRequest = true;
+ sp_update_pv(sp->parentSstack, ss, sp->ply);
}
- lock_release(&(sp->lock));
}
}
/* Here we have the lock still grabbed */
- sp->cpus--;
sp->slaves[threadID] = 0;
+ sp->cpus--;
lock_release(&(sp->lock));
}
Position pos(*sp->pos);
CheckInfo ci(pos);
SearchStack* ss = sp->sstack[threadID];
+ StateInfo st;
Value value = -VALUE_INFINITE;
int moveCount;
Move move;
- while ( lock_grab_bool(&(sp->lock))
- && sp->alpha < sp->beta
+ // Step 10. Loop through moves
+ // Loop through all legal moves until no moves remain or a beta cutoff occurs
+ lock_grab(&(sp->lock));
+
+ while ( sp->alpha < sp->beta
&& !TM.thread_should_stop(threadID)
&& (move = sp->mp->get_next_move()) != MOVE_NONE)
{
bool moveIsCheck = pos.move_is_check(move, ci);
bool captureOrPromotion = pos.move_is_capture_or_promotion(move);
- ss[sp->ply].currentMove = move;
-
- // Decide the new search depth
+ // Step 11. Decide the new search depth
bool dangerous;
Depth ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
Depth newDepth = sp->depth - OnePly + ext;
- // Make and search the move.
- StateInfo st;
+ // Update current move
+ ss[sp->ply].currentMove = move;
+
+ // Step 12. Futility pruning (is omitted in PV nodes)
+
+ // Step 13. Make the move
pos.do_move(move, st, ci, moveIsCheck);
- // Try to reduce non-pv search depth by one ply if move seems not problematic,
+ // Step 14. Reduced search
// if the move fails high will be re-searched at full depth.
bool doFullDepthSearch = true;
}
}
- if (doFullDepthSearch) // Go with full depth non-pv search
+ // Step 15. Full depth search
+ if (doFullDepthSearch)
{
Value localAlpha = sp->alpha;
ss[sp->ply].reduction = Depth(0);
value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID);
}
}
+
+ // Step 16. Undo move
pos.undo_move(move);
assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
- // New best move?
- if (value > sp->bestValue) // Less then 2% of cases
+ // Step 17. Check for new best move
+ lock_grab(&(sp->lock));
+
+ if (value > sp->bestValue && !TM.thread_should_stop(threadID))
{
- lock_grab(&(sp->lock));
- if (value > sp->bestValue && !TM.thread_should_stop(threadID))
+ sp->bestValue = value;
+ if (value > sp->alpha)
{
- sp->bestValue = value;
- if (value > sp->alpha)
- {
- // Ask threads to stop before to modify sp->alpha
- if (value >= sp->beta)
- sp->stopRequest = true;
-
- sp->alpha = value;
-
- sp_update_pv(sp->parentSstack, ss, sp->ply);
- if (value == value_mate_in(sp->ply + 1))
- ss[sp->ply].mateKiller = move;
- }
+ // Ask threads to stop before to modify sp->alpha
+ if (value >= sp->beta)
+ sp->stopRequest = true;
+
+ sp->alpha = value;
+
+ sp_update_pv(sp->parentSstack, ss, sp->ply);
+ if (value == value_mate_in(sp->ply + 1))
+ ss[sp->ply].mateKiller = move;
}
- lock_release(&(sp->lock));
}
}
/* Here we have the lock still grabbed */
- sp->cpus--;
sp->slaves[threadID] = 0;
+ sp->cpus--;
lock_release(&(sp->lock));
}
projects / stockfish / blobdiff