Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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:

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

like image 366
PanJanek Avatar asked May 01 '15 15:05

PanJanek


People also ask

What is the role of the transposition table in this algorithm?

A transposition table is a cache of previously seen positions, and associated evaluations, in a game tree generated by a computer game playing program. If a position recurs via a different sequence of moves, the value of the position is retrieved from the table, avoiding re-searching the game tree below that position.

What do you store in a transposition table?

For this reason, chess programs have a transposition table, which is a large hash table storing information about positions previously searched, how deeply they were searched, and what we concluded about them.

What is pruning elaborate the Alpha Beta pruning procedure with example?

–> Beta is used and updated only by the Minimizer and it represents the minimum value found. The initial value is ∞. Again, the value of beta is passed down to the children node, but actual node values are used to backtrack. The condition used by alpha beta pruning to prune the useless branches is: alpha >= beta.

What is difference between alpha pruning and beta pruning?

Alpha Pruning: Search can be stopped below any MIN node having a beta value less than or equal to the alpha value of any of its MAX ancestors. Beta Pruning: Search can be stopped below any MAX node having a alpha value greater than or equal to the beta value of any of its MIN ancestors.


1 Answers

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

like image 134
manlio Avatar answered Sep 28 '22 06:09

manlio