I'm trying to implement alphabeta minmax prunning enhanced with transposition tables. I use this pseudocode as reference:
http://people.csail.mit.edu/plaat/mtdf.html#abmem
function AlphaBetaWithMemory(n : node_type; alpha , beta , d : integer) : integer;
if retrieve(n) == OK then /* Transposition table lookup */
if n.lowerbound >= beta then return n.lowerbound;
if n.upperbound <= alpha then return n.upperbound;
alpha := max(alpha, n.lowerbound);
beta := min(beta, n.upperbound);
if d == 0 then g := evaluate(n); /* leaf node */
else if n == MAXNODE then
g := INFINITY; a := alpha; /* save original alpha value */
c := firstchild(n);
while (g < beta) and (c != NOCHILD) do
g := max(g, AlphaBetaWithMemory(c, a, beta, d  1));
a := max(a, g);
c := nextbrother(c);
else /* n is a MINNODE */
g := +INFINITY; b := beta; /* save original beta value */
c := firstchild(n);
while (g > alpha) and (c != NOCHILD) do
g := min(g, AlphaBetaWithMemory(c, alpha, b, d  1));
b := min(b, g);
c := nextbrother(c);
if g <= alpha then
n.upperbound := g;
store n.upperbound;
if g > alpha and g < beta then
n.lowerbound := g;
n.upperbound := g;
store n.lowerbound, n.upperbound;
if g >= beta then
n.lowerbound := g;
store n.lowerbound;
return g;
Three questions to this algorithm:

I belive that I should store depth (=distance to leaf level) with each saved transposition table entry and use entry only when entry.depth>=currentDepth (= entry is more or equal distant from leaves level). That is not shown in above pseudocode and is not discussed there, I wanted to make sure I understand that correctly.

I would like to store best move for each position to use it for move ordering AND extracting best move after the search stops. In pure minmax it's obvious which move is the best, but which move is the best when iterating with alphabeta cutoffs? Can I assume that the best move for given position is the best move found when the loop ends (with cutoff or without)?

When executing this algorithm in iterative deepening scheme – should I clear transposition table before each depth increase? I think not, I'd like tu use stored position from previous iteration, but I'm not sure if the information is adequate for deeper searches (It should be when checking table entry depth)?
Best Solution
You're right.
entry.depth
stores the number of plies the information in the transposition table entry are based on. So you can use those information only whenentry.depth >= remaining_depth
.The logic is that we don't want to use a result weaker than the "normal" search.
Sometimes, for debugging purpose, the condition is changed to:
this avoids some search instabilities. Anyway it doesn't guarantee the same result of a search without transposition table.
There isn't always a best move to store.
When the search fails low, there isn't a "best move". The only thing we know is that no move is good enough to produce a score bigger than
alpha
. There is no way to guess which move is best.So you should store a move in the hash table only for lower bounds (betacutoff i.e. a refutation move) and exact scores (PV node).
No, you shouldn't. With iterative deepening the same position is reached again and again and the transposition table can speed up the search.
You should clear the transposition table between moves (or, better, use an additional
entry.age
field).