/*
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
/*
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
Stockfish is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
Stockfish is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
void put_threads_to_sleep();
void idle_loop(int threadID, SplitPoint* waitSp);
bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
void put_threads_to_sleep();
void idle_loop(int threadID, SplitPoint* waitSp);
bool split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue,
- Depth depth, int* moves, MovePicker* mp, int master, bool pvNode);
+ Depth depth, bool mateThreat, int* moves, MovePicker* mp, int master, bool pvNode);
- int8_t PVReductionMatrix[64][64]; // [depth][moveNumber]
- int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber]
+ int8_t PVReductionMatrix[8][64][64]; // [depth][moveNumber]
+ int8_t NonPVReductionMatrix[8][64][64]; // [depth][moveNumber]
- inline Depth pv_reduction(Depth d, int mn) { return (Depth) PVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; }
- inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; }
+ inline Depth pv_reduction(Depth d, int mn) { return (Depth) PVReductionMatrix[ReductionLevel][Min(d / 2, 63)][Min(mn, 63)]; }
+ inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[ReductionLevel][Min(d / 2, 63)][Min(mn, 63)]; }
- int RootMoveNumber, SearchStartTime, MaxNodes, MaxDepth;
- int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
+ int SearchStartTime, MaxNodes, MaxDepth, MaxSearchTime;
+ int AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
- bool AbortSearch, Quit, AspirationFailLow;
+ bool FirstRootMove, AbortSearch, Quit, AspirationFailLow;
- Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta);
+ Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE);
Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE);
Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
// Initialize global search variables
StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
// Initialize global search variables
StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
+// init_reduction_tables() is called by init_search() and initializes
+// the tables used by LMR.
+static void init_reduction_tables(int8_t pvTable[64][64], int8_t nonPvTable[64][64], int pvInhib, int nonPvInhib)
+{
+ double pvBase = 1.001 - log(3.0) * log(16.0) / pvInhib;
+ double nonPvBase = 1.001 - log(3.0) * log(4.0) / nonPvInhib;
for (int i = 1; i < 64; i++) // i == depth (OnePly = 1)
for (int j = 1; j < 64; j++) // j == moveNumber
{
for (int i = 1; i < 64; i++) // i == depth (OnePly = 1)
for (int j = 1; j < 64; j++) // j == moveNumber
{
- double pvRed = 0.5 + log(double(i)) * log(double(j)) / 6.0;
- double nonPVRed = 0.5 + log(double(i)) * log(double(j)) / 3.0;
- PVReductionMatrix[i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0);
- NonPVReductionMatrix[i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0);
+ double pvRed = pvBase + log(double(i)) * log(double(j)) / pvInhib;
+ double nonPVRed = nonPvBase + log(double(i)) * log(double(j)) / nonPvInhib;
+
+ pvTable[i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0);
+ nonPvTable[i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0);
+}
+
+// init_search() is called during startup. It initializes various lookup tables
+void init_search() {
+
+ // Init reduction lookup tables
+ for (int i = 0; i < 8; i++)
+ init_reduction_tables(PVReductionMatrix[i], NonPVReductionMatrix[i], int(4 * pow(1.3, i)), int(2 * pow(1.3, i)));
- // Search to the current depth, rml is updated and sorted
- value = root_search(p, ss, rml, alpha, beta);
+ // Choose optimum reduction level
+ ReductionLevel = 2;
+
+ if (UseTimeManagement)
+ {
+ int level = int(floor(log(float(MaxSearchTime) / current_search_time()) / log(2.0) + 1.0));
+ ReductionLevel = Min(Max(level, 0), 7);
+ }
+ else
+ {
+ //FIXME
+ }
+
+ // Search to the current depth, rml is updated and sorted, alpha and beta could change
+ value = root_search(p, ss, rml, &alpha, &beta);
// Write PV to transposition table, in case the relevant entries have
// been overwritten during the search.
// Write PV to transposition table, in case the relevant entries have
// been overwritten during the search.
// scheme, prints some information to the standard output and handles
// the fail low/high loops.
// 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& oldAlpha, Value& beta) {
+ Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
- // Evaluate the position statically
- ss[0].eval = !isCheck ? evaluate(pos, ei, 0) : VALUE_NONE;
+ // Step 1. Initialize node and poll (omitted at root, but I can see no good reason for this, FIXME)
+ // Step 2. Check for aborted search (omitted at root, because we do not initialize root node)
+ // Step 3. Mate distance pruning (omitted at root)
+ // Step 4. Transposition table lookup (omitted at root)
+
+ // Step 5. Evaluate the position statically
+ // At root we do this only to get reference value for child nodes
+ if (!isCheck)
+ ss[0].eval = evaluate(pos, ei, 0);
+ else
+ ss[0].eval = VALUE_NONE; // HACK because we do not initialize root node
- while (1) // Fail low loop
+ // Step 6. Razoring (omitted at root)
+ // Step 7. Static null move pruning (omitted at root)
+ // Step 8. Null move search with verification search (omitted at root)
+ // Step 9. Internal iterative deepening (omitted at root)
+
+ // Step extra. Fail low loop
+ // We start with small aspiration window and in case of fail low, we research
+ // with bigger window until we are not failing low anymore.
+ while (1)
- if (alpha >= beta)
- {
- // We failed high, invalidate and skip next moves, leave node-counters
- // and beta-counters as they are and quickly return, we will try to do
- // a research at the next iteration with a bigger aspiration window.
- rml.set_move_score(i, -VALUE_INFINITE);
- continue;
- }
-
- // This is used by time management and starts from 1
- RootMoveNumber = i + 1;
+ // This is used by time management
+ FirstRootMove = (i == 0);
depth = (Iteration - 2) * OnePly + InitialDepth;
ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
newDepth = depth + ext;
depth = (Iteration - 2) * OnePly + InitialDepth;
ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
newDepth = depth + ext;
- // Reset value before the search
+ // Step 12. Futility pruning (omitted at root)
+
+ // Step extra. Fail high loop
+ // If move fails high, we research with bigger window until we are not failing
+ // high anymore.
pos.do_move(move, st, ci, moveIsCheck);
pos.do_move(move, st, ci, moveIsCheck);
- // Try to reduce non-pv search depth by one ply if move seems not problematic,
- // if the move fails high will be re-searched at full depth.
+ // Step 14. Reduced search
+ // if the move fails high will be re-searched at full depth
print_pv_info(pos, ss, alpha, beta, value);
// Prepare for a research after a fail high, each time with a wider window
print_pv_info(pos, ss, alpha, beta, value);
// Prepare for a research after a fail high, each time with a wider window
rml.set_move_nodes(i, TM.nodes_searched() - nodes);
assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
rml.set_move_nodes(i, TM.nodes_searched() - nodes);
assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
if (value <= alpha && i >= MultiPV)
rml.set_move_score(i, -VALUE_INFINITE);
else
if (value <= alpha && i >= MultiPV)
rml.set_move_score(i, -VALUE_INFINITE);
else
// Print information to the standard output
print_pv_info(pos, ss, alpha, beta, value);
// Print information to the standard output
print_pv_info(pos, ss, alpha, beta, value);
&& !AbortSearch
&& !TM.thread_should_stop(threadID)
&& TM.split(pos, ss, ply, &alpha, beta, &bestValue,
&& !AbortSearch
&& !TM.thread_should_stop(threadID)
&& TM.split(pos, ss, ply, &alpha, beta, &bestValue,
- depth, &moveCount, &mp, threadID, true))
+ depth, mateThreat, &moveCount, &mp, threadID, true))
Value rbeta = beta - razor_margin(depth);
Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
if (v < rbeta)
Value rbeta = beta - razor_margin(depth);
Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
if (v < rbeta)
// Do zugzwang verification search
Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
if (v >= beta)
// Do zugzwang verification search
Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
if (v >= beta)
} else {
// The null move failed low, which means that we may be faced with
// some kind of threat. If the previous move was reduced, check if
} else {
// The null move failed low, which means that we may be faced with
// some kind of threat. If the previous move was reduced, check if
&& !AbortSearch
&& !TM.thread_should_stop(threadID)
&& TM.split(pos, ss, ply, NULL, beta, &bestValue,
&& !AbortSearch
&& !TM.thread_should_stop(threadID)
&& TM.split(pos, ss, ply, NULL, beta, &bestValue,
- depth, &moveCount, &mp, threadID, false))
+ depth, mateThreat, &moveCount, &mp, threadID, false))
// splitting, we don't have to repeat all this work in sp_search(). We
// also don't need to store anything to the hash table here: This is taken
// care of after we return from the split point.
// splitting, we don't have to repeat all this work in sp_search(). We
// also don't need to store anything to the hash table here: This is taken
// care of after we return from the split point.
- ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous);
+ ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
// don't have to repeat all this work in sp_search_pv(). We also don't
// need to store anything to the hash table here: This is taken care of
// after we return from the split point.
// don't have to repeat all this work in sp_search_pv(). We also don't
// need to store anything to the hash table here: This is taken care of
// after we return from the split point.
- ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
+ ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous);
bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply,
Value* alpha, const Value beta, Value* bestValue,
bool ThreadsManager::split(const Position& p, SearchStack* sstck, int ply,
Value* alpha, const Value beta, Value* bestValue,
- Depth depth, int* moves, MovePicker* mp, int master, bool pvNode) {
+ Depth depth, bool mateThreat, int* moves, MovePicker* mp, int master, bool pvNode) {