Move Analysis Tree

[peterhughes]

I've always found working on the Search-related functions to be quite challenging. It can be hard to visualise the affect your code is going to have - a bit like "poking around in the dark" at times. Also, the terminology is somewhat confusing to begin with: "cut-off" is different to a "cut-node", but is the same as a fail-high etc...

In an attempt to make things easier for myself, from both understanding and debugging point-of-view, I created a Move Analysis window in the SharpChess GUI, which you can see below. It's probably easier to read on the URL below, which also has direct links to http://chessprogramming.wikispaces.com/.

http://sharpchess.com/?page=50%20Development/05%20Move%20Analysis

It has been most useful to be able to actually see the move ordering assignments, as well as the extension and reduction points. Also it gives a good idea as what's happening (or not) with the branching factor.



# *PV* - Principal Variation (PV) Node score inside the Alpha-Beta window.(Type 1)
# (CUT) - Cut (fail-high) Node fail-high node where a child node cause a beta-cutoff. (Type 2)
# (ALL) - All (fail-low) Node fail-low node in which no move's score exceeded alpha. (Type 3)

# (Q:CUT) - Beta cutoff in Quiescence.
# (Q:PAT-CUT) - Stand-pat beta cutoff in Quiescence.

# -PVS-WIN- - Principal Variation Search successful using zero window.
# -F- Principal Variation Search failed. Perform re-search using full window.

# E-1REP - One Reply Extension
# E-CHK - Check Evation Extension
# E-RECAP - Recapture Extension
# E-PAWN7 - Passed Pawn Extension

# R-FUT3 - Futility Pruning where Depth=2 and LazyEval + Margin = Knight.
# R-FUT5 - Extended Futility Pruning where Depth=3 and LazyEval + Margin = Rook.
# R-FUT9 - Deep Futility Pruning where Depth=4 and LazyEval + Margin = Queen.

# O-HASH - Best move from Transposition table.
# O-PROM - A pawn promotion.
# O-SEE - Move order value of winning (or losing) capture using Static Exchange Evaluation (SEE).
# O-MVV - Where SEE is even, move order value of MVV-LVA (Most Valuable Victim - Least Valuable Aggressor).
# O-KILL(A|B) - Killer Move from slot A or B.
# O-HIST - Move order value from History Heuristic.
# O-SV - Move order value from Piece-Square Value tables.

[Folkert van Heusden]

This looks very very cool!

[Gerd Isenberg]

I've always found working on the Search-related functions to be quite challenging. It can be hard to visualise the affect your code is going to have - a bit like "poking around in the dark" at times. Also, the terminology is somewhat confusing to begin with: "cut-off" is different to a "cut-node", but is the same as a fail-high etc...

In an attempt to make things easier for myself, from both understanding and debugging point-of-view, I created a Move Analysis window in the SharpChess GUI, which you can see below. It's probably easier to read on the URL below, which also has direct links to http://chessprogramming.wikispaces.com/.

http://sharpchess.com/?page=50%20Development/05%20Move%20Analysis

Hi Peter,
very nice

I read on your site on In-Check Hash Tables, but I am actually too lazy to have a look to your source yet. Can you elaborate a bit on this. What does it store, how is it indexed etc..

Thanks,
Gerd

[peterhughes]

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