const bool FakeSplit = false;
// Different node types, used as template parameter
- enum NodeType { Root, PV, NonPV, SplitPointPV, SplitPointNonPV };
+ enum NodeType { Root, PV, NonPV, SplitPointRoot, SplitPointPV, SplitPointNonPV };
// RootMove struct is used for moves at the root of the tree. For each root
- // move, we store a pv_score, a node count, and a PV (really a refutation
- // in the case of moves which fail low). Value pv_score is normally set at
+ // move, we store a score, a node count, and a PV (really a refutation
+ // in the case of moves which fail low). Score is normally set at
// -VALUE_INFINITE for all non-pv moves.
struct RootMove {
- RootMove();
- RootMove(const RootMove& rm) { *this = rm; }
- RootMove& operator=(const RootMove& rm);
-
// RootMove::operator<() is the comparison function used when
// sorting the moves. A move m1 is considered to be better
- // than a move m2 if it has an higher pv_score
- bool operator<(const RootMove& m) const { return pv_score < m.pv_score; }
+ // than a move m2 if it has an higher score
+ bool operator<(const RootMove& m) const { return score < m.score; }
void extract_pv_from_tt(Position& pos);
void insert_pv_in_tt(Position& pos);
int64_t nodes;
- Value pv_score;
- Move pv[PLY_MAX_PLUS_2];
+ Value score;
+ Value prevScore;
+ std::vector<Move> pv;
};
// RootMoveList struct is mainly a std::vector of RootMove objects
struct RootMoveList : public std::vector<RootMove> {
+
void init(Position& pos, Move searchMoves[]);
- RootMove* find(const Move &m, const int startIndex = 0);
+ RootMove* find(const Move& m, int startIndex = 0);
+
int bestMoveChanges;
};
bool connected_moves(const Position& pos, Move m1, Move m2);
Value value_to_tt(Value v, int ply);
Value value_from_tt(Value v, int ply);
- bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
+ bool can_return_tt(const TTEntry* tte, Depth depth, Value beta, int ply);
bool connected_threat(const Position& pos, Move m, Move threat);
Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
void do_skill_level(Move* best, Move* ponder);
int current_search_time(int set = 0);
- string score_to_uci(Value v, Value alpha, Value beta);
+ string score_to_uci(Value v, Value alpha = -VALUE_INFINITE, Value beta = VALUE_INFINITE);
string speed_to_uci(int64_t nodes);
- string pv_to_uci(Move pv[], int pvNum, bool chess960);
+ string pv_to_uci(const Move pv[], int pvNum, bool chess960);
string pretty_pv(Position& pos, int depth, Value score, int time, Move pv[]);
string depth_to_uci(Depth depth);
void poll(const Position& pos);
// 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 {
+ template<bool SpNode> 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) {}
};
// In case of a SpNode we use split point's shared MovePicker object as moves source
- template<> struct MovePickerExt<SplitPointNonPV> : public MovePickerExt<NonPV> {
+ template<> struct MovePickerExt<true> : public MovePicker {
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) {}
+ : MovePicker(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) {}
- };
-
// 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) {
// Iterative deepening loop until requested to stop or target depth reached
while (!StopRequest && ++depth <= PLY_MAX && (!Limits.maxDepth || depth <= Limits.maxDepth))
{
- Rml.bestMoveChanges = 0;
+ // Save last iteration's scores, this needs to be done now, because in
+ // the following MultiPV loop Rml moves could be reordered.
+ for (size_t i = 0; i < Rml.size(); i++)
+ Rml[i].prevScore = Rml[i].score;
- // Remember best moves and values from previous iteration
- std::vector<Move> prevMoves;
- std::vector<Value> prevValues;
-
- for (int i = 0; i < Min(MultiPV, (int)Rml.size()); i++)
- {
- prevMoves.push_back(Rml[i].pv[0]);
- prevValues.push_back(Rml[i].pv_score);
- }
+ Rml.bestMoveChanges = 0;
// MultiPV iteration loop
for (MultiPVIteration = 0; MultiPVIteration < Min(MultiPV, (int)Rml.size()); MultiPVIteration++)
{
// Calculate dynamic aspiration window based on previous iterations
- if (depth >= 5 && abs(prevValues[MultiPVIteration]) < VALUE_KNOWN_WIN)
+ if (depth >= 5 && abs(Rml[MultiPVIteration].prevScore) < VALUE_KNOWN_WIN)
{
int prevDelta1 = bestValues[depth - 1] - bestValues[depth - 2];
int prevDelta2 = bestValues[depth - 2] - bestValues[depth - 3];
aspirationDelta = Min(Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16), 24);
aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize
- alpha = Max(prevValues[MultiPVIteration] - aspirationDelta, -VALUE_INFINITE);
- beta = Min(prevValues[MultiPVIteration] + aspirationDelta, VALUE_INFINITE);
+ alpha = Max(Rml[MultiPVIteration].prevScore - aspirationDelta, -VALUE_INFINITE);
+ beta = Min(Rml[MultiPVIteration].prevScore + aspirationDelta, VALUE_INFINITE);
}
else
{
// because 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.
+ sort<RootMove>(Rml.begin() + MultiPVIteration, Rml.end());
+
+ // In case we have found an exact score reorder the PV moves
+ // before leaving the fail high/low loop, otherwise leave the
+ // last PV move in its position so to be searched again.
if (value > alpha && value < beta)
- sort<RootMove>(Rml.begin(), Rml.end());
- else
- // In MultiPV mode, sort only the tail of the list
- // until all fail-highs and fail-lows have been resolved
- sort<RootMove>(Rml.begin() + MultiPVIteration, Rml.end());
+ sort<RootMove>(Rml.begin(), Rml.begin() + MultiPVIteration);
// Write PV back to transposition table in case the relevant entries
// have been overwritten during the search.
// Send full PV info to GUI if we are going to leave the loop or
// if we have a fail high/low and we are deep in the search.
if ((value > alpha && value < beta) || current_search_time() > 2000)
- for (int i = 0; i < Min(UCIMultiPV, (int)Rml.size()); i++)
- {
- bool updated = (i <= MultiPVIteration);
- bool match = (i == MultiPVIteration);
-
- if (!updated && depth == 1)
- continue;
-
+ for (int i = 0; i < Min(UCIMultiPV, MultiPVIteration + 1); i++)
cout << "info"
- << depth_to_uci((updated ? depth : depth - 1) * ONE_PLY)
- << score_to_uci(updated ? Rml[i].pv_score : prevValues[i],
- match ? alpha : -VALUE_INFINITE,
- match ? beta : VALUE_INFINITE)
+ << depth_to_uci(depth * ONE_PLY)
+ << (i == MultiPVIteration ? score_to_uci(Rml[i].score, alpha, beta) :
+ score_to_uci(Rml[i].score))
<< speed_to_uci(pos.nodes_searched())
- << pv_to_uci(updated ? Rml[i].pv : Rml.find(prevMoves[i])->pv,
- i + 1, pos.is_chess960())
+ << pv_to_uci(&Rml[i].pv[0], i + 1, pos.is_chess960())
<< endl;
- }
// In case of failing high/low increase aspiration window and research,
// otherwise exit the fail high/low loop.
do_skill_level(&skillBest, &skillPonder);
if (LogFile.is_open())
- LogFile << pretty_pv(pos, depth, value, current_search_time(), Rml[0].pv) << endl;
+ LogFile << pretty_pv(pos, depth, value, current_search_time(), &Rml[0].pv[0]) << endl;
// Init easyMove after first iteration or drop if differs from the best move
- if (depth == 1 && (Rml.size() == 1 || Rml[0].pv_score > Rml[1].pv_score + EasyMoveMargin))
+ if (depth == 1 && (Rml.size() == 1 || Rml[0].score > Rml[1].score + EasyMoveMargin))
easyMove = bestMove;
else if (bestMove != easyMove)
easyMove = MOVE_NONE;
template <NodeType NT>
Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) {
- const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV);
- const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV);
- const bool RootNode = (NT == Root);
+ const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot);
+ const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot);
+ const bool RootNode = (NT == Root || NT == SplitPointRoot);
assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
assert(beta > alpha && beta <= VALUE_INFINITE);
excludedMove = ss->excludedMove;
posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
tte = TT.probe(posKey);
- ttMove = tte ? tte->move() : MOVE_NONE;
+ ttMove = RootNode ? Rml[MultiPVIteration].pv[0] : tte ? tte->move() : MOVE_NONE;
// At PV nodes we check for exact scores, while at non-PV nodes we check for
// a fail high/low. Biggest advantage at probing at PV nodes is to have a
// smooth experience in analysis mode. We don't probe at Root nodes otherwise
// we should also update RootMoveList to avoid bogus output.
if (!RootNode && tte && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT
- : ok_to_use_TT(tte, depth, beta, ss->ply)))
+ : can_return_tt(tte, depth, beta, ss->ply)))
{
TT.refresh(tte);
ss->bestMove = ttMove; // Can be MOVE_NONE
split_point_start: // At split points actual search starts from here
// Initialize a MovePicker object for the current position
- MovePickerExt<NT> mp(pos, RootNode ? Rml[MultiPVIteration].pv[0] : ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta);
+ MovePickerExt<SpNode> mp(pos, ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta);
CheckInfo ci(pos);
ss->bestMove = MOVE_NONE;
futilityBase = ss->eval + ss->evalMargin;
// At root obey the "searchmoves" option and skip moves not listed in Root Move List.
// Also in MultiPV mode we skip moves which already have got an exact score
- // in previous MultiPV Iteration.
+ // in previous MultiPV Iteration. Finally any illegal move is skipped here.
if (RootNode && !Rml.find(move, MultiPVIteration))
continue;
// If it's time to send nodes info, do it here where we have the
// correct accumulated node counts searched by each thread.
- if (SendSearchedNodes)
+ if (!SpNode && SendSearchedNodes)
{
SendSearchedNodes = false;
cout << "info" << speed_to_uci(pos.nodes_searched()) << endl;
}
// For long searches send current move info to GUI
- if (current_search_time() > 2000)
+ if (pos.thread() == 0 && current_search_time() > 2000)
cout << "info" << depth_to_uci(depth)
- << " currmove " << move << " currmovenumber " << moveCount + MultiPVIteration << endl;
+ << " currmove " << move
+ << " currmovenumber " << moveCount + MultiPVIteration << endl;
}
// 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) ? MAX_MOVES : 1));
+ isPvMove = (PvNode && moveCount <= (RootNode && depth <= ONE_PLY ? MAX_MOVES : 1));
givesCheck = pos.move_gives_check(move, ci);
captureOrPromotion = pos.move_is_capture_or_promotion(move);
alpha = sp->alpha;
}
- if (value > bestValue)
- {
- bestValue = value;
- ss->bestMove = move;
-
- if ( !RootNode
- && PvNode
- && value > alpha
- && value < beta) // We want always alpha < beta
- alpha = value;
-
- if (SpNode && !thread.cutoff_occurred())
- {
- sp->bestValue = value;
- sp->ss->bestMove = move;
- sp->alpha = alpha;
- sp->is_betaCutoff = (value >= beta);
- }
- }
if (RootNode)
{
break;
// Remember searched nodes counts for this move
- Rml.find(move)->nodes += pos.nodes_searched() - nodes;
+ RootMove* rm = Rml.find(move);
+ rm->nodes += pos.nodes_searched() - nodes;
// PV move or new best move ?
if (isPvMove || value > alpha)
{
// Update PV
- Rml.find(move)->pv_score = value;
- Rml.find(move)->extract_pv_from_tt(pos);
+ rm->score = value;
+ rm->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
// the best move changes frequently, we allocate some more time.
if (!isPvMove && MultiPV == 1)
Rml.bestMoveChanges++;
-
- // Update alpha.
- if (value > alpha)
- alpha = value;
}
else
// 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.
- Rml.find(move)->pv_score = -VALUE_INFINITE;
+ rm->score = -VALUE_INFINITE;
} // RootNode
+ if (value > bestValue)
+ {
+ bestValue = value;
+ ss->bestMove = move;
+
+ if ( PvNode
+ && value > alpha
+ && value < beta) // We want always alpha < beta
+ alpha = value;
+
+ if (SpNode && !thread.cutoff_occurred())
+ {
+ sp->bestValue = value;
+ sp->ss->bestMove = move;
+ sp->alpha = alpha;
+ sp->is_betaCutoff = (value >= beta);
+ }
+ }
+
// Step 19. Check for split
if ( !RootNode
&& !SpNode
tte = TT.probe(pos.get_key());
ttMove = (tte ? tte->move() : MOVE_NONE);
- if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ss->ply))
+ if (!PvNode && tte && can_return_tt(tte, ttDepth, beta, ss->ply))
{
ss->bestMove = ttMove; // Can be MOVE_NONE
return value_from_tt(tte->value(), ss->ply);
}
- // ok_to_use_TT() returns true if a transposition table score
- // can be used at a given point in search.
+ // can_return_tt() returns true if a transposition table score
+ // can be used to cut-off at a given point in search.
- bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) {
+ bool can_return_tt(const TTEntry* tte, Depth depth, Value beta, int ply) {
Value v = value_from_tt(tte->value(), ply);
// pv_to_uci() returns a string with information on the current PV line
// formatted according to UCI specification.
- string pv_to_uci(Move pv[], int pvNum, bool chess960) {
+ string pv_to_uci(const Move pv[], int pvNum, bool chess960) {
std::stringstream s;
static RKISS rk;
- // Rml list is already sorted by pv_score in descending order
+ // Rml list is already sorted by score in descending order
int s;
int max_s = -VALUE_INFINITE;
int size = Min(MultiPV, (int)Rml.size());
- int max = Rml[0].pv_score;
- int var = Min(max - Rml[size - 1].pv_score, PawnValueMidgame);
+ int max = Rml[0].score;
+ int var = Min(max - Rml[size - 1].score, PawnValueMidgame);
int wk = 120 - 2 * SkillLevel;
// PRNG sequence should be non deterministic
// then we choose the move with the resulting highest score.
for (int i = 0; i < size; i++)
{
- s = Rml[i].pv_score;
+ s = Rml[i].score;
// Don't allow crazy blunders even at very low skills
- if (i > 0 && Rml[i-1].pv_score > s + EasyMoveMargin)
+ if (i > 0 && Rml[i-1].score > s + EasyMoveMargin)
break;
// This is our magical formula
/// RootMove and RootMoveList method's definitions
- RootMove::RootMove() {
-
- nodes = 0;
- pv_score = -VALUE_INFINITE;
- pv[0] = MOVE_NONE;
- }
-
- RootMove& RootMove::operator=(const RootMove& rm) {
-
- const Move* src = rm.pv;
- Move* dst = pv;
-
- // Avoid a costly full rm.pv[] copy
- do *dst++ = *src; while (*src++ != MOVE_NONE);
-
- nodes = rm.nodes;
- pv_score = rm.pv_score;
- return *this;
- }
-
void RootMoveList::init(Position& pos, Move searchMoves[]) {
Move* sm;
continue;
RootMove rm;
- rm.pv[0] = ml.move();
- rm.pv[1] = MOVE_NONE;
- rm.pv_score = -VALUE_INFINITE;
+ rm.pv.push_back(ml.move());
+ rm.pv.push_back(MOVE_NONE);
+ rm.score = rm.prevScore = -VALUE_INFINITE;
+ rm.nodes = 0;
push_back(rm);
}
}
- RootMove* RootMoveList::find(const Move &m, const int startIndex) {
+ RootMove* RootMoveList::find(const Move& m, int startIndex) {
- for (int i = startIndex; i < int(size()); i++)
- {
- if ((*this)[i].pv[0] == m)
- return &(*this)[i];
- }
+ for (size_t i = startIndex; i < size(); i++)
+ if ((*this)[i].pv[0] == m)
+ return &(*this)[i];
- return NULL;
+ return NULL;
}
// extract_pv_from_tt() builds a PV by adding moves from the transposition table.
StateInfo state[PLY_MAX_PLUS_2], *st = state;
TTEntry* tte;
int ply = 1;
+ Move m = pv[0];
- assert(pv[0] != MOVE_NONE && pos.move_is_pl(pv[0]));
+ assert(m != MOVE_NONE && pos.move_is_pl(m));
- pos.do_move(pv[0], *st++);
+ pv.clear();
+ pv.push_back(m);
+ pos.do_move(m, *st++);
while ( (tte = TT.probe(pos.get_key())) != NULL
&& tte->move() != MOVE_NONE
&& ply < PLY_MAX
&& (!pos.is_draw<false>() || ply < 2))
{
- pv[ply] = tte->move();
- pos.do_move(pv[ply++], *st++);
+ pv.push_back(tte->move());
+ pos.do_move(tte->move(), *st++);
+ ply++;
}
- pv[ply] = MOVE_NONE;
+ pv.push_back(MOVE_NONE);
do pos.undo_move(pv[--ply]); while (ply);
}