2

Is there a standardized method for generation of hash keys for chess positions. I want to implement hash key generation in my program, so wanted to know the best way to do it. It would be great if someone can provide details on how the opening books do their hashing (.bin?).

Thanks!

  • 2
    In theory, any hash will work, even the built-in provided by the programming language. – Glorfindel Sep 22 '17 at 17:49
  • 1
    Generating a hash has nothing to do with chess. It is a general programming issue which has built-in solutions in many programming languages. – Brian Towers Sep 22 '17 at 23:02
4

I believe you're talking about Zobrist Hashing.

a technique to transform a board position of arbitrary size into a number of a set length, with an equal distribution over all possible numbers

https://chessprogramming.wikispaces.com/Zobrist+Hashing

Why Zobrist?

  • Rather than computing the hash for the entire board every time, the hash value of a board can be updated simply by XORing out the bitstring(s) for positions that have changed. That makes the hashing algorithm very efficient for chess engines.
0

Here's how I update the Zobrist hash in MadChess, my chess engine. MadChess uses "mailbox" board representation (uses an int[] to represent pieces on the board), not bitboards.

The Board constructor:

// Create Zobrist position keys.
_piecesSquaresInitialKey = ULongRandom.Next();
_pieceSquareKeys = new ulong[13][];
for (int piece = 0; piece < 13; piece++)
{
    _pieceSquareKeys[piece] = new ulong[64];
    for (int square = 0; square < 64; square++)
    {
        _pieceSquareKeys[piece][square] = ULongRandom.Next();
    }
}
_sideToMoveKeys = new[] { ULongRandom.Next(), ULongRandom.Next() };
_castlingKeys = new ulong[16];
{
    for (int castlingRights = 0; castlingRights < 16; castlingRights++)
    {
        _castlingKeys[castlingRights] = ULongRandom.Next();
    }
}
_enPassantKeys = new ulong[64];
for (int square = 0; square < 64; square++)
{
    _enPassantKeys[square] = ULongRandom.Next();
}

This is called every time a piece is added or removed from a square:

private void UpdatePiecesSquaresKey(int Piece, int Square)
{
    ulong pieceSquareKey = _pieceSquareKeys[Piece][Square];
    // XOR square piece key.
    CurrentPosition.PiecesSquaresKey ^= pieceSquareKey;
    #if DEBUG
    // Verify incrementally updated pieces squares key matches fully updated pieces squares key.
    ulong fullyUpdatedPiecesSquaresKey = _piecesSquaresInitialKey;
    for (int square = 0; square < 64; square++)
    {
        int piece = CurrentPosition.Squares[square];
        if (piece != Engine.Piece.None)
        {
            pieceSquareKey = _pieceSquareKeys[piece][square];
            fullyUpdatedPiecesSquaresKey ^= pieceSquareKey;
        }
    }
    Debug.Assert(fullyUpdatedPiecesSquaresKey == CurrentPosition.PiecesSquaresKey);
    #endif
}

This combines all the board state keys to produce a position key:

private ulong GetPositionKey()
{
    ulong sideToMoveKey = CurrentPosition.WhiteMove ? _sideToMoveKeys[0] : _sideToMoveKeys[1];
    ulong castlingKey = _castlingKeys[CurrentPosition.Castling];
    ulong enPassantKey = CurrentPosition.EnPassantSquare == Square.Illegal ? _enPassantKeys[0] : _enPassantKeys[CurrentPosition.EnPassantSquare];
    // XOR keys.
    return CurrentPosition.PiecesSquaresKey ^ sideToMoveKey ^ castlingKey ^ enPassantKey;
}

This is called when all pieces are removed from the board (prior to setting up a new position from a FEN string):

private void Reset(bool PreserveMoveCount)
{
    // Reset position index, position, key, and stats.
    _positionIndex = 0;
    CurrentPosition.Reset();
    CurrentPosition.PiecesSquaresKey = _piecesSquaresInitialKey;
    if (!PreserveMoveCount)
    {
        // Reset nodes.
        Nodes = 0L;
        NodesInfoUpdate = UciStream.NodesInfoInterval;
    }
}

This generates a random unsigned long (64 bit integer):

public static class ULongRandom
{
    private static readonly byte[] _buffer = new byte[sizeof(ulong)];
    private static readonly Random _random = new Random();


    public static ulong Next()
    {
        _random.NextBytes(_buffer);
        return BitConverter.ToUInt64(_buffer, 0);
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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