Strange null move behavior

[eligolf]

Hi all,

I recently switched back to my 1D dict board representation in Python since the bitboard concept was around 4-5 times slower. Huge dissapointment after all trouble in trying to get the move generation right. Anyway, back to the main question...

After having implemented null move logic my engine behaves strange in some scenarios, especially when trying to find mate. In the following example it gives mate in 3 (Rh1, Kc2, Rh2, Kb1, Qg1#):

[d]3k4/8/8/8/8/6qr/8/2K5 b - - 0 1

Switching off the null move logic it finds the mate in 2 as expected. The code I am using is same as in most sites I have looked at (I think):

Code: Select all

        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

Where R is set to 2 and my make and unmake nullmove functions are as follows:

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]

I also find the mate detection score a bit weird. In evaluation I return score if white to move and -score if black to move, but in the mate detection I always return -mate_score:

Code: Select all

        if not legal_moves:
            if self.gamestate.is_in_check:
                return -self.mate_value + ply

Adding it to below gives that it doesn't find mate at all or plays very strangely in the endgames:

Code: Select all

      if not legal_moves:
            if self.gamestate.is_in_check:
                return -self.mate_value + ply if self.gamestate.is_white_turn else self.mate_value - ply
                

Not sure if it is related, just posting it too since I found the null move issues when trying some mate positions.

[Ferdy]

Add another conditions:
evalScore >= beta and material(stm) >= ROOK

[eligolf]

Thanks Ferdy, that did the trick!

[maksimKorzh]

Hi all,

I recently switched back to my 1D dict board representation in Python since the bitboard concept was around 4-5 times slower. Huge dissapointment after all trouble in trying to get the move generation right. Anyway, back to the main question...

After having implemented null move logic my engine behaves strange in some scenarios, especially when trying to find mate. In the following example it gives mate in 3 (Rh1, Kc2, Rh2, Kb1, Qg1#):

[d]3k4/8/8/8/8/6qr/8/2K5 b - - 0 1

Switching off the null move logic it finds the mate in 2 as expected. The code I am using is same as in most sites I have looked at (I think):

Code: Select all

        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

Where R is set to 2 and my make and unmake nullmove functions are as follows:

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]

I also find the mate detection score a bit weird. In evaluation I return score if white to move and -score if black to move, but in the mate detection I always return -mate_score:

Code: Select all

        if not legal_moves:
            if self.gamestate.is_in_check:
                return -self.mate_value + ply

Adding it to below gives that it doesn't find mate at all or plays very strangely in the endgames:

Code: Select all

      if not legal_moves:
            if self.gamestate.is_in_check:
                return -self.mate_value + ply if self.gamestate.is_white_turn else self.mate_value - ply
                

Not sure if it is related, just posting it too since I found the null move issues when trying some mate positions.

Not to the point but what kind of bitboard implementation did you use?

I head same issues in the past but eventually made bitboards around 3x faster then array based. Most savings were done thanks to isSquareAttacked() lookup instead of on the fly calculations.

[hgm]

This is suspect. Null move can only be harmful in cases of zugzwang, and there is no zugzwang involved in this checkmate at all. If the opponent null-moves after Rh2, he will still get mated with Qg1#. Of course you have to give it enough depth to see it (5 ply, because with R=2 a null move counts for 3), but it should eventually see the mate in 2.

Of course it might see longer mates earlier. This is a general problem when you do extensions and reductions. E.g. check extension would prefer to force the mates through checks, because the evasions do not count in that case. But when you properly score the mate (i.e. award fast mates more than slow mates), it should eventually overturn that with the faster line.

Also, adding the condition material >= ROOK should not have had any effect at all, as you have more than a Rook here.

[hgm]

I head same issues in the past but eventually made bitboards around 3x faster then array based. Most savings were done thanks to isSquareAttacked() lookup instead of on the fly calculations.

For what purposes do you use IsSquareAttacked()?

[maksimKorzh]

I head same issues in the past but eventually made bitboards around 3x faster then array based. Most savings were done thanks to isSquareAttacked() lookup instead of on the fly calculations.

For what purposes do you use IsSquareAttacked()?

To check whether king has been exposed into a check during move generation. Anything wrong with it?

[hgm]

I was just curious how it could make so much difference. Potentially such a routine could be used for many purposes.

It does seem to me, though, that guarding against moving into check can be done more efficiently even with a mailbox engine then by calling a general IsSquareAttacked() routine for every generated move, even if the latter routine is a very fast one. I can even imagine that not checking for this at all, and just leave it for the move generation in the daughter node to detect the King capture, would be faster. On the average you would detect it after half a move generation, which is pretty expensive, but the fraction of moves that actually does expose your King to capture is quite small. And on all the other moves you would have reduced the overhead to zero. So on average per move it could still be very cheap.

But in more advanced engines I usually do detect pinned pieces before I start move generation, and then limit the generation of moves with those pieces to those along the pin ray. The pin detection is still quite fast even with mailbox, as in most cases the enemy sliders are not even positioned such that they could give check on an otherwise empty board, and in case there is a pin you gain back some time by not having to generate the moves that are doomed to be rejected later after testing. Then it is only the King moves that could potentially stumble into check. And there are few of those, and often even fewer that you actually need to search (as they are usually not very good, and thus sorted somewhere in the back, where you might never get to). And of course I defer the testing to after it is decided they should be searched. And once a move will be searched, that search (even if it is just 1 ply deep) should always require far more time than a simple IsSquareAttacked(), no matter how inefficiently the latter is programmed.

[maksimKorzh]

I was just curious how it could make so much difference. Potentially such a routine could be used for many purposes.

It does seem to me, though, that guarding against moving into check can be done more efficiently even with a mailbox engine then by calling a general IsSquareAttacked() routine for every generated move, even if the latter routine is a very fast one. I can even imagine that not checking for this at all, and just leave it for the move generation in the daughter node to detect the King capture, would be faster. On the average you would detect it after half a move generation, which is pretty expensive, but the fraction of moves that actually does expose your King to capture is quite small. And on all the other moves you would have reduced the overhead to zero. So on average per move it could still be very cheap.

But in more advanced engines I usually do detect pinned pieces before I start move generation, and then limit the generation of moves with those pieces to those along the pin ray. The pin detection is still quite fast even with mailbox, as in most cases the enemy sliders are not even positioned such that they could give check on an otherwise empty board, and in case there is a pin you gain back some time by not having to generate the moves that are doomed to be rejected later after testing. Then it is only the King moves that could potentially stumble into check. And there are few of those, and often even fewer that you actually need to search (as they are usually not very good, and thus sorted somewhere in the back, where you might never get to). And of course I defer the testing to after it is decided they should be searched. And once a move will be searched, that search (even if it is just 1 ply deep) should always require far more time than a simple IsSquareAttacked(), no matter how inefficiently the latter is programmed.

I'm deeply impressed by your microMax king capture implementation - making beta cutoff on king capture is a very bold original idea.
My engines feels a big lack of efficiency all along the way. Even if I go for your approach regarding isSquareAttacked() or ideas regarding
hashing null moves - this would be after I would be fully understanding what an I doing. You know like for me chess programming is a way
to fight my natural dumbness. When I read your ideas - I feel very impressed on the one had and very stupid on the other)
When I just started I didn't understand I don't know... around 70% of what am I doing believe it or not.
Now I finally came to the stage when I can understand 99% of my own code (still have some white spaces with understanding how collecting PV works and maybe a couple more minor things that does not affect speed/strength)
And it's already a great result for me.

I just can't learn how normal people do - like take a subject, learn essence and then consciously applying it to the subject, no
I can do things only in what I call code monkey king's way - just pick up an existing pattern and try to learn in by repeating as
many times as needed to understand it - thats the reason why I have many engines)

I tried Vive's and microMax's patterns. First is too extensive, second is too obfuscated, so as soon as I've realized all the needed
bricks to build a move generator I've started creating my own pattern and WukongJS represents the latest form of it.
Then I started looking for search/eval patterns.
The most lovely eval pattern I took from PeSTO by Ronald Friederich - he and some other guys explained to me how to implement
tapered evaluation and I'm using it since then. Also Ronald explained to me the most basic texel's tuning pattern which I'm exploring now.
Regarding search I'm getting inspired by CPW engine's pattern which is simplified Crafty pattern in essence.
As far as I'm getting my own experience I'm starting to change the search pattern on my own.

So the main issue I have while reading brilliant answers here on talkchess is that those answers go beyond patterns
which needs totally different type of consciousness to understand and make use of them.

Just an example - I've started understanding your questions partially only after working out microMax's pattern to
get an idea you you think in particular. I've made 3 engines based on microMax (better to call them move generators for
they don't even have a quiescence search) and even one movegen in NASM assembly) All this took me about half a year.

This pattern based way of learning is more eastern than western way. I'm a long term practioner of traditional Chinese martial arts
(for health, not for fight) - and they are totally build of patterns, they call it "forms". Forms brought together formulate form sets,
just like engine's parts formulate actual engine. But CHinese forms mostly work with the body ,while consciousness is left untouched.
Chess programming helps me work out my consciousness just like I do with the body)

Your recent interest to my experiments is very surprising and flattering) Thank you)

[eligolf]

This is suspect. Null move can only be harmful in cases of zugzwang, and there is no zugzwang involved in this checkmate at all. If the opponent null-moves after Rh2, he will still get mated with Qg1#. Of course you have to give it enough depth to see it (5 ply, because with R=2 a null move counts for 3), but it should eventually see the mate in 2.

Of course it might see longer mates earlier. This is a general problem when you do extensions and reductions. E.g. check extension would prefer to force the mates through checks, because the evasions do not count in that case. But when you properly score the mate (i.e. award fast mates more than slow mates), it should eventually overturn that with the faster line.

Also, adding the condition material >= ROOK should not have had any effect at all, as you have more than a Rook here.

Yes it is very weird at all. I can't think of why it would work with the added conditions and not without, but as long as it does I am happy It currently sees to ply 5 in this position which should be enough to spot the mate, and I do have check extensions turned on (no difference with them turned off though in this case).