/*
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
- Copyright (C) 2008-2009 Marco Costalba
+ Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad
Stockfish is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
// Step 14. Reduced search
// Reduction lookup tables (initialized at startup) and their getter functions
- 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[0][Min(d / 2, 63)][Min(mn, 63)]; }
+ inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[0][Min(d / 2, 63)][Min(mn, 63)]; }
// Common adjustments
/// Local functions
Value id_loop(const Position& pos, Move searchMoves[]);
- 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);
// Initialize global search variables
StopOnPonderhit = AbortSearch = Quit = AspirationFailLow = false;
+ MaxSearchTime = AbsoluteMaxSearchTime = ExtraSearchTime = 0;
NodesSincePoll = 0;
TM.resetNodeCounters();
SearchStartTime = get_system_time();
{
TM.set_active_threads(newActiveThreads);
init_eval(TM.active_threads());
- // HACK: init_eval() destroys the static castleRightsMask[] array in the
- // Position class. The below line repairs the damage.
- Position p(pos.to_fen());
- assert(pos.is_ok());
}
// Wake up sleeping threads
return !Quit;
}
+// init_reduction_tables()
-/// init_search() is called during startup. It initializes various lookup tables
-
-void init_search() {
+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;
- // Init our reduction lookup tables
+ // Init reduction lookup tables
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() {
+
+ for (int i = 0; i < 8; i++)
+ init_reduction_tables(PVReductionMatrix[i], NonPVReductionMatrix[i], 4.0 * pow(1.3, i), 2.0 * pow(1.3, i));
// Init futility margins array
for (int i = 0; i < 16; i++) // i == depth (OnePly = 2)
// Initialize iteration
Iteration++;
BestMoveChangesByIteration[Iteration] = 0;
- if (Iteration <= 5)
- ExtraSearchTime = 0;
cout << "info depth " << Iteration << endl;
beta = Min(ValueByIteration[Iteration - 1] + AspirationDelta, VALUE_INFINITE);
}
- // Search to the current depth, rml is updated and sorted
- value = root_search(p, ss, rml, alpha, beta);
+ // 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.
// 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) {
EvalInfo ei;
StateInfo st;
+ CheckInfo ci(pos);
int64_t nodes;
Move move;
Depth depth, ext, newDepth;
- Value value, alpha;
+ Value value, alpha, beta;
bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
- int researchCount = 0;
- CheckInfo ci(pos);
- alpha = oldAlpha;
+ int researchCountFH, researchCountFL;
+
+ researchCountFH = researchCountFL = 0;
+ alpha = *alphaPtr;
+ beta = *betaPtr;
isCheck = pos.is_check();
// Step 1. Initialize node and poll (omitted at root, but I can see no good reason for this, FIXME)
print_pv_info(pos, ss, alpha, beta, value);
// Prepare for a research after a fail high, each time with a wider window
- researchCount++;
- beta = Min(beta + AspirationDelta * (1 << researchCount), VALUE_INFINITE);
+ *betaPtr = beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
+ researchCountFH++;
} // End of fail high loop
}
} // PV move or new best move
- assert(alpha >= oldAlpha);
+ assert(alpha >= *alphaPtr);
- AspirationFailLow = (alpha == oldAlpha);
+ AspirationFailLow = (alpha == *alphaPtr);
if (AspirationFailLow && StopOnPonderhit)
StopOnPonderhit = false;
}
// Can we exit fail low loop ?
- if (AbortSearch || alpha > oldAlpha)
+ if (AbortSearch || !AspirationFailLow)
break;
// Prepare for a research after a fail low, each time with a wider window
- researchCount++;
- alpha = Max(alpha - AspirationDelta * (1 << researchCount), -VALUE_INFINITE);
- oldAlpha = alpha;
+ *alphaPtr = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
+ researchCountFL++;
} // Fail low loop
if (nullValue >= beta)
{
+ // Do not return unproven mate scores
+ if (nullValue >= value_mate_in(PLY_MAX))
+ nullValue = beta;
+
if (depth < 6 * OnePly)
- return beta;
+ return nullValue;
// Do zugzwang verification search
Value v = search(pos, ss, beta, depth-5*OnePly, ply, false, threadID);
if (v >= beta)
- return beta;
+ return nullValue;
} 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