3

I have implemented a simple variant of Zobrist keys to store and look up positional data, but whenever I let my engine play itself with either white or black using hashtables and the opponent doesn't, the player using the hashtable consistently performs worse.

I can rule out a significant computational load due to the hash key updates and storing/retrieval of data - the kilonodes per second are more or less within the same range. Secondly, I observe that in the endgame, a 9 ply depth of the player not using hashtables is met with about 11 plies for the player using hashtables. In the early game, there is almost no discernible advantage in search depth (which is a side question - does that seem sensible?). Still, given the increased endgame depth, one would expect a systematic benefit for the player using hashtables - all else being equal (no quiescence search, same allocated time for iterative deepening), that is.

Hence, I believe that the error has to do with storage or retrieval of data; or incorrect hash keys. The latter seems implausible based on tests. I would appreciate if anyone can point out a potential problem with the hashtable implementation.

Here is the code to insert data into the hashtable, which is called at each node when alpha beta returns a value:

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 part of the alpha-beta-search function that invokes the hashtable. This part is executed before the possible moves at this position are determined and alphabeta is called recursively:

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);
    }
}

The idea being that I either have searched a position fully (exact node- I can just return the value), or I can update alpha or beta if they provide an improvement of an earlier bound. Moreover, I can store the preferred move (may not be the best one due to an early cutoff) and pass that to an alpha beta implementation that executes this preferred move first (Engine::alphaBeta_preferredMove).

Lastly, here is the code for updating the Zobrist key given a move (this has been tested to be self-inverse, but perhaps there is still a problem somewhere - and apologies for the lack of case statements, and the nasty std::get<> notation). Obviously, this gets called every time a move is made, and every time a move is unmade. "hk_[...]" are (arrays of) random bitstrings per board feature that are initialized at the start.

    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)];
}
Improve this question
2
  • 1
    Have you measured or counted how often a hash collision occurs? I don't see any method to deal with hash collisions aside from eviction, and the hash being based on Hashtable::hash seems suspicious (it should be a function based on the key, but I'm not sure the definition of Hashtable::hash)
    – nanofarad
    Mar 17, 2021 at 16:16
  • Thanks - hash collisions were the main issue. I will post an answer.
    – Paul
    Mar 20, 2021 at 20:08

1 Answer 1

Reset to default
3

There were three main issues - I was foolishly using unsigned long as a variable to store the hash instead of unsigned long long. I wrote a functionto detect hash collisions, and there were plenty. Lastly, there were two bugs with the hash generation that I have now fixed.

Improve this answer
1
  • Note that experiments on SF show that you should be able to go down to 20 bits of hash without notable performance degradation.
    – Oscar Smith
    Mar 21, 2021 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.