[Guide] Perft scores - validating the move generation

I should have done this much earlier, but here we are.

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:

1  20
2  400
3  8902
4  197281
5  4865609
6  119060324
7  3195901860
8  84998978956
9  2439530234167
10 69352859712417

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));

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++)
  {
    board.makeMove((Move)moves.get(i));
    nodes += miniMax(board, depth-1);
    board.unmakeMove((Move)moves.get(i));
  }
  
  return nodes;
}

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.

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 5

Move Nodes
Nc3  234656
Na3  198572
Nh3  198502
Nf3  233491
a3   181046
a4   217832
b3   215255
b4   216145
c3   222861
c4   240082
d3   328511
d4   361790
e3   402988
e4   405385
f3   178889
f4   198473
g3   217210
g4   214048
h3   181044
h4   218829

Total nodes: 4865609

Now 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.

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.