void read_uci_options();
bool available_thread_exists(int master) const;
bool thread_is_available(int slave, int master) const;
- bool thread_should_stop(int threadID) const;
+ bool cutoff_at_splitpoint(int threadID) const;
void wake_sleeping_thread(int threadID);
void idle_loop(int threadID, SplitPoint* sp);
template <NodeType PvNode>
Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
+ bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue);
bool connected_moves(const Position& pos, Move m1, Move m2);
bool value_is_mate(Value value);
Value value_to_tt(Value v, int ply);
threatMove = sp->threatMove;
mateThreat = sp->mateThreat;
goto split_point_start;
- } else {} // Hack to fix icc's "statement is unreachable" warning
+ }
+ else {} // Hack to fix icc's "statement is unreachable" warning
// Step 1. Initialize node and poll. Polling can abort search
ss->currentMove = ss->bestMove = threatMove = MOVE_NONE;
}
// Step 2. Check for aborted search and immediate draw
- if ( AbortSearch || ThreadsMgr.thread_should_stop(threadID)
- || pos.is_draw() || ply >= PLY_MAX - 1)
+ if ( AbortSearch
+ || ThreadsMgr.cutoff_at_splitpoint(threadID)
+ || pos.is_draw()
+ || ply >= PLY_MAX - 1)
return VALUE_DRAW;
// Step 3. Mate distance pruning
threatMove = (ss+1)->bestMove;
if ( depth < ThreatDepth
&& (ss-1)->reduction
+ && threatMove != MOVE_NONE
&& connected_moves(pos, (ss-1)->currentMove, threatMove))
return beta - 1;
}
// Loop through all legal moves until no moves remain or a beta cutoff occurs
while ( bestValue < beta
&& (move = mp.get_next_move()) != MOVE_NONE
- && !ThreadsMgr.thread_should_stop(threadID))
+ && !ThreadsMgr.cutoff_at_splitpoint(threadID))
{
assert(move_is_ok(move));
continue;
}
- // Prune neg. see moves at low depths
+ // Prune moves with negative SEE at low depths
if ( predictedDepth < 2 * ONE_PLY
&& bestValue > value_mated_in(PLY_MAX)
&& pos.see_sign(move) < 0)
// Step extra. pv search (only in PV nodes)
// The first move in list is the expected PV
- if (!SpNode && PvNode && moveCount == 1)
+ if (PvNode && moveCount == 1)
value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
else
{
&& !captureOrPromotion
&& !dangerous
&& !move_is_castle(move)
- && !(ss->killers[0] == move || ss->killers[1] == move))
+ && ss->killers[0] != move
+ && ss->killers[1] != move)
{
ss->reduction = reduction<PvNode>(depth, moveCount);
+
if (ss->reduction)
{
alpha = SpNode ? sp->alpha : alpha;
alpha = sp->alpha;
}
- if (value > bestValue && !(SpNode && ThreadsMgr.thread_should_stop(threadID)))
+ if (value > bestValue && !(SpNode && ThreadsMgr.cutoff_at_splitpoint(threadID)))
{
bestValue = value;
if (value > alpha)
{
- if (SpNode && (!PvNode || value >= beta))
- sp->stopRequest = true;
-
if (PvNode && value < beta) // We want always alpha < beta
{
alpha = value;
+
if (SpNode)
sp->alpha = value;
}
+ else if (SpNode)
+ sp->betaCutoff = true;
if (value == value_mate_in(ply + 1))
ss->mateKiller = move;
&& bestValue < beta
&& ThreadsMgr.available_thread_exists(threadID)
&& !AbortSearch
- && !ThreadsMgr.thread_should_stop(threadID)
+ && !ThreadsMgr.cutoff_at_splitpoint(threadID)
&& Iteration <= 99)
ThreadsMgr.split<FakeSplit>(pos, ss, ply, &alpha, beta, &bestValue, depth,
threatMove, mateThreat, moveCount, &mp, PvNode);
// Step 20. Update tables
// If the search is not aborted, update the transposition table,
// history counters, and killer moves.
- if (!SpNode && !AbortSearch && !ThreadsMgr.thread_should_stop(threadID))
+ if (!SpNode && !AbortSearch && !ThreadsMgr.cutoff_at_splitpoint(threadID))
{
move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove;
vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER
return bestValue;
}
- Bitboard attacks(const Piece P, const Square sq, const Bitboard occ)
- {
- switch(P)
- {
- case WP:
- case BP:
- case WN:
- case BN:
- case WK:
- case BK:
- return StepAttackBB[P][sq];
- case WB:
- case BB:
- return bishop_attacks_bb(sq, occ);
- case WR:
- case BR:
- return rook_attacks_bb(sq, occ);
- case WQ:
- case BQ:
- return bishop_attacks_bb(sq, occ) | rook_attacks_bb(sq, occ);
- default:
- assert(false);
- return 0ULL;
- }
- }
-
- bool check_is_useless(Position &pos, Move move, Value eval, Value futilityBase, Value beta, Value *bValue)
- {
- Value bestValue = *bValue;
-
- /// Rule 1. Using checks to reposition pieces when close to beta
- if (eval + PawnValueMidgame / 4 < beta)
- {
- if (eval + PawnValueMidgame / 4 > bestValue)
- bestValue = eval + PawnValueMidgame / 4;
- }
- else
- return false;
-
- Square from = move_from(move);
- Square to = move_to(move);
- Color oppColor = opposite_color(pos.side_to_move());
- Square oppKing = pos.king_square(oppColor);
-
- Bitboard occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL <<oppKing);
- Bitboard oppOcc = pos.pieces_of_color(oppColor) & ~(1ULL <<oppKing);
- Bitboard oldAtt = attacks(pos.piece_on(from), from, occ);
- Bitboard newAtt = attacks(pos.piece_on(from), to, occ);
-
- // Rule 2. Checks which give opponent's king at most one escape square are dangerous
- Bitboard escapeBB = attacks(WK, oppKing, 0) & ~oppOcc & ~newAtt & ~(1ULL << to);
-
- if (!escapeBB)
- return false;
-
- if (!(escapeBB & (escapeBB - 1)))
- return false;
-
- /// Rule 3. Queen contact check is very dangerous
- if ( pos.type_of_piece_on(from) == QUEEN
- && bit_is_set(attacks(WK, oppKing, 0), to))
- return false;
-
- /// Rule 4. Creating new double threats with checks
- Bitboard newVictims = oppOcc & ~oldAtt & newAtt;
-
- while(newVictims)
- {
- Square victimSq = pop_1st_bit(&newVictims);
-
- Value futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
-
- // Note that here we generate illegal "double move"!
- if (futilityValue >= beta && pos.see_sign(make_move(from, victimSq)) >= 0)
- return false;
-
- if (futilityValue > bestValue)
- bestValue = futilityValue;
- }
-
- *bValue = bestValue;
- return true;
- }
-
// qsearch() is the quiescence search function, which is called by the main
// search function when the remaining depth is zero (or, to be more precise,
// less than ONE_PLY).
Value bestValue, value, evalMargin, futilityValue, futilityBase;
bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
const TTEntry* tte;
+ Depth ttDepth;
Value oldAlpha = alpha;
ss->bestMove = ss->currentMove = MOVE_NONE;
if (pos.is_draw() || ply >= PLY_MAX - 1)
return VALUE_DRAW;
- // Decide whether or not to include checks
+ // Decide whether or not to include checks, this fixes also the type of
+ // TT entry depth that we are going to use. Note that in qsearch we use
+ // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
isCheck = pos.is_check();
-
- Depth d;
- if (isCheck || depth >= -ONE_PLY)
- d = DEPTH_ZERO;
- else
- d = DEPTH_ZERO - ONE_PLY;
+ ttDepth = (isCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
// Transposition table lookup. At PV nodes, we don't use the TT for
// pruning, but only for move ordering.
tte = TT.retrieve(pos.get_key());
ttMove = (tte ? tte->move() : MOVE_NONE);
- if (!PvNode && tte && ok_to_use_TT(tte, d, beta, ply))
+ if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ply))
{
ss->bestMove = ttMove; // Can be MOVE_NONE
return value_from_tt(tte->value(), ply);
// Initialize a MovePicker object for the current position, and prepare
// to search the moves. Because the depth is <= 0 here, only captures,
- // queen promotions and checks (only if depth == 0 or depth == -ONE_PLY
- // and we are near beta) will be generated.
- MovePicker mp = MovePicker(pos, ttMove, d, H);
+ // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
+ // be generated.
+ MovePicker mp = MovePicker(pos, ttMove, depth, H);
CheckInfo ci(pos);
// Loop through the moves until no moves remain or a beta cutoff occurs
// Don't search useless checks
if ( !PvNode
&& !isCheck
- && move != ttMove
- && !move_is_promotion(move)
- && !pos.move_is_capture(move)
- && moveIsCheck
- && check_is_useless(pos, move, ss->eval, futilityBase, beta, &bestValue))
+ && moveIsCheck
+ && move != ttMove
+ && !pos.move_is_capture_or_promotion(move)
+ && ss->eval + PawnValueMidgame / 4 < beta
+ && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue))
+ {
+ if (ss->eval + PawnValueMidgame / 4 > bestValue)
+ bestValue = ss->eval + PawnValueMidgame / 4;
+
continue;
+ }
// Update current move
ss->currentMove = move;
// Update transposition table
ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
- TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, d, ss->bestMove, ss->eval, evalMargin);
+ TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin);
assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
}
+ // check_is_dangerous() tests if a checking move can be pruned in qsearch().
+ // bestValue is updated only when returning false because in that case move
+ // will be pruned.
+
+ bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bestValue)
+ {
+ Bitboard b, occ, oldAtt, newAtt, kingAtt;
+ Square from, to, ksq, victimSq;
+ Piece pc;
+ Color them;
+ Value futilityValue, bv = *bestValue;
+
+ from = move_from(move);
+ to = move_to(move);
+ them = opposite_color(pos.side_to_move());
+ ksq = pos.king_square(them);
+ kingAtt = pos.attacks_from<KING>(ksq);
+ pc = pos.piece_on(from);
+
+ occ = pos.occupied_squares() & ~(1ULL << from) & ~(1ULL << ksq);
+ oldAtt = pos.attacks_from(pc, from, occ);
+ newAtt = pos.attacks_from(pc, to, occ);
+
+ // Rule 1. Checks which give opponent's king at most one escape square are dangerous
+ b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to);
+
+ if (!(b && (b & (b - 1))))
+ return true;
+
+ // Rule 2. Queen contact check is very dangerous
+ if ( type_of_piece(pc) == QUEEN
+ && bit_is_set(kingAtt, to))
+ return true;
+
+ // Rule 3. Creating new double threats with checks
+ b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq);
+
+ while (b)
+ {
+ victimSq = pop_1st_bit(&b);
+ futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq);
+
+ // Note that here we generate illegal "double move"!
+ if ( futilityValue >= beta
+ && pos.see_sign(make_move(from, victimSq)) >= 0)
+ return true;
+
+ if (futilityValue > bv)
+ bv = futilityValue;
+ }
+
+ // Update bestValue only if check is not dangerous (because we will prune the move)
+ *bestValue = bv;
+ return false;
+ }
+
+
// connected_moves() tests whether two moves are 'connected' in the sense
// that the first move somehow made the second move possible (for instance
// if the moving piece is the same in both moves). The first move is assumed
Square f1, t1, f2, t2;
Piece p;
- assert(move_is_ok(m1));
- assert(move_is_ok(m2));
-
- if (m2 == MOVE_NONE)
- return false;
+ assert(m1 && move_is_ok(m1));
+ assert(m2 && move_is_ok(m2));
// Case 1: The moving piece is the same in both moves
f2 = move_from(m2);
}
- // thread_should_stop() checks whether the thread should stop its search.
- // This can happen if a beta cutoff has occurred in the thread's currently
- // active split point, or in some ancestor of the current split point.
+ // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
+ // the thread's currently active split point, or in some ancestor of
+ // the current split point.
- bool ThreadsManager::thread_should_stop(int threadID) const {
+ bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
assert(threadID >= 0 && threadID < activeThreads);
SplitPoint* sp = threads[threadID].splitPoint;
- for ( ; sp && !sp->stopRequest; sp = sp->parent) {}
+ for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
return sp != NULL;
}
// Initialize the split point object
splitPoint.parent = masterThread.splitPoint;
splitPoint.master = master;
- splitPoint.stopRequest = false;
+ splitPoint.betaCutoff = false;
splitPoint.ply = ply;
splitPoint.depth = depth;
splitPoint.threatMove = threatMove;