Chess Engine in C #3: Hashkeys

#chessprogramming #c #chivickshazard

In the last project dev log, I talked about bitboards, how they are used to show the position of a single piece on the board, and how I set them up in the project. In this article, I will talk about hashkeys.

A hashkey is a unique 64-bit integer used to denote a single position on the chessboard. It is generating by xoring the piece's pseudorandom number with the pseudorandom numbers of all the other pieces on the chessboard. When a piece is moved(e.g. a white bishop moves from f3 to d5), the hashkey xors out the previous position and the engine updates it by xoring in the new position of the bishop.

After doing some extra digging, I discovered that this technique is called Zobrist Hashing. So this is basically done by creating an array of all the pieces, a variable for the side key to hash a random number if it's white's turn to move, and an array for all the castling permissions. So we have something like this:

U64 PieceKeys[13][120];
U64 SideKey;
U64 CastleKeys[16];

Then we use the function below to fill them up with their respective pseudorandom numbers:

#define RAND_64 ( \
    (U64) rand() | \
    ((U64) rand() << 15) | \
    ((U64) rand() << 30) | \
    ((U64) rand() << 45) | \
    (((U64) rand() & 0xf) << 60) \
);

void InitHashKeys() {
    int index = 0;
    int index2 = 0;

    for (index = 0; index < 13; index++) {
        for (index2 = 0; index2 < 120; index2++) {
            PieceKeys[index][index2] = RAND_64;
        }
    }

    SideKey = RAND_64;

    for (index = 0; index < 16; index++) {
        CastleKeys[index] = RAND_64;
    }
}

If you are trying to visualize how the 64-bit integer looks like, this is it:

After all that, we will use this function to generate the position key:

U64 GeneratePosKey(const S_BOARD *pos) {
    int sq = 0;
    U64 finalKey = 0;
    int piece = EMPTY;

    // pieces
    for (sq = 0; sq < BOARD_SQ_NUMBER; sq++) {
        piece = pos->pieces[sq];

        if (piece != NO_SQ && piece != EMPTY && piece != OFFBOARD) {
            ASSERT(piece >= wP && piece <= bK);
            finalKey ^= PieceKeys[piece][sq];
        }
    }

    if (pos->side == WHITE) {
        finalKey ^= SideKey;
    }

    if (pos->enPassant != NO_SQ) {
        ASSERT(pos->enPassant >= 0 && pos->enPassant < BOARD_SQ_NUMBER);
        finalKey ^= PieceKeys[EMPTY][pos->enPassant];
    }

    ASSERT(pos->castlePerm >= 0 && pos->castlePerm <= 15);
    finalKey ^= CastleKeys[pos->castlePerm];
    return finalKey;
}

This is how it works: we have a sq, a finalKey that we will return, and a piece and the function takes a pointer to the position that the key will be generated for. The loop goes all the squares on the chessboard and sets the piece to the pos value of pieces that is stored at that particular sq. Then if piece is not equal to No_SQ, EMPTY & OFFBOARD, and it is greater than or equal to a wP(white Pawn) and it is less than or equal to a bK(black King), then the finalKey is xored with the value of PieceKeys at piece and at sq.

Then if white is to move, finalKey is xored with SideKey. If enPassant is not equal to NO_SQ, and it is greater than or equal to 0 & it is not greater than BOARD_SQ_NUMBER, then the engine xors finalKey with the value of PieceKeys at EMPTY and enPassant.

Lastly, the engine asserts whether the value of castlePerm is between 0 and 15, and if true, the engine xors finalKey with the value of CastleKeys at castlePerm and returns it.

If you haven't read the previous article, click here so that you can follow along and if you want to see the code, you can click here to view the Github repo.

Until the next commit....bye 👋

DEV Community

Chess Engine in C #3: Hashkeys

Top comments (0)