A question about Transposition Table

Code, algorithms, languages, construction...
Post Reply
notachessplayer
Posts: 30
Joined: Thu Dec 29, 2016 10:13 pm

A question about Transposition Table

Post by notachessplayer » Thu Dec 29, 2016 10:17 pm

Hello,

Could someone knowledgeable tell me this:
I'm doing an iterative deepening. Each time a best move is found (beating alpha), I store it in the transposition table, with an additional information, the depth searched.
Say I found this move when my depth was 5, it means I found this move with an accuracy of depth 5. So in my iterative deepening, instead of doing AlphaBeta for every depth, I check if a best move was found at this position (from earlier searches). If so, I start the iterative deepening at depth found+1.
Code looks like this:

Code: Select all

 for (mSearchDepth = 1; mSearchDepth < MAX_DEPTH; mSearchDepth++) {
        line = "";
        mNodes = 0;
        node = mHashMap.get(mGame.getCurrentPosition());
        if (node != null) {
            bestMove = node.getMove();
            mSearchDepth = node.getSearchDepth() + 1;
        }

        bestScore = alphaBeta(-Values.INFINITE, Values.INFINITE, mSearchDepth);

        if (stop) {
            break;
        }

        node = mHashMap.get(mGame.getCurrentPosition());
        if (node != null) {
            bestMove = node.getMove();
        } else {
            break;
        }
 }
This enables me to start generally at depth 7-8, and get another one "for free". But is there a risk to this?
I don't see a reason this should not work, but other programs seem to search from depth 1 for every move instead.

H.G.Muller
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: A question about Transposition Table

Post by H.G.Muller » Thu Dec 29, 2016 11:43 pm

In micro-Max I do that in every node. (Because I do internal iterative deepeing in every node.) The idea of a transposition table is to avoid work you have already done before, by taking it from the table.

Note that to be useful in the root the score in the TT should be exact. Otherwise the listed move might ot be the best move, but merely one that was good enough at the time. And the other moves might not have been searched at all then, so that starting on them at high depth totally uninformed can be very expensive.

Post Reply