Alpha-beta prunning with transposition table, iterative deepening

I'm trying to implement alpha-beta min-max 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 min-max it's obvious which move is the best, but which move is the best when iterating with alpha-beta cutoffs? Can I assume that the best move for given position is the best move found when the loop ends (with cut-off 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)?

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 when entry.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:
```
entry.depth == remaining_depth
```
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 (beta-cutoff 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).

Recommended topics

Hot tags