OpenCL perft() Technical Issues

[sje]

Are Oscar's hash codes good enough? That pseudorandom bit generator looks too simple and runs too fast to escape suspicion.

The first 16 codes:

Code: Select all

1a545350330f4cfff70f7ef8cf711f98
7f3880e147837e40ef66c69cfde7dc46
279f71c6a1e6841d4e46260f27845078
9d61222571db3bf6e60c05b874764842
15c62581468277c52a7a1bdcdfc99b92
cf7db1ba0dba79611227a7ae4b67a026
ddeaba7d6df593b2d8e38dcf764e00ba
fbbb8769f9d3b621d8b62743aea1d073
9ccb963d93d226033024a1edbec669b4
f54a41ac0229ea10f3e06f5c25b62493
0907200ba8fbafaa66edcfd3de5abb84
e57472384c3fca9ba8c8c3b9d47e0a42
f3ec1b54b1b3a78cdced8135c28e510b
0da0e5903eec76fea143b11b87f92832
99d1b6284026a3247e43f36fc95df21a
6bbf5743f5deae764afcb583ecfe4097

You can see the complete set of 824 codes (each formatted as 32 ASCII hexadecimal digits, one code per line) here: https://dl.dropboxusercontent.com/u/316 ... /HashCodes

The codes pass the Eyeball Test. I suspect they pass plenty of other tests, too. At least until the 9,699,690 long period is hit; at that point, a few more primes could be added to the generator resulting with only a slight increase in initialization time.

[petero2]

Are Oscar's hash codes good enough? That pseudorandom bit generator looks too simple and runs too fast to escape suspicion.

The first 16 codes:

Code: Select all

1a545350330f4cfff70f7ef8cf711f98
7f3880e147837e40ef66c69cfde7dc46
279f71c6a1e6841d4e46260f27845078
9d61222571db3bf6e60c05b874764842
15c62581468277c52a7a1bdcdfc99b92
cf7db1ba0dba79611227a7ae4b67a026
ddeaba7d6df593b2d8e38dcf764e00ba
fbbb8769f9d3b621d8b62743aea1d073
9ccb963d93d226033024a1edbec669b4
f54a41ac0229ea10f3e06f5c25b62493
0907200ba8fbafaa66edcfd3de5abb84
e57472384c3fca9ba8c8c3b9d47e0a42
f3ec1b54b1b3a78cdced8135c28e510b
0da0e5903eec76fea143b11b87f92832
99d1b6284026a3247e43f36fc95df21a
6bbf5743f5deae764afcb583ecfe4097

You can see the complete set of 824 codes (each formatted as 32 ASCII hexadecimal digits, one code per line) here: https://dl.dropboxusercontent.com/u/316 ... /HashCodes

The codes pass the Eyeball Test. I suspect they pass plenty of other tests, too.

It does not pass my compression test though. When I compress this file with the "xz" program the file size is 12900 bytes. When I compress the same type of file but generated by extracting data from /dev/urandom, the average file size is 14611 bytes and the standard deviation is 29. So the compressed size of your file is about 59 standard deviations smaller than what would be expected when using truly random data.

Whether this has any negative effects on the number of hash collisions is of course a different question, but personally I would not want to take any chances by using an unproven PRNG.

[mar]

The codes pass the Eyeball Test. I suspect they pass plenty of other tests, too. At least until the 9,699,690 long period is hit; at that point, a few more primes could be added to the generator resulting with only a slight increase in initialization time.

I'm not sure the period is long enough, 9M seems rather low but perhaps fine for Zobrist.
There is old "diehard" set of PRNG tests (which rand() in Microsoft CRT (simple LCG) fails miserably), developed by Marsaglia (RIP) so perhaps you could try that.
IIRC it just needs you to generate n random-bytes binary file.
Or dieharder here (I found that even some PRNGs that pass diehard fail dieharder):http://www.phy.duke.edu/~rgb/General/dieharder.php
but I found some of those tests a bit dubious (Mersenne Twister doesn't seem to do very well in some).
I bet there are more test suites like that.
I also found a simple test (don't remember - have to look tomorrow) that showed that my PRNG (similar to Jenkins' KISS) is not as good as I thought but probably ok.

[mar]

I also found a simple test (don't remember - have to look tomorrow)

Found it. The idea is very simple (I call it set-fill): create a bit set of (I use 128*1048576 bits), clear all of them.
In each iteration, set a random bit to 1. Measure number of iterations it takes to fill the entire set.
The higher number of iterations, the better the quality of a PRNG in theory (if it terminates of course).
(it's possible to forge non-PRNGs that will do well in this "test").
Good PRNGs should be use around 2.8 or 2.9 billion iterations.
Of course this depends on seeding as well but shows rougly the expected values.
For comparison, using Microsoft CRT's (rand() << 15) ^ rand(), this takes less than 1 billion iterations, indicating poor quality.
EDIT: this test requires a period of at least 4G

[sje]

Given a transposition table of length L =2^n elements, a key with B bits, and an ordered set of positions P with arbitrarily large cardinality, then we could generate a Figure Of Merit FOM(L, B, P) for the key maker PRNG.

Consider an experimental setup using a simple overwrite replacement scheme, plus taking reasonable values for L, R and letting P be the sorted (FEN ASCII) set of each of the 96,400,068 positions for unique(7). To generate the FOM for a given PRNG, take a clear transposition table and insert the positions until half the table is filled. The smaller the insertion count, the greater the FOM.

I'd have much more confidence in this very empirical test than any bunch of less empirical tests pulled out of math books.

It would not be very difficult to add support for the above into Oscar where the program would read the keys from a foreign PRNG at start time.

[mar]

It would not be very difficult to add support for the above into Oscar where the program would read the keys from a foreign PRNG at start time.

Would be interesting to compare. Here are random keys I generated using MT: http://www.crabaware.com/Random/random_data.txt (passes Peter's compression test

[sje]

It would not be very difficult to add support for the above into Oscar where the program would read the keys from a foreign PRNG at start time.

Would be interesting to compare. Here are random keys I generated using MT: http://www.crabaware.com/Random/random_data.txt (passes Peter's compression test

Give me at least a few weeks. Or you could do it yourself after I release Oscar's source code.

I've got a feeling that even the fanciest PRNG won't perform much better than my little row of primes.

--------

Some more tests, these using the KiwiPete position:

Code: Select all

gail:tmp sje$ ./operft "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1" 4
4085603   6.90 MHz
gail:tmp sje$ ./operft "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1" 5
193690690   46.98 MHz
gail:tmp sje$ ./operft "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1" 6
8031647685   79.20 MHz
gail:tmp sje$ ./operft "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1" 7
374190009323   181.90 MHz

[sje]

Announcing: The Great Battle of the Hash Codes

And you're invited to participate.

Soon I will give the not-yet-released version of Oscar the option of reading its set of base hash code constants from a file at start time.

Oscar needs 824 of these codes, each 128 bits long. The input file is 824 codes, one per line, with each code represented as 32 hexadecimal digits. For an example input file, see Oscar's default set at: https://dl.dropboxusercontent.com/u/316 ... /HashCodes

Oscar's transposition table implementation is a vector with 2^N elements, with N=24 in the default configuration giving 24 bits of addressing (16,777,216 elements) using the least significant bits of a position's 128 bit signature.

Each signature maps onto two adjacent elements by wildcarding the bottom addressing bit. Both elements are searched during a fetch; on a stash, the element with the lesser perft subtotal is overwritten.

When a perft() calculation is finished, Oscar prints the table's utilization coefficient Cu, the value of the count of used elements divided by the total number of elements. Note that bulk counting is used at the next to bottom ply and these bulk counts are not stored in the table.

With the default base hash code set:

Code: Select all

./operft "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" 5
4865609
Utilization: 0.000345

./operft "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" 6
119060324
Utilization: 0.004641

./operft "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" 7
Utilization: 0.053571
3195901860

./operft "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" 8
Utilization: 0.528047
84998978956

./operft "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" 9
Utilization: 0.999979
2439530234167

The goal is to have the hash code file which results in the greatest utilization coefficients. The codes should be easily reproduced in a quick, deterministic, and portable manner. Extra praise awarded to a winner who has a pseudorandom bit generator even simpler than Oscar's routine which uses a row of the first eight primes.

To participate, just post a link to your entry and I'll take it from there.

[sje]

It would not be very difficult to add support for the above into Oscar where the program would read the keys from a foreign PRNG at start time.

Would be interesting to compare. Here are random keys I generated using MT: http://www.crabaware.com/Random/random_data.txt (passes Peter's compression test

Some of the values in your file have less than 32 hexadecimal digits.

[mar]

Some of the values in your file have less than 32 hexadecimal digits.

Oops, yes, you're right. Should be fixed now.