World Draughts Forum

It is currently Fri Sep 22, 2017 07:14

All times are UTC+01:00




Post new topic  Reply to topic  [ 25 posts ]  Go to page Previous 1 2
Author Message
PostPosted: Tue Aug 15, 2017 22:59 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
jj wrote:
Code:
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:
   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


Top
   
PostPosted: Tue Aug 15, 2017 23:16 
Offline

Joined: Sun Sep 13, 2009 22:33
Posts: 116
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands
I see. In this position, after move 8,

Code:
 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.


Top
   
PostPosted: Tue Aug 15, 2017 23:24 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
jj wrote:
I see. In this position, after move 8,

Code:
 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.


Top
   
PostPosted: Wed Aug 16, 2017 09:18 
Offline

Joined: Sun Sep 13, 2009 22:33
Posts: 116
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands
Rein Halbersma wrote:
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?


Top
   
PostPosted: Wed Aug 16, 2017 09:28 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
jj wrote:
Rein Halbersma wrote:
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.


Top
   
PostPosted: Wed Aug 16, 2017 10:11 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
jj wrote:
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 :)


Top
   
PostPosted: Wed Aug 16, 2017 11:03 
Offline

Joined: Sun Sep 13, 2009 22:33
Posts: 116
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands
Rein Halbersma wrote:
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.


Top
   
PostPosted: Wed Aug 16, 2017 11:13 
Offline

Joined: Sun Sep 13, 2009 22:33
Posts: 116
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands
Rein Halbersma wrote:
jj wrote:
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.


Top
   
PostPosted: Wed Aug 16, 2017 11:32 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
jj wrote:
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

Quote:
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.


Top
   
PostPosted: Wed Aug 16, 2017 11:34 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1550
jj wrote:
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.


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 25 posts ]  Go to page Previous 1 2

All times are UTC+01:00


Who is online

Users browsing this forum: Google Feedfetcher and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited