Problem with checkmate detection

[eligolf]

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

[Ferdy]

First try this and see what happens. Don't go to qsearch if you are incheck.

Code: Select all

    def negamax(depth, alpha, beta):

        # Init PV length
        self.pv_length[self.ply] = self.ply
		
	# 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

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

[eligolf]

Thank you, this made the program think for longer time but it gave same result as before.

[Ferdy]

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.

This is not a problem because you have a statement to print it.

Code: Select all

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

[Ferdy]

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?

Could you explain more about that "But shouldn't the score be changed when it finds something better to play for itself?"

[eligolf]

Yes sorry if explanation was bad, English is not my native language

At depth 3 I assume it found the mate Nxf4 (or any other knight move really except Nc7 or Ng7) which leads to mate by Rxd8#. That gives the score of -M2 (mate in 2 plies). But as you can see from the PV-line it found this was bad and instead went for Rxd5 Nxd5 Kg8. Then the score should be something in line of the score at depth 2, lets say -3.4 instead of -M2.

What I find strange is that it returns the score of -M2 (which I save in the iterative deepening for print later) but it should return the best score for itself which is say -3.4? I am scared there is something wrong in how I detect checkmate or score the position.

[Ferdy]

Yes sorry if explanation was bad, English is not my native language

At depth 3 I assume it found the mate Nxf4 (or any other knight move really except Nc7 or Ng7) which leads to mate by Rxd8#. That gives the score of -M2 (mate in 2 plies). But as you can see from the PV-line it found this was bad and instead went for Rxd5 Nxd5 Kg8. Then the score should be something in line of the score at depth 2, lets say -3.4 instead of -M2.

What I find strange is that it returns the score of -M2 (which I save in the iterative deepening for print later) but it should return the best score for itself which is say -3.4? I am scared there is something wrong in how I detect checkmate or score the position.

Right I see it now. Could you post your quiescence?

[Ferdy]

Also try to use something like this,

Code: Select all

score = negamax(depth, -1e9, 1e9, False)

[eligolf]

Yes same result with changing window. Here is the quiescence:

Code: Select all

    def quiescence(self, alpha, beta):

        # Increment nodes count
        self.nodes += 1

        # Evaluate the position
        evaluation = e.evaluate(self.gamestate)

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

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

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

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

        # Negamax recursive loop
        for child in children:

            # If move isn't legal, continue to next candidate
            if self.gamestate.make_move(child) == 0:
                continue

            # Increase ply
            self.ply += 1

            # Score the position after current move is made
            score = -self.quiescence(-beta, -alpha)

            # Decrement ply
            self.ply -= 1

            # Take back move
            self.gamestate.unmake_move()

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

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

        # Node fails low
        return alpha

[Ferdy]

Did you use a GUI in the image showing the depth, time, nodes score mainline?

Are the scores -M4, -M3 coming from your engine?

Also try this mate in 1 position, let's see its output.

[d]1k6/7Q/1K6/8/8/8/8/8 w - - 0 1