Another perft(7) challenge position

[zullil]

Another perft(7) challenge position, this from Perft(14) work unit 413 (line 92,766):
[d]rnbq1b1r/ppppkppp/4pn2/8/1Q6/2PP4/PP2PPPP/RNB1KBNR b KQ - 2 4[/d]

One program says 3,016,077,677.

Another program says 3,016,055,832.

What does your program say?

Code: Select all

FEN string = rnbq1b1r/ppppkppp/4pn2/8/1Q6/2PP4/PP2PPPP/RNB1KBNR b KQ -
Depth = 7
Leaf nodes = 3016055832
Time taken = 42016 ms

[sje]

128 bit signatures win again.

Very roughly, about one out of one million perft(7) searches has different answers depending on using 64 bit vs 128 bit hash signatures. There are a lot of variables involved, but maybe it's not too much to say that about one out of a million searches by a chess engine will exhibit the same false positive rate when using 64 bit vs 128 bit signatures.

[jwes]

GnuCheese: Perft(7)=3016055832 time=80.27s nps=647917

Maybe 32 bit overflow in the nps calculation?

[jwes]

128 bit signatures win again.

Very roughly, about one out of one million perft(7) searches has different answers depending on using 64 bit vs 128 bit hash signatures. There are a lot of variables involved, but maybe it's not too much to say that about one out of a million searches by a chess engine will exhibit the same false positive rate when using 64 bit vs 128 bit signatures.

A little less roughly, a chess engine will have a false positive per year of search time which, unlike perft, probably will not change the result.

[bob]

128 bit signatures win again.

Very roughly, about one out of one million perft(7) searches has different answers depending on using 64 bit vs 128 bit hash signatures. There are a lot of variables involved, but maybe it's not too much to say that about one out of a million searches by a chess engine will exhibit the same false positive rate when using 64 bit vs 128 bit signatures.

A little less roughly, a chess engine will have a false positive per year of search time which, unlike perft, probably will not change the result.

One out of a million false positives will not change much at all. See the paper Cozzie and I wrote for the ICGA. It might even be on my web page...

[sje]

One out of a million false positives will not change much at all. See the paper Cozzie and I wrote for the ICGA. It might even be on my web page...

This is one of those "pay your money, take your choice" kind of things.

1) Use 64 signatures, employ retrieved move sanity checking to avoid crashing (eats time), and live with rare false positives giving a bad score or bound.

2) Use 128 bit signatures, eat more table space, but never worry about false positives nor bother spending time with retrieved move sanity checking.

[bob]

One out of a million false positives will not change much at all. See the paper Cozzie and I wrote for the ICGA. It might even be on my web page...

This is one of those "pay your money, take your choice" kind of things.

1) Use 64 signatures, employ retrieved move sanity checking to avoid crashing (eats time), and live with rare false positives giving a bad score or bound.

2) Use 128 bit signatures, eat more table space, but never worry about false positives nor bother spending time with retrieved move sanity checking.

Hate to tell you, but if you use HASHING, it will never be perfect. If you don't check things that could cause a crash on a false match, you will ALWAYS have the chance of crashing without the checking. So you get to check no matter what, to eliminate a tiny number of 64 bit collisions, and replace them with a smaller number of 128 bit collisions.. Seems that the fastest approach is 64 bit.

[sje]

Hate to tell you, but if you use HASHING, it will never be perfect. If you don't check things that could cause a crash on a false match, you will ALWAYS have the chance of crashing without the checking. So you get to check no matter what, to eliminate a tiny number of 64 bit collisions, and replace them with a smaller number of 128 bit collisions.. Seems that the fastest approach is 64 bit.

I may be off a bit on the numbers, but adding 64 bits of hash reduces false positives by about 2^32. So if a 64 bit signature system has a false positive once a month, then a 128 bit version will have one about once every 350 million years. No, that's not perfect. But it's closer to perfect than what it first appears, for a chess position takes only some 200 bits for a perfect unique encoding. So 128 bits is not only twice 64, but it's also that much closer to the theoretical bound. With the right base codes, a 200 bit Zobrist system might not be capable of a false positive. Tough to prove, though.

Anyway, it doesn't have to be perfect. But it the false positive rate should be lower than combined rates of other error types like flakey chips and cosmic rays.

[bob]

Hate to tell you, but if you use HASHING, it will never be perfect. If you don't check things that could cause a crash on a false match, you will ALWAYS have the chance of crashing without the checking. So you get to check no matter what, to eliminate a tiny number of 64 bit collisions, and replace them with a smaller number of 128 bit collisions.. Seems that the fastest approach is 64 bit.

I may be off a bit on the numbers, but adding 64 bits of hash reduces false positives by about 2^32. So if a 64 bit signature system has a false positive once a month, then a 128 bit version will have one about once every 350 million years. No, that's not perfect. But it's closer to perfect than what it first appears, for a chess position takes only some 200 bits for a perfect unique encoding. So 128 bits is not only twice 64, but it's also that much closer to the theoretical bound. With the right base codes, a 200 bit Zobrist system might not be capable of a false positive. Tough to prove, though.

Anyway, it doesn't have to be perfect. But it the false positive rate should be lower than combined rates of other error types like flakey chips and cosmic rays.

But the issue is that once a month has zero impact on the tree search result. Once a day has zero impact. Even once a minute has zero impact. Verified with two different chess programs. One false match per million nodes searched had no effect.

So adding 64 bits and doubling the computational cost only reduces something that is already zero...

[sje]

But the issue is that once a month has zero impact on the tree search result. Once a day has zero impact. Even once a minute has zero impact. Verified with two different chess programs. One false match per million nodes searched had no effect.

So adding 64 bits and doubling the computational cost only reduces something that is already zero...

Your argument would be stronger if only scores or bounds are stored.

But when also storing moves, using 128 bit signatures means no need for running move sanity tests on each move retrieval. I'll bet that the time saved by skipping sanity testing is much more than the time spent on shoving around an extra eight bytes here and there.

When my programs went from 64 bit to 128 bit signatures, I tossed the move sanity test code. But I remember that it was non-trivial because of special case moves and that even a fast path through would hit several conditionals:

1) Origin square must have STM man.
2) Destination square must be vacant or have non-STM man.
3) CanMoveTo(origin, destination) to be proven.

Number three also needs an make/unmake test if subsequent logic expects legal-only moves.

That's all bug magnet code. The only simple way to code a sanity test is to generate all the moves and see if one matches.

I'll stick with 128 bit signatures instead. I suppose that could be cut down to 96 bits, going from a 350 million year MTBF to a 60,000 year MTBF.