Strange null move behavior

[hgm]

..., but as long as it does I am happy

You should not be! You detected a bad problem, and all you did was find a way to mask it in this particular position. But the cause of the problem is still unknown and was not addressed. So there is every reason to assume the problem is still there, and will come back to bite you in other positions.

Finding a case where the engine does overlook something it should have seen is a rare opportunity to fix a bug that might be very hard to track down otherways. Don't let the opportunity pass!

[eligolf]

You are right of course, I was just so happy to "solve" something that has bugged me for days. At least move gen works (perft ok) so it is probably something in the search function.

[hgm]

I'm deeply impressed by your microMax king capture implementation - making beta cutoff on king capture is a very bold original idea
...

It is true that I usually don't study source codes of other engines, but I don't think I can take any credit for this as an invention of mine. I was under the impression that this is a very old method for doing things, known as 'king-capture engine'.

I was triggered by your remark that bitboards brought you so much speedup, because of IsSquareAttacked(). Now the speed of any engine is above all determined by branching ratio, which heavily depends on move ordering. So if you would have used the IsSquareAttacked() for move ordering purposes, I would believe everything. But if it is just doing a fixed amount of work, like checking the generated moves for legality, it just sounds wrong that it could ever consume so much time that you could get savings like you mention, even when it could be made infinitely faster.

The 'dumbest' way to make an IsInCheck() would be something like

Code: Select all

IsInCheck(player)
{
  GenerateMoves(OPPONENT(player));
  MVV = ExtractBestCapture();
  return (MVV == KING);
}

It has the advantage that it is guaranteed to be fundamentally correct, as it basically rephrases the definition of 'in check'. So it works even in the presence of fairy pieces that can turn corners or jump over others, for which is can be expensive and error prone to find a dedicated method. And it happens to be exactly how your Search() routine would start as well, which makes it possible to mitigate the cost through the micro-Max trick. It would be expensive, but even if you are not in check, you would not have done the work in vain.

But even if you want to test all moves for legality at generation time, it should be very easy to do that with mailbox. There are 3 reasons a move could be illegal:
1) You moved a pinned piece
2) Your King stepped to an attacked square
3) Your King was already under attack, and you did not do anything about it.

Now (2) can obviously only happen on King moves, and (1) only on moves with other pieces, so you would never have to test for both. As to (1), there is a very fast mailbox test for whether a piece could be pinned; it would be something like

if(alignment[fromSqr - kingSqr]) ...

where alignment[] is a prepared table that for each possible board step indicates whether a Queen could make it or not. This test should be much cheaper than any bitboard attack getter, and it would almost always be the only thing you have to do, as most pieces would not be aligned with your King. Only when a piece happens to be aligned you have to do more; in particular scan the board from your King in the corresponding direction (which you could have put as non-zero elements in the alignment[] table), ignoring the moved piece, to see if you hit an enemy slider that can move in that direction. And since during most of the game your King will be safely tucked away behind a Pawn shield, scanning the board usually ends on the fist step, where you bump into the shield, so even that is not as expensive as it sounds.

But there is more: once you have established whether the piece was pinned or not, this information can be used for all the other moves of that same piece, without redoing it. So you should not test in the order REPEAT(GenerateMove -> TestLegality), but in the order LiftPiece -> TestLegality -> REPEAT(GenerateMove). Where you would only generate the moves in the unrestricted way when the legality test showed the piece was not pinned, and you could use an alternative generator that only generates moves along a given ray in the case it was pinned.

For the King moves the problem is more precarious, (but fortunately there are few...), as attacks could come from anywhere by any piece. Mailbox engines usually keep track of where every piece is located, in a 'piece list', and the usual implementation of IsAttacked() is to run through that piece list, and do the alignment test. In this case a more specific one that takes the piece type into account, so that Rooks are checked only for orthogonal alignment, etc. For Pawn attacks it s better to just check the two board squares from which they could come, as there might be 8 Pawns in the piece list, so you only test alignment for the non-Pawn section of the list. Again, most pieces would not be aligned, and for those you wouldn't have to do anything extra.

Also here there is the possibility for 'bulk checking', though: you could tabulate (for each piece type of the potential checker) whether a certain location relative to King would make its moves intersect the King neighborhood, and where (e.g. as a 'mini bitboard' of the 3x3 area around the King). Each new hit on the King neighborhood that way would first have to be validated for not being blocked through a ray scan over the board, but again most pieces would not even be aligned with the king neighborhood. This would give you a map of all attacked squares near the King in one swoop through the piece list, which you can then use to only generate the King moves to non-attacked squares.

[eligolf]

I have yet to figure out this issue unfortunately. I implemented Ferdy's solution wrong so it never entered the nullmove logic, my bad So basically removing null moves at all solved the issue.

One more input is that if I change the first

Code: Select all

depth - 1 - s.R >= 0

to

Code: Select all

depth - 1 - s.R > 0

it works fine in this case. So it seems as there is something wrong with my null move implementation, but can't know why. Did anyone else have some similar issue and can point me in the right direction to where to start looking? Again, here is the make/unmake nullmove logic:

Code: Select all

    def make_nullmove(self):

        # Enpassant square
        if self.enpassant_square:
            self.zobrist_key ^= self.zobrist_enpassant[self.enpassant_square]
        self.enpassant_square = None

        # Switch player turn after the move is made
        self.is_white_turn = not self.is_white_turn
        self.zobrist_key ^= self.zobrist_side

        # Update move log
        self.move_log.append([(0, 0, 'no', '--', 0), self.piece_moved, self.piece_captured, self.castling_rights, self.enpassant_square, self.zobrist_key, self.piece_values[:]])

    def unmake_nullmove(self):

        self.move_log.pop()

        # Switch player turn after the move is made
        self.is_white_turn = not self.is_white_turn

        # Update from previous moves
        self.enpassant_square = self.move_log[-1][4]
        self.zobrist_key = self.move_log[-1][5]

And if it helps, the negamax algorithm for the relevant parts:

Code: Select all

    def negamax(self, depth, ply, alpha, beta, allow_nullmove):

        # Find if the position is a draw due to 3 fold repetition, if so return a draw score
        if self.is_repetition():
            return 0

        # Depth with quiescence search
        if depth == 0:
            return self.quiescence(ply, alpha, beta)

        # Increment node count
        self.nodes += 1

        # Get legal moves (need to do before nullmove to see if we are in check or not
        children = self.gamestate.get_valid_moves()

        # Null move logic
        if allow_nullmove:
            if depth - 1 - s.R >= 0 and not self.gamestate.is_in_check and ply:
                self.gamestate.make_nullmove()
                score = -self.negamax(depth - 1 - s.R, ply + 1, -beta, -beta + 1, False)
                self.gamestate.unmake_nullmove()

                if score >= beta:
                    return beta

        # Sort moves before Negamax
        children = self.sort_moves(ply, children)

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

        # Init legal moves counter
        legal_moves = 0

        # Negamax loop
        for child in children:

            # Make the move
            self.gamestate.make_move(child)

            # Increment legal moves
            legal_moves += 1

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

            # Unmake the move
            self.gamestate.unmake_move()

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

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

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

            # Checkmate, return checkmate score
            if self.gamestate.is_in_check:
                return -self.mate_value + ply

            # Stalemate, return stalemate score
            return 0

        # Node fails low
        return alpha

Getting desperate to find this bug and I looked all over, I guess I am not experienced enough to even know where to continue looking...

[hgm]

One problem is that you would not apply the check extension at d=0, because you test for check only after you have already decided to jump into QS. Or does your QS do its own check extension?

Since you do not do null move for d=2 or d=1, a search with d=3 and check extension should find the mate, and it should not matter whether null move is switched on or not, because you never have enough depth to try it. That is, when black would null-move at d=3 he obviously cannot score above beta, as beta should be +INFINITE in the root. After 1... Rh2 you are at d=2, so you cannot null-move anymore. White would have to play a King move, black would try 2... Qg1+, and black would be in check at d=0, extend to d=1, find no evasion, and return the checkmate score.

Rather than getting desparate you should build diagnostics into your engine that allows you to quickly and decisively zoom in on the cause of any blunder. I always use a conditional print statement right after the unmake() that gives the ply, remaining depth, current move (internal code and text form), its score, and the best score so far (alpha for fail hard). And I keep track of the current line in a global array path[], indexed by ply. The condition for printing then looks like

if(ply == 0 || path[0] == MOVE1 && (path == 1 || path[1] == MOVE2 ...)) print ...

where I start with all MOVEn invalid (so that I only get an overview of what happens in the root), then set MOVE1 to the move that IMO got the erroneous score (in this case Rh2), and try again to see what happens in the node after that, etc. That has helped me find bugs even at ply = 24, and for a 3-ply search it should only take minutes to find the problem.

[eligolf]

One problem is that you would not apply the check extension at d=0, because you test for check only after you have already decided to jump into QS. Or does your QS do its own check extension?

So I should not go into QS if I am in check? I don't currently have check extension in QS at all.

Not sure how you mean with the path thing, but you are right that I should somehow try to narrow it down. I think I need to get better understanding of how everything is connected and works, it is very complicated to wrap my head around hehe.

[hgm]

I am not saying that you have to use check extension; that is up to you. But if you jump into QS at d=0 even when in check, you are obviously not doing a check extension there. The normal way to do it would be to apply the extension first, and then test whether you are at d=0. Then you will not be blind to checkmates at the horizon.

The important thing for debugging a search is to know the moves and scores in every node of the line along which the erroneous score propagated to the root. Here you observe that 1. Rh2 gets a wrong score in the root. (Namely not mate in 2.) So the next step is to print the score of all moves in the node after 1. Rh2 (which should only be Kc1 and Ke1) to see which one succesfully defends against the mate. Say that is Ke1. Then you have to get the scores of the moves in the node after 1. Rh2 Ke1, so see what score 2. Qg1 got, as it should have been mate-in-1, and it obviously wasn't (unless there is a bug in how you keep track of the best score, which would then become obvious). So then you look what moves black thinks are good in the node after 1. Rh2 Ke1 2. Qg1. He should have none, so that the node could have concluded black was mated, but apparently black is not impressed here, so he must think he has a move with a good score. While in reality any move steps into check. At that point you can put additional prints in your program to figure out why the in-check test fails, so that it allows the King to step into check on that particular move.

[eligolf]

It seems as if without nullmove the position at root with Rg4-g2 gets a mate score. But if I print with nullmove the same line gets a score of 1500 something at depth 4. I tried to change the condition to be

Code: Select all

                if score > beta:
                    return beta

instead of

Code: Select all

                if score >= beta:
                    return beta

Would this be a cause? That by doing a null move it gets the same score as before and therefore returns beta without looking at the actual best move? Or am I still having a bug in the code?

Sorry for the basic questions, I am having a hard time figuring out how null moves work.

EDIT: After a few testings this lead to me checking even more nodes than before.... So that is not right

[hgm]

You should think of null-move pruning as making the engine consider turn passing a legal chess move. But not in the main line, just for the purpose of refuting a deviation.