Testing Zobrist key

[eligolf]

Hi,

I have recently tried to implement a TT into my engine, which seems super easy in theory. Then I saw really strange behaviors when using it, first of all the node count and time it took to a certain depth went up.

Then I tried a simple approach for move generation:

Code: Select all

        if key in self.tt_move:
            children = self.tt_move[key]
        else:
            children = self.gamestate.get_valid_moves()
            self.tt_move[key] = children

Where self.tt_move is simply a Python dict with the Zobrist key as key and the valid move list as item. Simple enough right?

But when testing I found that while this simple "TT" reduced my overall time to a depth slightly, it also reduced the number of moves searched. Since this is just a matter of getting the legal moves in a position this seems very strange, and I suspect there is a bug somewhere.

So to the main question:Is there a testing framework to test if I incrementally update my Zobrist key correct? I have made some simple manual tests which seems to be fine, but is there more of a batch approach similar to perft? Or how do you guys handle this?

[mvanthoor]

But when testing I found that while this simple "TT" reduced my overall time to a depth slightly, it also reduced the number of moves searched. Since this is just a matter of getting the legal moves in a position this seems very strange, and I suspect there is a bug somewhere.

I have yet to implement a TT myself (next task, actually), but I think this can be true. If the position is in the TT, the best_move stored with that position could cause a beta-cutoff in your current search. That would thus mean you need to search less positions.

So to the main question:Is there a testing framework to test if I incrementally update my Zobrist key correct? I have made some simple manual tests which seems to be fine, but is there more of a batch approach similar to perft? Or how do you guys handle this?

Yes. When you start the engine, you should have something like init_zobrist() which creates the initial Zobrist value.

In your make_move() function, add a part that calculates the Zobrist key of the position by calling init_zobrist(). Check the result against youru currently incremented Zobrist key. They should be the same. if they are not, you have a bug:

- Either your init_zobrist() is not correct, or...
- The functions moving your pieces are not correct, or...
- You are (for example) forgetting to remove the Zobrist hashes for castling, in make_move(), when castling rights are lost.

I do exactly that in my engine:
Initialize Zobrist: https://github.com/mvanthoor/rustic/blo ... zobrist.rs
Testing (in debug mode only): https://github.com/mvanthoor/rustic/blo ... laymove.rs

[emadsen]

So to the main question:Is there a testing framework to test if I incrementally update my Zobrist key correct? I have made some simple manual tests which seems to be fine, but is there more of a batch approach similar to perft? Or how do you guys handle this?

In a debug configuration (#if DEBUG), compare the incrementally updated Zobrist key (when you add or remove a piece to a square) with a fully calculated Zobrist key. Like this:

Code: Select all

private void UpdatePiecesSquaresKey(int Piece, int Square)
{
    CurrentPosition.PiecesSquaresKey ^= _pieceSquareKeys[Piece][Square];
    Debug.Assert(AssertPiecesSquaresKeyIntegrity());
}


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


private bool AssertPiecesSquaresKeyIntegrity()
{
    // Verify incrementally updated pieces squares key matches fully updated pieces squares key.
    var fullyUpdatedPiecesSquaresKey = _piecesSquaresInitialKey;
    for (var square = 0; square < 64; square++)
    {
        var piece = CurrentPosition.GetPiece(square);
        if (piece != Piece.None) fullyUpdatedPiecesSquaresKey ^= _pieceSquareKeys[piece][square];
    }
    return fullyUpdatedPiecesSquaresKey == CurrentPosition.PiecesSquaresKey;
}

Then build a debug version and run it to see if the incrementally updated Zobrist key ever differs from the fully updated key. The perft command is perfect for this test.

In C#, Debug.Assert statements throw exceptions if false. Debug.Asserts are excluded from Release builds. So this integrity check slows down a Debug build but does not adversely impact performance of a Release build.

In C#, ^= means XOR compound assignment. Same as fullyUpdatedPiecesSquaresKey = fullyUpdatedPiecesSquaresKey ^ _pieceSquareKeys[piece][square];

[eligolf]

Thanks guys, this is a great test, should have thought about it myself