Caching Check in SharpChess

[Gerd Isenberg]

To don't interfere too much with the Move Analysis Tree topic, I start a new thread ...

Hi Gerd, it's a hash table using http://chessprogramming.wikispaces.com/Zobrist+Hashing, modified by the player's colour, and indexed using the MOD of the hash key. I use double hash codes in all my hash tables, to reduce the chance of two chess positions resolving to the same hash. I'm not sure if double hash codes are really necessary, but there you go...

The code below is in C#. I use the C# "unsafe" modifier to enable use of pointer manipulation (like in C) which was/is considerably faster than using C# arrays.

Code: Select all

        /// <summary>
        /// Checks is the player is in check for the specified position, and caches the result.
        /// </summary>
        /// <param name="hashCodeA">
        /// Hash Code for Board position A
        /// </param>
        /// <param name="hashCodeB">
        /// Hash Code for Board position B
        /// </param>
        /// <param name="player">
        /// The player.
        /// </param>
        /// <returns>
        /// Returns whether the player in check.
        /// </returns>
        public static unsafe bool QueryandCachePlayerInCheckStatusForPosition(ulong hashCodeA, ulong hashCodeB, Player player)
        {
            fixed (HashEntry* phashBase = &hashTableEntries[0])
            {
                if (player.Colour == Player.PlayerColourNames.Black)
                {
                    hashCodeA |= 0x1;
                    hashCodeB |= 0x1;
                }
                else
                {
                    hashCodeA &= 0xFFFFFFFFFFFFFFFE;
                    hashCodeB &= 0xFFFFFFFFFFFFFFFE;
                }

                HashEntry* phashEntry = phashBase;
                phashEntry += (uint)(hashCodeA % hashTableSize);

                if (phashEntry->HashCodeA != hashCodeA || phashEntry->HashCodeB != hashCodeB)
                {
                    phashEntry->HashCodeA = hashCodeA;
                    phashEntry->HashCodeB = hashCodeB;
                    phashEntry->IsInCheck = player.DetermineCheckStatus();
                }

                return phashEntry->IsInCheck;
            }
        }


Ahh, I see, super safe 126-bit Zobrist signatures for each side. For usual TT, most would use 64 signatures, already incorporating side to move. Did you count number of probes and hits and is that caching a win for you?

Of course it depends on how expensive player.DetermineCheckStatus is, but check detection by last move is usually quite cheap with 0x88.

Gerd

[peterhughes]

End Game Position: "8/2R2pk1/2P5/2r5/1p6/1P2Pq2/8/2K1B3 w - - 5 44"
Search Depth: 5

Nodes searched: 12370
Probes: 324398
Hits: 271702
Writes: 52696
Overwites: 19316

*Opening Position*
Search depth : 5
Nodes searched: 10974
Probes: 120935
Hits: 98987
Writes: 21948
Overwites: 4012

"QueryandCachePlayerInCheckStatusForPosition" is called from 14 places in the source code. 12 places inside the alpha beta loop.

It would probably be more optimal to calculate and store the check status for each side when a move is generated, then store those values as a couple Booleans on the move class. The move class itself might still intially query the Check Hash Table, in order to sets its intial values. I wager that would dramtically reduce the number of Probes. It would require some restructuring, as the Check status is a property of a player.

Out of interest, I've attached the code that determines if the player is in check.

From the PieceKing class:

Code: Select all

        public bool DetermineCheckStatus()
        {
            return this.Base.Square.PlayerCanAttackSquare(this.Base.Player.OpposingPlayer);
        }

From the Square class:

Code: Select all

        /// <summary>
        /// Determines whether the specified player can attack this square.
        /// </summary>
        /// <param name="player">
        /// The player being tested.
        /// </param>
        /// <returns>
        /// True if player can move a piece to this square.
        /// </returns>
        public bool PlayerCanAttackSquare(Player player)
        {
            Piece piece;

            // Pawn
            piece = Board.GetPiece(this.Ordinal - player.PawnAttackLeftOffset);
            if (piece != null && piece.Name == Piece.PieceNames.Pawn && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal - player.PawnAttackRightOffset);
            if (piece != null && piece.Name == Piece.PieceNames.Pawn && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            // Knight
            piece = Board.GetPiece(this.Ordinal + 33);
            if (piece != null && piece.Name == Piece.PieceNames.Knight && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal + 18);
            if (piece != null && piece.Name == Piece.PieceNames.Knight && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal - 14);
            if (piece != null && piece.Name == Piece.PieceNames.Knight && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal - 31);
            if (piece != null && piece.Name == Piece.PieceNames.Knight && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal - 33);
            if (piece != null && piece.Name == Piece.PieceNames.Knight && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal - 18);
            if (piece != null && piece.Name == Piece.PieceNames.Knight && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal + 14);
            if (piece != null && piece.Name == Piece.PieceNames.Knight && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal + 31);
            if (piece != null && piece.Name == Piece.PieceNames.Knight && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            // Bishop & Queen
            if (Board.LinesFirstPiece(player.Colour, Piece.PieceNames.Bishop, this, 15) != null)
            {
                return true;
            }

            if (Board.LinesFirstPiece(player.Colour, Piece.PieceNames.Bishop, this, 17) != null)
            {
                return true;
            }

            if (Board.LinesFirstPiece(player.Colour, Piece.PieceNames.Bishop, this, -15) != null)
            {
                return true;
            }

            if (Board.LinesFirstPiece(player.Colour, Piece.PieceNames.Bishop, this, -17) != null)
            {
                return true;
            }

            // Rook & Queen
            if (Board.LinesFirstPiece(player.Colour, Piece.PieceNames.Rook, this, 1) != null)
            {
                return true;
            }

            if (Board.LinesFirstPiece(player.Colour, Piece.PieceNames.Rook, this, -1) != null)
            {
                return true;
            }

            if (Board.LinesFirstPiece(player.Colour, Piece.PieceNames.Rook, this, 16) != null)
            {
                return true;
            }

            if (Board.LinesFirstPiece(player.Colour, Piece.PieceNames.Rook, this, -16) != null)
            {
                return true;
            }

            // King!
            piece = Board.GetPiece(this.Ordinal + 16);
            if (piece != null && piece.Name == Piece.PieceNames.King && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal + 17);
            if (piece != null && piece.Name == Piece.PieceNames.King && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal + 1);
            if (piece != null && piece.Name == Piece.PieceNames.King && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal - 15);
            if (piece != null && piece.Name == Piece.PieceNames.King && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal - 16);
            if (piece != null && piece.Name == Piece.PieceNames.King && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal - 17);
            if (piece != null && piece.Name == Piece.PieceNames.King && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal - 1);
            if (piece != null && piece.Name == Piece.PieceNames.King && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            piece = Board.GetPiece(this.Ordinal + 15);
            if (piece != null && piece.Name == Piece.PieceNames.King && piece.Player.Colour == player.Colour)
            {
                return true;
            }

            return false;
        }


From the Board class:

Code: Select all

        /// <summary>
        /// Returns the first piece found in a vector from the specified Square.
        /// </summary>
        /// <param name="colour">
        /// The colour.
        /// </param>
        /// <param name="pieceName">
        /// The piece name.
        /// </param>
        /// <param name="squareStart">
        /// The square start.
        /// </param>
        /// <param name="vectorOffset">
        /// The vector offset.
        /// </param>
        /// <returns>
        /// The first piece on the line, or null.
        /// </returns>
        public static Piece LinesFirstPiece(
            Player.PlayerColourNames colour, Piece.PieceNames pieceName, Square squareStart, int vectorOffset)
        {
            int intOrdinal = squareStart.Ordinal;
            Square square;

            intOrdinal += vectorOffset;
            while ((square = GetSquare(intOrdinal)) != null)
            {
                if (square.Piece == null)
                {
                }
                else if (square.Piece.Player.Colour != colour)
                {
                    return null;
                }
                else if (square.Piece.Name == pieceName || square.Piece.Name == Piece.PieceNames.Queen)
                {
                    return square.Piece;
                }
                else
                {
                    return null;
                }

                intOrdinal += vectorOffset;
            }

            return null;
        }


[Gerd Isenberg]

"QueryandCachePlayerInCheckStatusForPosition" is called from 14 places in the source code. 12 places inside the alpha beta loop.

It would probably be more optimal to calculate and store the check status for each side when a move is generated, then store those values as a couple Booleans on the move class. The move class itself might still intially query the Check Hash Table, in order to sets its intial values. I wager that would dramtically reduce the number of Probes. It would require some restructuring, as the Check status is a property of a player.

Yes, that is what I suggest. Determine in check once per node to store it in the position. You need to consider that probing your hash table that way (once per node) versus calculation once on the fly (best and fast from last move made inside the tree) favors calculation, due to cash misses from L2-cache (additionally to table misses), competing with TT and other tables and memory accesses, possibly polluting caches. Also the ratio of used information of one (or two) bits versus entry size and stored key of 128 bits looks a bit wasteful to me.