Transposition table replacement strategies

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
zd3nik
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Re: Transposition table replacement strategies

Here is how I handle TT probes/stores in my main search routine. If anyone can spot potential problem(s) I would appreciate feedback.

Code: Select all

``````    pv = EMPTY
bestScore = MATED_AT&#40;ply&#41;;

ttGets++;
ttMove = NONE;
ttEntry = TT.GetEntryAt&#40;positionKey&#41;;
if &#40;ttEntry.Matches&#40;positionKey&#41;) &#123;
ttHits++;
ttMove = ttEntry.BestMove&#40;);
if &#40;ttEntry.Depth&#40;) >= depth&#41; &#123;
switch &#40;ttEntry.Type&#40;)) &#123;
case UpperBound&#58;
if &#40;ttEntry.Score&#40;) <= alpha&#41; &#123;
pv = ttMove;
return ttEntry.Score&#40;);
&#125;
break;
case LowerBound&#58;
if &#40;ttEntry.Score&#40;) >= beta&#41; &#123;
pv = ttMove;
return ttEntry.Score&#40;);
&#125;
break;
case ExactScore&#58;
if (&#40;ttEntry.Score&#40;) <= alpha&#41; OR &#40;ttEntry.Score&#40;) >= beta&#41; OR &#40;not pvNode&#41;) &#123;
pv = ttMove;
return ttEntry.Score&#40;);
&#125;
break;
&#125;
&#125;
Exec&#40;ttMove&#41;;
bestScore = -child.Search&#40;-beta, -alpha&#41;
Undo&#40;ttMove&#41;;
pv = ttMove + child.pv;
if &#40;bestScore >= beta&#41; &#123;
ttEntry.Set&#40;bestScore, LowerBound, ttMove&#41;;
return bestScore;
&#125;
&#125;

GenerateMoves&#40;);
if &#40;no legal moves&#41; &#123;
if &#40;in check&#41; return MATED_AT&#40;ply&#41; else return DRAW;
&#125;

foreach&#40;move&#41; &#123;
if &#40;move != ttMove&#41; &#123;
Exec&#40;move&#41;;
score = -child.Search&#40;-beta, -alpha&#41;;
Undo&#40;move&#41;;
if &#40;score > bestScore&#41; &#123;
pv = move + child.pv;
bestScore = score
&#125;
if &#40;score >= beta&#41; &#123;
ttEntry.Set&#40;score, LowerBound, move&#41;;
return score;
&#125;
alpha = max&#40;score, alpha&#41;;
&#125;
&#125;

if &#40;bestScore > original_alpha&#41; &#123;
ttEntry.Set&#40;bestScore, ExactScore, pv.FirstMove&#40;));
&#125;
else &#123;
ttEntry.Set&#40;bestScore, UpperBound, pv.FirstMove&#40;));
&#125;

return bestScore;
``````
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)