Hashtables decrease playstrength

[Paul88]

Full disclosure, I have already posted this question on the Chess Stackexchange community https://chess.stackexchange.com/questio ... aystrength, but I figured that this would be a good place for more technical, programming-specific questions.

To summarize the question, I am looking to enhance my engine with hashtables, but it seems to consistently perform worse when it plays the (otherwise identical) algorithm that does not look up hashtable data. Due to insignificantly higher computational load, and somewhat deeper plies towards the endgame if the TT is utilized, I wonder if the way I store/retrieve/interpret hashtable data is erroneous.

The main idea is as follows: Whenever a call of alpha beta returns, I store: the type of node (upper cutoff/lower cutoff/exact), the value, the hash key, the preferred move, the distance to the leaf node. This is stored at a position as indexed by the current hash key modulo the number of hashtable entries. Whenever alphabeta is called and before all possible moves that that node are investigated, the hash key of the current board is used to access the hashtable, and if the stored key coincides and the distance to the leaf node is at least as high as the algorithm would search without hashtables, the stored data is retrieved and used to either: (a) return the search if it was an "exact" node, or (b) update the alpha/beta window if it was an upper/lower node, and execute the "preferred" move first (in the hopes of getting more cutoffs).

Now, if this is conceptually correct, then the issue could lie within the technical implementation. Some relevant bits are attached here - and I apologize for the somewhat nasty notation, this is all very much "wip" while I am ironing out these issues.

The part that looks up data from the hashtable (where alphaBeta_preferredMove just executes the passed move first and does not look up hashtable data - I should consolidate both functions down the line):

Code: Select all

int Engine::alphaBeta(ChessBoard* board, Colour colour, char depth, int alpha, int beta) 
[...]
if (useHashtable) {
    HashData data = Engine::transpos_table.getHashData();
    if ((data.zobristKey == Engine::transpos_table.hash) && (data.distanceToLeaf >= (depthLimit - depth))) {
        Engine::transpos_table.hashHits++;

        if ((data.type == NodeType::Exact))
            return data.value;
        else if ((data.type == NodeType::Lower) && (data.value < beta))
            beta = data.value;
        else if ((data.type == NodeType::Upper) && (data.value > alpha))
            alpha = data.value;

        if (alpha >= beta) return data.value;

        if (colour == Colour::White)
            return Engine::alphaBeta_preferredMove(board, Colour::White, depth, alpha, beta, data.preferredMove);
        else
            return Engine::alphaBeta_preferredMove(board, Colour::Black, depth, alpha, beta, data.preferredMove);
    }
}
[continue with the normal alpha beta search, i.e. generate moveset and recursively call alphaBeta]

Here is the code to insert data into the hashtable, which is called during the "normal" alpha beta seach whenever a recursive function call returns a value (at each node I keep track of the currently preferred move):

Code: Select all

void Hashtable::setHashData(int distanceToLeaf, int value, int alpha, int beta, std::tuple<char, char, char, char> preferredMove) {
    unsigned long index = Hashtable::hash % Hashtable::HASH_SIZE;
    if (((value > alpha) && (value < beta)) || (alpha == beta)) {
        Hashtable::table[index].type = NodeType::Exact;
        Hashtable::table[index].value = value;
    }
    else if (value >= beta) {
        Hashtable::table[index].type = NodeType::Upper;
        Hashtable::table[index].value = value;
    }
    else if (value <= alpha) {
        Hashtable::table[index].type = NodeType::Lower;
        Hashtable::table[index].value = value;
    }

    Hashtable::table[index].distanceToLeaf = distanceToLeaf;
    Hashtable::table[index].zobristKey = Hashtable::hash;
    Hashtable::table[index].preferredMove = preferredMove;
}

Here is the code that updates the Zobrist key whenever a move is execute and undone. I tested this to be self-inverse but for the sake of completeness and in case there is anything of note (which reminds me that this would be cleaner with "case" statements):

Code: Select all

 void Hashtable::updateHash(ChessBoard* board, MoveData move) {
    if (move.pieceMoved->colour == Colour::White) {
        hash ^= hk_blackToMove;
        if (move.pieceMoved->getPieceType() == PieceType::Pawn)
            hash = hash ^ hk_whitePawn[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_whitePawn[std::get<0>(move.dest)][std::get<1>(move.dest)];
        else if (move.pieceMoved->getPieceType() == PieceType::Knight)
            hash = hash ^ hk_whiteKnight[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_whiteKnight[std::get<0>(move.dest)][std::get<1>(move.dest)];
        else if (move.pieceMoved->getPieceType() == PieceType::Bishop)
            hash = hash ^ hk_whiteBishop[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_whiteBishop[std::get<0>(move.dest)][std::get<1>(move.dest)];
        else if (move.pieceMoved->getPieceType() == PieceType::Rook)
            hash = hash ^ hk_whiteRook[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_whiteRook[std::get<0>(move.dest)][std::get<1>(move.dest)];
        else if (move.pieceMoved->getPieceType() == PieceType::Queen)
            hash = hash ^ hk_whiteQueen[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_whiteQueen[std::get<0>(move.dest)][std::get<1>(move.dest)];
        else if (move.pieceMoved->getPieceType() == PieceType::King)
            hash = hash ^ hk_whiteKing[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_whiteKing[std::get<0>(move.dest)][std::get<1>(move.dest)];
        if (move.pieceTaken != nullptr) {
            if (move.pieceTaken->getPieceType() == PieceType::Pawn)
                hash = hash ^ hk_blackPawn[std::get<0>(move.dest)][std::get<1>(move.dest)];
            else if (move.pieceTaken->getPieceType() == PieceType::Knight)
                hash = hash ^ hk_blackKnight[std::get<0>(move.dest)][std::get<1>(move.dest)];
            else if (move.pieceTaken->getPieceType() == PieceType::Bishop)
                hash = hash ^ hk_blackBishop[std::get<0>(move.dest)][std::get<1>(move.dest)];
            else if (move.pieceTaken->getPieceType() == PieceType::Rook)
                hash = hash ^ hk_blackRook[std::get<0>(move.dest)][std::get<1>(move.dest)];
            else if (move.pieceTaken->getPieceType() == PieceType::Queen)
                hash = hash ^ hk_blackQueen[std::get<0>(move.dest)][std::get<1>(move.dest)];
            else if (move.pieceTaken->getPieceType() == PieceType::King)
                hash = hash ^ hk_blackKing[std::get<0>(move.dest)][std::get<1>(move.dest)];
        }
        if (move.isWhiteLRookCastling)
            hash = hash ^ hk_whiteLRookCastling;
        else if (move.isWhiteRRookCastling)
            hash = hash ^ hk_whiteRRookCastling;
    }
    else {
        hash = hash ^ hk_whiteToMove;
        if (move.pieceMoved->getPieceType() == PieceType::Pawn)
            hash = hash ^ hk_blackPawn[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_blackPawn[std::get<0>(move.dest)][std::get<1>(move.dest)];
        else if (move.pieceMoved->getPieceType() == PieceType::Knight)
            hash = hash ^ hk_blackKnight[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_blackKnight[std::get<0>(move.dest)][std::get<1>(move.dest)];
        else if (move.pieceMoved->getPieceType() == PieceType::Bishop)
            hash = hash ^ hk_blackBishop[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_blackBishop[std::get<0>(move.dest)][std::get<1>(move.dest)];
        else if (move.pieceMoved->getPieceType() == PieceType::Rook)
            hash = hash ^ hk_blackRook[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_blackRook[std::get<0>(move.dest)][std::get<1>(move.dest)];
        else if (move.pieceMoved->getPieceType() == PieceType::Queen)
            hash = hash ^ hk_blackQueen[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_blackQueen[std::get<0>(move.dest)][std::get<1>(move.dest)];
        else if (move.pieceMoved->getPieceType() == PieceType::King)
            hash = hash ^ hk_blackKing[std::get<0>(move.orig)][std::get<1>(move.orig)] ^ hk_blackKing[std::get<0>(move.dest)][std::get<1>(move.dest)];
        if (move.pieceTaken != nullptr) {
            if (move.pieceTaken->getPieceType() == PieceType::Pawn)
                hash = hash ^ hk_whitePawn[std::get<0>(move.dest)][std::get<1>(move.dest)];
            else if (move.pieceTaken->getPieceType() == PieceType::Knight)
                hash = hash ^ hk_whiteKnight[std::get<0>(move.dest)][std::get<1>(move.dest)];
            else if (move.pieceTaken->getPieceType() == PieceType::Bishop)
                hash = hash ^ hk_whiteBishop[std::get<0>(move.dest)][std::get<1>(move.dest)];
            else if (move.pieceTaken->getPieceType() == PieceType::Rook)
                hash = hash ^ hk_whiteRook[std::get<0>(move.dest)][std::get<1>(move.dest)];
            else if (move.pieceTaken->getPieceType() == PieceType::Queen)
                hash = hash ^ hk_whiteQueen[std::get<0>(move.dest)][std::get<1>(move.dest)];
            else if (move.pieceTaken->getPieceType() == PieceType::King)
                hash = hash ^ hk_whiteKing[std::get<0>(move.dest)][std::get<1>(move.dest)];
        }
        if (move.isBlackLRookCastling)
            hash = hash ^ hk_blackLRookCastling;
        else if (move.isBlackRRookCastling)
            hash = hash ^ hk_blackRRookCastling;
    }
    if (move.prevEnPassantPawn != std::tuple<char, char>(127, 127))
        hash = hash ^ hk_enPassantSquare[std::get<0>(move.prevEnPassantPawn)][std::get<1>(move.prevEnPassantPawn)];
}

Any help would be greatly appreciated. I am looking to move on to more interesting topics, i.e. a better eval function and parallelism, but this has been a head scratcher for me.

[mvanthoor]

To summarize the question, I am looking to enhance my engine with hashtables, but it seems to consistently perform worse when it plays the (otherwise identical) algorithm that does not look up hashtable data. Due to insignificantly higher computational load, and somewhat deeper plies towards the endgame if the TT is utilized, I wonder if the way I store/retrieve/interpret hashtable data is erroneous.

Before you look into the TT, I would advise to -first- check if your Zobrist key is always correct. If this is not the case, then this is an absolute hash table/performance killer, because you'll constantly be storing/retrieving the wrong positions. This will cause performance to tank, even if your hash table is otherwise fully correct.

First: Check if you are doing all the hashing correctly.
- Remove a piece from the hash when it disappears from a square (captured, or is moving)
- Put it into the hash if it reappears on a different square (when moving)
- When promoting, take into account you remove a pawn, but replace one of the four promoted pieces.
- While undoing, make sure you replace a pawn (or the piece you promoted from), while removing the queen.
- Take en-passant square hashing into account.
- Remove and then add the castling rules when they change.
Second: If you think your hashing is correct, then write a little piece of code at the end of make_move(), which generates the Zobrist hash FROM SCRATCH and compares it to the Zobrist hash you're keeping incrementally. Panic/Abort if it's not the same; you then still have problems with the Zobrist hash. It should _ALWAYS_ be correct.

If this is 100% correct all the time, then look into the hash table.

[hgm]

The key updating for the side to move looks a bit suspect. Normally you would XOR with the same 'side-to-move' key on every update. But you use different keys on a white and a black turn. So if both players would pass their turn, you would be in the same position, but you would not have the same key.

Also, you should use the preferred move even when the depth was not sufficient. This is the basis of iterative deepening: that you would copy all cut moves from the previous iteration, in the hope they will still be cut-moves if you search them one ply deeper. As you do it now you completely ignore everything from the previous iteration.

The alpha == beta condition in your hash store routine is also suspect. This can only happen when alpha gets increased as the result of a searched move, and if alpha >= beta you would get a beta cutoff. Which gives you a lower-bound score for the current node, not an exact one.

[Dann Corbit]

A really nice exercise is to create a full rebuild of the hash from a board, along with incremental update of the hash with each movement.

Then, if you have _DEBUG defined, do a complete rebuild whenever you are about to use the hash, and check the hash value from the complete rebuild against the incremental one.

If the two hash values are not identical, you have a bug.

Common places for hashing bugs are:
null move
e.p. rights
castle rights
captures
In that order.

Another thing to investigate is makemove() followed by unmakemove().
If the hash value is not identical to the original after an unmakemove, then you have a bug.

And, if your program gets weaker by using a hash table, then you have a bug.

[niel5946]

Firstly, what does "depthLimit - depth" refer to? Is "depth" the ply, that the position is in? If it is the distance to the leaf nodes, you should just pass that since that is how you store the depth in a position.
Also, why do you only return exact scores? What I do in my engine is:

Code: Select all

if (ttHit && ttEntry->depth >= current_depth && !is_pv){
	if (ttEntry->flag == ALPHA && score <= alpha){
		return alpha;
	}
	if (ttEntry->flag == BETA && score >= beta){
		return beta;
	}
}

I don't return if the score is exact since i probably have the best move and the PV would get shortened.

A last thing is that, in the case of mate scores you should insert these relative to the position you're searching instead of relative to the root. If, for example, you encounter a mate score ten moves from the position you're at now and you are at depth = 5, you should return the score as a mate in fifteen (from the root), but value inserted in the TT should be mate in ten (since that is the relative depth to the current position).
It is usually done like this:

Code: Select all

// Makes a mate score relative to the position instead of the root.
inline int value_to_tt(int score, int ply) {
	return (score > MATE) ? score + ply : ((score < -MATE) ? score - ply : score);
}

// Makes a mate score relative to probing root instead of the stored position
inline int value_from_tt(int score, int ply) {
	return (score > MATE) ? score - ply : ((score < -MATE) ? score + ply : score);
}

Just use the return value of this on everything that you insert or extract to/from the hashtable.

[Paul88]

Thank you all for your replies. This has been immensely helpful. In short, there were three main issues - one was an admittedly silly one, but the most pertinent. Namely, I was using unsigned long as a variable to store the hash instead of unsigned long long. 32 bits just isn't enough, which became completely obvious when I wrote a routine to detect hash collisions. Secondly, the side-to-move-hashing needed to be fixed as pointed out by H.G.Muller, and lastly the promotion hashing, as pointed out by mvanthoor.
Currently, the hashtable-using engine is 7-2-2 (win-draw-lose) against the non-hashtable engine at a fixed 2.5 seconds per player per move, but that's not statistically conclusive - I'll leave it running for several hours to draw a better comparison.

@mvanthoor: Thanks, I did look into the hashing routine to ensure it works properly:
"- While undoing, make sure you replace a pawn (or the piece you promoted from), while removing the queen." - This needed to be fixed.

@H.G.Muller:
Thanks, I did update the side-to-move-rule - the other comments are also extremely helpful. It makes sense to use the preferred move to hopefully cut off more branches.

@Dann Corbit: Good advice - If I rewrite the engine some day or implement hashing for another game, then the recreate-from-scratch-approach would come in handy.

Firstly, what does "depthLimit - depth" refer to? Is "depth" the ply, that the position is in? If it is the distance to the leaf nodes, you should just pass that since that is how you store the depth in a position.
Also, why do you only return exact scores? What I do in my engine is:

Code: Select all

if (ttHit && ttEntry->depth >= current_depth && !is_pv){
	if (ttEntry->flag == ALPHA && score <= alpha){
		return alpha;
	}
	if (ttEntry->flag == BETA && score >= beta){
		return beta;
	}
}

I don't return if the score is exact since i probably have the best move and the PV would get shortened.

A last thing is that, in the case of mate scores you should insert these relative to the position you're searching instead of relative to the root. If, for example, you encounter a mate score ten moves from the position you're at now and you are at depth = 5, you should return the score as a mate in fifteen (from the root), but value inserted in the TT should be mate in ten (since that is the relative depth to the current position).
It is usually done like this:

Code: Select all

// Makes a mate score relative to the position instead of the root.
inline int value_to_tt(int score, int ply) {
	return (score > MATE) ? score + ply : ((score < -MATE) ? score - ply : score);
}

// Makes a mate score relative to probing root instead of the stored position
inline int value_from_tt(int score, int ply) {
	return (score > MATE) ? score - ply : ((score < -MATE) ? score + ply : score);
}

Just use the return value of this on everything that you insert or extract to/from the hashtable.

Depth is the ply, which is always <= depthLimit. It's not particularly neat that I have distanceToLeafNode as a separate metric- would perhaps be cleaner to start at depth=depthLimit and then decrease.
I will look into your comment on mate scores in more detail, thank you.

[Ras]

Namely, I was using unsigned long as a variable to store the hash instead of unsigned long long. 32 bits just isn't enough

Don't use the "raw" integer types for that, use uint64_t. Unsigned long in fact can be 64 bit, namely on 64 bit Linux, but it will be 32 bits on 64 bit Windows. While you're at it, don't use int for things like indexing large arrays, use size_t. And don't use int for storing addresses, use uintptr_t.

I don't return if the score is exact since i probably have the best move and the PV would get shortened.

I faced the same problem with chopped off PVs, and my solution was to not return if I'm in a PV node. That way, an "exact" score can allow a return, that is if the PV changes and the lookup now happens in a non-PV node.