# Transposition Table

A multi-purpose data structure
A chess tree can be viewed as a graph, where transpositions can lead back into sub-trees that may have already been examined.  A transposition hash table can be used to detect these cases in order to avoid duplicating work.  If the position after 1. e4 d6 2. d4 has already been searched, it makes no sense to search the position after 1. d4 d6 2. e4.

It's possible that this line of reasoning inspired early computer chess programmers, and this is in fact a minor reason to implement a transposition hash table.  And in some positions, such as endgame king+pawn endings with locked pawns, the number of transpositions is so high that detecting transpositions is such a fantastic help that huge search depths can be reached in a matter of seconds.

Eliminating duplicate work is a fine feature of a transposition table, but in normal middlegame positions, another use of the table is more important.  One of the fields in each hash element is the best move found in the position.  As I explained in my explanation of iterative deepening, searching good moves first makes the search much more efficient.  So if you find that there is a "best" move in your hash element, and you search it first, you will often improve your move ordering, which will improve your branching factor, which will result in a deeper search in less time.

Implementation
The main transposition table is an array of hash elements.  Each hash element looks something like this:

#define    hashfEXACT   0

#define    hashfALPHA   1

#define    hashfBETA    2

 

typedef struct tagHASHE {

    U64 key;

    int depth;

    int flags;

    int value;

    MOVE best;

}   HASHE;

The hash array is indexed via a Zobrist key.  You take the key for the position, modulo it by the number of elements in your table, and that's the hash element that corresponds to this position.  Since many positions are apt to map to the same element in the hash table, the table elements contain a verification value, which can be used to make sure that the element in the table is the one that you are trying to find.  An obvious verification value is the full 64-bit key, so that is the first field in the example above.

When you get a result from a search, and you want to store an element in the table, it is important to record how deep the search went, if you plan to use the hash table to avoid doing redundant work.  If you searched this position with a 3-ply search, and you come along later planning to do a 10-ply search, you can't assume that the information in this hash element is accurate.  So the search depth for this sub-tree is also recorded.

In an alpha-beta search, rarely do you get an exact value when you search a node.  "Alpha" and "beta" exist to help you prune out useless sub-trees, but the minor disadvantage to using alpha-beta is that you don't often know exactly how bad or good a node is, you just know that it is bad enough or good enough that you don't need to waste any more time on it.

Of course, this raises the question as to what value you store in the hash element, and what you can do with it when you retrieve it.  The answer is to store a value, and a flag that indicates what the value means.  In my example above, if you store, let's say, a 16 in the value field, and "hashfEXACT" in the flags field, this means that the value of the node was exactly 16.  If you store "hashfALPHA" in the flags field, the value of the node was at most 16.  If you store "hashfBETA", the value is at least 16.

It is pretty easy to figure out which value and flags to store given any particular circumstance you might encounter when searching, but it is important to avoid bugs.  Hashing bugs are easy to make, and once you make one they are very difficult to track down.

The final field in my hash element is the "best" move encountered last time I searched this position.  Sometimes I don't get a best move, like if everything failed low (returned a score <= alpha), but other times there is a definite best move, like when something fails high (returns a score >= beta).

If  a best move is found, it will be searched first.

Some sample code, overlaid onto an alpha-beta function, with changes highlighted:

int AlphaBeta(int depth, int alpha, int beta)
{

    int hashf = hashfALPHA;

 

    if ((val = ProbeHash(depth, alpha, beta)) != valUNKNOWN)

        return val;
    if (depth == 0) {

        val = Evaluate();

        RecordHash(depth, val, hashfEXACT);

        return val;

    }
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        val = -AlphaBeta(depth - 1, -beta, -alpha);
        UnmakeMove();
        if (val >= beta) {

            RecordHash(depth, beta, hashfBETA);
            return beta;

        }
        if (val > alpha) {

            hashf = hashfEXACT;
            alpha = val;

        }
    }

    RecordHash(depth, alpha, hashf);
    return alpha;
}

 

Here is the source for the two new functions::

int ProbeHash(int depth, int alpha, int beta)

{

    HASHE * phashe = &hash_table[ZobristKey() % TableSize()];

 

    if (phashe->key == ZobristKey()) {

        if (phashe->depth >= depth) {

            if (phashe->flags == hashfEXACT)

                return phashe->val;

            if ((phashe->flags == hashfALPHA) &&

                (phashe->val <= alpha))

                return alpha;
            if ((phashe->flags == hashfBETA) &&

                (phashe->val >= beta))

                return beta;

        }

        RememberBestMove();

    }

    return valUNKNOWN;

}

 

void RecordHash(int depth, int val, int hashf)

{

    HASHE * phashe = &hash_table[ZobristKey() % TableSize()];

 

    phashe->key = ZobristKey();

    phashe->best = BestMove();

    phashe->val = val;

    phashe->hashf = hashf;

    phashe->depth = depth;
}

As you can see, this isn't exactly rocket science, but it's possible to have bugs, and there are some nuances I haven't discussed.  If you do have bugs, they will be really, really bad bugs.

Replacement schemes
The most major nuance involves when to over-write a hash element.  In the example above, I use the scheme "always replace", which simply over-writes anything that was already there.  This may not be the best scheme, and in fact there has been a lot of work trying to figure out what the best scheme is.

Another scheme is "replace if same depth or deeper".  This leaves a currently existing node alone unless the depth attached the new one is greater than or equal to the depth of the one in the table.

There is lots of room for experimentation here.  In 1994 I asked a question about replacement scheme in the Usenet group rec.games.chess (now rec.games.chess.computer), and I received an answer from Ken Thompson.

His answer was to use two tables.  One uses the "replace always" scheme, and the other uses "replace if same depth or deeper".  When you probe, you probe both tables, and if one of them lets you cut off, you do it.  If neither of them let you cut off, you might at least get a best move from one of them, and in fact you might get two different ones, both of which should be tried first (or second).

When recording, you simply use the appropriate replacement scheme.

If you use the "replace if deeper or same depth" scheme, your table might eventually fill up with outdated deep nodes.  The solution to this is either to clear the table each time you move, or add a "sequence" field to your element, so the replacement scheme becomes, "replace if same depth, deeper, or the element pertains to an ancient search".

I use Thompson's scheme today in Ferret, and it works fine.  Gerbil also uses this scheme, if you want to see some real source code.

The instability problem
Another problem that happens when you start using a transposition hash table, if you allow the search to cut off based upon elements in the table, is that your search suffers from instability.

You get instability for at least a couple of reasons:

You might be trying to do a 6-ply search here, but if you have results for a 10-ply search in your hash element, you might cut off based upon these.  Later on you come back and the element has been over-written, so you get a different value back for this node.
The Zobrist key does not take into account the path taken to get to a node.  Not every path is the same.  It is possible that the score in a hash element might be based upon a path that would contain a repetition if encountered at some other point in the tree.  A repetition might result in a draw score, or at least a different score.
There is nothing that can be done about this, as far as I can tell.

 
Send mail to brucemo@seanet.com with questions or comments about this web site.
Copyright © 2001 Bruce Moreland
Last modified: 01/24/03
