Alpha-beta prunning with transposition table, iterative deepening

Question

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:

1. 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.

2. 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)?

3. 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)?

Solution

1. 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.

2. 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).

3. 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).

Comments

[PanJanek]

If there is no best move to store in some circumstances, how to decide which move is the best after calling v=aphaBeta(root, -inf, +inf)? I thought that I will call alphaBeta for root node and apart form the minmax value (that is not so interesting for me) I'll get the "winning" move. I know I can execute alphaBeta(child, -inf, +inf) for each child of the root node and choose the best - is it the only option?

[manlio]

Not sure to understand... calling aphaBeta(root, -inf, +inf) you cannot get a fail low/fail high, just an exact score/best move (you should pay attention not to overwrite the entry related to the root node). You don't have to call the search function to extract the mainline: it can be extracted directly from the transposition table (e.g. see chessprogramming.wikispaces.com/Principal+variation or open-aurec.com/wbforum/viewtopic.php?f=4&t=3440). Sometimes a ad-hoc PV TT is used.

[PanJanek]

Ofcourse, I forgot that calling alphaBeta with -inf,+inf guarantees exact score. So If I understand correctly, after calling alphaBeta(root, -inf, +inf) I will always have the best move in tt[root.getHash()], but if I try extract further moves from transposition table there may be fewer of them than the search depth (because some positions will not have best move)?

[manlio]

There may be fewer of them (the infamous "truncated PV" problem) but for other reasons. In theory, since each element in the PV contains a score that is between alpha and beta, there should be a "best move" stored in each hash element. Unfortunately hash table entries can be overwritten.