Help with Transposition Table

[Gary]

Hello guys! Good to meet you all.

I'm pretty new to chess programming has a hobby. I've done a lot of contest programming and I work in software development.

I feel like I'm implementing my tranposition table wrong because I'm not getting as much of a search depth improvement with it as I expected. I've checked the hashing thoroughly. Could someone look over my code for me?

I know it's not easy going over 50+ lines of code written by someone else, but I do appreciate any help!

I use an array of size 2 million to store my entries. I replace only if the new entry has higher depth, or has the same depth and a better bound. In case of a collision, I replace if the new entry has a higher depth.

Each entry contains the following information about a single state. It includes a lower bound and upper bound on the score of the node. These bounds may have been from different depths.

• wholeHash : the entire 64bit hash value of the node.
• bestMoveInd : index of the best move we've seen at minDepth
• minDepth : the depth of the lower bound.
• minScore : lower bound of the score
• maxDepth : the depth of the upper bound.
• maxScore : upper bound of the score

Code: Select all

void AI::tryAddTranspose(NodeType type, int depth, int ind, int score){
    TranspositionData curData = TT[game.getHash()%TTSize];

    //we have a collision
    if (game.getHash() != curData.wholeHash){

        //Override IFF this entry has higher depth
        if (depth > max(curData.maxDepth,curData.minDepth) ){
            curData = TranspositionData();
        } else {
            return;
        }
    }

    //In case of a new entry or an override..
    curData.wholeHash = game.getHash();


    if (type == PV || type == ALL){
        if (depth > curData.maxDepth){
            curData.maxDepth = depth;
            curData.maxScore = score;
        } else if (depth == curData.maxDepth){
            curData.maxScore = min(curData.maxScore,score);
        }
        
    }

    if (type == PV || type == CUT){
        if (depth > curData.minDepth ){
            curData.minDepth = depth;
            curData.minScore = score;
            curData.bestMoveInd = ind;
        } else if (depth == curData.minDepth && score>curData.minScore){
            curData.minScore = score;
            curData.bestMoveInd = ind;
        }
    }

    TT[game.getHash()%TTSize] = curData;
}

TranspositionQueryResult AI::queryTT(int depth) const{

    TranspositionData curData = TT[game.getHash()%TTSize];

    //We have a collision
    if (curData.wholeHash != game.getHash()){
        return TranspositionQueryResult(-INF,INF,NO_MOVE);
    }

    int minToReturn = (depth <= curData.minDepth) ? curData.minScore : -INF;
    int maxToReturn = (depth <= curData.maxDepth) ? curData.maxScore : INF;

    return TranspositionQueryResult(minToReturn,maxToReturn,curData.bestMoveInd);
}

Thanks a lot!

[Adam Hair]

Hi Gary! Welcome to CCC!

I moved your thread to the technical forum where it will more likely be seen by the other programmers.

Good luck with your chess engine!

[Edsel Apostol]

Welcome to CCC!

You should probably post also how you are using the return value TranspositionQueryResult to determine the cutoff.

[Evert]

You'll also want to look at your replacement strategy: never overwriting a deeper entry means that eventually your TT will fill up with entries that are entirely useless but will never be discarded.

It seems natural that you should prefer to keep deeper entries, but think about it: if that entry had been useful, it would have caused a cut-off and you would have never tried to store a new entry. It's probably better to overwrite the useless entry.

You can avoid throwing entries away immediately by using multiple buckets per entry.

[Sven]

Hi Gary,

welcome to CCC!

Here are my suggestions.

1) Keep your current approach with two bounds, which looks good but is already quite sophisticated, as a future goal and start with a much simpler approach:
- one score
- type of score is either exact, lower bound, or upper bound
- always replace a hash entry, even if this looks "wrong" for you (it will actually perform better than your current strategy which practically turns your hash table into a bunch of useless information as soon as the table is 100% full)
This should already result in a small improvement of your search performance only by detecting transpositions. In general the improvement is already significant if you also use the TT for move ordering, by always trying the TT move first.

2) If you have reached the goal of my first point above then start improving it step by step, for instance:
- use more than one bucket per TT index, and replace the entry with the highest "replacement score";
- introduce aging, i.e. prefer overwriting of entries originating in previous searches from older root nodes over those from the current search;
- introduce your strategy of maintaining two bounds;
- make your hashing behaviour depend on the node type, as in your current code (it may be possible that you even don't need this in the "simple approach" of my first point above);
- etc.

It is a common experience that starting with a simple approach and improving it later on has greater chances of being successful than starting with the most sophisticated approach and trying hard to get it working. One of the reasons is that with a sophisticated approach you usually have a lot of dependencies between specific concepts of search and TT implementation, which makes debugging harder. Your current approach may be working as a charm as soon as you find and fix the blocking issue, but it might be a long road to that point.

3) Just a hint about common wording. Most people define "collision" in the context of transposition tables differently: two different positions with identical 64-bit hash key cause a collision (in your code: game.getHash() == curData.wholeHash). This is a rare case but it happens. What you call a "collision" in your code comment is only the normal condition that two different 64-bit hash keys are mapped to the same TT index due to identical N lower bits (N = log2(TTSize), in your case N=21).

Good luck!
Sven

[Gary]

Edsel, Evert, Sven: Thanks a lot to all of you!

You should probably post also how you are using the return value TranspositionQueryResult to determine the cutoff.

Here it is. I also search the TTRes.bestMoveInd first, though that's not shown here.

Code: Select all

SearchResult AI::search(int depth, int ply, int alpha, int beta,vector<int> PVLine){

    vector<int> bestLine;

    TranspositionQueryResult TTRes = queryTT(depth);
    
    alpha = max(alpha,TTRes.low);
    beta = min(beta,TTRes.high);
    bestLine.push_back(TTRes.bestMoveInd);
    
    if (beta<=alpha){
        return SearchResult(alpha, bestLine);
    }
    
    ...
    
}

I know there is a slicker way of extracting the PV than using a vector, but the overhead is small enough that I don't care to change it at moment.

I'm going to try the simpler approach Sven described. I'll get back to you guys with how it goes.

[Gary]

Sven,

What you call a "collision" in your code comment is only the normal condition that two different 64-bit hash keys are mapped to the same TT index due to identical N lower bits (N = log2(TTSize), in your case N=21).

You actually made be realize a problem with my hashing. I currently use the lower 10 bits of my hash to store enpeasent, castling, turn, and isInCheck. That would caused more keys than usual to map to the same TT index.

I'll move those to the upper bits. Do you guys think that leaving only 54 bits for actual hash is a problem?

[Sven]

Sven,

What you call a "collision" in your code comment is only the normal condition that two different 64-bit hash keys are mapped to the same TT index due to identical N lower bits (N = log2(TTSize), in your case N=21).

You actually made be realize a problem with my hashing. I currently use the lower 10 bits of my hash to store enpeasent, castling, turn, and isInCheck. That would caused more keys than usual to map to the same TT index.

I'll move those to the upper bits. Do you guys think that leaving only 54 bits for actual hash is a problem?

You don't need "isInCheck" in that context, it is redundant since it can be derived immediately from all the other information. As to EP, castling rights and turn, virtually all other programs use the same zobrist key techniques for these as for the board state.

Sven

[Gary]

That is actually where I store the information. I don't have enpeasent/castling information anywhere else. I was a bit obsessive over perft speed when I decided that.

[Edsel Apostol]

Edsel, Evert, Sven: Thanks a lot to all of you!

You should probably post also how you are using the return value TranspositionQueryResult to determine the cutoff.

Here it is. I also search the TTRes.bestMoveInd first, though that's not shown here.

Code: Select all

SearchResult AI::search(int depth, int ply, int alpha, int beta,vector<int> PVLine){

    vector<int> bestLine;

    TranspositionQueryResult TTRes = queryTT(depth);
    
    alpha = max(alpha,TTRes.low);
    beta = min(beta,TTRes.high);
    bestLine.push_back(TTRes.bestMoveInd);
    
    if (beta<=alpha){
        return SearchResult(alpha, bestLine);
    }
    
    ...
    
}

I know there is a slicker way of extracting the PV than using a vector, but the overhead is small enough that I don't care to change it at moment.

I'm going to try the simpler approach Sven described. I'll get back to you guys with how it goes.

There's seems to be something wrong with how you implement cutoff. First , for stability pusposes, most of the engines I've seen don't update the values of alpha and beta by the values from the TT. Second, you only return a cutoff if beta <= alpha. It may not work in cases where (beta-alpha > 1).

Can you try something like this:

Code: Select all

SearchResult AI::search(int depth, int ply, int alpha, int beta,vector<int> PVLine){

    vector<int> bestLine;

    TranspositionQueryResult TTRes = queryTT(depth);
    
    bestLine.push_back(TTRes.bestMoveInd);
    if (TTRes.low > alpha) return SearchResult(TTRes.low, bestLine);     
    if (TTRes.high < beta) return SearchResult(TTRes.high, bestLine);     
    
    ...
    
}

You should also follow Sven's advice to replace always the hash entries in the TT in the meantime, if you want immediate improvements without much changes to the code.

Code: Select all

    if (type == PV || type == ALL){ 
        curData.maxDepth = depth; 
        curData.maxScore = score; 
    } 

    if (type == PV || type == CUT){ 
        curData.minDepth = depth; 
        curData.minScore = score; 
        curData.bestMoveInd = ind; 
    }