Perft(7) challenge position #5

[sje]

So, if the error rate for perft(7) operations is about the same as for five second searches AND your program plays blitz chess 24/7, then your program will incur a false positive error about once every two months.

A false positive error which returns a score only will only very rarely cause a difference in move selection because almost all retrieved scores do NOT get propagated upward in the search tree.

A false positive error which returns a move will change the search tree, but again a change is unlikely to be propagated upwards. However, if the move is illegal in the current position AND gets played because of no cut-off, then the program may crash if there isn't sufficient legality checking or resistance to bogus move make/unmake.

Now if the program author doesn't mind their program crashing just a few times per year of constant use, then 64 bit signatures are okay. And if the author will implement full legality checking for retrieved moves, then there won't be any bogus move crashes at all. But in this second case, there is a penalty paid with the extra time spent testing each retrieved move.

[bob]

So, if the error rate for perft(7) operations is about the same as for five second searches AND your program plays blitz chess 24/7, then your program will incur a false positive error about once every two months.

A false positive error which returns a score only will only very rarely cause a difference in move selection because almost all retrieved scores do NOT get propagated upward in the search tree.

A false positive error which returns a move will change the search tree, but again a change is unlikely to be propagated upwards. However, if the move is illegal in the current position AND gets played because of no cut-off, then the program may crash if there isn't sufficient legality checking or resistance to bogus move make/unmake.

Now if the program author doesn't mind their program crashing just a few times per year of constant use, then 64 bit signatures are okay. And if the author will implement full legality checking for retrieved moves, then there won't be any bogus move crashes at all. But in this second case, there is a penalty paid with the extra time spent testing each retrieved move.

A couple of key points.

(1) this "legality check" is trivial in computational cost. All you have to do is catch the cases that will make you crash. For me, the only problem is castling. A castle move where the king and rook are not on their original squares will cause problems. But this is a trivial check. The other is just as trivial, verifying that the moving piece is on the source square, and that the captured piece (if any) is on the destination square. This is not a very expensive operation.

(2) It is done pretty infrequently for most of the game, as you have to get a hash hit before you can have a hash move to test. And then you actually have to try to search that move before it needs to be checked for validity.

(3) You can NOT eliminate the validity check with a 128 bit signature. Until you hit the 160+ bit range where you have a perfect hashing function that never produces a collision, you will always be constrained to check for legality to avoid the potential crash.

(4) worrying about false matches causing problems with the tree data (as opposed to producing a crash) is pointless. One false positive every 1M nodes won't do a thing.

[bob]

So, if the error rate for perft(7) operations is about the same as for five second searches AND your program plays blitz chess 24/7, then your program will incur a false positive error about once every two months.

A false positive error which returns a score only will only very rarely cause a difference in move selection because almost all retrieved scores do NOT get propagated upward in the search tree.

A false positive error which returns a move will change the search tree, but again a change is unlikely to be propagated upwards. However, if the move is illegal in the current position AND gets played because of no cut-off, then the program may crash if there isn't sufficient legality checking or resistance to bogus move make/unmake.

Now if the program author doesn't mind their program crashing just a few times per year of constant use, then 64 bit signatures are okay. And if the author will implement full legality checking for retrieved moves, then there won't be any bogus move crashes at all. But in this second case, there is a penalty paid with the extra time spent testing each retrieved move.

A couple of key points.

(1) this "legality check" is trivial in computational cost. All you have to do is catch the cases that will make you crash. For me, the only problem is castling. A castle move where the king and rook are not on their original squares will cause problems. But this is a trivial check. The other is just as trivial, verifying that the moving piece is on the source square, and that the captured piece (if any) is on the destination square. This is not a very expensive operation.

(2) It is done pretty infrequently for most of the game, as you have to get a hash hit before you can have a hash move to test. And then you actually have to try to search that move before it needs to be checked for validity.

(3) You can NOT eliminate the validity check with a 128 bit signature. Until you hit the 160+ bit range where you have a perfect hashing function that never produces a collision, you will always be constrained to check for legality to avoid the potential crash.

(4) worrying about false matches causing problems with the tree data (as opposed to producing a crash) is pointless. One false positive every 1M nodes won't do a thing.

[sje]

64 bit signature false positive rate is now circa 1.8*10^-6 (1/560,000)

5 cases were located from 28 work units; each work unit has 100,000 unique positions.

Fully verified work units (23):
400-408 411-412 414 416 419 421-422 424-426 428 430 432 435

Work units with at least one false positive (5):
409-410 413 415 417

[sje]

A retrieved move legality check may not be so simple if it's a full legality test vs a pseudolegality test. Testing a retrieved en passant move including moving into check might not be very trivial at all. A psuedolegal move which won't crash one program might quite well crash another.

Delaying a legality test just means more wasted processing time if the move turns out to be bogus.

A retrieved move legality test should be omitted when using 128 bit signatures, at least until other more useful tests are performed. A false positive 128 bit match might happen only once ever 300 million years or so, and so there are other problems due to cosmic rays which would be more profitable to test. For example, running each and every calculation three times and taking the majority result.

[Joost Buijs]

A retrieved move legality check may not be so simple if it's a full legality test vs a pseudolegality test. Testing a retrieved en passant move including moving into check might not be very trivial at all. A psuedolegal move which won't crash one program might quite well crash another.

Delaying a legality test just means more wasted processing time if the move turns out to be bogus.

A retrieved move legality test should be omitted when using 128 bit signatures, at least until other more useful tests are performed. A false positive 128 bit match might happen only once ever 300 million years or so, and so there are other problems due to cosmic rays which would be more profitable to test. For example, running each and every calculation three times and taking the majority result.

In my engine there is a full move legality test that includes a test for moving into check.
When I retrieve a move from the hash-table I can use this test to check for legality.
In the past I always had this test disabled, lately I enabled it again, the overhead of this test is hardly noticeable and lies within the noise you normally will encounter.

A 128 bit key seems to be very safe, but you can pack a position perfectly into something like 22 bytes (give or take a byte) that would be even safer, especially for perft where you don't want to have a single error.
It is true that with a 128 bit key you may have an error once in 300 mln. years, but that once could be today or tomorrow.

Indeed there is the problem of cosmic rays, when I was still working in the lab, with very sensitive CCD chips, we saw on average each second a cosmic ray event.
Somehow computer chips don't seem to be very sensitive to this phenomena, otherwise your computer would crash immediately after turning on.

[Mark]

For fun, I let this run until perft 8 finished. (Took my program about 3 days!) Could someone with a faster search verify the result? Thanks!

Perft 1 = 40
Perft 2 = 1091
Perft 3 = 41284
Perft 4 = 1149593
Perft 5 = 42490376
Perft 6 = 1226949550
Perft 7 = 44950307154
Perft 8 = 1348381824306

[vittyvirus]

Here's the output from Yaka, for whatever it's worth:

Code: Select all

perft 7
h3h1: 617871698
h3h2: 924086794
h3d3: 1925384359
h3e3: 1137021524
h3f3: 1383536879
h3g3: 1336844711
h3h4: 1108391082
h3h5: 1134469332
h3h6: 1232069768
h3g2: 1312270381
h3g4: 1526527123
h3f5: 1384149842
h3e6: 1268691049
h3d7: 854847058
c8g4: 1004059495
c8f5: 1135318701
c8e6: 883860943
c8d7: 1126202678
b8a6: 1050434810
b8c6: 1285179276
b8d7: 932777644
g8f6: 1229971418
g8h6: 1003703238
e8d7: 887566497
e8d8: 1086276099
d5d4: 912094611
a7a6: 1018600925
b7b6: 1127072091
c7c6: 936096505
e7e6: 1127665031
f7f6: 981020886
g7g6: 1157418927
h7h6: 966416325
a7a5: 1392582392
b7b5: 966412633
c7c5: 1182245226
e7e5: 1511078305
f7f5: 799599588
g7g5: 1055506286
h7h5: 1044985024
Took 133244 ms for 44950307154 nodes, 337353 knps

Hmm... Hash tables didn't seem to effect the result for me.

[vittyvirus]

For fun, I let this run until perft 8 finished. (Took my program about 3 days!) Could someone with a faster search verify the result? Thanks!

Perft 1 = 40
Perft 2 = 1091
Perft 3 = 41284
Perft 4 = 1149593
Perft 5 = 42490376
Perft 6 = 1226949550
Perft 7 = 44950307154
Perft 8 = 1348381824306

Your results look correct to me. Output from Yaka:

Code: Select all

perft 8 26
h3h1: 16333676708
h3h2: 27107045317
h3d3: 63321661198
h3e3: 32736581151
h3f3: 41870002497
h3g3: 40363792671
h3h4: 32915312911
h3h5: 34295424012
h3h6: 37806113197
h3g2: 39455980622
h3g4: 46311669078
h3f5: 42975741275
h3e6: 39596669001
h3d7: 27199650761
c8g4: 29321169547
c8f5: 33848319583
c8e6: 26270159537
c8d7: 33601355568
b8a6: 31391977885
b8c6: 38252939943
b8d7: 27810167533
g8f6: 36489418678
g8h6: 29722813658
e8d7: 26470114153
e8d8: 32533742421
d5d4: 26245862098
a7a6: 30522724944
b7b6: 33639490106
c7c6: 28071722190
e7e6: 33221391979
f7f6: 29092621508
g7g6: 34503279649
h7h6: 28578731294
a7a5: 42328017610
b7b5: 28400971889
c7c5: 36062342412
e7e5: 44469826296
f7f5: 23638514273
g7g5: 31084163071
h7h5: 30520666082
Took 950261 ms for 1348381824306 nodes, 1418959 KNPS

I used a 1GB hash table, though.

[ibid]

For fun, I let this run until perft 8 finished. (Took my program about 3 days!) Could someone with a faster search verify the result? Thanks!

Perft 1 = 40
Perft 2 = 1091
Perft 3 = 41284
Perft 4 = 1149593
Perft 5 = 42490376
Perft 6 = 1226949550
Perft 7 = 44950307154
Perft 8 = 1348381824306

gperft agrees:

Code: Select all

Qxg2       39,455,980,622
Qxd3       63,321,661,198
Qxh1       16,333,676,708
Nd7        27,810,167,533
Na6        31,391,977,885
Nc6        38,252,939,943
Nf6        36,489,418,678
Nh6        29,722,813,658
Bd7        33,601,355,568
Be6        26,270,159,537
Bf5        33,848,319,583
Bg4        29,321,169,547
Qd7        27,199,650,761
Qe6        39,596,669,001
Qf5        42,975,741,275
Qg4        46,311,669,078
Qh6        37,806,113,197
Qh5        34,295,424,012
Qh4        32,915,312,911
Qe3        32,736,581,151
Qf3        41,870,002,497
Qg3        40,363,792,671
Qh2        27,107,045,317
a6         30,522,724,944
b6         33,639,490,106
c6         28,071,722,190
e6         33,221,391,979
f6         29,092,621,508
g6         34,503,279,649
h6         28,578,731,294
d4         26,245,862,098
a5         42,328,017,610
b5         28,400,971,889
c5         36,062,342,412
e5         44,469,826,296
f5         23,638,514,273
g5         31,084,163,071
h5         30,520,666,082
Kd8        32,533,742,421
Kd7        26,470,114,153
TOTAL   1,348,381,824,306
28.290 seconds