A few informations regarding perft/divide
Intro
When writing a new move generator or chess engine, there is often the need to check if there are some hidden bugs in the move generation process. And believe me, usually there are some well hidden bugs. Playing a lot of games is one way to figure out that everything is fine but that is a very timeconsuming approach. Another and much better solution is to implement 'perft' into the chess engine. Perft counts by definition all the legal nodes (positions) from depth-1 to depth. So if perft 1 is called with the startposition on the board the answer should be 20. 'perft 2' should give the answer 400 because 420-20=400. Keep in mind that for some of the testpositions a 64-bit counter is needed as the numbers getting big quickly. That would be long long on UNIX/Linux systems or __int64 for the windows world. If unsure about that, just check your compiler/OS documentation.
Startposition
                      |
perft values
| depth | nodes | totalnodes |
| 1 | 20 | 20 |
| 2 | 400 | 420 |
| 3 | 8902 | 9322 |
| 4 | 197281 | 206603 |
| 5 | 4865609 | 5072212 |
| 6 | 119060324 | 124132536 |
| 7 | 3195901860 | 3320034396 |
Good testposition
The startposition isn't a very good testposition as it doesn't uncover flaws that might still be hidden regarding promotion or castling. Therefore the following position should be a better test. Still, even if this position is no problem for an engine, it doesn't mean there are no bugs left. The link below leads to a textfile with a lot of positions with precalculated perft values. The positions were collected/calculated by Andrew Wagner and published in 2004 on CCC.
|
perft values
| depth | nodes | totalnodes |
| 1 | 48 | 48 |
| 2 | 2039 | 2087 |
| 3 | 97862 | 99949 |
| 4 | 4085603 | 4185552 |
| 5 | 193690690 | 197876242 |
| 6 | 8031647685 | 8229523927 |
Discover promotion bugs
The following position doesn't look very realistic but nevertheless helps to uncover promotion bugs.
 |
perft values
| depth | nodes | totalnodes |
| 1 | 24 | 24 |
| 2 | 496 | 520 |
| 3 | 9483 | 10003 |
| 4 | 182838 | 192841 |
| 5 | 3605103 | 3797944 |
| 6 | 71179139 | 74977083 |
Textfile with a lot of positions and perft values
As you might work on your move generator again and again (at least I did) you might introduce new bugs. So it's no mistake to check the validity of your move generator from time to time. Doing this manually is a rather timeconsuming task. My engine is able to read the epd file, perform the perft calculation and compare the calculated number with the one provided in the epd-file. A nice thing to have imo.
The format looks like that. A fen-string an then the depthts with their corresponding perft numbers.
4k3/8/8/8/8/8/8/4K2R w K - 0 1 ;D1 15 ;D2 66 ;D3 1197 ;D4 7059 ;D5 133987 ;D6 764643Perft-testsuite
divide
While perft is a great help to discover if there are any bugs left, there still remains the problem tracking the bugs down. One approach is to go step by step through all the possible moves at depth 1 and compare the perft values with the perft values of another reliable program. That can be a bit timeconsuming if the initial position already has a lot of legal moves. One way to make things simpler is to implement a function that counts the moves and the number of child moves. Once you have this feature implemented, finding bugs gets simpler and definitely much quicker. As a source to compare your values with you can either modify an existing open source engine and add that feature or just use Sharper or Roce which both offer the command divide.
Example for divide with the position from above.
FEN-string: n1n5/PPPk4/8/8/8/8/4Kppp/5N1N b - - 0 1roce: divide 5
d7e7 203075
d7c7 144121
d7d6 211186
d7c6 198410
d7e8 146984
d7e6 226311
a8c7 287482
a8b6 232333
c8b6 190892
c8a7 185316
c8e7 221064
c8d6 249997
g2g1 196031
g2g1 201350
g2g1 72525
g2g1 24145
g2f1 33700
g2f1 91129
g2f1 33399
g2f1 54682
g2h1 141001
g2h1 92321
g2h1 109225
g2h1 58424
Moves: 24
Nodes: 3605103
As you can see 'divide depth' gives you the legal moves with the number of their child moves. It's like you would make a move in this position and call perft with the argument depth-1 from the resulting position.
Hint: Don't forget to use other useful tools like sort.