RootMoveList Rml;
// MultiPV mode
- int MultiPV;
+ int MultiPV, UCIMultiPV;
// Time management variables
int SearchStartTime, MaxNodes, MaxDepth, ExactMaxTime;
bool UseLogFile;
std::ofstream LogFile;
+ // Skill level adjustment
+ int SkillLevel;
+ RKISS RK;
+
// Multi-threads manager object
ThreadsManager ThreadsMgr;
bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue);
bool connected_moves(const Position& pos, Move m1, Move m2);
- bool value_is_mate(Value value);
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 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 update_killers(Move m, Move killers[]);
void update_gains(const Position& pos, Move move, Value before, Value after);
- void qsearch_scoring(Position& pos, MoveStack* mlist, MoveStack* last);
int current_search_time();
std::string value_to_uci(Value v);
PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value<Depth>();
MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value<Depth>();
MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value<Depth>();
- MultiPV = Options["MultiPV"].value<int>();
+ UCIMultiPV = Options["MultiPV"].value<int>();
+ SkillLevel = Options["Skill level"].value<int>();
UseLogFile = Options["Use Search Log"].value<bool>();
read_evaluation_uci_options(pos.side_to_move());
+ // Do we have to play with skill handicap? In this case enable MultiPV that
+ // we will use behind the scenes to retrieve a set of possible moves.
+ MultiPV = (SkillLevel < 20 ? Max(UCIMultiPV, 4) : UCIMultiPV);
+
// Set the number of active threads
ThreadsMgr.read_uci_options();
init_eval(ThreadsMgr.active_threads());
if (!StopRequest && (Pondering || InfiniteSearch))
wait_for_stop_or_ponderhit();
- // Could be both MOVE_NONE when searching on a stalemate position
- cout << "bestmove " << bestMove << " ponder " << ponderMove << endl;
+ // Could be MOVE_NONE when searching on a stalemate position
+ cout << "bestmove " << bestMove;
+
+ // UCI protol is not clear on allowing sending an empty ponder move, instead
+ // it is clear that ponder move is optional. So skip it if empty.
+ if (ponderMove != MOVE_NONE)
+ cout << " ponder " << ponderMove;
+
+ cout << endl;
return !QuitRequest;
}
SearchStack ss[PLY_MAX_PLUS_2];
Value bestValues[PLY_MAX_PLUS_2];
int bestMoveChanges[PLY_MAX_PLUS_2];
- int depth, researchCountFL, researchCountFH, aspirationDelta;
+ int depth, aspirationDelta;
Value value, alpha, beta;
Move bestMove, easyMove;
- // Moves to search are verified, scored and sorted
- Rml.init(pos, searchMoves);
-
- // Initialize FIXME move before Rml.init()
+ // Initialize stuff before a new search
+ memset(ss, 0, 4 * sizeof(SearchStack));
TT.new_search();
H.clear();
- memset(ss, 0, 4 * sizeof(SearchStack));
*ponderMove = bestMove = easyMove = MOVE_NONE;
depth = aspirationDelta = 0;
- ss->currentMove = MOVE_NULL; // Hack to skip update_gains()
alpha = -VALUE_INFINITE, beta = VALUE_INFINITE;
+ ss->currentMove = MOVE_NULL; // Hack to skip update_gains()
+
+ // Moves to search are verified and copied
+ Rml.init(pos, searchMoves);
// Handle special case of searching on a mate/stalemate position
if (Rml.size() == 0)
return MOVE_NONE;
}
- // Is one move significantly better than others after initial scoring ?
- if ( Rml.size() == 1
- || Rml[0].pv_score > Rml[1].pv_score + EasyMoveMargin)
- easyMove = Rml[0].pv[0];
-
// Iterative deepening loop
while (++depth <= PLY_MAX && (!MaxDepth || depth <= MaxDepth) && !StopRequest)
{
- Rml.bestMoveChanges = researchCountFL = researchCountFH = 0;
- cout << "info depth " << depth << endl;
+ Rml.bestMoveChanges = 0;
+ cout << set960(pos.is_chess960()) << "info depth " << depth << endl;
// Calculate dynamic aspiration window based on previous iterations
if (MultiPV == 1 && depth >= 5 && abs(bestValues[depth - 1]) < VALUE_KNOWN_WIN)
// Start with a small aspiration window and, in case of fail high/low,
// research with bigger window until not failing high/low anymore.
- while (true)
- {
+ do {
// Search starting from ss+1 to allow calling update_gains()
value = search<PV, false, true>(pos, ss+1, alpha, beta, depth * ONE_PLY, 0);
- // Send PV line to GUI and write to transposition table in case the
- // relevant entries have been overwritten during the search.
+ // Write PV back to transposition table in case the relevant entries
+ // have been overwritten during the search.
for (int i = 0; i < Min(MultiPV, (int)Rml.size()); i++)
- {
Rml[i].insert_pv_in_tt(pos);
- cout << set960(pos.is_chess960())
- << Rml[i].pv_info_to_uci(pos, depth, alpha, beta, i) << endl;
- }
// Value cannot be trusted. Break out immediately!
if (StopRequest)
// otherwise exit the fail high/low loop.
if (value >= beta)
{
- beta = Min(beta + aspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
- researchCountFH++;
+ beta = Min(beta + aspirationDelta, VALUE_INFINITE);
+ aspirationDelta += aspirationDelta / 2;
}
else if (value <= alpha)
{
AspirationFailLow = true;
StopOnPonderhit = false;
- alpha = Max(alpha - aspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
- researchCountFL++;
+ alpha = Max(alpha - aspirationDelta, -VALUE_INFINITE);
+ aspirationDelta += aspirationDelta / 2;
}
else
break;
- }
+
+ } while (abs(value) < VALUE_KNOWN_WIN);
// Collect info about search result
bestMove = Rml[0].pv[0];
+ *ponderMove = Rml[0].pv[1];
bestValues[depth] = value;
bestMoveChanges[depth] = Rml.bestMoveChanges;
+ // Send PV line to GUI and to log file
+ for (int i = 0; i < Min(UCIMultiPV, (int)Rml.size()); i++)
+ cout << Rml[i].pv_info_to_uci(pos, depth, alpha, beta, i) << endl;
+
if (UseLogFile)
LogFile << pretty_pv(pos, depth, value, current_search_time(), Rml[0].pv) << endl;
- // Drop the easy move if differs from the new best move
- if (bestMove != easyMove)
+ // 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))
+ easyMove = bestMove;
+ else if (bestMove != easyMove)
easyMove = MOVE_NONE;
if (UseTimeManagement && !StopRequest)
}
}
- *ponderMove = Rml[0].pv[1];
+ // When playing with strength handicap choose best move among the MultiPV set
+ // using a statistical rule dependent on SkillLevel. Idea by Heinz van Saanen.
+ if (SkillLevel < 20)
+ {
+ assert(MultiPV > 1);
+
+ // Rml list is already sorted by pv_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 wk = 120 - 2 * SkillLevel;
+
+ // PRNG sequence should be non deterministic
+ for (int i = abs(get_system_time() % 50); i > 0; i--)
+ RK.rand<unsigned>();
+
+ // Choose best move. For each move's score we add two terms both dependent
+ // on wk, one deterministic and bigger for weaker moves, and one random,
+ // then we choose the move with the resulting highest score.
+ for (int i = 0; i < size; i++)
+ {
+ s = Rml[i].pv_score;
+
+ // Don't allow crazy blunders even at very low skills
+ if (i > 0 && Rml[i-1].pv_score > s + EasyMoveMargin)
+ break;
+
+ // This is our magical formula
+ s += ((max - s) * wk + var * (RK.rand<unsigned>() % wk)) / 128;
+
+ if (s > max_s)
+ {
+ max_s = s;
+ bestMove = Rml[i].pv[0];
+ *ponderMove = Rml[i].pv[1];
+ }
+ }
+ }
+
return bestMove;
}
&& !isCheck
&& refinedValue < beta - razor_margin(depth)
&& ttMove == MOVE_NONE
- && !value_is_mate(beta)
+ && abs(beta) < VALUE_MATE_IN_PLY_MAX
&& !pos.has_pawn_on_7th(pos.side_to_move()))
{
Value rbeta = beta - razor_margin(depth);
&& depth < RazorDepth
&& !isCheck
&& refinedValue >= beta + futility_margin(depth, 0)
- && !value_is_mate(beta)
+ && abs(beta) < VALUE_MATE_IN_PLY_MAX
&& pos.non_pawn_material(pos.side_to_move()))
return refinedValue - futility_margin(depth, 0);
&& depth > ONE_PLY
&& !isCheck
&& refinedValue >= beta
- && !value_is_mate(beta)
+ && abs(beta) < VALUE_MATE_IN_PLY_MAX
&& pos.non_pawn_material(pos.side_to_move()))
{
ss->currentMove = MOVE_NULL;
if (nullValue >= beta)
{
// Do not return unproven mate scores
- if (nullValue >= value_mate_in(PLY_MAX))
+ if (nullValue >= VALUE_MATE_IN_PLY_MAX)
nullValue = beta;
if (depth < 6 * ONE_PLY)
<< " currmovenumber " << moveCount << endl;
}
- isPvMove = (PvNode && moveCount <= (Root ? MultiPV : 1));
+ // At Root and at first iteration do a PV search on all the moves
+ // to score root moves. Otherwise only the first one is the PV.
+ isPvMove = (PvNode && moveCount <= (Root ? MultiPV + 1000 * (depth <= ONE_PLY) : 1));
moveIsCheck = pos.move_is_check(move, ci);
captureOrPromotion = pos.move_is_capture_or_promotion(move);
if (abs(ttValue) < VALUE_KNOWN_WIN)
{
- Value b = ttValue - depth;
+ Value b = ttValue - int(depth);
ss->excludedMove = move;
ss->skipNullMove = true;
Value v = search<NonPV>(pos, ss, b - 1, b, depth / 2, ply);
// Move count based pruning
if ( moveCount >= futility_move_count(depth)
&& !(threatMove && connected_threat(pos, move, threatMove))
- && bestValue > value_mated_in(PLY_MAX)) // FIXME bestValue is racy
+ && bestValue > VALUE_MATED_IN_PLY_MAX) // FIXME bestValue is racy
{
if (SpNode)
lock_grab(&(sp->lock));
// Prune moves with negative SEE at low depths
if ( predictedDepth < 2 * ONE_PLY
- && bestValue > value_mated_in(PLY_MAX)
+ && bestValue > VALUE_MATED_IN_PLY_MAX
&& pos.see_sign(move) < 0)
{
if (SpNode)
if ( bestValue >= beta
&& !pos.move_is_capture_or_promotion(move))
{
+ if (move != ss->killers[0])
+ {
+ ss->killers[1] = ss->killers[0];
+ ss->killers[0] = move;
+ }
update_history(pos, move, depth, movesSearched, playedMoveCount);
- update_killers(move, ss->killers);
}
}
// Prune moves with negative or equal SEE
if ( futilityBase < beta
&& depth < DEPTH_ZERO
- && bestValue > value_mated_in(PLY_MAX)
&& pos.see(move) <= 0)
continue;
}
// Detect non-capture evasions that are candidate to be pruned
evasionPrunable = isCheck
- && bestValue > value_mated_in(PLY_MAX)
+ && bestValue > VALUE_MATED_IN_PLY_MAX
&& !pos.move_is_capture(move)
&& !pos.can_castle(pos.side_to_move());
}
- // qsearch_scoring() scores each move of a list using a qsearch() evaluation,
- // it is used in RootMoveList to get an initial scoring.
- void qsearch_scoring(Position& pos, MoveStack* mlist, MoveStack* last) {
-
- SearchStack ss[PLY_MAX_PLUS_2];
- StateInfo st;
-
- memset(ss, 0, 4 * sizeof(SearchStack));
- ss[0].eval = ss[0].evalMargin = VALUE_NONE;
-
- for (MoveStack* cur = mlist; cur != last; cur++)
- {
- ss[0].currentMove = cur->move;
- pos.do_move(cur->move, st);
- cur->score = -qsearch<PV>(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, DEPTH_ZERO, 1);
- pos.undo_move(cur->move);
- }
- }
-
-
// check_is_dangerous() tests if a checking move can be pruned in qsearch().
// bestValue is updated only when returning false because in that case move
// will be pruned.
}
- // value_is_mate() checks if the given value is a mate one eventually
- // compensated for the ply.
-
- bool value_is_mate(Value value) {
-
- assert(abs(value) <= VALUE_INFINITE);
-
- return value <= value_mated_in(PLY_MAX)
- || value >= value_mate_in(PLY_MAX);
- }
-
-
// value_to_tt() adjusts a mate score from "plies to mate from the root" to
// "plies to mate from the current ply". Non-mate scores are unchanged.
// The function is called before storing a value to the transposition table.
Value value_to_tt(Value v, int ply) {
- if (v >= value_mate_in(PLY_MAX))
+ if (v >= VALUE_MATE_IN_PLY_MAX)
return v + ply;
- if (v <= value_mated_in(PLY_MAX))
+ if (v <= VALUE_MATED_IN_PLY_MAX)
return v - ply;
return v;
Value value_from_tt(Value v, int ply) {
- if (v >= value_mate_in(PLY_MAX))
+ if (v >= VALUE_MATE_IN_PLY_MAX)
return v - ply;
- if (v <= value_mated_in(PLY_MAX))
+ if (v <= VALUE_MATED_IN_PLY_MAX)
return v + ply;
return v;
Value v = value_from_tt(tte->value(), ply);
return ( tte->depth() >= depth
- || v >= Max(value_mate_in(PLY_MAX), beta)
- || v < Min(value_mated_in(PLY_MAX), beta))
+ || v >= Max(VALUE_MATE_IN_PLY_MAX, beta)
+ || v < Min(VALUE_MATED_IN_PLY_MAX, beta))
&& ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta)
|| ((tte->type() & VALUE_TYPE_UPPER) && v < beta));
}
- // update_killers() add a good move that produced a beta-cutoff
- // among the killer moves of that ply.
-
- void update_killers(Move m, Move killers[]) {
-
- if (m != killers[0])
- {
- killers[1] = killers[0];
- killers[0] = m;
- }
- }
-
-
// update_gains() updates the gains table of a non-capture move given
// the static position evaluation before and after the move.
H.update_gain(pos.piece_on(move_to(m)), move_to(m), -(before + after));
}
+
// current_search_time() returns the number of milliseconds which have passed
// since the beginning of the current search.
if (abs(v) < VALUE_MATE - PLY_MAX * ONE_PLY)
s << "cp " << int(v) * 100 / int(PawnValueMidgame); // Scale to centipawns
else
- s << "mate " << (v > 0 ? (VALUE_MATE - v + 1) / 2 : -(VALUE_MATE + v) / 2);
+ s << "mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2;
return s.str();
}
// We are line oriented, don't read single chars
std::string command;
- if (!std::getline(std::cin, command))
- command = "quit";
-
- if (command == "quit")
+ if (!std::getline(std::cin, command) || command == "quit")
{
// Quit the program as soon as possible
Pondering = false;
std::string command;
- while (true)
- {
- // Wait for a command from stdin
- if (!std::getline(std::cin, command))
- command = "quit";
+ // Wait for a command from stdin
+ while ( std::getline(std::cin, command)
+ && command != "ponderhit" && command != "stop" && command != "quit") {};
- if (command == "quit")
- {
- QuitRequest = true;
- break;
- }
- else if (command == "ponderhit" || command == "stop")
- break;
- }
+ if (command != "ponderhit" && command != "stop")
+ QuitRequest = true; // Must be "quit" or getline() returned false
}
clear();
bestMoveChanges = 0;
- // Generate all legal moves and score them
+ // Generate all legal moves and add them to RootMoveList
MoveStack* last = generate<MV_LEGAL>(pos, mlist);
- qsearch_scoring(pos, mlist, last);
-
- // Add each move to the RootMoveList's vector
for (MoveStack* cur = mlist; cur != last; cur++)
{
// If we have a searchMoves[] list then verify cur->move
RootMove rm;
rm.pv[0] = cur->move;
rm.pv[1] = MOVE_NONE;
- rm.pv_score = Value(cur->score);
+ rm.pv_score = -VALUE_INFINITE;
push_back(rm);
}
- sort();
}
} // namespace