Hint for debugging move generators through perft

[AartBik]

If you are lost in debugging a move generator with perft, an obvious but useful "trick" that is already used widely for chess is to breakdown perft(d) per move. Suppose you are writing a new 8x8 checkers engine, and you compare perft(d) for various d against the numbers generated by a trusted other engine:

Code: Select all

d=1  :           7  
d=2  :          49  
d=3  :         302  
d=4  :        1469 
d=5  :        7361  
d=6  :       36768  
d=7  :      179740 
d=8  :      845931

Now suppose your perft(d) scores are correct for 1<=d<=7 but are off for d=8. How to proceed without aimlessly staring at many positions? In this case, breakdown the perft scores of the trusted engine down per move, as in:

Code: Select all

breakdown perft(8):
12-16  :       nodes=142459
11-16  :       nodes=163687
11-15  :       nodes=96625
10-15  :       nodes=108364
10-14  :       nodes=94412
 9-14   :       nodes=92267
 9-13   :       nodes=148117

total-nodes=845931

and compare those with the perft scores per move of the new engine. Then pick the move that is wrong (if the counts of several or all moves are off, just pick a faulty one abritrarily), apply it on the board, and compute perft(d-1) broken down per move. Unless you have a very nasty bug, one of those perft scores will be wrong and you proceed with applying that move and perft(d-2) etc. At one point, you have a perft(1) score that is off, and debugging the move generator is easy.

Simple, obvious, but hopefully a useful hint.

[AartBik]

While browsing through the previous "perft" thread after my post, I realize Rein already pointed to the chess habit of breaking down perft per move for debugging. Still hope it's useful information

[Rein Halbersma]

While browsing through the previous "perft" thread after my post, I realize Rein already pointed to the chess habit of breaking down perft per move for debugging. Still hope it's useful information

Yes, good point Aart. The chess guys call this tool "divide()". It's quite useful.

[64_bit_checkers_engine]

If you are lost in debugging a move generator with perft, an obvious but useful "trick" that is already used widely for chess is to breakdown perft(d) per move.

At this time I would like to thank Aart for his help in debugging my 64-bit checkers move generator. Just so everyone knows, Aart and I agreed through 12 plies of perft() and only differed by 394 nodes for perft(13) which has a correct count of 1,766,623,630. It turns out if you don't do a perft() through 13 plies, you will not know if two candidate move generators are in fact working.

At first, I did not understand the concept of "playing forward" into the perft() line since I had not written a "perft()-by-move" tool. Aart was nice enough to demonstrate the concept to me. Then, of course, it made perfect sense!

I will post some perft() numbers here a little later. Thanks again Aart!

[AartBik]

I will post some perft() numbers here a little later. Thanks again Aart!

Ed,
You are very welcome. Glad I could help.
Looking forward to see more results with your fast move generator!
Aart