int32_t FutilityMarginsMatrix[16][64]; // [depth][moveNumber]
int FutilityMoveCountArray[32]; // [depth]
- inline Value futility_margin(Depth d, int mn) { return Value(d < 7 * OnePly ? FutilityMarginsMatrix[Max(d, 0)][Min(mn, 63)] : 2 * VALUE_INFINITE); }
+ inline Value futility_margin(Depth d, int mn) { return Value(d < 7 * OnePly ? FutilityMarginsMatrix[Max(d, 1)][Min(mn, 63)] : 2 * VALUE_INFINITE); }
inline int futility_move_count(Depth d) { return d < 16 * OnePly ? FutilityMoveCountArray[d] : 512; }
// Step 14. Reduced search
const Value EasyMoveMargin = Value(0x200);
// Last seconds noise filtering (LSN)
- const bool UseLSNFiltering = false;
+ const bool UseLSNFiltering = true;
const int LSNTime = 100; // In milliseconds
const Value LSNValue = value_from_centipawns(200);
bool loseOnTime = false;
/// 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);
}
// Init futility margins array
- for (d = 0; d < 16; d++) for (mc = 0; mc < 64; mc++)
+ for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
FutilityMarginsMatrix[d][mc] = 112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45;
// Init futility move count array
// Called at the beginning of search() when starting to examine a new node.
void SearchStack::init() {
- pv[0] = pv[1] = bestMove = 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)
Depth ext, newDepth;
Value bestValue, value, oldAlpha;
Value refinedValue, nullValue, futilityValueScaled; // Non-PV specific
- bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
+ bool isCheck, singleEvasion, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
bool mateThreat = false;
int moveCount = 0;
int threadID = pos.thread();
// Initialize a MovePicker object for the current position
MovePicker mp = MovePicker(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta));
CheckInfo ci(pos);
- bool singularExtensionNode = depth >= SingularExtensionDepth[PvNode]
- && tte && tte->move()
- && !excludedMove // Do not allow recursive singular extension search
- && is_lower_bound(tte->type())
- && tte->depth() >= depth - 3 * OnePly;
+ singleEvasion = isCheck && mp.number_of_evasions() == 1;
+ singularExtensionNode = depth >= SingularExtensionDepth[PvNode]
+ && tte && tte->move()
+ && !excludedMove // Do not allow recursive singular extension search
+ && is_lower_bound(tte->type())
+ && tte->depth() >= depth - 3 * OnePly;
// Step 10. Loop through moves
// Loop through all legal moves until no moves remain or a beta cutoff occurs
if (move == excludedMove)
continue;
- singleEvasion = (isCheck && mp.number_of_evasions() == 1);
moveIsCheck = pos.move_is_check(move, ci);
captureOrPromotion = pos.move_is_capture_or_promotion(move);
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;
}
}
Value oldAlpha = alpha;
TM.incrementNodeCounter(pos.thread());
- ss->pv[0] = ss->pv[1] = ss->bestMove = 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;
}
}
}
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->bestMove = 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 = pss->bestMove = ss->bestMove = 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
// 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;
}
}