void init(Position& pos, Move searchMoves[]);
void sort() { insertion_sort<RootMove, Base::iterator>(begin(), end()); }
- void sort_multipv(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n); }
+ void sort_first(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n); }
int bestMoveChanges;
};
- // MovePickerExt template class extends MovePicker and allows to choose at compile
- // time the proper moves source according to the type of node. In the default case
- // we simply create and use a standard MovePicker object.
- template<NodeType> struct MovePickerExt : public MovePicker {
-
- MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b)
- : MovePicker(p, ttm, d, h, ss, b) {}
-
- RootMoveList::iterator rm; // Dummy, needed to compile
- };
-
- // In case of a SpNode we use split point's shared MovePicker object as moves source
- template<> struct MovePickerExt<SplitPointNonPV> : public MovePickerExt<NonPV> {
-
- MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b)
- : MovePickerExt<NonPV>(p, ttm, d, h, ss, b), mp(ss->sp->mp) {}
-
- Move get_next_move() { return mp->get_next_move(); }
- MovePicker* mp;
- };
-
- template<> struct MovePickerExt<SplitPointPV> : public MovePickerExt<SplitPointNonPV> {
-
- MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b)
- : MovePickerExt<SplitPointNonPV>(p, ttm, d, h, ss, b) {}
- };
-
- // In case of a Root node we use RootMoveList as moves source
- template<> struct MovePickerExt<Root> : public MovePicker {
-
- MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value);
- Move get_next_move();
-
- RootMoveList::iterator rm;
- bool firstCall;
- };
-
/// Constants
template <NodeType NT>
Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth);
- template <bool PvNode>
- Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, 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);
Value value_to_tt(Value v, int ply);
void poll(const Position& pos);
void wait_for_stop_or_ponderhit();
+ // MovePickerExt template class extends MovePicker and allows to choose at compile
+ // time the proper moves source according to the type of node. In the default case
+ // we simply create and use a standard MovePicker object.
+ template<NodeType> struct MovePickerExt : public MovePicker {
+
+ MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b)
+ : MovePicker(p, ttm, d, h, ss, b) {}
+
+ RootMove& current() { assert(false); return Rml[0]; } // Dummy, needed to compile
+ };
+
+ // In case of a SpNode we use split point's shared MovePicker object as moves source
+ template<> struct MovePickerExt<SplitPointNonPV> : public MovePickerExt<NonPV> {
+
+ MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b)
+ : MovePickerExt<NonPV>(p, ttm, d, h, ss, b), mp(ss->sp->mp) {}
+
+ Move get_next_move() { return mp->get_next_move(); }
+ MovePicker* mp;
+ };
+
+ template<> struct MovePickerExt<SplitPointPV> : public MovePickerExt<SplitPointNonPV> {
+
+ MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b)
+ : MovePickerExt<SplitPointNonPV>(p, ttm, d, h, ss, b) {}
+ };
+
+ // In case of a Root node we use RootMoveList as moves source
+ template<> struct MovePickerExt<Root> : public MovePicker {
+
+ MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value);
+ RootMove& current() { return Rml[cur]; }
+ Move get_next_move() { return ++cur < (int)Rml.size() ? Rml[cur].pv[0] : MOVE_NONE; }
+
+ int cur;
+ };
+
// Overload operator<<() to make it easier to print moves in a coordinate
// notation compatible with UCI protocol.
std::ostream& operator<<(std::ostream& os, Move m) {
return os;
}
+ // 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 and in
+ // any case are marked as 'dangerous'. Note that also if a move is not
+ // extended, as example because the corresponding UCI option is set to zero,
+ // the move is marked as 'dangerous' so, at least, we avoid to prune it.
+ template <bool PvNode>
+ FORCE_INLINE Depth extension(const Position& pos, Move m, bool captureOrPromotion,
+ bool moveIsCheck, bool* dangerous) {
+ assert(m != MOVE_NONE);
+
+ Depth result = DEPTH_ZERO;
+ *dangerous = moveIsCheck;
+
+ if (moveIsCheck && pos.see_sign(m) >= 0)
+ result += CheckExtension[PvNode];
+
+ if (pos.type_of_piece_on(move_from(m)) == PAWN)
+ {
+ Color c = pos.side_to_move();
+ if (relative_rank(c, move_to(m)) == RANK_7)
+ {
+ result += PawnPushTo7thExtension[PvNode];
+ *dangerous = true;
+ }
+ if (pos.pawn_is_passed(c, move_to(m)))
+ {
+ result += PassedPawnExtension[PvNode];
+ *dangerous = true;
+ }
+ }
+
+ if ( captureOrPromotion
+ && pos.type_of_piece_on(move_to(m)) != PAWN
+ && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
+ - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
+ && !move_is_special(m))
+ {
+ result += PawnEndgameExtension[PvNode];
+ *dangerous = true;
+ }
+
+ return Min(result, ONE_PLY);
+ }
+
} // namespace
if (StopRequest)
break;
- assert(value >= alpha);
-
// In case of failing high/low increase aspiration window and research,
// otherwise exit the fail high/low loop.
if (value >= beta)
StateInfo st;
const TTEntry *tte;
Key posKey;
- Bitboard pinned;
Move ttMove, move, excludedMove, threatMove;
Depth ext, newDepth;
ValueType vt;
threatMove = sp->threatMove;
goto split_point_start;
}
- else if (RootNode)
- bestValue = alpha;
// Step 1. Initialize node and poll. Polling can abort search
ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE;
// Step 2. Check for aborted search and immediate draw
if (( StopRequest
- || pos.is_draw()
+ || pos.is_draw<false>()
|| ss->ply > PLY_MAX) && !RootNode)
return VALUE_DRAW;
// Step 3. Mate distance pruning
- alpha = Max(value_mated_in(ss->ply), alpha);
- beta = Min(value_mate_in(ss->ply+1), beta);
- if (alpha >= beta)
- return alpha;
+ if (!RootNode)
+ {
+ alpha = Max(value_mated_in(ss->ply), alpha);
+ beta = Min(value_mate_in(ss->ply+1), beta);
+ if (alpha >= beta)
+ return alpha;
+ }
// Step 4. Transposition table lookup
// We don't want the score of a partial search to overwrite a previous full search
assert(rdepth >= ONE_PLY);
MovePicker mp(pos, ttMove, H, Position::see_value(pos.captured_piece_type()));
- pinned = pos.pinned_pieces(pos.side_to_move());
+ CheckInfo ci(pos);
while ((move = mp.get_next_move()) != MOVE_NONE)
- if (pos.pl_move_is_legal(move, pinned))
+ if (pos.pl_move_is_legal(move, ci.pinned))
{
- pos.do_move(move, st);
+ pos.do_move(move, st, ci, pos.move_gives_check(move, ci));
value = -search<NonPV>(pos, ss+1, -rbeta, -rbeta+1, rdepth);
pos.undo_move(move);
if (value >= rbeta)
// Initialize a MovePicker object for the current position
MovePickerExt<NT> mp(pos, ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta);
CheckInfo ci(pos);
- pinned = pos.pinned_pieces(pos.side_to_move());
ss->bestMove = MOVE_NONE;
futilityBase = ss->eval + ss->evalMargin;
singularExtensionNode = !RootNode
continue;
// At PV and SpNode nodes we want the moves to be legal
- if ((PvNode || SpNode) && !pos.pl_move_is_legal(move, pinned))
+ if ((PvNode || SpNode) && !pos.pl_move_is_legal(move, ci.pinned))
continue;
if (SpNode)
}
// At Root and at first iteration do a PV search on all the moves to score root moves
- isPvMove = (PvNode && moveCount <= (RootNode ? depth <= ONE_PLY ? 1000 : MultiPV : 1));
+ isPvMove = (PvNode && moveCount <= (RootNode ? depth <= ONE_PLY ? MAX_MOVES : MultiPV : 1));
givesCheck = pos.move_gives_check(move, ci);
captureOrPromotion = pos.move_is_capture(move) || move_is_promotion(move);
// a margin then we extend ttMove.
if ( singularExtensionNode
&& move == ttMove
- && pos.pl_move_is_legal(move, pinned)
+ && pos.pl_move_is_legal(move, ci.pinned)
&& ext < ONE_PLY)
{
Value ttValue = value_from_tt(tte->value(), ss->ply);
}
// Check for legality only before to do the move
- if (!pos.pl_move_is_legal(move, pinned))
+ if (!pos.pl_move_is_legal(move, ci.pinned))
{
moveCount--;
continue;
// Step extra. pv search (only in PV nodes)
// The first move in list is the expected PV
if (isPvMove)
- {
- // Aspiration window is disabled in multi-pv case
- if (RootNode && MultiPV > 1)
- alpha = -VALUE_INFINITE;
-
value = newDepth < ONE_PLY ? -qsearch<PV>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
: - search<PV>(pos, ss+1, -beta, -alpha, newDepth);
- }
else
{
// Step 15. Reduced depth search
bool doFullDepthSearch = true;
alpha = SpNode ? sp->alpha : alpha;
- if ( depth >= 3 * ONE_PLY
+ if ( depth > 3 * ONE_PLY
&& !captureOrPromotion
&& !dangerous
&& !move_is_castle(move)
break;
// Remember searched nodes counts for this move
- mp.rm->nodes += pos.nodes_searched() - nodes;
+ mp.current().nodes += pos.nodes_searched() - nodes;
// PV move or new best move ?
if (isPvMove || value > alpha)
{
// Update PV
ss->bestMove = move;
- mp.rm->pv_score = value;
- mp.rm->extract_pv_from_tt(pos);
+ mp.current().pv_score = value;
+ mp.current().extract_pv_from_tt(pos);
// We record how often the best move has been changed in each
// iteration. This information is used for time management: When
if (!isPvMove && MultiPV == 1)
Rml.bestMoveChanges++;
- Rml.sort_multipv(moveCount);
+ // It is critical that sorting is done with a stable algorithm
+ // becuase all the values but the first are usually set to
+ // -VALUE_INFINITE and we want to keep the same order for all
+ // the moves but the new PV that goes to head.
+ Rml.sort_first(moveCount);
- // Update alpha. In multi-pv we don't use aspiration window, so
- // set alpha equal to minimum score among the PV lines.
+ // Update alpha. In multi-pv we don't use aspiration window, so set
+ // alpha equal to minimum score among the PV lines searched so far.
if (MultiPV > 1)
- alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount?
+ alpha = Rml[Min(moveCount, MultiPV) - 1].pv_score;
else if (value > alpha)
alpha = value;
}
else
- mp.rm->pv_score = -VALUE_INFINITE;
+ // All other moves but the PV are set to the lowest value, this
+ // is not a problem when sorting becuase sort is stable and move
+ // position in the list is preserved, just the PV is pushed up.
+ mp.current().pv_score = -VALUE_INFINITE;
} // RootNode
ss->ply = (ss-1)->ply + 1;
// Check for an instant draw or maximum ply reached
- if (ss->ply > PLY_MAX || pos.is_draw())
+ if (pos.is_draw<true>() || ss->ply > PLY_MAX)
return VALUE_DRAW;
// Decide whether or not to include checks, this fixes also the type of
else
ss->eval = bestValue = evaluate(pos, evalMargin);
- update_gains(pos, (ss-1)->currentMove, (ss-1)->eval, ss->eval);
-
// Stand pat. Return immediately if static value is at least beta
if (bestValue >= beta)
{
// to search the moves. Because the depth is <= 0 here, only captures,
// queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
// be generated.
- MovePicker mp(pos, ttMove, depth, H);
+ MovePicker mp(pos, ttMove, depth, H, move_to((ss-1)->currentMove));
CheckInfo ci(pos);
- Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
// Loop through the moves until no moves remain or a beta cutoff occurs
while ( alpha < beta
}
// Check for legality only before to do the move
- if (!pos.pl_move_is_legal(move, pinned))
+ if (!pos.pl_move_is_legal(move, ci.pinned))
continue;
// Update current move
}
- // 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 and in
- // any case are marked as 'dangerous'. Note that also if a move is not
- // extended, as example because the corresponding UCI option is set to zero,
- // the move is marked as 'dangerous' so, at least, we avoid to prune it.
- template <bool PvNode>
- Depth extension(const Position& pos, Move m, bool captureOrPromotion,
- bool moveIsCheck, bool* dangerous) {
-
- assert(m != MOVE_NONE);
-
- Depth result = DEPTH_ZERO;
- *dangerous = moveIsCheck;
-
- if (moveIsCheck && pos.see_sign(m) >= 0)
- result += CheckExtension[PvNode];
-
- if (pos.type_of_piece_on(move_from(m)) == PAWN)
- {
- Color c = pos.side_to_move();
- if (relative_rank(c, move_to(m)) == RANK_7)
- {
- result += PawnPushTo7thExtension[PvNode];
- *dangerous = true;
- }
- if (pos.pawn_is_passed(c, move_to(m)))
- {
- result += PassedPawnExtension[PvNode];
- *dangerous = true;
- }
- }
-
- if ( captureOrPromotion
- && pos.type_of_piece_on(move_to(m)) != PAWN
- && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
- - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO)
- && !move_is_special(m))
- {
- result += PawnEndgameExtension[PvNode];
- *dangerous = true;
- }
-
- return Min(result, ONE_PLY);
- }
-
-
// connected_threat() tests whether it is safe to forward prune a move or if
// is somehow connected to the threat move returned by null search.
&& pos.move_is_pl(tte->move())
&& pos.pl_move_is_legal(tte->move(), pos.pinned_pieces(pos.side_to_move()))
&& ply < PLY_MAX
- && (!pos.is_draw() || ply < 2))
+ && (!pos.is_draw<false>() || ply < 2))
{
pv[ply] = tte->move();
pos.do_move(pv[ply++], *st++);
// Specializations for MovePickerExt in case of Root node
MovePickerExt<Root>::MovePickerExt(const Position& p, Move ttm, Depth d,
- const History& h, SearchStack* ss, Value b)
- : MovePicker(p, ttm, d, h, ss, b), firstCall(true) {
+ const History& h, SearchStack* ss, Value b)
+ : MovePicker(p, ttm, d, h, ss, b), cur(-1) {
Move move;
Value score = VALUE_ZERO;
// This is the second order score that is used to compare the moves when
// the first orders pv_score of both moves are equal.
while ((move = MovePicker::get_next_move()) != MOVE_NONE)
- for (rm = Rml.begin(); rm != Rml.end(); ++rm)
+ for (RootMoveList::iterator rm = Rml.begin(); rm != Rml.end(); ++rm)
if (rm->pv[0] == move)
{
rm->non_pv_score = score--;
}
Rml.sort();
- rm = Rml.begin();
- }
-
- Move MovePickerExt<Root>::get_next_move() {
-
- if (!firstCall)
- ++rm;
- else
- firstCall = false;
-
- return rm != Rml.end() ? rm->pv[0] : MOVE_NONE;
}
} // namespace