Which perft result is correct (and why)?

[sluijten]

I am using a perft to test my move generator/(un)make move, using position No 2 from wikispace: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 0

With depth 2, my engine returns 47x O-O castlings and 46x O-O-O castlings, (93 total) and I believe this is correct, but the website lists 91 castlings, so I checked by hand

Depth=1 (white to move): 48 moves with 2 castlings. So far I agree.
Now let's look at all illegal castlings (black to move) at depth=2,
I can only find 5.
If there were no illegal castlings, then the total number would be 2 + 48*2 = 98.

These are black's illegal castlings that I can find:

Code: Select all

                       O-O: 49         O-O-O: 49

after Bxa6:                                   -1
after Nc6:                                    -1
after Nxd7:                 -1
after Nxg6:                 -1
after Nxf7:                                   -1

so total = 98 - 5 = 93 ?
Am I missing something here?

[Evert]

Do you get the correct total number of moves?
My perft program only outputs total number of moves, so I can't directly say how many castling moves I get, but it gives the same number of total moves.

[sluijten]

I get a different perft(2) count, that's why I started to isolate the problem using this position, and added a castling count into my perft, saw a different castling count, and basically got stuck because I think my engine *IS* correct as far as castling is concerned... (but I am not a strong chess player...)
It seems that there are more white moves restricting black's castling, more than the five I can see, but which ones??

[Evert]

[strike]Well, I checked, and my program returns 93 castling moves for perft=2, so it would seem that the listing on the wiki is indeed wrong.[/strike]

EDIT: actually, it is right if it's listing the number of castling moves in leaf nodes rather than the total number in the tree. Make sure you're comparing the right numbers. At depth=1, there are 2 castling moves, at depth=2, there are 91 castling moves for black and 2 for white, for a total of 93 in the tree.

If your total is off, I would probably suggest starting with en-passant captures, which is where I found the largest number of bugs in my program.

[sluijten]

That's very confusing, because I think the listing for the first position is cumulative.

[Giorgio Medeot]

That's very confusing, because I think the listing for the first position is cumulative.

I don't think so. Perft is the count of unique paths to a certain depth, that is the count of the end leaves of the tree, so you should only count castling moves happening in the last ply. If you look at the stats on the wiki page for the second position, you will see that the number of promotion moves goes from 15'172 down to 8'392, going from depth 4 to 5, so they are not cumulated for sure.

Cheers,

• Giorgio

[Sven]

That's very confusing, because I think the listing for the first position is cumulative.

I don't think so. Perft is the count of unique paths to a certain depth, that is the count of the end leaves of the tree, so you should only count castling moves happening in the last ply. If you look at the stats on the wiki page for the second position, you will see that the number of promotion moves goes from 15'172 down to 8'392, going from depth 4 to 5, so they are not cumulated for sure.

Cheers,

• Giorgio

I agree. Perft counts all legal move paths which have exactly length N. That means, also leaf nodes at depth < N do not count.

http://chessprogramming.wikispaces.com/perft

Sven

[bob]

That's very confusing, because I think the listing for the first position is cumulative.

I don't think so. Perft is the count of unique paths to a certain depth, that is the count of the end leaves of the tree, so you should only count castling moves happening in the last ply. If you look at the stats on the wiki page for the second position, you will see that the number of promotion moves goes from 15'172 down to 8'392, going from depth 4 to 5, so they are not cumulated for sure.

Cheers,

• Giorgio

I agree. Perft counts all legal move paths which have exactly length N. That means, also leaf nodes at depth < N do not count.

http://chessprogramming.wikispaces.com/perft

Sven

It has been amazing to watch this "story" grow. I wrote perft in an early version of Crafty since I was continually tweaking with different ways of doing bitboard move generation, before I came up with the rotated idea. The intent was to catch gross errors. Others liked the idea, and at one point it became a race to see who could do perft to some fixed depth the fastest, which added hashing and other optimizations.

It really was designed as a debugging tool. I am not sure why I chose to count terminal positions rather than total positions, other than it made a simple mental calculation that perft 2 from the root should generate 20*20 terminal positions.

I have since seen this question raised over and over (all nodes including internal ones or just tips?). At least in Crafty, is has always been "terminal positions". I even added the ability to do a "trace" and print out every single path, each on a single line, so that I could "diff" the two results and see where a move was not getting generated in the new version, or where an extra move was being produced...

[Sven]

I have since seen this question raised over and over (all nodes including internal ones or just tips?). At least in Crafty, is has always been "terminal positions".

While initially it was only a Crafty feature it has now become a standard, and can't (or shouldn't) be changed in the next 50 years or so, since virtually everyone uses the numbers based on exactly that definition to verify - sometimes even in an automatic self-test - his move generator.

Sven

[bob]

I have since seen this question raised over and over (all nodes including internal ones or just tips?). At least in Crafty, is has always been "terminal positions".

While initially it was only a Crafty feature it has now become a standard, and can't (or shouldn't) be changed in the next 50 years or so, since virtually everyone uses the numbers based on exactly that definition to verify - sometimes even in an automatic self-test - his move generator.

Sven

I know. My point was that several things I have done have become "cast in stone" even if they are sub-optimal. It would have been better to count every node, rather than every path, since that gives more information for debugging. Same goes for my simple q-search pruning where I computed a value "delta" which is alpha - material-score. That tells me what kind of change (or delta) I need to get the score back to at least alpha. And it became known as "delta pruning" solely based on my choice of variable names. I chose the name based on a simple mathematical term, like "delta-V", what is the change in the velocity over time?" And to this day, I hate that terminology. It is nothing but futility pruning. It wasn't my idea. I just was the first to express it exactly in that way... (delta = alpha - Material; if (value(captured) < delta, no point in trying that capture). (actually there is a fudge factor tossed in as well, but that's the basic idea, and that is nothing more than simple futility pruning...)

My parallel search approach is much more unique than that, and calling it the "Crafty SMP search" is something I don't object to. It was thought out and implemented over several months, after a lot of prior experience with blitz and Cray Blitz doing parallel searches. So as a "standard metric" the SMP search is pretty good. But these other things were just things I did and now have become cast in stone, and even mis-used (some use perft as a speed measure and try to optimize the fool out of it, when it was intended to help find subtle move generator or make/unmake issues only...)