A perft score is the node count from a plain mini-max search on a certain position. For example the start position at depth 1 has 20 nodes, since there are 20 possible moves (nodes). At depth 2 we have 400 nodes, since for every move white makes black can answer with 20 different moves (20*20=400). And so on.
This is used to make sure our move generation works as it should. Now how should we know how many nodes a certain position is supposed to have at a certain depth? Well you could either count them by hand (I rather not do that :) or use another engine which you know has a correct move generator.
Or you could use validated results available on different web sites. Like Sharper.
Or just a test suite, which is basically a text file with fen-strings followed by the correct results at each depth.
Here are the correct number of moves each depth should return, starting with the initial position:
Those values are correct and if your engine does not return the same figures, something is wrong.
My Perft code looks like this:
System.out.println(miniMax(board, 5));As you can see it is a mini-max routine which returns '1' on every leaf of the tree. Every node collects the result, and when the search is done you have the final result which is returned and printed.
private long miniMax(Board board, int depth)
long nodes = 0;
if(depth == 0) return 1;
Vector moves = board.generateMoves();
for(int i = 0; i < moves.size(); i++)
nodes += miniMax(board, depth-1);
If you get a conflicting result, something is wrong with your move generation and you will have to go bug-hunting.
Divide the trouble
If you get a result that differs from the validated amount of nodes at a certain depth you know you have a bug somewhere. But unfortunately the number says nothing about where it might be.
To make it easier you can write a 'divide'-method that instead of just printing the total number of nodes, prints every initial move, and then the number of child moves to it. The output from the initital position could look like this:
Searching with depth 5Now you need to compare it to another verified engine with a divide function. Sharper has it and also Roce. I used Roce when I verified my results, just start the .exe-file and write 'help' to get the commands.
Total nodes: 4865609
When you see a conflicting result for some move, you play it on the board and do another divide-search with one less depth. And so on until you reach depth 1 and you will see all the moves and what move you are missing.
It takes time
Testing deeper depths can take a lot of time. We are talking hours and days for 10 ply searches. This is of course because no part of the tree gets cut off like in alpha-beta searches. And even though we do no kind of evaluation in the end, there are insane amounts of nodes to find (from the initial position 10 plies results in nearly 70 trillion nodes).
You will find any errors you might have eventually so it is well worth it. But I recommend you find some good test suite and run every position to about depth 6. This should catch all bugs with alot less time.
Here is the test suite from Roce.
perftsuite.epd (right click and choose 'Save as' to download the file)
To run the test suite automatically you will of course have to do some more programming or just take the fen-strings from the file and check the results manually. I leave that to you.