Perft for arbitrary board sizes

[Rein Halbersma]

Code: Select all

1. divide 5-9 349 nodes
2. divide 6-9 412 nodes
3. divide 7-11 523 nodes
4. divide 8-11 505 nodes
5. divide 10-14 261 nodes
6. divide 12-16 263 nodes
7. divide 15-18 119 nodes
8. divide 15-19 2 nodes
perft(5) 2434 leafs 764 nodes in 4 msec 191 kN/s

Move 7.

 x x x x
x x x x 
 . x . x
x . . . 
 o x . .
o o o o 
 o o o o
. o o o 
white to move

1. divide 22x15 12 nodes
2. divide 23x14 107 nodes
perft(4) 119 leafs 43 nodes in 2 msec 21 kN/s

Almost there, some forced captures (moves 1 and 1)

Code: Select all

   b   b   b   b
 b   b   b   b  
   .   b   .   b
 b   .   .   .  
   w   b   .   .
 w   w   w   w  
   w   w   w   w
 .   w   w   w  
"W:B1,2,3,4,5,6,7,8,10,12,13,18:W17,21,22,23,24,25,26,27,28,30,31,32"

Searching to nominal depth=4

Found 2 moves, searching each to nominal depth=3

 1.22x15 info depth  3 leafs           11 time      0 nps     inf
 2.23x14 info depth  3 leafs          107 time      0 nps     inf
Total leafs: 118

   b   b   b   b
 b   b   b   b  
   .   b   .   b
 b   .   w   .  
   w   .   .   .
 w   .   w   w  
   w   w   w   w
 .   w   w   w  
"B:B1,2,3,4,5,6,7,8,10,12,13:W15,17,21,23,24,25,26,27,28,30,31,32"

Searching to nominal depth=3

Found 1 moves, searching each to nominal depth=2

 1.13x29 info depth  2 leafs           11 time      0 nps     inf
Total leafs: 11

   b   b   b   b
 b   b   b   b  
   .   b   .   b
 .   .   w   .  
   .   .   .   .
 w   .   w   w  
   .   w   w   w
 B   w   w   w  
"W:B1,2,3,4,5,6,7,8,10,12,K29:W15,21,23,24,26,27,28,30,31,32"

Searching to nominal depth=2

Found 8 moves, searching each to nominal depth=1

 1.15-11 info depth  1 leafs            2 time      0 nps     inf
 2.21-17 info depth  1 leafs            2 time      0 nps     inf
 3.23-18 info depth  1 leafs            1 time      0 nps     inf
 4.23-19 info depth  1 leafs            1 time      0 nps     inf
 5.24-19 info depth  1 leafs            1 time      0 nps     inf
 6.24-20 info depth  1 leafs            2 time      0 nps     inf
 7.26-22 info depth  1 leafs            1 time      0 nps     inf
 8.30-25 info depth  1 leafs            1 time      0 nps     inf
Total leafs: 11

[jj]

I see. In this position, after move 8,

Code: Select all

 x x x x
x x x x 
 . x . x
. . o . 
 . . . .
o . o o 
 o o o o
X . o o 
black to move

I have two different "raw" moves, king multiple captures with different landing squares in the middle.
1. 29x22x11
2. 29x18x11
and only if I switch on filtering duplicates only one move remains.

You probably have a different way of doing this (bitboards), generating only one move in the first place? Thanks for helping to sort this out.

[Rein Halbersma]

I see. In this position, after move 8,

Code: Select all

 x x x x
x x x x 
 . x . x
. . o . 
 . . . .
o . o o 
 o o o o
X . o o 
black to move

I have two different "raw" moves, king multiple captures with different landing squares in the middle.
1. 29x22x11
2. 29x18x11
and only if I switch on filtering duplicates only one move remains.

You probably have a different way of doing this (bitboards), generating only one move in the first place? Thanks for helping to sort this out.

The bug is that you need to filter on captured pieces, not on landing squares. I don't save landing squares inside perft, that is only for GUI moves that want to have their path animated.
The good thing is of course that it is not a correctness bug for tournament play.

[jj]

The bug is that you need to filter on captured pieces, not on landing squares. I don't save landing squares inside perft, that is only for GUI moves that want to have their path animated.
The good thing is of course that it is not a correctness bug for tournament play.

I don't think it's a bug. I don't save the landing squares inside perft/search, I save only captured pieces (squares) and of course use these to filter identical moves.
I just meant that the move generator recursively finds two different paths to the same move (29xx11) via two different intermediate squares. Normally the second move is correctly filtered out when the generator tries to add it to the list, but we agreed to switch off the filter and allow duplicates. So I get two identical moves.
How do you prevent two moves from being generated in this case if the duplicate filter is switched off?

[Rein Halbersma]

The bug is that you need to filter on captured pieces, not on landing squares. I don't save landing squares inside perft, that is only for GUI moves that want to have their path animated.
The good thing is of course that it is not a correctness bug for tournament play.

I don't think it's a bug. I don't save the landing squares inside perft/search, I save only captured pieces (squares) and of course use these to filter identical moves.
I just meant that the move generator recursively finds two different paths to the same move (29xx11) via two different intermediate squares. Normally the second move is correctly filtered out when the generator tries to add it to the list, but we agreed to switch off the filter and allow duplicates. So I get two identical moves.
How do you prevent two moves from being generated in this case if the duplicate filter is switched off?

My capture routine has 2 parts: the root and the recursive parts. At the root, I check for a capture, and find 29x22. I do not find 29x18 because I only look for the first square behind a jumped piece. From square 22 onwards, I do the following. First I check from square 22 and look in the 2 sideways and the 1 forward direction. I recurse for any newly found target. I store a boolean "next_target" if there is anything new discovered. Then I slide from square 22 forward, but only looking in the 2 sideways directions, until I hit an occupied square. In this case, I only look sideways from square 18. During the sliding, I update my boolean "new_target". Now I check the boolean. If it is true, I am done. If it is false (i.e. no new jumps found), I start sliding again from square 22 onwards till I hit an occupied square (so only squares 22 and 18 here) and I get the 2 different desination squares. In the current example, the boolean was true, so the intermediate squares 22 and 18 never were stored anywhere, and I only find 29x11. If I were to store the intermediate squares, I would only store 22 (first square after a jumped piece), which is how the PDN 3.0 grammar specifies this.

So I think what you do differently is that you do forward capture continuations multiple times, and I only check in the forward direction once.

BTW, I do a bitboard lookup to determine the empty squares ahead, and cache the number of sliding squares in an integer variable, so that I do a counted loop, instead of manually checking for an occupied square during sliding.

[Rein Halbersma]

Plus:
- W x H = 8 x 10 draughts unique depth 11: to be confirmed
- W x H = 10 x 8 draughts unique depth 11: to be confirmed

Confirmed, I already had done 10x8 many years ago (GM Spantsiretti has this board named after him, this game is occasionally played in Russia), never published here.

BTW, for debugging purposes (divide etc.) I find it most convenient to have the board coloring such that a W x (W+2) or W x (W-2) has the same front row structure as the WxW boards. In that case, the opening moves in a divide() call are identical

[jj]

My capture routine has 2 parts: the root and the recursive parts. At the root, I check for a capture, and find 29x22. I do not find 29x18 because I only look for the first square behind a jumped piece. From square 22 onwards, I do the following. First I check from square 22 and look in the 2 sideways and the 1 forward direction. I recurse for any newly found target. I store a boolean "next_target" if there is anything new discovered. Then I slide from square 22 forward, but only looking in the 2 sideways directions, until I hit an occupied square. In this case, I only look sideways from square 18. During the sliding, I update my boolean "new_target". Now I check the boolean. If it is true, I am done. If it is false (i.e. no new jumps found), I start sliding again from square 22 onwards till I hit an occupied square (so only squares 22 and 18 here) and I get the 2 different desination squares. In the current example, the boolean was true, so the intermediate squares 22 and 18 never were stored anywhere, and I only find 29x11. If I were to store the intermediate squares, I would only store 22 (first square after a jumped piece), which is how the PDN 3.0 grammar specifies this.

So I think what you do differently is that you do forward capture continuations multiple times, and I only check in the forward direction once.

BTW, I do a bitboard lookup to determine the empty squares ahead, and cache the number of sliding squares in an integer variable, so that I do a counted loop, instead of manually checking for an occupied square during sliding.

Thanks for clearing that up. So my "bug" is a missing optimization. The NxN (now WxH) array-based code is indeed very simple and I didn't want to spend much time optimizing it (my bitboard generator is a bit more advanced). This situation can only happen with flying kings, which explains why my duplicate checkers perft numbers match with Aart Bik's, and with yours as long as there are no kings.

[jj]

Plus:
- W x H = 8 x 10 draughts unique depth 11: to be confirmed
- W x H = 10 x 8 draughts unique depth 11: to be confirmed

Confirmed, I already had done 10x8 many years ago (GM Spantsiretti has this board named after him, this game is occasionally played in Russia), never published here.

BTW, for debugging purposes (divide etc.) I find it most convenient to have the board coloring such that a W x (W+2) or W x (W-2) has the same front row structure as the WxW boards. In that case, the opening moves in a divide() call are identical

Great! So now we have single move generators (+makeMove) that link independently verified (unique) perft numbers for checkers 6x6/8x8 and international draughts 4x4/6x6/8x8/10x10/12x12/14x14 and 8x10/10x8/10x12/12x10. Which gives the reassurance that all published perft numbers are correct.

[Rein Halbersma]

Thanks for clearing that up. So my "bug" is a missing optimization. The NxN (now WxH) array-based code is indeed very simple and I didn't want to spend much time optimizing it (my bitboard generator is a bit more advanced). This situation can only happen with flying kings, which explains why my duplicate checkers perft numbers match with Aart Bik's, and with yours as long as there are no kings.

Yes, a small performance pessimization but also a real PDN bug https://pdn.fmjd.org/grammar.html

9. Disambiguated capture sequences have to specify a complete sequence of intermediate squares along the path of the capture. If there is a change in direction, an intermediate square is the square where a turn in direction was made. If there was not a change in direction, the intermediate square is the square immediately behind a captured piece. There is no intermediate square behind the last captured piece, but otherwise leaving out an intermediate square that is not necessary for the disambiguation is forbidden.

[Rein Halbersma]

Great! So now we have single move generators (+makeMove) that link independently verified (unique) perft numbers for checkers 6x6/8x8 and international draughts 4x4/6x6/8x8/10x10/12x12/14x14 and 8x10/10x8/10x12/12x10. Which gives the reassurance that all published perft numbers are correct.

Yes I am very happy that there is someone else who went to all the trouble of having a generalized move generator! If you ever get around to other rule variations (Russian, Pool, Spanish, Italian, Thai, Czech), you know where to find the perft numbers

BTW, 4x4 checkers is also interesting: there the board is too small for 2 kings to win against 1 king (the double corner escapes are too close to each other). This is very funny because mostly the drawing margin increases with board size.