First, testing questions. I have run 1000 games match between original version and my new version, at 1minute/game, 32M hash, ponder off, 1 thread, with stockfish book, repeating, book depth 40 plies. The result was +202 =633 -165 in favor of my version, bayeselo says that means 96% likelihood of superiority. That could just mean it is 1 of 25 tests of equal strength versions.
Is the draw ratio normal? Or should I use lower "bookdepth" setting (risking duplicate games?)?
Umm, well, the opponent was not exactly the original stockfish. I went under impression that cutechess-cli does not clear hash properly enough between games, so for both versions, I have edited handle_command() in uci.cpp to
Code: Select all
else if (token == "ucinewgame")
{
push_button("New Game");
push_button("Clear Hash");
Position::init_piece_square_tables();
RootPosition.from_fen(StartPosition);
}Test was using 1 of 2 cores, the other core was doing browsing, compiling, testposition analysis, etc. But when I was testing my previous idea, I noticed the result depended dramatically on usage of the other core. Previous idea was heavy on TT store/retrieve and it started to lose badly (from previously quite balanced match) when the other core was also fiddling with memory. I tried to test the final version with other core idle, but since the final version uses TT slightly less than original stockfish, it might be not so good on other hardware as is on my old cheap Core Duo laptop.
So, about the idea. The short name is "Hash Depth Extension", full name is "Transposition Table Replacement Scheme And PV Search Extension Based On Previous Higher Depth Transposition Table Entry". Stockfish does not use TT values for cutoff in pv search, but if there is a deep TT entry that is not compatible with what pv search sees, why not to extend pv search to find the promising truth? And even if TT entry is compatible, we probably do not want to overwrite it with shallower one.
Implementation is far from clean, I was in the "code first, edit later, think even later" mode, and I am still not sure why the final version works and previous versions not. Also, HDE uses a loop in which depth varies, so it should be possible to do Internal Iterative Deepening in this loop too, but it does not test well yet.
For the future, would it be a good idea if I try to write one template function for both search_pv() and search()? You know, less lines of code, doing things the same way (unless explicitly stated otherwise) and so on?
And at last, the code. Only search_pv() is changed, but on several places, so I paste it all:
Code: Select all
// search_pv() is the main search function for PV nodes.
Value search_pv(Position& pos, SearchStack ss[], Value oldAlpha, Value beta,
Depth oldDepth, int ply, int threadID) {
assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE);
assert(beta > alpha && beta <= VALUE_INFINITE);
assert(ply >= 0 && ply < PLY_MAX);
assert(threadID >= 0 && threadID < TM.active_threads());
Move movesSearched[256];
EvalInfo ei;
StateInfo st;
const TTEntry* tte;
Move ttMove, move;
Depth ttDepth, ext, newDepth, depth = oldDepth;
Value ttValue, bestValue, value, alpha = oldAlpha;
ValueType ttType;
bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
bool mateThreat = false;
if (depth < OnePly)
return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
// Step 1. Initialize node and poll
// Polling can abort search.
init_node(ss, ply, threadID);
// Step 2. Check for aborted search and immediate draw
if (AbortSearch || TM.thread_should_stop(threadID))
return Value(0);
if (pos.is_draw() || ply >= PLY_MAX - 1)
return VALUE_DRAW;
// Step 3. Mate distance pruning
alpha = Max(value_mated_in(ply), alpha);
beta = Min(value_mate_in(ply+1), beta);
if (alpha >= beta)
return alpha;
// Step 4. Transposition table lookup
// At PV nodes, we don't use the TT for pruning, but only for move ordering.
// This is to avoid problems in the following areas:
//
// * Repetition draw detection
// * Fifty move rule detection
// * Searching for a mate
// * Printing of full PV line
tte = TT.retrieve(pos.get_key());
ttMove = (tte ? tte->move() : MOVE_NONE);
ttDepth = (tte ? tte->depth() : Depth(-2));
ttValue = (tte ? value_from_tt(tte->value(), ply) : Value(0));
ttType = (tte ? tte->type() : VALUE_TYPE_EV_LO); // hack, not to replace TT entry
// Step 5. Evaluate the position statically
// At PV nodes we do this only to update gain statistics
isCheck = pos.is_check();
if (!isCheck)
{
ss[ply].eval = evaluate(pos, ei, threadID);
update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
}
// Step 6. Razoring (is omitted in PV nodes)
// Step 7. Static null move pruning (is omitted in PV nodes)
// Step 8. Null move search with verification search (is omitted in PV nodes)
// Step 9. Internal iterative deepening
if ( depth >= IIDDepthAtPVNodes
&& ttMove == MOVE_NONE)
{
search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID);
ttMove = ss[ply].pv[ply];
tte = TT.retrieve(pos.get_key());
ttDepth = (tte ? tte->depth() : Depth(-2));
ttValue = (tte ? value_from_tt(tte->value(), ply) : Value(0));
ttType = (tte ? tte->type() : VALUE_TYPE_EV_LO); // hack, not to replace TT entry
}
// Initialize a MovePicker object for the current position
mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move()));
CheckInfo ci(pos);
// Step extra. HDE loop.
while(1)
{ // Also, the scope for mp.
// Check for abort.
if (AbortSearch || TM.thread_should_stop(threadID))
return bestValue;
int moveCount = 0;
MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
alpha = oldAlpha;
bestValue = -VALUE_INFINITE;
// Step 10. Loop through moves
// Loop through all legal moves until no moves remain or a beta cutoff occurs
while ( alpha < beta
&& (move = mp.get_next_move()) != MOVE_NONE
&& !TM.thread_should_stop(threadID))
{
assert(move_is_ok(move));
singleEvasion = (isCheck && mp.number_of_evasions() == 1);
moveIsCheck = pos.move_is_check(move, ci);
captureOrPromotion = pos.move_is_capture_or_promotion(move);
// Step 11. Decide the new search depth
ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
// Singular extension search. We extend the TT move if its value is much better than
// its siblings. To verify this we do a reduced search on all the other moves but the
// ttMove, if result is lower then ttValue minus a margin then we extend ttMove.
if ( depth >= SingularExtensionDepthAtPVNodes
&& tte
&& move == ttMove
&& ext < OnePly
&& is_lower_bound(ttType)
&& ttDepth >= depth - 3 * OnePly)
{
// Value ttValue = value_from_tt(tte->value(), ply);
if (abs(ttValue) < VALUE_KNOWN_WIN)
{
Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move);
if (excValue < ttValue - SingularExtensionMargin)
ext = OnePly;
}
}
newDepth = depth - OnePly + ext;
// Update current move (this must be done after singular extension search)
movesSearched[moveCount++] = ss[ply].currentMove = move;
// Step 12. Futility pruning (is omitted in PV nodes)
// Step 13. Make the move
pos.do_move(move, st, ci, moveIsCheck);
// Step extra. pv search (only in PV nodes)
// The first move in list is the expected PV
if (moveCount == 1)
{
value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
}
else
{
// Step 14. Reduced search
// if the move fails high will be re-searched at full depth.
bool doFullDepthSearch = true;
if ( depth >= 3 * OnePly
&& !dangerous
&& !captureOrPromotion
&& !move_is_castle(move)
&& !move_is_killer(move, ss[ply]))
{
ss[ply].reduction = pv_reduction(depth, moveCount);
if (ss[ply].reduction)
{
value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
doFullDepthSearch = (value > alpha);
}
}
// Step 15. Full depth search
if (doFullDepthSearch)
{
ss[ply].reduction = Depth(0);
value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
// Step extra. pv search (only in PV nodes)
if (value > alpha && value < beta) // (value > bestValue)
value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
}
}
// Step 16. Undo move
pos.undo_move(move);
assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
// Step 17. Check for new best move
if (value > bestValue)
{
bestValue = value;
update_pv(ss, ply);
if (value > alpha)
{
alpha = value;
if (value == value_mate_in(ply + 1))
ss[ply].mateKiller = move;
}
}
// Step 18. Check for split
if ( TM.active_threads() > 1
&& bestValue < beta
&& depth >= MinimumSplitDepth
&& Iteration <= 99
&& TM.available_thread_exists(threadID)
&& !AbortSearch
&& !TM.thread_should_stop(threadID)
&& TM.split(pos, ss, ply, &alpha, beta, &bestValue,
depth, mateThreat, &moveCount, &mp, threadID, true))
break;
} // Move list.
// Step 19. Check for mate and stalemate
// All legal moves have been searched and if there were
// no legal moves, it must be mate or stalemate.
if (moveCount == 0)
return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
// Step 20. Update tables
// If the search is not aborted, update the transposition table,
// history counters, and killer moves.
if (AbortSearch || TM.thread_should_stop(threadID))
return bestValue;
if (true) // HDE
{
if (bestValue <= oldAlpha)
{ // failing low
// Hash depth extension.
if (ttDepth > depth && is_lower_bound(ttType) && ttValue > oldAlpha)
{ // Incompatible deeper TT entry.
depth = Min(ttDepth, depth+2*OnePly);
continue; // The HDE loop with higher depth.
} // HDE low.
if ( depth > ttDepth || !is_upper_bound(ttType)
|| (depth >= ttDepth && ttType != VALUE_TYPE_EXACT))
{ // Storing new entry.
TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
}
}
else if (bestValue >= beta)
{ // failing high
// Hash depth extension.
if (ttDepth > depth && is_upper_bound(ttType) && ttValue < beta)
{ // Incompatible deeper TT entry.
depth = Min(ttDepth, depth+2*OnePly);
continue; // The HDE loop with higher depth.
} // HDE high.
// Update statistics after HDE check.
TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
move = ss[ply].pv[ply];
if (!pos.move_is_capture_or_promotion(move))
{
update_history(pos, move, depth, movesSearched, moveCount);
update_killers(move, ss[ply]);
}
if ( depth > ttDepth || !is_lower_bound(ttType)
|| (depth >= ttDepth && ttType != VALUE_TYPE_EXACT))
{ // Storing new entry.
TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
}
}
else
{ // exact score
// Hash depth extension.
if ( (ttDepth > depth && is_lower_bound(ttType) && ttValue >= beta)
|| (ttDepth > depth && is_upper_bound(ttType) && ttValue <= oldAlpha)
|| (ttDepth > depth && ttType == VALUE_TYPE_EXACT && ttMove != ss[ply].pv[ply]))
{ // Incompatible deeper TT entry.
depth = Min(ttDepth, depth+2*OnePly);
continue; // The HDE loop with higher depth.
} // HDE exact.
if (depth >= ttDepth || ttType != VALUE_TYPE_EXACT)
{ // Storing new entry.
TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
}
}
}
else // No HDE.
{
if (bestValue <= oldAlpha)
TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
else if (bestValue >= beta)
{
TM.incrementBetaCounter(pos.side_to_move(), depth, threadID);
move = ss[ply].pv[ply];
if (!pos.move_is_capture_or_promotion(move))
{
update_history(pos, move, depth, movesSearched, moveCount);
update_killers(move, ss[ply]);
}
TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
}
else
TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]);
}
break; // Exit from HDE loop.
} // HDE loop.
return bestValue;
}
it is in current development branch. I tell you this so just to avoid you an useless work.