help with Storing hash best move

[AndrewShort]

I have built a simple chess engine in Visual Basic, and to get something working, I used Bruce Moreland's famous sample code as a base (incredibly helpful, btw). The engine works, killer moves work, hashing works, and my hash key is built incrementally, and I verify that the incremental hash key is always correct because I have Asserts that the incremental hash key is the same as a hash key built from scratch. Even my mating scores are hashed correctly, as I adjust them bearing in mind distance to mate. This all works great and I've debugged it extensively.

Now I want to implement the hash best move feature, where if the hashed position was found but the depth wasn't deep enough to use or the score wasn't good enough for a cutoff, we at least see if there is a best move which we try first in our sort. Seems to me there are 3 conditions where we do NOT know the best move:

(1) we are on a leaf node (Depth = 0)
(2) there are no moves to make (player is mated or stalemated)
(3) hash score type was a fail low (score was <= Alpha)

So moves that yield Exact scores or Beta cutoff scores get stored as the best move. To implement this, my AlphaBeta() has a local var uiBestMove (an unsigned 32-bit Integer containing all the move info/coordinates) which is passed byRef to iReadHash(), so after the iReadHash() call, uiBestMove is either a move or it's 0 (0 is an impossible value for a move). I then pass uiBestMove to my SortMoveList() routine, and I have an assert in SortMoveList() that if uiBestMove is non-zero, then it must be found in the move list. But that assert fails! I don't know why. With some debugging I found that it only fails on best moves that are beta cutoff moves. It works with exact-score-best-moves. Here is my AlphaBeta() routine (thanks to Bruce Moreland for his sample code):

Code: Select all

Function AlphaBeta(ByVal iDepth As Integer, ByVal iAlpha As Integer, ByVal iBeta As Integer, ByRef iMoveIndex As Integer) As Integer
    
'iDepth is initially passed in as iMAXPLY   

        Dim iVal As Integer
        Dim iScoreType As Integer
        iScoreType = iHASH_ALPHA

        Dim uiBestMove As UInteger
        uiBestMove = 0

        Dim iBestMoveIndex As Integer
        iBestMoveIndex = -1

        iVal = iReadHash(iDepth, iAlpha, iBeta, uiBestMove)
        If iVal <> iVAL_UNKNOWN Then
            Return iVal
        End If

        If iDepth = 0 Then
            iVal = iEvaluate() 'if mating score, score is offset by iPly
            Call SaveHash(iDepth, iVal, iHASH_EXACT)
            'since iDepth is 0, no 'BestMove' is stored
            Return iVal
        End If

        Call GenerateMoves(iDepth) 'for whoever's turn it is
        If aMOVENUMS(iDepth) = 0 Then 'mate or stalemate
            'if player mated, return mating score
            If fInCheck() Then 'for whoever's turn it is
                Call SaveHash(iDepth, -iINFINITY + iMAXPLY - iDepth, iHASH_EXACT)
                'since aMOVENUMS(iDepth) = 0, no 'BestMove' is stored
                Return -iINFINITY + iMAXPLY - iDepth 'player is mated
            End If
            'player is stalemated, store score of 0 (tie)
            Call SaveHash(iDepth, 0, iHASH_EXACT)
            'since aMOVENUMS(iDepth) = 0, no 'BestMove' is stored
            Return 0
        Else
            Call SortMoveList(iDepth, uiBestMove)
        End If

        aMOVES(iDepth) = 0 'move counter for this ply
        While aMOVES(iDepth) < aMOVENUMS(iDepth) 'while there are moves left
            aMOVES(iDepth) = aMOVES(iDepth) + 1
            Call DoMove(aMOVELIST(aMOVES(iDepth), iDepth), False)
            iVal = -AlphaBeta(iDepth - 1, -iBeta, -iAlpha, iMoveIndex)
            Call UndoMove()
            If iVal >= iBeta Then
                Call StoreKiller(iDepth) 'killer move is beta cutoff move aMOVELIST(aMOVES(iDepth), iDepth)
                Call SaveHash(iDepth, iBeta, iHASH_BETA, aMOVES(iDepth))
                'beta cutoff move, which is aMOVELIST(aMOVES(iDepth), iDepth), will be stored as 'BestMove'
                Return iBeta
            End If
            If iVal > iAlpha Then
                iScoreType = iHASH_EXACT
                iAlpha = iVal
                iBestMoveIndex = aMOVES(iDepth)
            End If
        End While
        Call SaveHash(iDepth, iAlpha, iScoreType, iBestMoveIndex) 'save score in hash table (it will be fail-low or exact)
        'if score type is iHASH_ALPHA, no 'BestMove' is stored (iBestMoveIndex would still be -1)
        'if score type is iHASH_EXACT, the 'BestMove' aMOVELIST(iBestMoveIndex, iDepth) is stored

        iMoveIndex = iBestMoveIndex 'so a ply1 move gets set (iMoveIndex is passed byRef)
        Return iAlpha

End Function

and here is my iReadHash() routine, again, thanks to Bruce Moreland's sample code:

Code: Select all

Function iReadHash(ByVal iDepth As Integer, ByVal iAlpha As Integer, ByVal iBeta As Integer, ByRef uiBestMove As UInteger) As Integer
        'called by AlphaBeta()

        Dim iAdjustedScore As Integer

        Debug.Assert(ulHash() = ulCURRENT_HASH) 'incremental hash is the same as computing hash from scratch

        With aHASH_TABLE(CInt(ulCURRENT_HASH And ulHASHENTRIES))
            If .ulHashCode = ulCURRENT_HASH Then 'we found a match in the hash table
                If .iDepth >= iDepth Then 'depth searched is >= depth to search now
                    If Math.Abs(.iScore) > iMINMATESCORE Then
                        'mating score in hash is really showing the distance to mate (as an offset from +/- infinity)
                        If .iScore > 0 Then
                            iAdjustedScore = .iScore - iMAXPLY + iDepth 'this is like hashscore - ply
                        Else
                            iAdjustedScore = .iScore + iMAXPLY - iDepth 'this is like hashscore + ply
                        End If
                    Else
                        iAdjustedScore = .iScore 'it wasn't a mating score
                    End If
                    If .iScoreType = iHASH_EXACT Then
                        Return iAdjustedScore
                    End If
                    If .iScoreType = iHASH_ALPHA AndAlso iAdjustedScore <= iAlpha Then
                        Return iAlpha
                    End If
                    If .iScoreType = iHASH_BETA AndAlso iAdjustedScore >= iBeta Then
                        Return iBeta
                    End If
                End If
                'remember best move (if any)
                uiBestMove = .uiBestMove
            End If
            Return iVAL_UNKNOWN
        End With

End Function

and here is my SaveHash() routine (for now, 'always replace' scheme, which is what Bruce's sample code does):

Code: Select all

Sub SaveHash(ByVal iDepth As Integer, ByVal iVal As Integer, ByVal iScoreType As Integer, Optional ByVal iBestMoveIndex As Integer = -1)
        'called by AlphaBeta()

        If Math.Abs(iVal) > iMINMATESCORE Then
            'a mating score is being saved in the hash, so adjust the offset from +/- infinity to be
            'the distance from mate, instead of the ply where the mating move is
            If iVal > 0 Then
                iVal = iVal + iMAXPLY - iDepth 'this is like score + ply
            Else
                iVal = iVal - iMAXPLY + iDepth 'this is like score - ply
            End If
        End If

        Debug.Assert(ulHash() = ulCURRENT_HASH) 'incremental hash is the same as computing hash from scratch

         '[hash table is presently cleared every move]
        With aHASH_TABLE(CInt(ulCURRENT_HASH And ulHASHENTRIES))
            .ulHashCode = ulCURRENT_HASH
            .iScore = iVal
            .iScoreType = iScoreType
            .iDepth = iDepth
    
            If iBestMoveIndex <> -1 Then
                'if score is exact or exceeds beta,
                'and not a leaf node, 
                'and player has a move to make - (not mated/stalemated),
                'then store best move
                .uiBestMove = aMOVELIST(iBestMoveIndex, iDepth)
                Debug.Assert(.uiBestMove <> 0)
            Else
                'score was fail low (did not exced alpha),
                'or position was a leaf node
                'or position was over because of mate or stalemate
                'so there is no best move
                .uiBestMove = 0
            End If
        End With
End Sub

This code all works, except that in my SortMoveList() routine (not shown here), I have a simple assert that if uiBestMove is passed in as non-zero, then it must be found in the moves to sort. But that assert fails in the case where the best move was a beta cutoff move. If I only store Exact score best moves, the assert does not fail. Help !

thank you!
[/code]

[hgm]

If I were you, I would first figure out what exactly the move variable retrieved from the hash table does contain. Is it a valid move?

Also count the number of times in your search where the assert fails (just treat the move as 0 when it does). You might just be dealing with key collissions. Remember that hardly any node will get an exact score, so the probability to get a collission on an exact score is very low.

To test if you have key collissions, you might update a second, independent hash key (e.g. similar to the one you use, but using a different table of randoms), and store that in the hash too, and check if it is the same in hash table and search when you porobe and find a non-existent move.

What helped me to find an error like this (which turned out to be due to me having switched to a random() routine that only retuned 16-bit random numbers for generating the keys) was simply write down the number of the entry where the problem occurs, and then rerun the search printing the board and hash key(s) every time something is stored into or read from this entry.

[Harald Johnsen]

The code seems correct to me, so the simplest explanation is that you are retrieving something from the hash that is not from the current position.
You have a hash collision, same key, different position. This should not happen so often (ok we have math crunchers here that can tell the exact probability) but it is of course possible.
Is your hash key a 64 bit value ?

HJ.

[AndrewShort]

Thanks. I figured out the problem. And it is instructive:

Taking your advice, as a temporary test, I set the best move feature to only save best moves if they are beta cutoff moves, then I counted the number of times a move was passed to SortMoveList() and found/not found.

I found that in that case, the move was actually in the move list thousands of times, but not in the move list (causing the assert to fail) only a handful of times (like 3).

Since I have a 64 bit hash key, I felt it was unlikely that a hash collision was my problem, but I increased the size of my hash table 8 fold as a test, and I still had the same problem.

Then I remembered something. I had forgotten to incorporate en passant rights into the hash key. I have the pieces, turn, and castling rights, but not the en passant rights. So as a test, I removed en passant moves completely from my move generation, and then it works - I never get the assert - the move is always found in the move list.

So the problem was not hash collisions after all...

What is the best way to implement en passant rights into the hash key? I guess if the previous pawn-up-2 move is on column 5, for example, then xOR the 5th random constant in an 8 item array of random constants. And if the previous move was not a pawn-up-2 move, then don't xOR a new constant in. Sound right?

[bob]

I did not have time to carefully go thru your code, but two things come to mind...

1. A best move from an EXACT node is the move you stuffed into the PV.

2. A best move from a fail high node is the last move you searched, not the one in the PV which will likely not be set and won't have anything valid in it.

Make sure you get the hash move from a sane place and the problem might well go away... remember that at a fail-high node, the PV doesn't get backed up to you, because the next ply was a fail-low node where nothing was backed up...