A method guaranteed to localize the toughest perft() bugs

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

A method guaranteed to localize the toughest perft() bugs

Post by sje » Thu Sep 18, 2014 3:52 am

A method guaranteed to localize the toughest perft() bugs:

The following is an idea which I may implement in Oscar so that all those coders with tough perft() bugs might benefit.

With this idea you might need lots of CPU time and a boatload of disk space.

Oscar keeps track of the current variation during perft(). By setting options to disable transposition assistance and to also disable bulk counting, Oscar will visit each and every node in the perft() tree. It would be easy to add an option to the CPU version (not the OpenCL version) of Oscar to dump the current variation, one per line, to a file. When the calculation is complete, the result is a BIG file with every variation seen and none which aren't seen. (An assumption here is that Oscar's perft() is bug-free.)

With this file in hand, the coder with a buggy perft() adds similar variation tracking and dump code to their program, then runs the same perft() from the same position.

As it is unlikely that the two programs traverse the tree in the same order, the two files should first be sorted. Also, both programs must use the same move notation which for Oscar is SAN.

Now, the two files can be compared with the Unix diff utility, and within a few seconds any missing and any extraneous variations will appear. This will show precisely which moves and positions were mishandled.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Variation files for perft(n) (n=1..5)

Post by sje » Thu Sep 18, 2014 4:33 am

Variation files for perft(n) (n=1..5)

I had Oscar calculate the variation files for perft(n) (n=1..5) and have uploaded the gzip versions for all to review.

https://dl.dropboxusercontent.com/u/316 ... n/vdmp1.gz
https://dl.dropboxusercontent.com/u/316 ... n/vdmp2.gz
https://dl.dropboxusercontent.com/u/316 ... n/vdmp3.gz
https://dl.dropboxusercontent.com/u/316 ... n/vdmp4.gz
https://dl.dropboxusercontent.com/u/316 ... n/vdmp5.gz

They are in the CaveMan directory because they're used with caveman-style debugging.

Note that for this application, Oscar has generated all moves at each ply in ascending SAN ASCII order, and that a variation is produced and printed immediately after every call to the Execute() routine.

AlvaroBegue
Posts: 924
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: A method guaranteed to localize the toughest perft() bug

Post by AlvaroBegue » Thu Sep 18, 2014 5:03 am

I have an alternative proposal. We could implement `divide' with a standard output format, and then we could have a script that takes two engines, runs perft tests on both and if they ever disagree it would repeatedly use divide to find moves where the count doesn't match, and thus discover a position in which the programs generate different move lists.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: A method guaranteed to localize the toughest perft() bug

Post by sje » Thu Sep 18, 2014 5:14 am

AlvaroBegue wrote:We could implement `divide' with a standard output format, and then we could have a script that takes two engines, runs perft tests on both and if they ever disagree it would repeatedly use divide to find moves where the count doesn't match, and thus discover a position in which the programs generate different move lists.
That would work in many cases, but not all of them.

It will not work in those cases where a buggy program produces incorrect sums with a given value for depth, but produces correct sums with a lower value of depth.

mar
Posts: 2108
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: A method guaranteed to localize the toughest perft() bug

Post by mar » Thu Sep 18, 2014 6:42 am

I prefer a small set of artificial positions that focus
on common pitfalls-you only need small depths
plus get the results in no time.
Some people even believe that perft from startpos
is enough, well it's a waste because they ´d have
to go very very deep...

aaronmell
Posts: 14
Joined: Sat Aug 30, 2014 12:32 am

Re: A method guaranteed to localize the toughest perft() bug

Post by aaronmell » Thu Sep 18, 2014 2:00 pm

This would really help me out with the current bug I am trying to fix in my own move generator.

Post Reply