/// Local functions
Value id_loop(const Position& pos, Move searchMoves[]);
- Value root_search(Position& pos, SearchStack* ss, RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
+ Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
template <NodeType PvNode>
Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply);
template <NodeType PvNode>
Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous);
- void update_pv(SearchStack* ss);
- void sp_update_pv(SearchStack* pss, SearchStack* ss);
bool connected_moves(const Position& pos, Move m1, Move m2);
bool value_is_mate(Value value);
bool move_is_killer(Move m, SearchStack* ss);
void ponderhit();
void wait_for_stop_or_ponderhit();
void init_ss_array(SearchStack* ss, int size);
- void print_pv_info(const Position& pos, SearchStack* ss, Value alpha, Value beta, Value value);
+ void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value);
#if !defined(_MSC_VER)
void *init_thread(void *threadID);
// Called at the beginning of search() when starting to examine a new node.
void SearchStack::init() {
- pv[0] = pv[1] = MOVE_NONE;
- currentMove = threatMove = MOVE_NONE;
+ currentMove = threatMove = bestMove = MOVE_NONE;
reduction = Depth(0);
eval = VALUE_NONE;
}
Position p(pos, pos.thread());
SearchStack ss[PLY_MAX_PLUS_2];
+ Move pv[PLY_MAX_PLUS_2];
Move EasyMove = MOVE_NONE;
Value value, alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
TT.new_search();
H.clear();
init_ss_array(ss, PLY_MAX_PLUS_2);
+ pv[0] = pv[1] = MOVE_NONE;
ValueByIteration[1] = rml.get_move_score(0);
Iteration = 1;
}
// Search to the current depth, rml is updated and sorted, alpha and beta could change
- value = root_search(p, ss, rml, &alpha, &beta);
+ value = root_search(p, ss, pv, rml, &alpha, &beta);
// Write PV to transposition table, in case the relevant entries have
// been overwritten during the search.
- TT.insert_pv(p, ss->pv);
+ TT.insert_pv(p, pv);
if (AbortSearch)
break; // Value cannot be trusted. Break out immediately!
ValueByIteration[Iteration] = value;
// Drop the easy move if differs from the new best move
- if (ss->pv[0] != EasyMove)
+ if (pv[0] != EasyMove)
EasyMove = MOVE_NONE;
if (UseTimeManagement)
// Stop search early if one move seems to be much better than the others
int64_t nodes = TM.nodes_searched();
if ( Iteration >= 8
- && EasyMove == ss->pv[0]
+ && EasyMove == pv[0]
&& ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100
&& current_search_time() > MaxSearchTime / 16)
||( rml.get_move_cumulative_nodes(0) > (nodes * 98) / 100
<< " hashfull " << TT.full() << endl;
// Print the best move and the ponder move to the standard output
- if (ss->pv[0] == MOVE_NONE)
+ if (pv[0] == MOVE_NONE)
{
- ss->pv[0] = rml.get_move(0);
- ss->pv[1] = MOVE_NONE;
+ pv[0] = rml.get_move(0);
+ pv[1] = MOVE_NONE;
}
- assert(ss->pv[0] != MOVE_NONE);
+ assert(pv[0] != MOVE_NONE);
- cout << "bestmove " << ss->pv[0];
+ cout << "bestmove " << pv[0];
- if (ss->pv[1] != MOVE_NONE)
- cout << " ponder " << ss->pv[1];
+ if (pv[1] != MOVE_NONE)
+ cout << " ponder " << pv[1];
cout << endl;
LogFile << "\nNodes: " << TM.nodes_searched()
<< "\nNodes/second: " << nps()
- << "\nBest move: " << move_to_san(p, ss->pv[0]);
+ << "\nBest move: " << move_to_san(p, pv[0]);
StateInfo st;
- p.do_move(ss->pv[0], st);
+ p.do_move(pv[0], st);
LogFile << "\nPonder move: "
- << move_to_san(p, ss->pv[1]) // Works also with MOVE_NONE
+ << move_to_san(p, pv[1]) // Works also with MOVE_NONE
<< endl;
}
return rml.get_move_score(0);
// scheme, prints some information to the standard output and handles
// the fail low/high loops.
- Value root_search(Position& pos, SearchStack* ss, RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
+ Value root_search(Position& pos, SearchStack* ss, Move* pv, RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
EvalInfo ei;
StateInfo st;
// We are failing high and going to do a research. It's important to update
// the score before research in case we run out of time while researching.
rml.set_move_score(i, value);
- update_pv(ss);
- TT.extract_pv(pos, ss->pv, PLY_MAX);
- rml.set_move_pv(i, ss->pv);
+ ss->bestMove = move;
+ TT.extract_pv(pos, move, pv, PLY_MAX);
+ rml.set_move_pv(i, pv);
// Print information to the standard output
- print_pv_info(pos, ss, alpha, beta, value);
+ print_pv_info(pos, pv, alpha, beta, value);
// Prepare for a research after a fail high, each time with a wider window
*betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
// Update PV
rml.set_move_score(i, value);
- update_pv(ss);
- TT.extract_pv(pos, ss->pv, PLY_MAX);
- rml.set_move_pv(i, ss->pv);
+ ss->bestMove = move;
+ TT.extract_pv(pos, move, pv, PLY_MAX);
+ rml.set_move_pv(i, pv);
if (MultiPV == 1)
{
BestMoveChangesByIteration[Iteration]++;
// Print information to the standard output
- print_pv_info(pos, ss, alpha, beta, value);
+ print_pv_info(pos, pv, alpha, beta, value);
// Raise alpha to setup proper non-pv search upper bound
if (value > alpha)
search<PvNode>(pos, ss, alpha, beta, d, ply);
ss->skipNullMove = false;
- ttMove = ss->pv[0];
+ ttMove = ss->bestMove;
tte = TT.retrieve(posKey);
}
if (PvNode && value < beta) // This guarantees that always: alpha < beta
alpha = value;
- update_pv(ss);
-
if (value == value_mate_in(ply + 1))
ss->mateKiller = move;
+
+ ss->bestMove = move;
}
}
if (AbortSearch || TM.thread_should_stop(threadID))
return bestValue;
- if (bestValue <= oldAlpha)
- TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]);
+ ValueType f = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
+ move = (bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove);
+ TT.store(posKey, value_to_tt(bestValue, ply), f, depth, move, ss->eval, ei.kingDanger[pos.side_to_move()]);
- else if (bestValue >= beta)
+ // Update killers and history only for non capture moves that fails high
+ if (bestValue >= beta)
{
TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
- move = ss->pv[0];
- TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move, ss->eval, ei.kingDanger[pos.side_to_move()]);
if (!pos.move_is_capture_or_promotion(move))
{
update_history(pos, move, depth, movesSearched, moveCount);
update_killers(move, ss);
}
}
- else
- TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss->pv[0], ss->eval, ei.kingDanger[pos.side_to_move()]);
assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
Value oldAlpha = alpha;
TM.incrementNodeCounter(pos.thread());
- ss->pv[0] = ss->pv[1] = ss->currentMove = MOVE_NONE;
+ ss->bestMove = ss->currentMove = MOVE_NONE;
ss->eval = VALUE_NONE;
// Check for an instant draw or maximum ply reached
if (value > alpha)
{
alpha = value;
- update_pv(ss);
+ ss->bestMove = move;
}
}
}
// Update transposition table
Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
- if (bestValue <= oldAlpha)
- TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, d, MOVE_NONE, ss->eval, ei.kingDanger[pos.side_to_move()]);
- else if (bestValue >= beta)
- {
- move = ss->pv[0];
- TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move, ss->eval, ei.kingDanger[pos.side_to_move()]);
+ ValueType f = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT);
+ TT.store(pos.get_key(), value_to_tt(bestValue, ply), f, d, ss->bestMove, ss->eval, ei.kingDanger[pos.side_to_move()]);
- // Update killers only for good checking moves
- if (!pos.move_is_capture_or_promotion(move))
- update_killers(move, ss);
- }
- else
- TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, d, ss->pv[0], ss->eval, ei.kingDanger[pos.side_to_move()]);
+ // Update killers only for checking moves that fails high
+ if ( bestValue >= beta
+ && !pos.move_is_capture_or_promotion(ss->bestMove))
+ update_killers(ss->bestMove, ss);
assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
if (PvNode && value < sp->beta) // This guarantees that always: sp->alpha < sp->beta
sp->alpha = value;
- sp_update_pv(sp->parentSstack, ss);
+ sp->parentSstack->bestMove = ss->bestMove = move;
}
}
}
lock_release(&(sp->lock));
}
- // update_pv() is called whenever a search returns a value > alpha.
- // It updates the PV in the SearchStack object corresponding to the
- // current node.
-
- void update_pv(SearchStack* ss) {
-
- Move* src = (ss+1)->pv;
- Move* dst = ss->pv;
-
- *dst = ss->currentMove;
-
- do
- *++dst = *src;
- while (*src++ != MOVE_NONE);
- }
-
-
- // sp_update_pv() is a variant of update_pv for use at split points. The
- // difference between the two functions is that sp_update_pv also updates
- // the PV at the parent node.
-
- void sp_update_pv(SearchStack* pss, SearchStack* ss) {
-
- Move* src = (ss+1)->pv;
- Move* dst = ss->pv;
- Move* pdst = pss->pv;
-
- *dst = *pdst = ss->currentMove;
-
- do
- *++dst = *++pdst = *src;
- while (*src++ != MOVE_NONE);
- }
-
// connected_moves() tests whether two moves are 'connected' in the sense
// that the first move somehow made the second move possible (for instance
if (*dangerous)
{
- if (moveIsCheck && pos.see_sign(m)>= 0)
+ if (moveIsCheck && pos.see_sign(m) >= 0)
result += CheckExtension[PvNode];
if (singleEvasion)
// print_pv_info() prints to standard output and eventually to log file information on
// the current PV line. It is called at each iteration or after a new pv is found.
- void print_pv_info(const Position& pos, SearchStack* ss, Value alpha, Value beta, Value value) {
+ void print_pv_info(const Position& pos, Move pv[], Value alpha, Value beta, Value value) {
cout << "info depth " << Iteration
- << " score " << value_to_string(value)
- << ((value >= beta) ? " lowerbound" :
- ((value <= alpha)? " upperbound" : ""))
+ << " score " << value_to_string(value)
+ << (value >= beta ? " lowerbound" : value <= alpha ? " upperbound" : "")
<< " time " << current_search_time()
<< " nodes " << TM.nodes_searched()
<< " nps " << nps()
<< " pv ";
- for (int j = 0; ss->pv[j] != MOVE_NONE && j < PLY_MAX; j++)
- cout << ss->pv[j] << " ";
+ for (Move* m = pv; *m != MOVE_NONE; m++)
+ cout << *m << " ";
cout << endl;
if (UseLogFile)
{
- ValueType type = (value >= beta ? VALUE_TYPE_LOWER
- : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT));
+ ValueType t = value >= beta ? VALUE_TYPE_LOWER :
+ value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT;
LogFile << pretty_pv(pos, current_search_time(), Iteration,
- TM.nodes_searched(), value, type, ss->pv) << endl;
+ TM.nodes_searched(), value, t, pv) << endl;
}
}