Problem with checkmate detection

[eligolf]

The arguments of the is_square_attacked are (square, color_to_move). It finds that it is in check and gives the correct checkmate attribute in the PV-line (if not if would give 0.5-0.5 since we would not be in check, no moves -> draw).

[Ferdy]

The I have the negamax function itself, where at the bottom I detect checkmate/stalemate:

Code: Select all

    def negamax(depth, alpha, beta):

        # Init PV length
        self.pv_length[self.ply] = self.ply

        # Depth = 0, return value from the quiescence search
        if depth == 0:
            return self.quiescence(alpha, beta)

        # Increment node count
        self.nodes += 1

        # Is own king in check?
        self.is_in_check = self.gamestate.is_square_attacked(self.gamestate.king_pos[self.gamestate.side_to_move], self.gamestate.side_to_move)

        # Check extension
        if self.is_in_check:
            depth += 1

        # Get pseudo legal moves
        children = mg.gen_moves(self.gamestate)

        # Sort the moves
        children = self.sort_moves(children)

        # If we are following PV line, we want to enable PV-scoring
        if self.follow_pv:
            self.enable_pv_scoring(children)

        # Init legal moves counter and best move so far
        self.legal_moves = 0

        # Number of moves searched in the moves list
        moves_searched = 0

        # Negamax recursive loop
        for child in children:

            # If move is legal, make it. Otherwise move on to the next candidate.
            if self.gamestate.make_move(child):

                # Increment legal moves and ply
                self.legal_moves += 1
                self.ply += 1

                # Do a normal search
                score = -self.negamax(depth - 1, -beta, -alpha)

                # Decrement ply and increase number of moves searched
                self.ply -= 1
                moves_searched += 1

                # Take back move
                self.gamestate.unmake_move()

                # Fail-hard beta cutoff (node fails high)
                if score >= beta:

                    # Store killer moves, only if it is a non-capturing move (used in move sorting)
                    if mg.extract_capture(child) == 0:
                        self.killer_moves[1][self.ply] = self.killer_moves[0][self.ply]
                        self.killer_moves[0][self.ply] = child

                    return beta

                # Found a better move (PV-node)
                if score > alpha:
                    alpha = score

                    # Store history moves, only if it is a non-capturing move (used in move sorting)
                    if mg.extract_capture(child) == 0:
                        self.history_moves[mg.extract_piece_moved(child)][mg.extract_to_square(child)] += depth

                    # Write PV move to PV table for the given ply
                    self.pv_table[self.ply][self.ply] = child

                    # Loop over the next ply
                    for next_ply in range(self.ply + 1, self.pv_length[self.ply + 1], 1):

                        # Copy move from deeper ply into current ply's line
                        self.pv_table[self.ply][next_ply] = self.pv_table[self.ply + 1][next_ply]

                    # Adjust PV length
                    self.pv_length[self.ply] = self.pv_length[self.ply + 1]

        # If we don't have a legal move to make in the position, check whether it's checkmate or stalemate
        if not self.legal_moves:

            # Checkmate, return checkmate score
            if self.is_in_check:
                return -1e9 + self.ply

            # Stalemate, return stalemate score
            return 0

        # Node fails low
        return alpha

Call this

Code: Select all

self.ply -= 1

after unmake()

[Sven]

The arguments of the is_square_attacked are (square, color_to_move). It finds that it is in check and gives the correct checkmate attribute in the PV-line (if not if would give 0.5-0.5 since we would not be in check, no moves -> draw).

Sounds ok, although I don't see why there is any reason to see that checkmate in a PV (it is just a checkmate occurring after a bad move) ...

Next question: Is "self.legal_moves" a local variable that is kept once per recursion level, or part of a global object (so that other recursion levels may overwrite it)? It looks like the latter to me but I may be wrong ...

[Pio]

Hi all,

I am getting some very strange behaviour with my scoring when it comes to checkmate detection. My perft is working fine so there is nothing wrong with my movegen or make/unmake move functions. The problem is that as soon as it sees a mate it will print the mate score in the output score. For example, in this position with black to move: [d]3r1k1b/5p2/4np2/3R1N2/3P1NPP/2K1PP2/8/8 b - - 0 1

The output from the search function looks like this (minus means that the AI think it is worse):


At depth 3 I assume it sees that playing Nxf4 results in Rxd8# (it needs an extra depth to actually find that black has no moves to play). But shouldn't the score be changed when it finds something better to play for itself? Here are some snippets of my code (just the important parts), I hope you can help me spot where I am thinking wrong.

Iterative deepening (where I save the score from each depth):

Code: Select all

for depth in range(1, max_search_depth + 1):
    self.legal_moves = 0
    self.ply = 0
    self.pv_length = [0]*max_ply 
    self.pv_table = [[0]*max_ply for _ in range(max_ply)]
    
    # Search the position with negamax to given depth
    score = negamax(depth, alpha, beta, False)
    
    # Here I save variables into a dict to be able to print in the GUI
    self.print_info[depth-1] = {'depth': str(depth), 'time': f'{self.timer:.2f}', 'nodes': str(self.nodes), 'score': score/100, 'main_line': self.pv_line}
    
     # Break if time has run out, if it has reached at least min given search depth
     if (self.timer > s.max_search_time and depth >= self.min_search_depth):
         break

The I have the negamax function itself, where at the bottom I detect checkmate/stalemate:

Code: Select all

    def negamax(depth, alpha, beta):

        # Init PV length
        self.pv_length[self.ply] = self.ply

        # Depth = 0, return value from the quiescence search
        if depth == 0:
            return self.quiescence(alpha, beta)

        # Increment node count
        self.nodes += 1

        # Is own king in check?
        self.is_in_check = self.gamestate.is_square_attacked(self.gamestate.king_pos[self.gamestate.side_to_move], self.gamestate.side_to_move)

        # Check extension
        if self.is_in_check:
            depth += 1

        # Get pseudo legal moves
        children = mg.gen_moves(self.gamestate)

        # Sort the moves
        children = self.sort_moves(children)

        # If we are following PV line, we want to enable PV-scoring
        if self.follow_pv:
            self.enable_pv_scoring(children)

        # Init legal moves counter and best move so far
        self.legal_moves = 0

        # Number of moves searched in the moves list
        moves_searched = 0

        # Negamax recursive loop
        for child in children:

            # If move is legal, make it. Otherwise move on to the next candidate.
            if self.gamestate.make_move(child):

                # Increment legal moves and ply
                self.legal_moves += 1
                self.ply += 1

                # Do a normal search
                score = -self.negamax(depth - 1, -beta, -alpha)

                # Decrement ply and increase number of moves searched
                self.ply -= 1
                moves_searched += 1

                # Take back move
                self.gamestate.unmake_move()

                # Fail-hard beta cutoff (node fails high)
                if score >= beta:

                    # Store killer moves, only if it is a non-capturing move (used in move sorting)
                    if mg.extract_capture(child) == 0:
                        self.killer_moves[1][self.ply] = self.killer_moves[0][self.ply]
                        self.killer_moves[0][self.ply] = child

                    return beta

                # Found a better move (PV-node)
                if score > alpha:
                    alpha = score

                    # Store history moves, only if it is a non-capturing move (used in move sorting)
                    if mg.extract_capture(child) == 0:
                        self.history_moves[mg.extract_piece_moved(child)][mg.extract_to_square(child)] += depth

                    # Write PV move to PV table for the given ply
                    self.pv_table[self.ply][self.ply] = child

                    # Loop over the next ply
                    for next_ply in range(self.ply + 1, self.pv_length[self.ply + 1], 1):

                        # Copy move from deeper ply into current ply's line
                        self.pv_table[self.ply][next_ply] = self.pv_table[self.ply + 1][next_ply]

                    # Adjust PV length
                    self.pv_length[self.ply] = self.pv_length[self.ply + 1]

        # If we don't have a legal move to make in the position, check whether it's checkmate or stalemate
        if not self.legal_moves:

            # Checkmate, return checkmate score
            if self.is_in_check:
                return -1e9 + self.ply

            # Stalemate, return stalemate score
            return 0

        # Node fails low
        return alpha

One possible related issue is that it finds mate in the position, but if depth increases it might play an "in-between move" and not play the shortest way to victory. This is solved by breaking the iterative deepening as soon as it finds mate by below code, but it might give me other weird behaviours:

Code: Select all

if abs(score) >= 1e6:
    break

One question is that, shouldn't the mate score I send depend on which color it is to move? For example like this in the checkmate detection code:

Code: Select all

if self.is_in_check:
    return -1e9 + self.ply if self.gamestate.side_to_move == Color.WHITE else 1e9 - self.ply

However, this leads to it not finding the mate at all in the first position and somehow it plays Nxf4 instead which is very strange.

Very thankful for any input and insights. I am following Maksims tutorial on YouTube, huge thanks to him for helping me with e.g. obtaining PV-line. The checkmate episode is found here https://www.youtube.com/watch?v=lAAdjCk ... s&index=51.

I think one of the errors you have done is to make legal_moves an object variable. You should make it a local variable within the function. As it is now if I am not mistaken some deeper function calls can reset the self.legal_moves to zero and that might give wrong stalemate and mate scores. I would have done the ply variable local as well passing it to the negamax function. Making variables as local as possible prevents lots of bugs and makes it possible for you later to parallelise your code.

I would put the mate and stalemate check in the beginning of the function (I always do the exit test for recursive functions in the beginning) but I see you use a pseudo legal generator and that is why you have to do the check after.

[Pio]

Hi all,

I am getting some very strange behaviour with my scoring when it comes to checkmate detection. My perft is working fine so there is nothing wrong with my movegen or make/unmake move functions. The problem is that as soon as it sees a mate it will print the mate score in the output score. For example, in this position with black to move: [d]3r1k1b/5p2/4np2/3R1N2/3P1NPP/2K1PP2/8/8 b - - 0 1

The output from the search function looks like this (minus means that the AI think it is worse):


At depth 3 I assume it sees that playing Nxf4 results in Rxd8# (it needs an extra depth to actually find that black has no moves to play). But shouldn't the score be changed when it finds something better to play for itself? Here are some snippets of my code (just the important parts), I hope you can help me spot where I am thinking wrong.

Iterative deepening (where I save the score from each depth):

Code: Select all

for depth in range(1, max_search_depth + 1):
    self.legal_moves = 0
    self.ply = 0
    self.pv_length = [0]*max_ply 
    self.pv_table = [[0]*max_ply for _ in range(max_ply)]
    
    # Search the position with negamax to given depth
    score = negamax(depth, alpha, beta, False)
    
    # Here I save variables into a dict to be able to print in the GUI
    self.print_info[depth-1] = {'depth': str(depth), 'time': f'{self.timer:.2f}', 'nodes': str(self.nodes), 'score': score/100, 'main_line': self.pv_line}
    
     # Break if time has run out, if it has reached at least min given search depth
     if (self.timer > s.max_search_time and depth >= self.min_search_depth):
         break

The I have the negamax function itself, where at the bottom I detect checkmate/stalemate:

Code: Select all

    def negamax(depth, alpha, beta):

        # Init PV length
        self.pv_length[self.ply] = self.ply

        # Depth = 0, return value from the quiescence search
        if depth == 0:
            return self.quiescence(alpha, beta)

        # Increment node count
        self.nodes += 1

        # Is own king in check?
        self.is_in_check = self.gamestate.is_square_attacked(self.gamestate.king_pos[self.gamestate.side_to_move], self.gamestate.side_to_move)

        # Check extension
        if self.is_in_check:
            depth += 1

        # Get pseudo legal moves
        children = mg.gen_moves(self.gamestate)

        # Sort the moves
        children = self.sort_moves(children)

        # If we are following PV line, we want to enable PV-scoring
        if self.follow_pv:
            self.enable_pv_scoring(children)

        # Init legal moves counter and best move so far
        self.legal_moves = 0

        # Number of moves searched in the moves list
        moves_searched = 0

        # Negamax recursive loop
        for child in children:

            # If move is legal, make it. Otherwise move on to the next candidate.
            if self.gamestate.make_move(child):

                # Increment legal moves and ply
                self.legal_moves += 1
                self.ply += 1

                # Do a normal search
                score = -self.negamax(depth - 1, -beta, -alpha)

                # Decrement ply and increase number of moves searched
                self.ply -= 1
                moves_searched += 1

                # Take back move
                self.gamestate.unmake_move()

                # Fail-hard beta cutoff (node fails high)
                if score >= beta:

                    # Store killer moves, only if it is a non-capturing move (used in move sorting)
                    if mg.extract_capture(child) == 0:
                        self.killer_moves[1][self.ply] = self.killer_moves[0][self.ply]
                        self.killer_moves[0][self.ply] = child

                    return beta

                # Found a better move (PV-node)
                if score > alpha:
                    alpha = score

                    # Store history moves, only if it is a non-capturing move (used in move sorting)
                    if mg.extract_capture(child) == 0:
                        self.history_moves[mg.extract_piece_moved(child)][mg.extract_to_square(child)] += depth

                    # Write PV move to PV table for the given ply
                    self.pv_table[self.ply][self.ply] = child

                    # Loop over the next ply
                    for next_ply in range(self.ply + 1, self.pv_length[self.ply + 1], 1):

                        # Copy move from deeper ply into current ply's line
                        self.pv_table[self.ply][next_ply] = self.pv_table[self.ply + 1][next_ply]

                    # Adjust PV length
                    self.pv_length[self.ply] = self.pv_length[self.ply + 1]

        # If we don't have a legal move to make in the position, check whether it's checkmate or stalemate
        if not self.legal_moves:

            # Checkmate, return checkmate score
            if self.is_in_check:
                return -1e9 + self.ply

            # Stalemate, return stalemate score
            return 0

        # Node fails low
        return alpha

One possible related issue is that it finds mate in the position, but if depth increases it might play an "in-between move" and not play the shortest way to victory. This is solved by breaking the iterative deepening as soon as it finds mate by below code, but it might give me other weird behaviours:

Code: Select all

if abs(score) >= 1e6:
    break

One question is that, shouldn't the mate score I send depend on which color it is to move? For example like this in the checkmate detection code:

Code: Select all

if self.is_in_check:
    return -1e9 + self.ply if self.gamestate.side_to_move == Color.WHITE else 1e9 - self.ply

However, this leads to it not finding the mate at all in the first position and somehow it plays Nxf4 instead which is very strange.

Very thankful for any input and insights. I am following Maksims tutorial on YouTube, huge thanks to him for helping me with e.g. obtaining PV-line. The checkmate episode is found here https://www.youtube.com/watch?v=lAAdjCk ... s&index=51.

I think one of the errors you have done is to make legal_moves an object variable. You should make it a local variable within the function. As it is now if I am not mistaken some deeper function calls can reset the self.legal_moves to zero and that might give wrong stalemate and mate scores. I would have done the ply variable local as well passing it to the negamax function. Making variables as local as possible prevents lots of bugs and makes it possible for you later to parallelise your code.

I would put the mate and stalemate check in the beginning of the function (I always do the exit test for recursive functions in the beginning) but I see you use a pseudo legal generator and that is why you have to do the check after.

What I meant was change self.legal_moves to legal_moves everywhere and remove the legal_moves from any field or constructor declaration. As it is now self.legal_moves will be set to the right most grandchild’s legal_moves before entering the mate and stalemate code and if the right most grandchild’s legal moves happens to be zero you will be in real trouble when entering the mate and stalemate code.

[eligolf]

Sven and Pio, you have done it It now works as expected with the output looking like this:



Also big thanks to Ferdy for pointing out several other fixes, really appreciate the help.

[Pio]

Sven and Pio, you have done it It now works as expected with the output looking like this:



Also big thanks to Ferdy for pointing out several other fixes, really appreciate the help.

I didn’t look at Sven’s answer but now I saw that he was first

For me it was a fast find because I see these errors at work all the time and they are so easy to prevent in the beginning. I also once made a similar mistake in my search function when I implemented my own move stack so I wouldn’t need to save lots of empty moves and so I could pause the search, dump the search tree, restart the computer and continue the search. My move stack finally worked and saved lots of stack, but the code got so complicated I threw it out.

I always try to save things as local as possible. It reduces the bugs, makes the code a lot easier to read and makes threading and performance optimisations such as memoization possible.

[eligolf]

Yes, I assume it is probably a rookie mistake, but what else to expect from a rookie like me hehe. Hard to find since it is not directly related to the error occuring