Finding bugs in legal move generation or make/unmake move functions (Python)

[eligolf]

Hi,

I am creating an engine in Python and thought I got the generating move functions working properly along with make/unmake move functions after testing some speical cases in the human vs human game mode. However, when I started playing with the engine I sometimes noticed some weird choice of moves which got me thinking that I should do a more proper testing of my code.

For a start I use the initial position and compare my results with what is found here: https://www.chessprogramming.org/Perft_Results. My engine seems to get the first 4 depths right but then it starts to deviate at depth 5 like this:

- Nodes searched: 4.872.754 (should be 4.865.609, finds 7.145 too many moves)
- Captures: 83.150 (should be 82.719, finds 431 too many captures)
- Enpassants: 258, correct!
- Checks: 32.500 (should be 27.832, finds 4.668 too many checks)
- Checkmates: 8, correct!

I am completely lost at where or how to start debugging my code and hope that any of you have some ideas or suggestions on where to start. I have been going through the make/unmake move functions a million times and I am currently compeltely blind to what can be the issue.

If you are interested in the code you can find the current version here (in debugging mode): https://github.com/eligolf/affinity_chess. If you run the GUI file it will now search to depth 6 in around 30 minutes and print some relevant information. Change to human in settings file if you want to try human vs human.

[unserializable]

Hi Elias!

- Checks: 32.500 (should be 27.832, finds 4.668 too many checks)

From you description, I would suggest to start with checks -- save / print out all the check position it encounters, e.g. in FEN form and then examine them. Since there are 4668/32500 ~ 14% of supposedly illegal checks, you should soon find among them an illegal position that can be debugged further

[mvanthoor]

If perft results are incorrect, these are the things to watch out for:

- If you capture an en-passant pawn, don't forget to remove the opponent's pawn from the board. It's often forgotten, because it is not on the square where the capturing pawn lands. This is also tricky with regard to checks:

[d]1r6/8/8/8/k2p3R/8/4P3/8 w - - 0 1

For example, if white moves e2-e3, and you capture the pawn, it's completely obvious that the black king is in check and the capture is thus illegal. However, if white moves e2-e4 and you capture en-passant, your king is ALSO in check because you have to remove the white pawn on e4 after the capture. If you forget this, you have two mistakes at once: not removing the pawn (so leaving a piece on the board that shouldn't be there), and the fact that you should be in check with black (but aren't if you don't remove the white pawn). Obviously this will increase the number of possible moves.

- Make sure that you REMOVE the correct castling permissions, if a rook in the corner is captured. It is possible (for example, in the KiwiPete position) to have a rook captured that hasn't moved yet. If you forget to remove the castling permissions correctly, the engine will castle without a rook.
- Make sure you have all the promotions correct: if a pawn lands on the last rank, add four moves: one for promoting to each piece.
- Make sure you take into account that you can also capture into a promotion. So, if your pawn can capture 2 pieces on the last rank, but also move there without capturing, you have to add 12 moves to your movelist.

[mvanthoor]

You can also implement a divide perft, and then check against a known good engine that also has a divide perft:

http://www.rocechess.ch/perft.html

What you are basically doing is listing all the legal moves in a position, and the number of positions that follow from that. You check it against a known good engine. If you have a move where the numbers don't match, you make that move, and do perft from that position. And so on; until you reach the point that, if you do perft 1 on a position, you will only find one non-matching number and you can then determine what the difference is between your engine and the known good one.

PS: I'm of the opinion that you're moving too fast. You've already started a GUI and have a bunch of functions in your engine already.

My advice would be to
- disable anything that is not essential to making moves (ESPECIALLY the hash table if you have it: that can only come after you have verified correct peft, and correct Zobrist generation)
- check your move generator, one piece at a time. Check movement of each piece on an empty board. Then put some blocking pieces (same color as the moving pieces) on the board and check if the generated moves are still correct. Then do the same with pieces of the opposite color; moves should be the same, plus capturing the other piece.
- check if check detection works correctly (square_attacked)
- make sure make_move and unmake_move are bug free and take into account what I wrote in the previous post.

Then test perft again.

You may actually need to write some stuff from scratch again if you're not 100% sure that it's bug free.

The mantra I keep to when writing software is:
- A program that has no code is 100% correct and bug free.
- If I write a function, I try to make sure it is bug free and works in all situations where it is needed.
- I test this function extensively.
- If it turns out working, I add it to the program.
- If I add something that is bug free and working (the new function that is) to a program that is bug free, it should stay bug free.

It works well for me; beside the one bug of not removing the castling permissions of a captured rook, I've not encountered bugs or problems in my engine up until now, except during the writing of the latest function, obviously.

This doesn't guarantee that you are always writing perft, 100% bug free code, but it makes the chance of having something creep in unnoticed a lot smaller.

[hgm]

Are you sure you are only counting legal moves?

A quick way to zoom in the discrepancy is to do a 'divided perft', which gives the sub-totals for every move, or even for every sequence of a number of moves. Utilities like qperft can provide such divided perft counts. Just let your engine print them too, and follow a branch of the tree dor which the numbers differ, to see where it leads.

Code: Select all

$ ./qperft 5 -2
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes

perft( 1)=           20 ( 0.000 sec)
perft( 2)=          400 ( 0.000 sec)
2. h2h3 moves =        380 ( 0.000 sec)
2. h2h4 moves =        420 ( 0.000 sec)
2. g2g3 moves =        420 ( 0.000 sec)
2. g2g4 moves =        421 ( 0.000 sec)
2. f2f3 moves =        380 ( 0.000 sec)
2. f2f4 moves =        401 ( 0.000 sec)
2. e2e3 moves =        599 ( 0.000 sec)
2. e2e4 moves =        600 ( 0.000 sec)
2. d2d3 moves =        539 ( 0.000 sec)
2. d2d4 moves =        560 ( 0.001 sec)
2. c2c3 moves =        420 ( 0.000 sec)
2. c2c4 moves =        441 ( 0.000 sec)
2. b2b3 moves =        420 ( 0.000 sec)
2. b2b4 moves =        421 ( 0.000 sec)
2. a2a3 moves =        380 ( 0.000 sec)
2. a2a4 moves =        420 ( 0.000 sec)
2. g1f3 moves =        440 ( 0.000 sec)
2. g1h3 moves =        400 ( 0.000 sec)
2. b1a3 moves =        400 ( 0.000 sec)
2. b1c3 moves =        440 ( 0.000 sec)
perft( 3)=         8902 ( 0.001 sec)
2. h2h3 moves =       8457 ( 0.000 sec)
2. h2h4 moves =       9329 ( 0.000 sec)
2. g2g3 moves =       9345 ( 0.000 sec)
2. g2g4 moves =       9328 ( 0.000 sec)
2. f2f3 moves =       8457 ( 0.001 sec)
2. f2f4 moves =       8929 ( 0.000 sec)
2. e2e3 moves =      13134 ( 0.000 sec)
2. e2e4 moves =      13160 ( 0.000 sec)
2. d2d3 moves =      11959 ( 0.000 sec)
2. d2d4 moves =      12435 ( 0.001 sec)
2. c2c3 moves =       9272 ( 0.000 sec)
2. c2c4 moves =       9744 ( 0.000 sec)
2. b2b3 moves =       9345 ( 0.000 sec)
2. b2b4 moves =       9332 ( 0.000 sec)
2. a2a3 moves =       8457 ( 0.000 sec)
2. a2a4 moves =       9329 ( 0.001 sec)
2. g1f3 moves =       9748 ( 0.000 sec)
2. g1h3 moves =       8881 ( 0.000 sec)
2. b1a3 moves =       8885 ( 0.000 sec)
2. b1c3 moves =       9755 ( 0.000 sec)
perft( 4)=       197281 ( 0.003 sec)
2. h2h3 moves =     181044 ( 0.003 sec)
2. h2h4 moves =     218829 ( 0.003 sec)
2. g2g3 moves =     217210 ( 0.003 sec)
2. g2g4 moves =     214048 ( 0.003 sec)
2. f2f3 moves =     178889 ( 0.003 sec)
2. f2f4 moves =     198473 ( 0.003 sec)
2. e2e3 moves =     402988 ( 0.002 sec)
2. e2e4 moves =     405385 ( 0.002 sec)
2. d2d3 moves =     328511 ( 0.002 sec)
2. d2d4 moves =     361790 ( 0.003 sec)
2. c2c3 moves =     222861 ( 0.001 sec)
2. c2c4 moves =     240082 ( 0.001 sec)
2. b2b3 moves =     215255 ( 0.002 sec)
2. b2b4 moves =     216145 ( 0.001 sec)
2. a2a3 moves =     181046 ( 0.001 sec)
2. a2a4 moves =     217832 ( 0.002 sec)
2. g1f3 moves =     233491 ( 0.001 sec)
2. g1h3 moves =     198502 ( 0.001 sec)
2. b1a3 moves =     198572 ( 0.001 sec)
2. b1c3 moves =     234656 ( 0.002 sec)
perft( 5)=      4865609 ( 0.040 sec)

[eligolf]

Thank you so much both for the answers! I wrote to a csv file whenever it made a capture and whenever it was a check detected and found some interesting things.

First @mvanthoor, those are really good suggestions. I thought I had a good working program from manual testing human vs human and that is why I continued with everything else. You are of course right though that THOROUGH testing is needed before continuing with other features. I might have to redo some of the code.

To the interesting errors:

1. Capturing king

Here is an example of how things went from studying the move log:

1. e4 Na6
2. Bb5 d6 (???)
3. Bxe8 (takes the black king...)

There are several more lines in which this appears (188 to be precise). This is super weird since I can't replicate this when playing human vs human, the move 2. .. d6 is not allowed since that piece is pinned.

2. Different results when I calculate moves before "if depth == 0" than after.

If I put the lines like this

Code: Select all

if depth == 0 or stalemate or checkmate:
	return None, Evaluation
	
children = gamestate.get_valid_moves()

It returns a different amount of nodes than:

Code: Select all

children = gamestate.get_valid_moves()

if depth == 0 or stalemate or checkmate:
	return None, Evaluation
	

Which also feels super weird.


Still looking at some more weird behaviours, this will be a pain to solve. Especially since I can't find the errors when making/unmaking move when playing as a human...

[mvanthoor]

Here is an example of how things went from studying the move log:

1. e4 Na6
2. Bb5 d6 (???)
3. Bxe8 (takes the black king...)

There are several more lines in which this appears (188 to be precise). This is super weird since I can't replicate this when playing human vs human, the move 2. .. d6 is not allowed since that piece is pinned.

So where do you check this?

I see you also have a GUI; it has to check move legality even before the engine checks it, to make sure a user doesn't input illegal moves.

If you implemented UCI in your GUI, you could actually implement a custom command, such as "legal d7d6". The engine would reply with "true" or "false" without doing anything else. This way, you could try to find out if your engine is actually allowing illegal moves, and it's much easier to check if you can use the GUI for that, without actually having the GUI check the moves itself.

You said you have a legal move generator. I haven't checked the code, but how do you create the legal moves? Do you generate a list of all possible, pseudo-legal moves, and discard the ones where the king ends up in check... or do you actually try to generate legal moves only, by calculating pinned pieces and such? I think the second is more difficult to do. It may be useful to drop back to generating a list of pseudo-legal moves, and leave it at that; just check the move for legality in make() at the end, and run unmake() if it happens to be illegal. (You could also check it for legality just before you add the move to the move list in the move generator, and not add it if it turns out to be illegal, but this is slower than the make-move way because you're checking moves that may actually never be played.)

[hgm]

Note that gross blunders by the engine are often not due to move-generator bugs, but to search errors. In particular problems with alpha-beta pruning. E.g. where it takes a beta cutoff because it thinks the previous move is already refuted, but in fact that previous move is still chosen on the level below because beta was somehow calculated wrong.

But of course it is a reason for worry when you don't get the correct perft counts. Still I hardly ever use perft to validate my engines. Often for the simple reason that the correct counts might not be known, or that my engine would not give the correct counts anyway, e.g. because it doesn't search under-promotion. But also because correct perft doesn't guarantee correct search. In search you do many things that you don't do in perft. Like sorting the move list. You can also lose moves there, or create duplicats. You could wrongly validate killer moves, have a hash bug that gives you invalid hash moves, etc.

If the engine makes a strange move, I just check out why it mis-evaluated that move, or the correct alternative, by printing the necessary debug info during search. That way I find all errors, also bugs in the move generation.

[eligolf]

First on how I get my legal moves:

1. From the king position out in all 8 directions I check if I am in check and also what the pinned pieces are (8x8 double for loop)
2. Calculate each piece legal move considering pins, see bishop code below as an example. For the king I try to put it in all 8 directions and see if it ends up in check or not.
3. If king is in check I reduce the number of possible moves to capture the attacking piece, blocking it, or moving the king.
4. If double check I only calculate valid moves for the king.

Code: Select all

    def get_bishop_moves(self, square, moves, piece_pinned):
        pin_direction = ()
        for i in range(len(self.pins)-1, -1, -1):
            if self.pins[i][0] == square:
                piece_pinned = True
                pin_direction = (self.pins[i][1])
                self.pins.remove(self.pins[i])
                break

        enemy_color = 'b' if self.is_white_turn else 'w'
        for d in s.directions[4:8]:
            for i in range(1, 8):
                end_square = square + d * i
                end_piece = self.board[end_square][0]
                if end_piece in f'{enemy_color}-':
                    if not piece_pinned or pin_direction in (-d, d):  # Able to move towards and away from pin
                        moves.append((square, end_square))
                        if end_piece == enemy_color:
                            break
                else:
                    break

In the GUI I simply do this calculation for the color to move and then display all the legal possibilities (if wanted_move in legal_moves: make_move()).

[Ferdy]

Here is an example of how things went from studying the move log:

1. e4 Na6
2. Bb5 d6 (???)
3. Bxe8 (takes the black king...)

There are several more lines in which this appears (188 to be precise). This is super weird since I can't replicate this when playing human vs human, the move 2. .. d6 is not allowed since that piece is pinned.

It looks like the move generation is dependent on the pinned pieces. The fix would be to call the check_for_pins_and_checks() first before get_all_possible_moves().

Here is a sample perft 5 which I think is right.

Code: Select all

affinity_chess, perft 5
a2a3 - 181046
a2a4 - 217832
b2b3 - 215255
b2b4 - 216145
c2c3 - 222861
c2c4 - 240082
d2d3 - 328511
d2d4 - 361790
e2e3 - 402988
e2e4 - 405385
f2f3 - 178889
f2f4 - 198473
g2g3 - 217210
g2g4 - 214048
h2h3 - 181044
h2h4 - 218829
b1a3 - 198572
b1c3 - 234656
g1f3 - 233491
g1h3 - 198502
Nodes: 4865609