Re: Transposition table replacement strategies
Posted: Sun Mar 06, 2016 2:10 am
Here is how I handle TT probes/stores in my main search routine. If anyone can spot potential problem(s) I would appreciate feedback.
Of course I've simplified things a lot in this psuedo-code. For example the real code implements null move pruning, PVS, LMR, etc...
QSearch does the TT lookup and returns ttEntry.Score() where appropriate. But QSearch does not store results (never calls ttEntry.Set)
Code: Select all
pv = EMPTY
bestScore = MATED_AT(ply);
ttGets++;
ttMove = NONE;
ttEntry = TT.GetEntryAt(positionKey);
if (ttEntry.Matches(positionKey)) {
ttHits++;
ttMove = ttEntry.BestMove();
if (ttEntry.Depth() >= depth) {
switch (ttEntry.Type()) {
case UpperBound:
if (ttEntry.Score() <= alpha) {
pv = ttMove;
return ttEntry.Score();
}
break;
case LowerBound:
if (ttEntry.Score() >= beta) {
pv = ttMove;
return ttEntry.Score();
}
break;
case ExactScore:
if ((ttEntry.Score() <= alpha) OR (ttEntry.Score() >= beta) OR (not pvNode)) {
pv = ttMove;
return ttEntry.Score();
}
break;
}
}
Exec(ttMove);
bestScore = -child.Search(-beta, -alpha)
Undo(ttMove);
pv = ttMove + child.pv;
if (bestScore >= beta) {
ttEntry.Set(bestScore, LowerBound, ttMove);
return bestScore;
}
}
GenerateMoves();
if (no legal moves) {
if (in check) return MATED_AT(ply) else return DRAW;
}
foreach(move) {
if (move != ttMove) {
Exec(move);
score = -child.Search(-beta, -alpha);
Undo(move);
if (score > bestScore) {
pv = move + child.pv;
bestScore = score
}
if (score >= beta) {
ttEntry.Set(score, LowerBound, move);
return score;
}
alpha = max(score, alpha);
}
}
if (bestScore > original_alpha) {
ttEntry.Set(bestScore, ExactScore, pv.FirstMove());
}
else {
ttEntry.Set(bestScore, UpperBound, pv.FirstMove());
}
return bestScore;
QSearch does the TT lookup and returns ttEntry.Score() where appropriate. But QSearch does not store results (never calls ttEntry.Set)