Depth depth, int ply, int threadID);
void sp_search(SplitPoint *sp, int threadID);
void sp_search_pv(SplitPoint *sp, int threadID);
+ void init_search_stack(SearchStack& ss);
void init_search_stack(SearchStack ss[]);
void init_node(const Position &pos, SearchStack ss[], int ply, int threadID);
void update_pv(SearchStack ss[], int ply);
void sp_update_pv(SearchStack *pss, SearchStack ss[], int ply);
bool connected_moves(const Position &pos, Move m1, Move m2);
- Depth extension(const Position &pos, Move m, bool pvNode, bool check,
- bool singleReply, bool mateThreat);
+ bool move_is_killer(Move m, const SearchStack& ss);
+ Depth extension(const Position &pos, Move m, bool pvNode, bool check, bool singleReply, bool mateThreat, bool* extendable);
bool ok_to_do_nullmove(const Position &pos);
bool ok_to_prune(const Position &pos, Move m, Move threat, Depth d);
bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
bool ok_to_history(const Position &pos, Move m);
- void update_history(const Position& pos, Move m, Depth depth,
- Move movesSearched[], int moveCount);
+ void update_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount);
+ void update_killers(Move m, SearchStack& ss);
bool fail_high_ply_1();
int current_search_time();
History H; // Should be made local?
+// The empty search stack
+SearchStack EmptySearchStack;
+
////
//// Functions
TimeAdvantage = myTime - oppTime;
if (!movesToGo) // Sudden death time control
- {
- if (increment)
+ {
+ if (myIncrement)
{
MaxSearchTime = myTime / 30 + myIncrement;
AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
// Wait until the thread has finished launching:
while (!Threads[i].running);
}
+
+ // Init also the empty search stack
+ init_search_stack(EmptySearchStack);
}
<< " currmovenumber " << i + 1 << std::endl;
// Decide search depth for this move
- ext = extension(pos, move, true, pos.move_is_check(move), false, false);
+ bool dummy;
+ ext = extension(pos, move, true, pos.move_is_check(move), false, false, &dummy);
newDepth = (Iteration - 2) * OnePly + ext + InitialDepth;
// Make the move, and search it
if (Problem && StopOnPonderhit)
StopOnPonderhit = false;
- }
+ }
else
{
value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
// Initialize a MovePicker object for the current position, and prepare
// to search all moves
- MovePicker mp = MovePicker(pos, true, ttMove, ss[ply].mateKiller,
- ss[ply].killer1, ss[ply].killer2, depth);
+ MovePicker mp = MovePicker(pos, true, ttMove, ss[ply], depth);
Move move, movesSearched[256];
int moveCount = 0;
ss[ply].currentMoveCaptureValue = Value(0);
// Decide the new search depth
- Depth ext = extension(pos, move, true, moveIsCheck, singleReply, mateThreat);
+ bool extendable;
+ Depth ext = extension(pos, move, true, moveIsCheck, singleReply, mateThreat, &extendable);
Depth newDepth = depth - OnePly + ext;
// Make and search the move
// Try to reduce non-pv search depth by one ply if move seems not problematic,
// if the move fails high will be re-searched at full depth.
if ( depth >= 2*OnePly
- && ext == Depth(0)
+ && !extendable
&& moveCount >= LMRPVMoves
&& !moveIsCapture
&& !move_promotion(move)
&& !moveIsPassedPawnPush
&& !move_is_castle(move)
- && move != ss[ply].killer1
- && move != ss[ply].killer2)
+ && !move_is_killer(move, ss[ply]))
{
ss[ply].reduction = OnePly;
value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID);
if (ok_to_history(pos, m)) // Only non capture moves are considered
{
update_history(pos, m, depth, movesSearched, moveCount);
- if (m != ss[ply].killer1)
- {
- ss[ply].killer2 = ss[ply].killer1;
- ss[ply].killer1 = m;
- }
+ update_killers(m, ss[ply]);
}
TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER);
}
// Initialize a MovePicker object for the current position, and prepare
// to search all moves:
- MovePicker mp = MovePicker(pos, false, ttMove, ss[ply].mateKiller,
- ss[ply].killer1, ss[ply].killer2, depth);
+ MovePicker mp = MovePicker(pos, false, ttMove, ss[ply], depth);
Move move, movesSearched[256];
int moveCount = 0;
movesSearched[moveCount++] = ss[ply].currentMove = move;
// Decide the new search depth
- Depth ext = extension(pos, move, false, moveIsCheck, singleReply, mateThreat);
+ bool extendable;
+ Depth ext = extension(pos, move, false, moveIsCheck, singleReply, mateThreat, &extendable);
Depth newDepth = depth - OnePly + ext;
// Futility pruning
if ( useFutilityPruning
- && ext == Depth(0)
+ && !extendable
&& !moveIsCapture
&& !moveIsPassedPawnPush
&& !move_promotion(move))
// Try to reduce non-pv search depth by one ply if move seems not problematic,
// if the move fails high will be re-searched at full depth.
if ( depth >= 2*OnePly
- && ext == Depth(0)
+ && !extendable
&& moveCount >= LMRNonPVMoves
&& !moveIsCapture
&& !move_promotion(move)
&& !moveIsPassedPawnPush
&& !move_is_castle(move)
- && move != ss[ply].killer1
- && move != ss[ply].killer2)
+ && !move_is_killer(move, ss[ply]))
{
ss[ply].reduction = OnePly;
value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
if (ok_to_history(pos, m)) // Only non capture moves are considered
{
update_history(pos, m, depth, movesSearched, moveCount);
- if (m != ss[ply].killer1)
- {
- ss[ply].killer2 = ss[ply].killer1;
- ss[ply].killer1 = m;
- }
+ update_killers(m, ss[ply]);
}
TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER);
}
// 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) will be generated.
- MovePicker mp = MovePicker(pos, false, MOVE_NONE, MOVE_NONE, MOVE_NONE,
- MOVE_NONE, depth);
+ MovePicker mp = MovePicker(pos, false, MOVE_NONE, EmptySearchStack, depth, &ei);
Move move;
int moveCount = 0;
Bitboard dcCandidates = mp.discovered_check_candidates();
bool isCheck = pos.is_check();
+ bool pvNode = (beta - alpha != 1);
+ bool enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
// Loop through the moves until no moves remain or a beta cutoff
// occurs.
&& !moveIsCheck
&& !move_promotion(move)
&& !moveIsPassedPawnPush
- && beta - alpha == 1
- && pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame)
+ && !pvNode
+ && enoughMaterial)
{
Value futilityValue = staticValue
+ Max(pos.midgame_value_of_piece_on(move_to(move)),
}
}
- // Don't search captures and checks with negative SEE values.
+ // Don't search captures and checks with negative SEE values
if ( !isCheck
&& !move_promotion(move)
&& (pos.midgame_value_of_piece_on(move_from(move)) >
if (alpha >= beta && ok_to_history(pos, m)) // Only non capture moves are considered
{
// Wrong to update history when depth is <= 0
-
- if (m != ss[ply].killer1)
- {
- ss[ply].killer2 = ss[ply].killer1;
- ss[ply].killer1 = m;
- }
+ update_killers(m, ss[ply]);
}
return bestValue;
}
ss[sp->ply].currentMove = move;
// Decide the new search depth.
- Depth ext = extension(pos, move, false, moveIsCheck, false, false);
+ bool extendable;
+ Depth ext = extension(pos, move, false, moveIsCheck, false, false, &extendable);
Depth newDepth = sp->depth - OnePly + ext;
// Prune?
if ( useFutilityPruning
- && ext == Depth(0)
+ && !extendable
&& !moveIsCapture
&& !moveIsPassedPawnPush
&& !move_promotion(move)
// Try to reduce non-pv search depth by one ply if move seems not problematic,
// if the move fails high will be re-searched at full depth.
- if ( ext == Depth(0)
+ if ( !extendable
&& moveCount >= LMRNonPVMoves
&& !moveIsCapture
&& !moveIsPassedPawnPush
&& !move_promotion(move)
&& !move_is_castle(move)
- && move != ss[sp->ply].killer1
- && move != ss[sp->ply].killer2)
+ && !move_is_killer(move, ss[sp->ply]))
{
ss[sp->ply].reduction = OnePly;
value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID);
ss[sp->ply].currentMove = move;
// Decide the new search depth.
- Depth ext = extension(pos, move, true, moveIsCheck, false, false);
+ bool extendable;
+ Depth ext = extension(pos, move, true, moveIsCheck, false, false, &extendable);
Depth newDepth = sp->depth - OnePly + ext;
// Make and search the move.
// Try to reduce non-pv search depth by one ply if move seems not problematic,
// if the move fails high will be re-searched at full depth.
- if ( ext == Depth(0)
+ if ( !extendable
&& moveCount >= LMRPVMoves
&& !moveIsCapture
&& !moveIsPassedPawnPush
&& !move_promotion(move)
&& !move_is_castle(move)
- && move != ss[sp->ply].killer1
- && move != ss[sp->ply].killer2)
+ && !move_is_killer(move, ss[sp->ply]))
{
ss[sp->ply].reduction = OnePly;
value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID);
// init_search_stack() initializes a search stack at the beginning of a
// new search from the root.
+ void init_search_stack(SearchStack& ss) {
+
+ ss.pv[0] = MOVE_NONE;
+ ss.pv[1] = MOVE_NONE;
+ ss.currentMove = MOVE_NONE;
+ ss.threatMove = MOVE_NONE;
+ ss.reduction = Depth(0);
+ for (int j = 0; j < KILLER_MAX; j++)
+ ss.killers[j] = MOVE_NONE;
+ }
void init_search_stack(SearchStack ss[]) {
- for(int i = 0; i < 3; i++) {
- ss[i].pv[i] = MOVE_NONE;
- ss[i].pv[i+1] = MOVE_NONE;
- ss[i].currentMove = MOVE_NONE;
- ss[i].mateKiller = MOVE_NONE;
- ss[i].killer1 = MOVE_NONE;
- ss[i].killer2 = MOVE_NONE;
- ss[i].threatMove = MOVE_NONE;
- ss[i].reduction = Depth(0);
+
+ for (int i = 0; i < 3; i++)
+ {
+ ss[i].pv[i] = MOVE_NONE;
+ ss[i].pv[i+1] = MOVE_NONE;
+ ss[i].currentMove = MOVE_NONE;
+ ss[i].threatMove = MOVE_NONE;
+ ss[i].reduction = Depth(0);
+ for (int j = 0; j < KILLER_MAX; j++)
+ ss[i].killers[j] = MOVE_NONE;
}
}
NodesSincePoll = 0;
}
}
-
ss[ply].pv[ply] = ss[ply].pv[ply+1] = ss[ply].currentMove = MOVE_NONE;
ss[ply+2].mateKiller = MOVE_NONE;
- ss[ply+2].killer1 = ss[ply+2].killer2 = MOVE_NONE;
ss[ply].threatMove = MOVE_NONE;
ss[ply].reduction = Depth(0);
ss[ply].currentMoveCaptureValue = Value(0);
+ for (int j = 0; j < KILLER_MAX; j++)
+ ss[ply+2].killers[j] = MOVE_NONE;
if(Threads[threadID].printCurrentLine)
print_current_line(ss, ply, threadID);
}
+ // move_is_killer() checks if the given move is among the
+ // killer moves of that ply.
+
+ bool move_is_killer(Move m, const SearchStack& ss) {
+
+ const Move* k = ss.killers;
+ for (int i = 0; i < KILLER_MAX; i++, k++)
+ if (*k == m)
+ return true;
+
+ return false;
+ }
+
+
// extension() decides whether a move should be searched with normal depth,
// or with extended depth. Certain classes of moves (checking moves, in
// particular) are searched with bigger depth than ordinary moves.
Depth extension(const Position &pos, Move m, bool pvNode,
- bool check, bool singleReply, bool mateThreat) {
+ bool check, bool singleReply, bool mateThreat, bool* extendable) {
Depth result = Depth(0);
+ *extendable = check || singleReply || mateThreat;
if (check)
result += CheckExtension[pvNode];
if (singleReply)
result += SingleReplyExtension[pvNode];
+ if (mateThreat)
+ result += MateThreatExtension[pvNode];
+
if (pos.move_is_pawn_push_to_7th(m))
+ {
result += PawnPushTo7thExtension[pvNode];
-
+ *extendable = true;
+ }
if (pos.move_is_passed_pawn_push(m))
+ {
result += PassedPawnExtension[pvNode];
+ *extendable = true;
+ }
- if (mateThreat)
- result += MateThreatExtension[pvNode];
-
- if ( pos.midgame_value_of_piece_on(move_to(m)) >= RookValueMidgame\r
- && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)\r
- - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))\r
+ 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))
+ {
result += PawnEndgameExtension[pvNode];
-
+ *extendable = true;
+ }
+
if ( pvNode
&& pos.move_is_capture(m)
&& pos.type_of_piece_on(move_to(m)) != PAWN
&& pos.see(m) >= 0)
+ {
result += OnePly/2;
+ *extendable = true;
+ }
return Min(result, OnePly);
}
// ok_to_history() returns true if a move m can be stored
- // in history. Should be a non capturing move.
+ // in history. Should be a non capturing move nor a promotion.
bool ok_to_history(const Position& pos, Move m) {
- return pos.square_is_empty(move_to(m))
- && !move_promotion(m)
- && !move_is_ep(m);
+ return !pos.move_is_capture(m) && !move_promotion(m);
}
}
}
+
+ // update_killers() add a good move that produced a beta-cutoff
+ // among the killer moves of that ply.
+
+ void update_killers(Move m, SearchStack& ss) {
+
+ if (m == ss.killers[0])
+ return;
+
+ for (int i = KILLER_MAX - 1; i > 0; i--)
+ ss.killers[i] = ss.killers[i - 1];
+
+ ss.killers[0] = m;
+ }
+
// fail_high_ply_1() checks if some thread is currently resolving a fail
// high at ply 1 at the node below the first root node. This information
// is used for time managment.
projects / stockfish / blobdiff