## Transposition table random numbers

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jdm64
Posts: 41
Joined: Thu May 27, 2010 9:32 pm

### Transposition table random numbers

I'm writing my transposition table, but I have a few questions:

1) What's a typical size of the transposition table? I'm thinking 2^22 items, which would make memory use about 80MB. If the table's too big (but still fits in ram) are there any negative side effects? What's a lower limit for the smallest size still effective?

2) For Zobrist Hashing, what requirements are there on the generated random 64bit numbers? I'm trying to reduce the number of hash collisions. Should all the low bit* for each number be unique? My current RNG (below) generates 64bit numbers such that every 16bit "block" is unique. Therefore, as long as the table is 2^16 or larger the low and hi bits are unique. Will this work?

Note: By low bits, I mean the bits that are used to determine the table index for a specific hash. If the table's size is 2^22 then the lower 19 bits of the hash will be the same as the table's index. Right?

Code: Select all

class Rand64 &#123;
private&#58;
uint64 box&#91;65536&#93;;
int size;

inline uint64 block&#40;)
&#123;
if &#40;size < 2&#41;
size = 65535;
swap&#40;box&#91;rand&#40;) % size&#93;, box&#91;size&#93;);
size--;
return box&#91;size + 1&#93;;
&#125;
public&#58;
Rand64&#40;)
&#123;
size = 65535;
for &#40;int i = 0; i < 65536; i++)
box&#91;i&#93; = i;
srand&#40;time&#40;NULL&#41;);
&#125;
uint64 next&#40;)
&#123;
uint64 val = 0;

for &#40;int i = 0; i < 4; i++)
val |= block&#40;) << &#40;16 * i&#41;;
return val;
&#125;
&#125;;

bob
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

### Re: Transposition table random numbers

jdm64 wrote:I'm writing my transposition table, but I have a few questions:

1) What's a typical size of the transposition table? I'm thinking 2^22 items, which would make memory use about 80MB. If the table's too big (but still fits in ram) are there any negative side effects? What's a lower limit for the smallest size still effective?
First, too big can hurt. You need TLB hits for virtual-to-real page translations. If that fails, you get an extra 4 memory accesses to do this translation, which kills the speed of a cache miss for that entry. If the table gets too large, you begin to replace TLB entries too frequently and suffer the above translation penalty.

The best way to determine what the optimal size is is to simply run some tests using a fixed time limit that you want to play at. Vary the hash size, and choose the one that gets you to the max depth the fastest. This number will be different for each different CPU configuration you run on, and for each different time control you use.

2) For Zobrist Hashing, what requirements are there on the generated random 64bit numbers? I'm trying to reduce the number of hash collisions. Should all the low bit* for each number be unique? My current RNG (below) generates 64bit numbers such that every 16bit "block" is unique. Therefore, as long as the table is 2^16 or larger the low and hi bits are unique. Will this work?

Good 64 bit random numbers are acceptable. There's not a lot you can do to optimize them, other than you can test them for randomness (poker test, runs test, uniformity test, etc) to make sure that they actually are reasonably random.

Note: By low bits, I mean the bits that are used to determine the table index for a specific hash. If the table's size is 2^22 then the lower 19 bits of the hash will be the same as the table's index. Right?
Assuming you have an 8 byte hash entry which seems way small..

Code: Select all

class Rand64 &#123;
private&#58;
uint64 box&#91;65536&#93;;
int size;

inline uint64 block&#40;)
&#123;
if &#40;size < 2&#41;
size = 65535;
swap&#40;box&#91;rand&#40;) % size&#93;, box&#91;size&#93;);
size--;
return box&#91;size + 1&#93;;
&#125;
public&#58;
Rand64&#40;)
&#123;
size = 65535;
for &#40;int i = 0; i < 65536; i++)
box&#91;i&#93; = i;
srand&#40;time&#40;NULL&#41;);
&#125;
uint64 next&#40;)
&#123;
uint64 val = 0;

for &#40;int i = 0; i < 4; i++)
val |= block&#40;) << &#40;16 * i&#41;;
return val;
&#125;
&#125;;
If you want, there is a well-known PRNG in Crafty's source. You can certainly use that, it is not my original code but is a freely distributed PRNG source program in C.

Dann Corbit
Posts: 9280
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

### Re: Transposition table random numbers

jdm64 wrote:I'm writing my transposition table, but I have a few questions:

1) What's a typical size of the transposition table? I'm thinking 2^22 items, which would make memory use about 80MB. If the table's too big (but still fits in ram) are there any negative side effects? What's a lower limit for the smallest size still effective?
Anywhere from 1 MB to 8 GB, depending on hardware, operating system bitness, time control, etc. Huge hash tables are only valuable for long time control and can actually hurt in lightning games.
2) For Zobrist Hashing, what requirements are there on the generated random 64bit numbers? I'm trying to reduce the number of hash collisions. Should all the low bit* for each number be unique? My current RNG (below) generates 64bit numbers such that every 16bit "block" is unique. Therefore, as long as the table is 2^16 or larger the low and hi bits are unique. Will this work?
Use the Mersenne Twister.
http://www.math.sci.hiroshima-u.ac.jp/~ ... T/emt.html
Note: By low bits, I mean the bits that are used to determine the table index for a specific hash. If the table's size is 2^22 then the lower 19 bits of the hash will be the same as the table's index. Right?
You don't need such a large table of random numbers. Examine a few working Zobrist hashing schemes in existing programs to get an idea of how it is done. It is possible to maximize hamming distance with an algorithm like this:

Code: Select all

unsigned long long hamdist&#40;unsigned long long x, unsigned long long y&#41;
&#123;
unsigned long long dist = 0,
val = x ^ y;
while &#40;val&#41; &#123;
++dist;
val &= val - 1;
&#125;
return dist;
&#125;
Or you can use a pre-maximized table of random values like this one:

Code: Select all

static const unsigned long long ham23bit&#91;999&#93; = &#123;
0x64d79b552a559d7fULL,
0x44a572665a6ee240ULL,
0xeb2bf6dc3d72135cULL,
0xe3836981f9f82ea0ULL,
0x43a38212350ee392ULL,
0xce77502bffcacf8bULL,
0x5d8a82d90126f0e7ULL,
0xc0510c6f402c1e3cULL,
0x48d895bf8b69f77bULL,
0x1126b97be8c91ce2ULL,
0xf05e1c9dc2674be2ULL,
0xe4d5327a12874c1eULL,
0xbba2bbfbecbc239aULL,
0xc5704350b17f0215ULL,
0x823a67c5f88337e7ULL,
0x9fbe3cfcd1f08059ULL,
0xdc29309412e352b9ULL,
0x5a0ff7908b1b3c57ULL,
0x46f39cb43b126c55ULL,
0x9648168491f3b126ULL,
0xdd3e72538fd39a1cULL,
0x0348399b7d2b8428ULL,
0xcf36d95eae514f52ULL,
0x7b9231d5308d7534ULL,
0xb225e28cfc5aa663ULL,
0xa833f6d5c72448a4ULL,
0xdaa565f5815de899ULL,
0xef6a48be001729c7ULL,
0xfdc570ba2fe979fbULL,
0xb57697121dfdfe93ULL,
0xb313b667a4d999d6ULL,
0x07c7fa1bd6fd7deaULL,
0x0ee9f4c15c57e92aULL,
0xc5fb71b8f4bf5f56ULL,
0xa251f93a4b335492ULL,
0xb2f0624214f522a2ULL,
0x22d91b683f251121ULL,
0x3462898a2ae7b001ULL,
0x468bc3a10a34890cULL,
0x84ff6ce56552b185ULL,
0xed95ff232c511188ULL,
0x4869be47a8137c83ULL,
0x97f3a778e242d0cfULL,
0xd870d281b293af3dULL,
0xc3a5f903a836fafdULL,
0x4e38ddc2719162a5ULL,
0xb75b43fb4c81784aULL,
0x562f36fae610a2e1ULL,
0x0e0e413e555bd736ULL,
0xd452549efe08402dULL,
0x0d84c9a356858060ULL,
0x19d5b3643bc029b6ULL,
0x0dd8131e97ffc842ULL,
0xf98c6d63ff48a16eULL,
0x83490ef054537f7eULL,
0xe071f833e55ebfe6ULL,
0xdae6e879b8eab74aULL,
0xe4a41f17e70d3e0aULL,
0xbc1abca3fbeeb2f3ULL,
0x5e37299d89089ba4ULL,
0xa1f735eb8235b32fULL,
0x2289d719e7b146eeULL,
0x1c9c9d0284d96719ULL,
0x317e34c009a07a39ULL,
0x5f45053666f3f84fULL,
0x63e7074f03c73d92ULL,
0x9643b3707db2cfb5ULL,
0x98e2db6c665e7178ULL,
0x36e7ac11d1f3a617ULL,
0x508f0acb609bd756ULL,
0x6f42d435193a1ac2ULL,
0x2df2cab9d65e0b00ULL,
0xc80d5b04f6337337ULL,
0x5d33cf557e6c4475ULL,
0x05b5a78be74ccd40ULL,
0x3ec2cce5290785f4ULL,
0x2eef1e9c4b36828bULL,
0x7ff345b4eb7f3639ULL,
0xa15f9c2826cb34dbULL,
0xc1cdaa5f9ca79b19ULL,
0x5094cafab11cbc3aULL,
0x94d40a57481346b5ULL,
0x0d493e410b68b6c6ULL,
0x71c1b0ba9e52a2deULL,
0xa7448d0059484568ULL,
0x2819237e5e8cb03aULL,
0x91e060fb399ecf2cULL,
0x5e650b9a3cb34308ULL,
0xe482d24e5b239833ULL,
0x52ed7d9f45c6b578ULL,
0x332f7ce3e077ecceULL,
0x5b057c64bda94a33ULL,
0xe974ffd57219e5e6ULL,
0x6750ecdf35c8471bULL,
0x2c6983c911c958afULL,
0x3220a56d67450e80ULL,
0xfd8137f8b59bd084ULL,
0x167cc7f46a511504ULL,
0x36374630d0ecb4e8ULL,
0x501337e1a7f1e218ULL,
0x589b8eaea60d54a4ULL,
0x8f1a8c1b84b3ba62ULL,
0xf69ffb64131633aeULL,
0xa837ae34963616fbULL,
0x11753aea03bb0ecdULL,
0x32d9cca610dceb34ULL,
0x94c1190da321d470ULL,
0x321e26bf321fb60bULL,
0xc9202ac8ba71c873ULL,
0x284d02d7552a3e90ULL,
0xa6e86f7ba2779a5cULL,
0x8f675048b7b012e5ULL,
0xe5e469aac68eaf1dULL,
0xc5967cdf353aeac6ULL,
0x59926f3401f437d4ULL,
0xfb49ab0635d66c3aULL,
0x316558d69efc8f6bULL,
0xfa9f65d2b4848b12ULL,
0x2b92665a263a5091ULL,
0x4171d5edd5468876ULL,
0x99bb4bf79b0a46c1ULL,
0x939ed8b0d7e91f87ULL,
0x8cb11929a65b6aeeULL,
0xbe6415659e12c64bULL,
0xbf2f4f23a6c92295ULL,
0x7890bc68793bb959ULL,
0x2a060f45a1719347ULL,
0x374635e7713ed165ULL,
0xbfb945ef1cf94d1dULL,
0x4b7519cb9028ac83ULL,
0x0301a07c84aaccdbULL,
0x93dee719932225a3ULL,
0x1528080b61f54198ULL,
0x2fc96b31dccafd9fULL,
0xe9fb2e3998d16a25ULL,
0xd5340e98fde806deULL,
0xc742bc0d0c55f125ULL,
0x3a9fa27258257e53ULL,
0xc12dc512aedc530cULL,
0xc8db824276c083ceULL,
0xb3c98071a3d13b20ULL,
0x679e0601953d1e31ULL,
0x96fc350ccdb76eabULL,
0x9fa0178362df447bULL,
0x451717a061972d1fULL,
0x0bbcbdae779cfbf3ULL,
0x7e2e9ef35a5aafbaULL,
0x68f4654bcc07435bULL,
0x30c6e14df59f8cefULL,
0xcfe629aa56717e20ULL,
0xfde48d87e844ec93ULL,
0x7c9d88364238519fULL,
0xe4ec475d296a69e5ULL,
0xf2ebc493b909d8c7ULL,
0x13834d3d0e43ab73ULL,
0x2dc12f9f04435661ULL,
0x563de834c4e56a46ULL,
0x9ec02036a6688a24ULL,
0x9847468f925dc38cULL,
0x8b0e5dca588e3f50ULL,
0x82337b3f1764851cULL,
0xd4166b32a26fc1c6ULL,
0x43e20045bcb06b0eULL,
0x3f58d1d6cd3aa0dcULL,
0xaf3d8a578b6d6232ULL,
0x762c21058ba50349ULL,
0x275d24c9aa1607f0ULL,
0x49efeab6642e9e45ULL,
0x791c96a57ea29814ULL,
0x18e883239eac0617ULL,
0x0ba51d62eb24045eULL,
0x98b487f3146aa174ULL,
0xcda6a4dccb6b73c9ULL,
0x9d66a7aa1fb4595cULL,
0xe221af6f18e45563ULL,
0x6e2c7411e8736390ULL,
0xacedd32f47936b61ULL,
0x7778b73e852e4d15ULL,
0x48ab18694d85497dULL,
0xbd7b6156c2c63188ULL,
0xb193700fe9937383ULL,
0x323beb9061b5af38ULL,
0x617864f443ee06a2ULL,
0x58faf5e64a26fbceULL,
0xa1210472d9abf2e6ULL,
0xb0880848c6f0ec2dULL,
0x0d5d48f4beaf279cULL,
0x98598e0027505d41ULL,
0xc6a8c29b036a0730ULL,
0x083dd247f0a9dfcdULL,
0x186a5d13e79a2806ULL,
0x889e7426b755fcc9ULL,
0x684fca18cc613bcbULL,
0x60dccc0ded809744ULL,
0x246a423aef3f89bfULL,
0x980cfc250f276150ULL,
0x9583176b78273ec5ULL,
0xd857f34b29fba06dULL,
0xc22ea4dbd5d4eb3dULL,
0x39846bce19845617ULL,
0x253f6c2acb91153cULL,
0xc4b501b09381f7dfULL,
0x8afdedfde82b6a2cULL,
0xc262732b5299fcc7ULL,
0x206ed744bef46053ULL,
0xed519f24bba3b7a0ULL,
0x86a9224fd39784e2ULL,
0xec32155b844684ccULL,
0x5038fe125722e26bULL,
0xc80c1dcc2a85da0eULL,
0xff6afaec984bb0bdULL,
0xbe81f9c9474c967fULL,
0xc2fb0f16bcbf30ceULL,
0xb5a94fce85369b23ULL,
0x83b09f892f3e7604ULL,
0x9d5cdb2eae76bc17ULL,
0x21be002177dac1fdULL,
0xb49075e6473925a9ULL,
0xf3f148c32f156c69ULL,
0x5c3c106d732d31a4ULL,
0x5b15d80b4950f0c6ULL,
0x4dee63522a811783ULL,
0x4fd8a3e8ff9268e9ULL,
0x1b67eb44e4c05609ULL,
0x2786afb08475eb89ULL,
0xf470219ba4d19b6bULL,
0x1bea4e946fcdfe80ULL,
0x21ebf22282a74064ULL,
0x041b669aa8caba7fULL,
0x89247e3e8fdac4e5ULL,
0xafe9ec5185000ccaULL,
0x353687e6f2b91aa7ULL,
0x0c04d510680657cfULL,
0x25cfd0ff7b4e767dULL,
0xfe110bb08b44a041ULL,
0xf91423aa2c286f94ULL,
0x5cc6b88d98a3cec1ULL,
0xbb59dedb371cb2a8ULL,
0x82c93115f2862155ULL,
0x53d0184675025da2ULL,
0x5b9eee674ed934bfULL,
0xd3481a6a879631d9ULL,
0x25df42a65e516091ULL,
0x300d5fc62140a89dULL,
0x9d613cdcdc06d7ecULL,
0xdf64f2c261780baeULL,
0xdc48e5079b7f1c6cULL,
0xbf20c573c7a4df16ULL,
0xb5f64fb1ef328cf0ULL,
0x01584766a000e46aULL,
0x9b1c4f7c166c5a18ULL,
0x0856ebd04bdcc953ULL,
0xeec423c4c81e3c65ULL,
0x0fe110a084141f59ULL,
0x5967b4bca28de312ULL,
0xb2e534fb4bc88391ULL,
0x174b91a8d27f409dULL,
0xf3a2dcd21bae4919ULL,
0xfe9f0b07bc28fd49ULL,
0x28470bfae915dec0ULL,
0x3ea221f3823327c4ULL,
0x640a0c676fb84d62ULL,
0xc2ca5337c9c10bd8ULL,
0x511eb890eb7efd2dULL,
0x782a77e63fc78d26ULL,
0xf7edd3abf0e8e8f4ULL,
0x3b14009bfec4fe60ULL,
0x54f5cebbdc8233a7ULL,
0x7f436eedfce43d10ULL,
0x40324ba22633147dULL,
0x8fd5c6f5d0bcc55eULL,
0x2bdcc1f030155a8eULL,
0x383062bfe3e25f19ULL,
0x7fb4e21fbd34a1fbULL,
0x8e2b3dbd42592403ULL,
0x3c95d093014fd9a8ULL,
0x6dd44c0c40febc8eULL,
0xc36dbbfedbf0e58eULL,
0xc0cfc583ea53a434ULL,
0xae44808c64eb123aULL,
0xfa465d1b01b5cd5fULL,
0x04b8be3720801be0ULL,
0xc0b2b846debda795ULL,
0x028966b957f2d943ULL,
0x8e9a964ff958a52dULL,
0x1ea371479081823fULL,
0x37b972dc22085d4dULL,
0x2e68b99e9ef515d7ULL,
0x2f72680378b2a5c2ULL,
0xfc2905d06898087cULL,
0xe97f7c71538c3917ULL,
0x2ab0db47d30ce099ULL,
0x773ef31c6d8dd7deULL,
0xc02c9b3249cabe35ULL,
0x6f5ee092d2b4202fULL,
0x88b5d75a341d1b63ULL,
0x8bbda8c0b3d73454ULL,
0x54d345222cc99eb0ULL,
0xfa9f84bc9bb56568ULL,
0x55d976319b868ed3ULL,
0x1d36070524abe9a8ULL,
0x12a6f3abdf519328ULL,
0xa21c99d12d00f952ULL,
0x4d6ff19d2d5064a8ULL,
0x0088e1003aa37e58ULL,
0x45a814ba1e6c9dedULL,
0xa49d950f7036dbb6ULL,
0xf556015fdf981992ULL,
0xf085743caa263407ULL,
0xcaf8222921640c9fULL,
0x7fa3140a9bb6be2eULL,
0xdc97dd7f8d25782bULL,
0x16173088784c1512ULL,
0xa4679275d2886afaULL,
0x1b52227e4ae5c5f6ULL,
0x6ac8777364a88ce1ULL,
0xa7522287d967ca68ULL,
0x19a9babd3fa1372cULL,
0x483a9fa995b8246aULL,
0xc25981e52898a6d1ULL,
0x46b3c54157aabff9ULL,
0x60372062a09ed423ULL,
0xcc80a989bd16c50aULL,
0x2a0597379ceb6f68ULL,
0xd96a252c2832036bULL,
0x44ee5ef1085c4e46ULL,
0x8655f3d016ea7481ULL,
0x4feebc1d03bd18bcULL,
0x35516b89f62115ceULL,
0x077a7910033cd348ULL,
0xe84a7bd3942b4afeULL,
0x4291838cddff05e5ULL,
0xf3395f4106d0c9aaULL,
0x3d2638ef1e7dd291ULL,
0x03c8c0425f3cfd57ULL,
0xc3ecd3942b828c6aULL,
0x5697ec8f7061e039ULL,
0xa1125e97c0949443ULL,
0x724240d826a9e69eULL,
0x2bff996618bb1707ULL,
0x2325d5954abdf8aaULL,
0x4bd95041860bd223ULL,
0x3b83eeb633e90c5eULL,
0xa18a1355045cde9dULL,
0xe49f18748ccb126cULL,
0x1660b4f6be263d3aULL,
0xd2f039d1584b1ec9ULL,
0xd1a64b151227fc11ULL,
0x0d7f99664658ca3cULL,
0x6f43f28f8d861cffULL,
0xa001cf0254be48c0ULL,
0xbc4c786ce164979aULL,
0xbd825980239dbbe6ULL,
0x8206c8ba22545bf9ULL,
0x0465490d1c862c49ULL,
0x58853b160b2ba6baULL,
0xcbf1b48304af80d8ULL,
0x287e840a5e8f4ee5ULL,
0xced5e028693dd7e9ULL,
0x03b185dea61025a7ULL,
0x6c197485b66de765ULL,
0x80bcbc406ae28883ULL,
0x32a438b70d14ccb6ULL,
0x79043354469a6b79ULL,
0x3875887c6f5fe087ULL,
0xda7a809e5c7a7c7bULL,
0x0c7b1c4ca0bcecf9ULL,
0xb1b035313ee4426eULL,
0x7278cde1d73f131cULL,
0xca351728d35427b2ULL,
0xfa24e4426ccd7ff8ULL,
0xf9b9182557579b09ULL,
0x597b231ff002c810ULL,
0x34ae7a2231de2d51ULL,
0x6a64af267b4e58d4ULL,
0x139bc5479df6c28bULL,
0xf63cc0a137236e93ULL,
0xb3a8222c7c673956ULL,
0x4f861e21c38af8cdULL,
0xf51fcaeabbf1964bULL,
0x26ef5b820f623976ULL,
0x0538d9e87f42b598ULL,
0x8be647a7bc1a78b7ULL,
0xc38a9550f67b91e2ULL,
0xf8fb954dbe4e3fc3ULL,
0xd7b8dce4ec0fcd47ULL,
0xc5d924c6637d605eULL,
0xbb04c18180e60ba5ULL,
0x07c5c78a9b0933d0ULL,
0xdbd343e7475abf56ULL,
0xf5f7ca0573fb50c0ULL,
0x981d24edcd8a0d61ULL,
0xcc388efa7e34ab07ULL,
0xce2344937335b360ULL,
0xfb3bfb6afd655ae6ULL,
0x78ac670bb09872e9ULL,
0xc9421cf06de78314ULL,
0x5e00b2e645e5746dULL,
0x81b2043cd8c75cb8ULL,
0xea1efdac2c398117ULL,
0x8a11c374d470bae5ULL,
0x699bce65e00ba39aULL,
0x928d82da6ffd2c9bULL,
0xa552ef485a46fff5ULL,
0x991b8d0309cf973eULL,
0x633caa40d664d580ULL,
0x0f736be77d9f0e2bULL,
0xe40ff3861805c6ebULL,
0x8c7955f369d47df3ULL,
0x0d4265df1bf0f827ULL,
0x3ceefeb335415a3bULL,
0x3dbc35cf6953022cULL,
0x917c71a7a7a815f4ULL,
0xb2f6920b08c8791eULL,
0xd0ef38031021254cULL,
0x8742752903030e3cULL,
0xd86881e2358f3a40ULL,
0xa6e08d58a0b9f3b3ULL,
0xb8d816f6f4b3f7f1ULL,
0x6961f1512f97b655ULL,
0x12447979a7ebfbe5ULL,
0x576f2c82b74573aeULL,
0xd007abf004301803ULL,
0xae85f8f7f2111525ULL,
0x779255e2cf447cd5ULL,
0x50f0521f765cc6daULL,
0x014c62efc7c9c81eULL,
0xfabdc986e9e223caULL,
0xcd5caa60470b073bULL,
0x05c44e7c13ba0b36ULL,
0x71b8a5eb8bb7e8b2ULL,
0xf2e57d6814d30b7dULL,
0x54aa7f7850f7d78bULL,
0x637b90e99fcb6504ULL,
0x301b41c51d4d23d6ULL,
0x4b465b1ce62485f9ULL,
0x374b8d0ec7a95b4cULL,
0xdcce91ff642f0573ULL,
0x718af3ecf14c0109ULL,
0x170f9c7b231dcc33ULL,
0x976e6c7875876470ULL,
0x5a8768055da2109cULL,
0x79878676c87620acULL,
0xd95d79e9c4f750a8ULL,
0x6266a937b703e10dULL,
0x674fe9e4aec083ffULL,
0x4306f2ea19d726b1ULL,
0xbf7d1558b729af7aULL,
0x613e7e8da58529f1ULL,
0xc51f148602fa8b41ULL,
0x6b67c0211a66e5bfULL,
0x8e27be5863efa5a4ULL,
0xcec1d624c8c40227ULL,
0x9d9b68e83eca6027ULL,
0xc5c9d87d3464c08fULL,
0x7f20af5a5f1fdc29ULL,
0x620c984d815a4ab7ULL,
0x0b0a250716f806f8ULL,
0x8d87a93c991da4b5ULL,
0x940ee3533e1cb59eULL,
0x2f7456ce13d185f8ULL,
0x84c916a3faa4518aULL,
0x2ef80a3c53a1f414ULL,
0x181c0733db73a989ULL,
0x06f276cbc12066d2ULL,
0x6a500291899efabaULL,
0xa18c99dcfa32c6d9ULL,
0x5ab9b53663dac4acULL,
0x01f9b1d6c895d43dULL,
0x9a853aea902e12e2ULL,
0x7ab5d635419705c3ULL,
0x6c5e0d9d1692f5f3ULL,
0xa404a02315c0acdcULL,
0xbc38bb095bb9c5fdULL,
0x46af30a5e1fc976eULL,
0x5b308704ea30bedaULL,
0xb61b5316ebee0f23ULL,
0x437522342ab99935ULL,
0x986e9ae169e246e8ULL,
0x72d43930f6b53cd0ULL,
0x18f3a2b8519892f6ULL,
0x053533d98cb86036ULL,
0xe9454956050d51a5ULL,
0xaf2b3be059c9eb49ULL,
0xbc6c06ee32cc3f7fULL,
0x21a69b5c544327aaULL,
0xb628e7b725d2e3c6ULL,
0x2951d30f226e2a58ULL,
0x38cf1fbc9d7909a6ULL,
0xe22f8fa9e087904dULL,
0xd61aa563d80a5b1bULL,
0xd705def12ae7387cULL,
0xedf68e4291635dfeULL,
0x1b7736679d0d76dcULL,
0x98aa3342c138f103ULL,
0x5bc1011c7941871dULL,
0x2f346d743362b969ULL,
0x3ca2e680898ee609ULL,
0x403dccfd19a0d0f8ULL,
0x7cc3625c6054e923ULL,
0xd596218937083278ULL,
0x700d1453c5e11423ULL,
0x14d8c0549245a2f9ULL,
0xd27eef2c87eea2fcULL,
0x142952780d4600eaULL,
0x6dc39ac85c3dceaeULL,
0x9bd2b5dc2a9c1a59ULL,
0x049fe1bbd13e7000ULL,
0x2e0e307a7ce62a0cULL,
0x660148ca886f57ddULL,
0x24e671c17a61cbfcULL,
0x7f144642ab1f710eULL,
0x40558e441fef782aULL,
0x837350fd617b45efULL,
0xc73b972bbef72379ULL,
0x4ea3b06acfd97892ULL,
0x569c58183a81cdb5ULL,
0x435cb44ae41fae1eULL,
0xb3c09ea6f9dd56cdULL,
0x3417fec98f12890fULL,
0x35bea0649a08f736ULL,
0xb4aa8a798c03ddd1ULL,
0xeaedf7eda3945610ULL,
0x2ef617f66dcdb05fULL,
0x212eb33c1b359a47ULL,
0x6b88787791d7de64ULL,
0x43a96d4c2ff8b818ULL,
0x64e46a6d375534b9ULL,
0x5c2588c1e64a2345ULL,
0x1bed8935ff24c9a0ULL,
0x9fbd29f3e6e3cf71ULL,
0x5059955a385765d4ULL,
0xffcf225519d9f3feULL,
0xaa7bcae9a84c9c72ULL,
0xe3bd3e177f4a6751ULL,
0xd7d8ea9faede02c5ULL,
0xbc7a263749bd3b2aULL,
0x38d85b8568707a65ULL,
0x7b49f4284c882188ULL,
0x72705e54288a3150ULL,
0xf12be24a17880cb5ULL,
0x5dc218f333f05549ULL,
0x357d6d32784e821eULL,
0x8de3bb4f82aa77bdULL,
0xcf8f4a9bd54d004fULL,
0xa3c602d7af37155cULL,
0x353099b6b95b7173ULL,
0x33729799020793d4ULL,
0x607bf12491fa999bULL,
0xf347d0678506a600ULL,
0xc707a1376e9640f2ULL,
0x8e3cf4693de11d46ULL,
0xdc320664e58450d3ULL,
0x6ce17ed49e00ba31ULL,
0x4dba1bdd4e8bbe47ULL,
0xc67d11535e21b215ULL,
0xaec0fa1f3f8ffb56ULL,
0x07b75b9cb9d4519dULL,
0x075e8f3d69f06256ULL,
0xf18cb61e48f9ca22ULL,
0x9402c2f5defb8048ULL,
0xe6534f4d2f18d6a7ULL,
0x1ebaa699aed2159aULL,
0x71f43397dd6ef186ULL,
0x125b2eddd1987588ULL,
0x09e87c1ed87b2bffULL,
0x8d02cdc9e3585c8cULL,
0x67b8692eb9ccb4c7ULL,
0xa6aaf0bce945ea13ULL,
0xf4fbafcb5ff22f08ULL,
0x8af2ed059e8c992eULL,
0xf940ae1e2b24c64cULL,
0x779ba8d60fa198e1ULL,
0x893732d5b54bb02bULL,
0xb1c82603e5694ffbULL,
0xebb3c99f16dba23cULL,
0x356b436d3a7ba624ULL,
0x7d8ae57d1453794eULL,
0xb539b2d575c70dd8ULL,
0x8dcf2d6e4def8acfULL,
0x11c63ffc3fd3defaULL,
0xbb2f6b1b1eafc9e3ULL,
0x1985f163746ab29bULL,
0x6ea5ce6a2351cf8fULL,
0xc50a13b6b4e024a1ULL,
0x6402723172a9130dULL,
0x3f9d08c059228b7fULL,
0x16100691647d53a7ULL,
0x045aac71e1ce044dULL,
0x65ca0990dbc1983eULL,
0x77553bf7e8d96f05ULL,
0x2bb02fd35d713c46ULL,
0xb911bf0ed215280fULL,
0x15c1e2a5620f5f36ULL,
0xc51c2f14919ce96fULL,
0xb1810c003088920bULL,
0xa636b81c40688f4fULL,
0xe6667f881d8f1092ULL,
0xd4b07fa7d1215914ULL,
0x4658ebb13d7197f2ULL,
0xb6fe1b8ae31505c5ULL,
0xa0bc63bc30f991c0ULL,
0xab6de18a0741e447ULL,
0xfeaebec534ee8a6dULL,
0x68bc23d4ac62ce0fULL,
0xa7da553446f4e532ULL,
0x7c20dbedd894934eULL,
0xa80ea0acd7b2ab82ULL,
0x81f5cda672764701ULL,
0x536a4e47d1ee5bf5ULL,
0xc154d6ddb8d6298aULL,
0x2bf6f400f0118871ULL,
0x08c76f4a7d26e72cULL,
0x6bf79e5605a4af3dULL,
0x6e4bbd7bb208909eULL,
0x173ee7824c1608b9ULL,
0xa1544b6b14ded34fULL,
0xba8753d9e0613db2ULL,
0x6b91332a01d8186bULL,
0xed8d52c9fbff4d38ULL,
0x57b20c3e0f1b0288ULL,
0x96411854e95e7a4aULL,
0x890c907302461006ULL,
0xb3fc881f197f89ccULL,
0x7fdae8088af55610ULL,
0xdbc1cffa7528794dULL,
0xf2fa09044a93cf53ULL,
0x667116e81074f9d7ULL,
0xa7cafcc3ee2b398dULL,
0x1e6943e7ae3fddd0ULL,
0xf4e21ca97d41a661ULL,
0x1935dcfe64916c98ULL,
0x3f4c5af99082c210ULL,
0xbb744ac4cdc12d37ULL,
0x24eba0152fe2f36bULL,
0xf66718cf3c9e6ff4ULL,
0x24ba5c4b0a8fd186ULL,
0x902a814ebc78cbb0ULL,
0xfb54e6afd7677377ULL,
0x3395462cb323dafcULL,
0x1765f64979059089ULL,
0x4f2503711b114ce4ULL,
0x1b2850a9a86db30fULL,
0x0ed33d0703e54b81ULL,
0x59e6911707d9a1e3ULL,
0xe15b68a6fa2dddb3ULL,
0x7d6cb238f25b4ec3ULL,
0x83bd75004f015be4ULL,
0x29d098736ebe7ea9ULL,
0xf7df7c3827638900ULL,
0x2c8392e222782637ULL,
0xaf8507f658939e9bULL,
0x1daeea4ff6332658ULL,
0xd523564746edb11bULL,
0xb44d4164ff8cda55ULL,
0xe9c76e93e2f60bdfULL,
0x004296289d0163bfULL,
0xbcb1c00839246844ULL,
0xba5300e273fc5c86ULL,
0x9f91c9fa91d72febULL,
0xe5bee2fb6e6fdeaaULL,
0x5ce33bb2d7474df8ULL,
0x9999761a31aef55aULL,
0xd09af91e66c718beULL,
0xeabe4ab34b9cd70dULL,
0xeb733d53f5b1d5b8ULL,
0x26ee2cceb9691e80ULL,
0xb81bec7e2de8f781ULL,
0x7e7925c145a6f484ULL,
0x41f2fda8abcf13a5ULL,
0x8217cdc62f8b0dccULL,
0x6ed89e51ddfc7343ULL,
0x9d4ffdd5dcf3b9d3ULL,
0x5b186539f5d4943bULL,
0xe76f6ffd5620ce53ULL,
0xc7b22abde412c37cULL,
0xa96ec0c950b59508ULL,
0x137cbf65b24f4027ULL,
0xfb977aed83e0efefULL,
0x29cc9eefdb0f1943ULL,
0x46d418cb4ff6da58ULL,
0xa654b9d497dd8aacULL,
0x7b522b71b23ccf2bULL,
0xd71887ed8381de65ULL,
0x54df226dfd47d14aULL,
0x60531b3859a2a8ccULL,
0xa6a6103b2372fc42ULL,
0x3c0f2c19ceccd159ULL,
0xf32c645f12397f84ULL,
0x95627043b646e8e3ULL,
0xdbea0fd2793c84b7ULL,
0x379a3b0b0b4e64e8ULL,
0xcecfc440122f2e06ULL,
0xc78e330a77c6d50dULL,
0x32d4abc39e1bfff3ULL,
0xd1672a2f4fc4fbe0ULL,
0x7ca7f9d91a0461d3ULL,
0xdb9f979f25e5fbc4ULL,
0x39be4cf8eb863eefULL,
0x6865fb9352d21828ULL,
0x6061368e4d3958f8ULL,
0xe580eab1009b64edULL,
0x90362dcc34f6659fULL,
0x83687ef60931b711ULL,
0x27e46692eb95ff7bULL,
0xe6840eae1418215aULL,
0x4b627eae25b4f08eULL,
0x9cd44859e2bd104bULL,
0x9b173a39761b1dbcULL,
0x4a329a5510e3c086ULL,
0xf13ccb53cc3907e8ULL,
0xff95257fabca3edcULL,
0xda4b7f1cf1ed9805ULL,
0x3a331c82d2924378ULL,
0x7686df1e66fa9655ULL,
0xb1c4ccc5565019f4ULL,
0x39b1fc9947ff6d37ULL,
0xba82db523c13640dULL,
0x91645d38c420b220ULL,
0xcb1a0a6c79fe9feaULL,
0x667fe176012925f0ULL,
0xf2b8446b585294f5ULL,
0x0691117ae0abb50eULL,
0x5eb6118ca2e62872ULL,
0xc924fbaf71c315dfULL,
0xf842177b71c6f22aULL,
0xc80754b46448ee6aULL,
0x21d3ff566b098e01ULL,
0xb149b5d9a0eee677ULL,
0x9b73429d2da4c233ULL,
0x9f885ddc498851abULL,
0xb22eda7ca1b9784cULL,
0xce09c914771d0ed9ULL,
0xe7139893ede5e68fULL,
0x8a1075b14e9fa79eULL,
0x47f16a5941c7e3c5ULL,
0x900a683d7bf56ee7ULL,
0xbff7f284ac239f94ULL,
0xaa6058650a798c9cULL,
0x66d60ffba7c059acULL,
0xa858d85aa9a0083fULL,
0xc28826779a21e0dfULL,
0x5f35efa1b5fe99d5ULL,
0x2fc8244af685d9b4ULL,
0x09a0108475a964d7ULL,
0x31024f713b9f20bbULL,
0xd970efd90cc18400ULL,
0xd61969558d72253fULL,
0xa78ee57a609e07a5ULL,
0xf2f7827f64199028ULL,
0x52c7eeaf8e3e6e1aULL,
0xd661e5ab6b0e254bULL,
0x3e05b4c701bc2852ULL,
0xd31acb22f296d220ULL,
0x342d8b1f90505e5cULL,
0xfc2348b58fd655a2ULL,
0x5a57c7ce5f310a34ULL,
0xa843c5acaaa2dd7dULL,
0xf7b1f0c5dc5c5a10ULL,
0xf4a1e7100c6c8bbfULL,
0x10faf8e33c1b0090ULL,
0x2881d5f64e455310ULL,
0x261dcd7c8bfedd46ULL,
0xfd423849dcdb645aULL,
0x13402769dc9da361ULL,
0x35832a72d7867b05ULL,
0xc3d4c4727b4c30a1ULL,
0x5b5179801ab877ffULL,
0xfd7d1c8f8702501aULL,
0x94605dfe134fe4beULL,
0x5ed44f84153de6c3ULL,
0x75558925a53502baULL,
0xd0abd43d349ae531ULL,
0x7e5c7ca2048f9fefULL,
0xe7cddce1d99ab42bULL,
0x05827d13bde355d6ULL,
0x01c0593caf195d0fULL,
0xe641a40c5afcee19ULL,
0x4f9b7fd1a856b701ULL,
0xdce3eea6efb1853bULL,
0xe28244e9c4e63acaULL,
0x3ef4b139cb56597dULL,
0x7fac5a181c687422ULL,
0x23ea86e377a1a003ULL,
0x14e089a655b2ce4eULL,
0xe215e3bd72cc0a97ULL,
0xf45af26303d5c581ULL,
0x7777f058896f9a73ULL,
0x99aec0374d142a5fULL,
0x552c8546d98e8584ULL,
0x89728b9d11317b9aULL,
0x7464d56911346f28ULL,
0xb19fc6c46914f6f0ULL,
0x15f4e2350578d40dULL,
0x1ddfb4b328b248efULL,
0x8418c3028fd170f6ULL,
0x25046319c34ed2a3ULL,
0x3e018dac9d47fa1eULL,
0x4f1f19bb2fbc34d5ULL,
0x0fba70b5df282972ULL,
0x02df13f0e30ec8b6ULL,
0xdd92d00049da4df1ULL,
0x49026d77fb069f9dULL,
0xdbaae0696329da50ULL,
0x361ba249c6ef3834ULL,
0x3f8d4469ca3868e3ULL,
0xc3ea9e0ea2008a95ULL,
0xee989a98e0c27f84ULL,
0xcbda49dbf8e7f17dULL,
0x42ed85724d734af3ULL,
0x0216234c8107208cULL,
0x97dc33f37554264bULL,
0x63a275b249f2a36dULL,
0x71db0720516bf741ULL,
0x08e4ecb1fef9519dULL,
0x6029a9fc387d3ebeULL,
0x0a55be6aaac4f34dULL,
0xec75d1821df80754ULL,
0x7a8e9282125cd050ULL,
0x688330ce6f0a95c5ULL,
0xf86a39a8ce48c8c4ULL,
0xf04459ab9abb2122ULL,
0xb848403544a7d883ULL,
0x40870758da58c40bULL,
0x5a4a69d56457824aULL,
0x6350619c1b5fbd00ULL,
0xbe46a30362255ca9ULL,
0x3563642107194153ULL,
0xd4549f6d5548f391ULL,
0x49a74dd8304b99dcULL,
0x8f0ce2b2e9235071ULL,
0x0e2ccf5ded9a8b7bULL,
0xcd987e088c2e0809ULL,
0x85ef9bc7ed0152d6ULL,
0xbe35677eff8341bfULL,
0x28b88cd720f7dd5aULL,
0x17c5479731a406acULL,
0x371ed4c130db5662ULL,
0x3bd87aa02d5ac70aULL,
0xfc01994f7de10985ULL,
0x442c4ac382a5aeb6ULL,
0xa34fa4b48d0c5f2fULL,
0x510400b5b016d4ccULL,
0x3b689912720d376dULL,
0x9ec6ea60cf14e2c4ULL,
0xd044145163329affULL,
0x0117185d6b9486acULL,
0x5573ea7a7aa8498aULL,
0x952bd0abd1044727ULL,
0x0f17a52dd8c101cbULL,
0x78b50fccf5c59e79ULL,
0xabacefe6dfe40ea9ULL,
0xca57246ba322697aULL,
0x5fd7df6eb1988ac8ULL,
0x3789eefa5041b684ULL,
0x5ede25e031ab43dcULL,
0x95819a9854f69430ULL,
0x33e3ed56011a727eULL,
0xef113c7fc6ae83a7ULL,
0x33fddf7b3a32eb42ULL,
0xa30cde8d9d71ddebULL,
0xfe60cc7fe3f32cf2ULL,
0x817692be4c6d02c0ULL,
0xfe5609a2f815b73eULL,
0x6d22f1de40a7ee20ULL,
0x77ce3eca9ab12b57ULL,
0x89cd08b7a9b89852ULL,
0x4c2a4a065c147fecULL,
0xce1b2ec486f59d8fULL,
0x0eceda66be6bc4aaULL,
0x7c7732a3c728fc77ULL,
0x1f6b965b48ce8947ULL,
0x11ecc7bc40cf72dfULL,
0x0cdbb71074783cdcULL,
0x6b71e2b1b20073c1ULL,
0x4660e9846cdb6d96ULL,
0xe5f2b31a4a1a3362ULL,
0x20a0b2f0cf3f4f4aULL,
0xef6aa63353c396edULL,
0xa5a596009f79a04dULL,
0x58f772dcd6d17555ULL,
0x7957ccbb31af0b61ULL,
0xb78429d6762f68b7ULL,
0x5d56c1985fe7a77aULL,
0xa7c39cbaeedbcf38ULL,
0x65995fc6feda19dbULL,
0x86bd2842e58c1abfULL,
0x6b8f580e7f95a512ULL,
0x04702eee85556f24ULL,
0x7d03323b15770702ULL,
0x7142db6082e23f0eULL,
0xa7187369f53d799bULL,
0x33ac09c9ef8b5011ULL,
0xa7215e563a441b86ULL,
0x719d08af2d6bbe27ULL,
0x411169b3cc4d2938ULL,
0xac27a7a1de0b5506ULL,
0x6a22863807d7a858ULL,
0x39ee2d2990d69bd2ULL,
0xa4532bde73a403f0ULL,
0x93140026ce0f907fULL,
0x3ee28286b7fb6bd9ULL,
0x9a764f034f6612c3ULL,
0x64a2aebf4bcc603eULL,
0xe3a52379d46f760dULL,
0x177bffaf24689dabULL,
0x50cae3da45597fe0ULL,
0x20965d5b98702278ULL,
0x2216f521a928cc88ULL,
0x66abbd80b4225632ULL,
0x4deb85d7906c2b68ULL,
0x086c679450374d70ULL,
0xda4dcd508b82c799ULL,
0x10d7894a856495d7ULL,
0x0da56c0076c24fbaULL,
0x0e326b797a477812ULL,
0xef6bd63cc63df6c4ULL,
0x79bc5723426d1f76ULL,
0xb75d3b456282beb3ULL,
0xae6e33cfa8828989ULL,
0x6ab76312f343be84ULL,
0xdc8f5b9ac09ecab9ULL,
0x431d138d0462179eULL,
0x52ef096bb35e1c0dULL,
0xf66a0311c0456476ULL,
0x096d359977f58b8eULL,
0xfe552ed33c46d0fbULL,
0x30de400c07364d98ULL,
0xb7b1f521b2cffd09ULL,
0x1ff582472dd69760ULL,
0x269542702e92e3a8ULL,
0x74cc87913e8fc54dULL,
0xfb2690d45bcc2646ULL,
0xc0d6a127b1e95606ULL,
0xa5fb89708bb60bddULL,
0x32c3cbfd9af652f4ULL,
0xe693fa7b4c6820d5ULL,
0x14183f649e3488f4ULL,
0x2a493ed4e84d01e9ULL,
0x5033458942015a8bULL,
0x08e7eafa81e22990ULL,
0xe61a4c18db1aa3d6ULL,
0xe884ae998f479eb4ULL
&#125;;
unsigned long long zobvalh23&#40;unsigned i&#41;
&#123;
return ham23bit&#91;i % 999&#93;;
&#125;

#ifdef UNIT_TEST
#include <stdio.h>
int             main&#40;void&#41;
&#123;
unsigned        index;
for &#40;index = 0; index < 2000; index++)
printf&#40;"zobvalh23&#40;%u&#41;=%llu\n", index, zobvalh23&#40;index&#41;);
return 0;
&#125;
#endif
But tests show that there is not much of a real benefit over a simple table generated with MT

Code: Select all

class Rand64 &#123;
private&#58;
uint64 box&#91;65536&#93;;
int size;

inline uint64 block&#40;)
&#123;
if &#40;size < 2&#41;
size = 65535;
swap&#40;box&#91;rand&#40;) % size&#93;, box&#91;size&#93;);
size--;
return box&#91;size + 1&#93;;
&#125;
public&#58;
Rand64&#40;)
&#123;
size = 65535;
for &#40;int i = 0; i < 65536; i++)
box&#91;i&#93; = i;
srand&#40;time&#40;NULL&#41;);
&#125;
uint64 next&#40;)
&#123;
uint64 val = 0;

for &#40;int i = 0; i < 4; i++)
val |= block&#40;) << &#40;16 * i&#41;;
return val;
&#125;
&#125;;

jdm64
Posts: 41
Joined: Thu May 27, 2010 9:32 pm

### Re: Transposition table random numbers

bob wrote:
Note: By low bits, I mean the bits that are used to determine the table index for a specific hash. If the table's size is 2^22 then the lower 19 bits of the hash will be the same as the table's index. Right?
Assuming you have an 8 byte hash entry which seems way small..
I guess I didn't explain right. When you look up a hash X you do: X%table-size. If table-size is a power of 2 then the resulting index into the table will be the same bit pattern as the lower Y bits of the hash, where Y is the number of bits needed to represent the largest table index. So, for a 64bit hash and a 2^22 sized table, the lower 19 bits of a hash will be the index of the table to find that entry if it's there.

Now my question is: for the array of 769 random numbers used to update the current board's hash, should all of the lower bit fore each number be unique (and upper bits)? Because if two values used to update/xor have the same lower bits, then the new hash will overwrite the last used table item (if there wasn't a capture). I want to limit this from happening and that's what my rng tried to do.

Say a pawn on b2 moves to b3 then to update the current hash for this move:

current_hash ^ hashbox[pawn on b2] ^ hashbox[pawn on b3]

But if the lower bits for hashbox[pawn on b2] and hashbox[pawn on b3] are the same then the table index of the trans-table will be the same.

jdm64
Posts: 41
Joined: Thu May 27, 2010 9:32 pm

### Re: Transposition table random numbers

Dann Corbit wrote:
Note: By low bits, I mean the bits that are used to determine the table index for a specific hash. If the table's size is 2^22 then the lower 19 bits of the hash will be the same as the table's index. Right?
You don't need such a large table of random numbers. Examine a few working Zobrist hashing schemes in existing programs to get an idea of how it is done. It is possible to maximize hamming distance with an algorithm like this:
No, I don't generate 2^22 random number -- only 769. Doesn't Zobrist hashing work like this:

There's a random 64 bit hash for each piece type for each square and for color to move. Therefore the array of random numbers is 769 in size. Then to update the current board position's hash for a move, you xor what changed.

But my question is shouldn't the random numbers be unique in such a way that the lower and upper bits are unique for each and every random number. You'd want to limit the following from happening:

current_hash ^ hashbox[Y] ^ hashbox[Z] == current_hash

(See my previous post where I try to explain what I mean by lower/upper bits)

Dann Corbit
Posts: 9280
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

### Re: Transposition table random numbers

jdm64 wrote:
Dann Corbit wrote:
Note: By low bits, I mean the bits that are used to determine the table index for a specific hash. If the table's size is 2^22 then the lower 19 bits of the hash will be the same as the table's index. Right?
You don't need such a large table of random numbers. Examine a few working Zobrist hashing schemes in existing programs to get an idea of how it is done. It is possible to maximize hamming distance with an algorithm like this:
No, I don't generate 2^22 random number -- only 769. Doesn't Zobrist hashing work like this:

There's a random 64 bit hash for each piece type for each square and for color to move. Therefore the array of random numbers is 769 in size. Then to update the current board position's hash for a move, you xor what changed.

But my question is shouldn't the random numbers be unique in such a way that the lower and upper bits are unique for each and every random number. You'd want to limit the following from happening:

current_hash ^ hashbox[Y] ^ hashbox[Z] == current_hash

(See my previous post where I try to explain what I mean by lower/upper bits)
OK, you have the general approach right.

As for the upper/lower bits being unique -- it is not generally achievable to have perfect hash collision avoidance, because your table entries will be the result of many consecutive xor operations. That is the main idea of using maximal hamming distance, but it turns out that in practice if you use a good PRNG like MT, the benefit is so small it is difficult to measure it.

A bad prng, on the other hand, will stick out like a sore thumb (there are some POSIX variants that have very bad randomness in the low order bits, for instance). So don't use the library rand() function.

Dann Corbit
Posts: 9280
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

### Re: Transposition table random numbers

jdm64 wrote:
bob wrote:
Note: By low bits, I mean the bits that are used to determine the table index for a specific hash. If the table's size is 2^22 then the lower 19 bits of the hash will be the same as the table's index. Right?
Assuming you have an 8 byte hash entry which seems way small..
I guess I didn't explain right. When you look up a hash X you do: X%table-size. If table-size is a power of 2 then the resulting index into the table will be the same bit pattern as the lower Y bits of the hash, where Y is the number of bits needed to represent the largest table index. So, for a 64bit hash and a 2^22 sized table, the lower 19 bits of a hash will be the index of the table to find that entry if it's there.

Now my question is: for the array of 769 random numbers used to update the current board's hash, should all of the lower bit fore each number be unique (and upper bits)? Because if two values used to update/xor have the same lower bits, then the new hash will overwrite the last used table item (if there wasn't a capture). I want to limit this from happening and that's what my rng tried to do.

Say a pawn on b2 moves to b3 then to update the current hash for this move:

current_hash ^ hashbox[pawn on b2] ^ hashbox[pawn on b3]

But if the lower bits for hashbox[pawn on b2] and hashbox[pawn on b3] are the same then the table index of the trans-table will be the same.
The probability that all 19 bits are identical is one in 2^20 -1 =1/1048575 about one in a million. I did not examine my table for small hash table sizes, but I guess that none of the entries will collide even with only 19 bits.
Easy to test it, of course, by simply masking and doing a nested loop xor or comparison (equivalent tests).

Milos
Posts: 3270
Joined: Wed Nov 25, 2009 12:47 am

### Re: Transposition table random numbers

Dann Corbit wrote: Use the Mersenne Twister.
http://www.math.sci.hiroshima-u.ac.jp/~ ... T/emt.html
The funny thing is, Ippo has on a first look a very weak and stupid rnd generator. However, I tested it thoroughly against MT with a default seed (the one SF uses too), and MT was always worse...

Dann Corbit
Posts: 9280
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

### Re: Transposition table random numbers

Dann Corbit wrote:
jdm64 wrote:
bob wrote:
Note: By low bits, I mean the bits that are used to determine the table index for a specific hash. If the table's size is 2^22 then the lower 19 bits of the hash will be the same as the table's index. Right?
Assuming you have an 8 byte hash entry which seems way small..
I guess I didn't explain right. When you look up a hash X you do: X%table-size. If table-size is a power of 2 then the resulting index into the table will be the same bit pattern as the lower Y bits of the hash, where Y is the number of bits needed to represent the largest table index. So, for a 64bit hash and a 2^22 sized table, the lower 19 bits of a hash will be the index of the table to find that entry if it's there.

Now my question is: for the array of 769 random numbers used to update the current board's hash, should all of the lower bit fore each number be unique (and upper bits)? Because if two values used to update/xor have the same lower bits, then the new hash will overwrite the last used table item (if there wasn't a capture). I want to limit this from happening and that's what my rng tried to do.

Say a pawn on b2 moves to b3 then to update the current hash for this move:

current_hash ^ hashbox[pawn on b2] ^ hashbox[pawn on b3]

But if the lower bits for hashbox[pawn on b2] and hashbox[pawn on b3] are the same then the table index of the trans-table will be the same.
The probability that all 19 bits are identical is one in 2^20 -1 =1/1048575 about one in a million. I did not examine my table for small hash table sizes, but I guess that none of the entries will collide even with only 19 bits.
Easy to test it, of course, by simply masking and doing a nested loop xor or comparison (equivalent tests).
Turns out (due to the birthday paradox) collisions are a lot more likely than I thought. However, simply choosing values with identical lower bits probably won't help. If there were a single xor to create the key, then it would make perfect sense. I guess that there is no easy solution but that a simple table will work well in most cases. I have a collision already at bit 48, which I found a little surprising. Perhaps the operation of maximizing hamming distance exacerbates the problem, which would explain why it does not seem to produce superior hashing.

Code: Select all

#include <stdlib.h>
#include <stdio.h>

static unsigned long long ham23bit&#91;999&#93; = &#123;
0x64d79b552a559d7fULL,
0x44a572665a6ee240ULL,
0xeb2bf6dc3d72135cULL,
0xe3836981f9f82ea0ULL,
0x43a38212350ee392ULL,
0xce77502bffcacf8bULL,
0x5d8a82d90126f0e7ULL,
0xc0510c6f402c1e3cULL,
0x48d895bf8b69f77bULL,
0x1126b97be8c91ce2ULL,
0xf05e1c9dc2674be2ULL,
0xe4d5327a12874c1eULL,
0xbba2bbfbecbc239aULL,
0xc5704350b17f0215ULL,
0x823a67c5f88337e7ULL,
0x9fbe3cfcd1f08059ULL,
0xdc29309412e352b9ULL,
0x5a0ff7908b1b3c57ULL,
0x46f39cb43b126c55ULL,
0x9648168491f3b126ULL,
0xdd3e72538fd39a1cULL,
0x0348399b7d2b8428ULL,
0xcf36d95eae514f52ULL,
0x7b9231d5308d7534ULL,
0xb225e28cfc5aa663ULL,
0xa833f6d5c72448a4ULL,
0xdaa565f5815de899ULL,
0xef6a48be001729c7ULL,
0xfdc570ba2fe979fbULL,
0xb57697121dfdfe93ULL,
0xb313b667a4d999d6ULL,
0x07c7fa1bd6fd7deaULL,
0x0ee9f4c15c57e92aULL,
0xc5fb71b8f4bf5f56ULL,
0xa251f93a4b335492ULL,
0xb2f0624214f522a2ULL,
0x22d91b683f251121ULL,
0x3462898a2ae7b001ULL,
0x468bc3a10a34890cULL,
0x84ff6ce56552b185ULL,
0xed95ff232c511188ULL,
0x4869be47a8137c83ULL,
0x97f3a778e242d0cfULL,
0xd870d281b293af3dULL,
0xc3a5f903a836fafdULL,
0x4e38ddc2719162a5ULL,
0xb75b43fb4c81784aULL,
0x562f36fae610a2e1ULL,
0x0e0e413e555bd736ULL,
0xd452549efe08402dULL,
0x0d84c9a356858060ULL,
0x19d5b3643bc029b6ULL,
0x0dd8131e97ffc842ULL,
0xf98c6d63ff48a16eULL,
0x83490ef054537f7eULL,
0xe071f833e55ebfe6ULL,
0xdae6e879b8eab74aULL,
0xe4a41f17e70d3e0aULL,
0xbc1abca3fbeeb2f3ULL,
0x5e37299d89089ba4ULL,
0xa1f735eb8235b32fULL,
0x2289d719e7b146eeULL,
0x1c9c9d0284d96719ULL,
0x317e34c009a07a39ULL,
0x5f45053666f3f84fULL,
0x63e7074f03c73d92ULL,
0x9643b3707db2cfb5ULL,
0x98e2db6c665e7178ULL,
0x36e7ac11d1f3a617ULL,
0x508f0acb609bd756ULL,
0x6f42d435193a1ac2ULL,
0x2df2cab9d65e0b00ULL,
0xc80d5b04f6337337ULL,
0x5d33cf557e6c4475ULL,
0x05b5a78be74ccd40ULL,
0x3ec2cce5290785f4ULL,
0x2eef1e9c4b36828bULL,
0x7ff345b4eb7f3639ULL,
0xa15f9c2826cb34dbULL,
0xc1cdaa5f9ca79b19ULL,
0x5094cafab11cbc3aULL,
0x94d40a57481346b5ULL,
0x0d493e410b68b6c6ULL,
0x71c1b0ba9e52a2deULL,
0xa7448d0059484568ULL,
0x2819237e5e8cb03aULL,
0x91e060fb399ecf2cULL,
0x5e650b9a3cb34308ULL,
0xe482d24e5b239833ULL,
0x52ed7d9f45c6b578ULL,
0x332f7ce3e077ecceULL,
0x5b057c64bda94a33ULL,
0xe974ffd57219e5e6ULL,
0x6750ecdf35c8471bULL,
0x2c6983c911c958afULL,
0x3220a56d67450e80ULL,
0xfd8137f8b59bd084ULL,
0x167cc7f46a511504ULL,
0x36374630d0ecb4e8ULL,
0x501337e1a7f1e218ULL,
0x589b8eaea60d54a4ULL,
0x8f1a8c1b84b3ba62ULL,
0xf69ffb64131633aeULL,
0xa837ae34963616fbULL,
0x11753aea03bb0ecdULL,
0x32d9cca610dceb34ULL,
0x94c1190da321d470ULL,
0x321e26bf321fb60bULL,
0xc9202ac8ba71c873ULL,
0x284d02d7552a3e90ULL,
0xa6e86f7ba2779a5cULL,
0x8f675048b7b012e5ULL,
0xe5e469aac68eaf1dULL,
0xc5967cdf353aeac6ULL,
0x59926f3401f437d4ULL,
0xfb49ab0635d66c3aULL,
0x316558d69efc8f6bULL,
0xfa9f65d2b4848b12ULL,
0x2b92665a263a5091ULL,
0x4171d5edd5468876ULL,
0x99bb4bf79b0a46c1ULL,
0x939ed8b0d7e91f87ULL,
0x8cb11929a65b6aeeULL,
0xbe6415659e12c64bULL,
0xbf2f4f23a6c92295ULL,
0x7890bc68793bb959ULL,
0x2a060f45a1719347ULL,
0x374635e7713ed165ULL,
0xbfb945ef1cf94d1dULL,
0x4b7519cb9028ac83ULL,
0x0301a07c84aaccdbULL,
0x93dee719932225a3ULL,
0x1528080b61f54198ULL,
0x2fc96b31dccafd9fULL,
0xe9fb2e3998d16a25ULL,
0xd5340e98fde806deULL,
0xc742bc0d0c55f125ULL,
0x3a9fa27258257e53ULL,
0xc12dc512aedc530cULL,
0xc8db824276c083ceULL,
0xb3c98071a3d13b20ULL,
0x679e0601953d1e31ULL,
0x96fc350ccdb76eabULL,
0x9fa0178362df447bULL,
0x451717a061972d1fULL,
0x0bbcbdae779cfbf3ULL,
0x7e2e9ef35a5aafbaULL,
0x68f4654bcc07435bULL,
0x30c6e14df59f8cefULL,
0xcfe629aa56717e20ULL,
0xfde48d87e844ec93ULL,
0x7c9d88364238519fULL,
0xe4ec475d296a69e5ULL,
0xf2ebc493b909d8c7ULL,
0x13834d3d0e43ab73ULL,
0x2dc12f9f04435661ULL,
0x563de834c4e56a46ULL,
0x9ec02036a6688a24ULL,
0x9847468f925dc38cULL,
0x8b0e5dca588e3f50ULL,
0x82337b3f1764851cULL,
0xd4166b32a26fc1c6ULL,
0x43e20045bcb06b0eULL,
0x3f58d1d6cd3aa0dcULL,
0xaf3d8a578b6d6232ULL,
0x762c21058ba50349ULL,
0x275d24c9aa1607f0ULL,
0x49efeab6642e9e45ULL,
0x791c96a57ea29814ULL,
0x18e883239eac0617ULL,
0x0ba51d62eb24045eULL,
0x98b487f3146aa174ULL,
0xcda6a4dccb6b73c9ULL,
0x9d66a7aa1fb4595cULL,
0xe221af6f18e45563ULL,
0x6e2c7411e8736390ULL,
0xacedd32f47936b61ULL,
0x7778b73e852e4d15ULL,
0x48ab18694d85497dULL,
0xbd7b6156c2c63188ULL,
0xb193700fe9937383ULL,
0x323beb9061b5af38ULL,
0x617864f443ee06a2ULL,
0x58faf5e64a26fbceULL,
0xa1210472d9abf2e6ULL,
0xb0880848c6f0ec2dULL,
0x0d5d48f4beaf279cULL,
0x98598e0027505d41ULL,
0xc6a8c29b036a0730ULL,
0x083dd247f0a9dfcdULL,
0x186a5d13e79a2806ULL,
0x889e7426b755fcc9ULL,
0x684fca18cc613bcbULL,
0x60dccc0ded809744ULL,
0x246a423aef3f89bfULL,
0x980cfc250f276150ULL,
0x9583176b78273ec5ULL,
0xd857f34b29fba06dULL,
0xc22ea4dbd5d4eb3dULL,
0x39846bce19845617ULL,
0x253f6c2acb91153cULL,
0xc4b501b09381f7dfULL,
0x8afdedfde82b6a2cULL,
0xc262732b5299fcc7ULL,
0x206ed744bef46053ULL,
0xed519f24bba3b7a0ULL,
0x86a9224fd39784e2ULL,
0xec32155b844684ccULL,
0x5038fe125722e26bULL,
0xc80c1dcc2a85da0eULL,
0xff6afaec984bb0bdULL,
0xbe81f9c9474c967fULL,
0xc2fb0f16bcbf30ceULL,
0xb5a94fce85369b23ULL,
0x83b09f892f3e7604ULL,
0x9d5cdb2eae76bc17ULL,
0x21be002177dac1fdULL,
0xb49075e6473925a9ULL,
0xf3f148c32f156c69ULL,
0x5c3c106d732d31a4ULL,
0x5b15d80b4950f0c6ULL,
0x4dee63522a811783ULL,
0x4fd8a3e8ff9268e9ULL,
0x1b67eb44e4c05609ULL,
0x2786afb08475eb89ULL,
0xf470219ba4d19b6bULL,
0x1bea4e946fcdfe80ULL,
0x21ebf22282a74064ULL,
0x041b669aa8caba7fULL,
0x89247e3e8fdac4e5ULL,
0xafe9ec5185000ccaULL,
0x353687e6f2b91aa7ULL,
0x0c04d510680657cfULL,
0x25cfd0ff7b4e767dULL,
0xfe110bb08b44a041ULL,
0xf91423aa2c286f94ULL,
0x5cc6b88d98a3cec1ULL,
0xbb59dedb371cb2a8ULL,
0x82c93115f2862155ULL,
0x53d0184675025da2ULL,
0x5b9eee674ed934bfULL,
0xd3481a6a879631d9ULL,
0x25df42a65e516091ULL,
0x300d5fc62140a89dULL,
0x9d613cdcdc06d7ecULL,
0xdf64f2c261780baeULL,
0xdc48e5079b7f1c6cULL,
0xbf20c573c7a4df16ULL,
0xb5f64fb1ef328cf0ULL,
0x01584766a000e46aULL,
0x9b1c4f7c166c5a18ULL,
0x0856ebd04bdcc953ULL,
0xeec423c4c81e3c65ULL,
0x0fe110a084141f59ULL,
0x5967b4bca28de312ULL,
0xb2e534fb4bc88391ULL,
0x174b91a8d27f409dULL,
0xf3a2dcd21bae4919ULL,
0xfe9f0b07bc28fd49ULL,
0x28470bfae915dec0ULL,
0x3ea221f3823327c4ULL,
0x640a0c676fb84d62ULL,
0xc2ca5337c9c10bd8ULL,
0x511eb890eb7efd2dULL,
0x782a77e63fc78d26ULL,
0xf7edd3abf0e8e8f4ULL,
0x3b14009bfec4fe60ULL,
0x54f5cebbdc8233a7ULL,
0x7f436eedfce43d10ULL,
0x40324ba22633147dULL,
0x8fd5c6f5d0bcc55eULL,
0x2bdcc1f030155a8eULL,
0x383062bfe3e25f19ULL,
0x7fb4e21fbd34a1fbULL,
0x8e2b3dbd42592403ULL,
0x3c95d093014fd9a8ULL,
0x6dd44c0c40febc8eULL,
0xc36dbbfedbf0e58eULL,
0xc0cfc583ea53a434ULL,
0xae44808c64eb123aULL,
0xfa465d1b01b5cd5fULL,
0x04b8be3720801be0ULL,
0xc0b2b846debda795ULL,
0x028966b957f2d943ULL,
0x8e9a964ff958a52dULL,
0x1ea371479081823fULL,
0x37b972dc22085d4dULL,
0x2e68b99e9ef515d7ULL,
0x2f72680378b2a5c2ULL,
0xfc2905d06898087cULL,
0xe97f7c71538c3917ULL,
0x2ab0db47d30ce099ULL,
0x773ef31c6d8dd7deULL,
0xc02c9b3249cabe35ULL,
0x6f5ee092d2b4202fULL,
0x88b5d75a341d1b63ULL,
0x8bbda8c0b3d73454ULL,
0x54d345222cc99eb0ULL,
0xfa9f84bc9bb56568ULL,
0x55d976319b868ed3ULL,
0x1d36070524abe9a8ULL,
0x12a6f3abdf519328ULL,
0xa21c99d12d00f952ULL,
0x4d6ff19d2d5064a8ULL,
0x0088e1003aa37e58ULL,
0x45a814ba1e6c9dedULL,
0xa49d950f7036dbb6ULL,
0xf556015fdf981992ULL,
0xf085743caa263407ULL,
0xcaf8222921640c9fULL,
0x7fa3140a9bb6be2eULL,
0xdc97dd7f8d25782bULL,
0x16173088784c1512ULL,
0xa4679275d2886afaULL,
0x1b52227e4ae5c5f6ULL,
0x6ac8777364a88ce1ULL,
0xa7522287d967ca68ULL,
0x19a9babd3fa1372cULL,
0x483a9fa995b8246aULL,
0xc25981e52898a6d1ULL,
0x46b3c54157aabff9ULL,
0x60372062a09ed423ULL,
0xcc80a989bd16c50aULL,
0x2a0597379ceb6f68ULL,
0xd96a252c2832036bULL,
0x44ee5ef1085c4e46ULL,
0x8655f3d016ea7481ULL,
0x4feebc1d03bd18bcULL,
0x35516b89f62115ceULL,
0x077a7910033cd348ULL,
0xe84a7bd3942b4afeULL,
0x4291838cddff05e5ULL,
0xf3395f4106d0c9aaULL,
0x3d2638ef1e7dd291ULL,
0x03c8c0425f3cfd57ULL,
0xc3ecd3942b828c6aULL,
0x5697ec8f7061e039ULL,
0xa1125e97c0949443ULL,
0x724240d826a9e69eULL,
0x2bff996618bb1707ULL,
0x2325d5954abdf8aaULL,
0x4bd95041860bd223ULL,
0x3b83eeb633e90c5eULL,
0xa18a1355045cde9dULL,
0xe49f18748ccb126cULL,
0x1660b4f6be263d3aULL,
0xd2f039d1584b1ec9ULL,
0xd1a64b151227fc11ULL,
0x0d7f99664658ca3cULL,
0x6f43f28f8d861cffULL,
0xa001cf0254be48c0ULL,
0xbc4c786ce164979aULL,
0xbd825980239dbbe6ULL,
0x8206c8ba22545bf9ULL,
0x0465490d1c862c49ULL,
0x58853b160b2ba6baULL,
0xcbf1b48304af80d8ULL,
0x287e840a5e8f4ee5ULL,
0xced5e028693dd7e9ULL,
0x03b185dea61025a7ULL,
0x6c197485b66de765ULL,
0x80bcbc406ae28883ULL,
0x32a438b70d14ccb6ULL,
0x79043354469a6b79ULL,
0x3875887c6f5fe087ULL,
0xda7a809e5c7a7c7bULL,
0x0c7b1c4ca0bcecf9ULL,
0xb1b035313ee4426eULL,
0x7278cde1d73f131cULL,
0xca351728d35427b2ULL,
0xfa24e4426ccd7ff8ULL,
0xf9b9182557579b09ULL,
0x597b231ff002c810ULL,
0x34ae7a2231de2d51ULL,
0x6a64af267b4e58d4ULL,
0x139bc5479df6c28bULL,
0xf63cc0a137236e93ULL,
0xb3a8222c7c673956ULL,
0x4f861e21c38af8cdULL,
0xf51fcaeabbf1964bULL,
0x26ef5b820f623976ULL,
0x0538d9e87f42b598ULL,
0x8be647a7bc1a78b7ULL,
0xc38a9550f67b91e2ULL,
0xf8fb954dbe4e3fc3ULL,
0xd7b8dce4ec0fcd47ULL,
0xc5d924c6637d605eULL,
0xbb04c18180e60ba5ULL,
0x07c5c78a9b0933d0ULL,
0xdbd343e7475abf56ULL,
0xf5f7ca0573fb50c0ULL,
0x981d24edcd8a0d61ULL,
0xcc388efa7e34ab07ULL,
0xce2344937335b360ULL,
0xfb3bfb6afd655ae6ULL,
0x78ac670bb09872e9ULL,
0xc9421cf06de78314ULL,
0x5e00b2e645e5746dULL,
0x81b2043cd8c75cb8ULL,
0xea1efdac2c398117ULL,
0x8a11c374d470bae5ULL,
0x699bce65e00ba39aULL,
0x928d82da6ffd2c9bULL,
0xa552ef485a46fff5ULL,
0x991b8d0309cf973eULL,
0x633caa40d664d580ULL,
0x0f736be77d9f0e2bULL,
0xe40ff3861805c6ebULL,
0x8c7955f369d47df3ULL,
0x0d4265df1bf0f827ULL,
0x3ceefeb335415a3bULL,
0x3dbc35cf6953022cULL,
0x917c71a7a7a815f4ULL,
0xb2f6920b08c8791eULL,
0xd0ef38031021254cULL,
0x8742752903030e3cULL,
0xd86881e2358f3a40ULL,
0xa6e08d58a0b9f3b3ULL,
0xb8d816f6f4b3f7f1ULL,
0x6961f1512f97b655ULL,
0x12447979a7ebfbe5ULL,
0x576f2c82b74573aeULL,
0xd007abf004301803ULL,
0xae85f8f7f2111525ULL,
0x779255e2cf447cd5ULL,
0x50f0521f765cc6daULL,
0x014c62efc7c9c81eULL,
0xfabdc986e9e223caULL,
0xcd5caa60470b073bULL,
0x05c44e7c13ba0b36ULL,
0x71b8a5eb8bb7e8b2ULL,
0xf2e57d6814d30b7dULL,
0x54aa7f7850f7d78bULL,
0x637b90e99fcb6504ULL,
0x301b41c51d4d23d6ULL,
0x4b465b1ce62485f9ULL,
0x374b8d0ec7a95b4cULL,
0xdcce91ff642f0573ULL,
0x718af3ecf14c0109ULL,
0x170f9c7b231dcc33ULL,
0x976e6c7875876470ULL,
0x5a8768055da2109cULL,
0x79878676c87620acULL,
0xd95d79e9c4f750a8ULL,
0x6266a937b703e10dULL,
0x674fe9e4aec083ffULL,
0x4306f2ea19d726b1ULL,
0xbf7d1558b729af7aULL,
0x613e7e8da58529f1ULL,
0xc51f148602fa8b41ULL,
0x6b67c0211a66e5bfULL,
0x8e27be5863efa5a4ULL,
0xcec1d624c8c40227ULL,
0x9d9b68e83eca6027ULL,
0xc5c9d87d3464c08fULL,
0x7f20af5a5f1fdc29ULL,
0x620c984d815a4ab7ULL,
0x0b0a250716f806f8ULL,
0x8d87a93c991da4b5ULL,
0x940ee3533e1cb59eULL,
0x2f7456ce13d185f8ULL,
0x84c916a3faa4518aULL,
0x2ef80a3c53a1f414ULL,
0x181c0733db73a989ULL,
0x06f276cbc12066d2ULL,
0x6a500291899efabaULL,
0xa18c99dcfa32c6d9ULL,
0x5ab9b53663dac4acULL,
0x01f9b1d6c895d43dULL,
0x9a853aea902e12e2ULL,
0x7ab5d635419705c3ULL,
0x6c5e0d9d1692f5f3ULL,
0xa404a02315c0acdcULL,
0xbc38bb095bb9c5fdULL,
0x46af30a5e1fc976eULL,
0x5b308704ea30bedaULL,
0xb61b5316ebee0f23ULL,
0x437522342ab99935ULL,
0x986e9ae169e246e8ULL,
0x72d43930f6b53cd0ULL,
0x18f3a2b8519892f6ULL,
0x053533d98cb86036ULL,
0xe9454956050d51a5ULL,
0xaf2b3be059c9eb49ULL,
0xbc6c06ee32cc3f7fULL,
0x21a69b5c544327aaULL,
0xb628e7b725d2e3c6ULL,
0x2951d30f226e2a58ULL,
0x38cf1fbc9d7909a6ULL,
0xe22f8fa9e087904dULL,
0xd61aa563d80a5b1bULL,
0xd705def12ae7387cULL,
0xedf68e4291635dfeULL,
0x1b7736679d0d76dcULL,
0x98aa3342c138f103ULL,
0x5bc1011c7941871dULL,
0x2f346d743362b969ULL,
0x3ca2e680898ee609ULL,
0x403dccfd19a0d0f8ULL,
0x7cc3625c6054e923ULL,
0xd596218937083278ULL,
0x700d1453c5e11423ULL,
0x14d8c0549245a2f9ULL,
0xd27eef2c87eea2fcULL,
0x142952780d4600eaULL,
0x6dc39ac85c3dceaeULL,
0x9bd2b5dc2a9c1a59ULL,
0x049fe1bbd13e7000ULL,
0x2e0e307a7ce62a0cULL,
0x660148ca886f57ddULL,
0x24e671c17a61cbfcULL,
0x7f144642ab1f710eULL,
0x40558e441fef782aULL,
0x837350fd617b45efULL,
0xc73b972bbef72379ULL,
0x4ea3b06acfd97892ULL,
0x569c58183a81cdb5ULL,
0x435cb44ae41fae1eULL,
0xb3c09ea6f9dd56cdULL,
0x3417fec98f12890fULL,
0x35bea0649a08f736ULL,
0xb4aa8a798c03ddd1ULL,
0xeaedf7eda3945610ULL,
0x2ef617f66dcdb05fULL,
0x212eb33c1b359a47ULL,
0x6b88787791d7de64ULL,
0x43a96d4c2ff8b818ULL,
0x64e46a6d375534b9ULL,
0x5c2588c1e64a2345ULL,
0x1bed8935ff24c9a0ULL,
0x9fbd29f3e6e3cf71ULL,
0x5059955a385765d4ULL,
0xffcf225519d9f3feULL,
0xaa7bcae9a84c9c72ULL,
0xe3bd3e177f4a6751ULL,
0xd7d8ea9faede02c5ULL,
0xbc7a263749bd3b2aULL,
0x38d85b8568707a65ULL,
0x7b49f4284c882188ULL,
0x72705e54288a3150ULL,
0xf12be24a17880cb5ULL,
0x5dc218f333f05549ULL,
0x357d6d32784e821eULL,
0x8de3bb4f82aa77bdULL,
0xcf8f4a9bd54d004fULL,
0xa3c602d7af37155cULL,
0x353099b6b95b7173ULL,
0x33729799020793d4ULL,
0x607bf12491fa999bULL,
0xf347d0678506a600ULL,
0xc707a1376e9640f2ULL,
0x8e3cf4693de11d46ULL,
0xdc320664e58450d3ULL,
0x6ce17ed49e00ba31ULL,
0x4dba1bdd4e8bbe47ULL,
0xc67d11535e21b215ULL,
0xaec0fa1f3f8ffb56ULL,
0x07b75b9cb9d4519dULL,
0x075e8f3d69f06256ULL,
0xf18cb61e48f9ca22ULL,
0x9402c2f5defb8048ULL,
0xe6534f4d2f18d6a7ULL,
0x1ebaa699aed2159aULL,
0x71f43397dd6ef186ULL,
0x125b2eddd1987588ULL,
0x09e87c1ed87b2bffULL,
0x8d02cdc9e3585c8cULL,
0x67b8692eb9ccb4c7ULL,
0xa6aaf0bce945ea13ULL,
0xf4fbafcb5ff22f08ULL,
0x8af2ed059e8c992eULL,
0xf940ae1e2b24c64cULL,
0x779ba8d60fa198e1ULL,
0x893732d5b54bb02bULL,
0xb1c82603e5694ffbULL,
0xebb3c99f16dba23cULL,
0x356b436d3a7ba624ULL,
0x7d8ae57d1453794eULL,
0xb539b2d575c70dd8ULL,
0x8dcf2d6e4def8acfULL,
0x11c63ffc3fd3defaULL,
0xbb2f6b1b1eafc9e3ULL,
0x1985f163746ab29bULL,
0x6ea5ce6a2351cf8fULL,
0xc50a13b6b4e024a1ULL,
0x6402723172a9130dULL,
0x3f9d08c059228b7fULL,
0x16100691647d53a7ULL,
0x045aac71e1ce044dULL,
0x65ca0990dbc1983eULL,
0x77553bf7e8d96f05ULL,
0x2bb02fd35d713c46ULL,
0xb911bf0ed215280fULL,
0x15c1e2a5620f5f36ULL,
0xc51c2f14919ce96fULL,
0xb1810c003088920bULL,
0xa636b81c40688f4fULL,
0xe6667f881d8f1092ULL,
0xd4b07fa7d1215914ULL,
0x4658ebb13d7197f2ULL,
0xb6fe1b8ae31505c5ULL,
0xa0bc63bc30f991c0ULL,
0xab6de18a0741e447ULL,
0xfeaebec534ee8a6dULL,
0x68bc23d4ac62ce0fULL,
0xa7da553446f4e532ULL,
0x7c20dbedd894934eULL,
0xa80ea0acd7b2ab82ULL,
0x81f5cda672764701ULL,
0x536a4e47d1ee5bf5ULL,
0xc154d6ddb8d6298aULL,
0x2bf6f400f0118871ULL,
0x08c76f4a7d26e72cULL,
0x6bf79e5605a4af3dULL,
0x6e4bbd7bb208909eULL,
0x173ee7824c1608b9ULL,
0xa1544b6b14ded34fULL,
0xba8753d9e0613db2ULL,
0x6b91332a01d8186bULL,
0xed8d52c9fbff4d38ULL,
0x57b20c3e0f1b0288ULL,
0x96411854e95e7a4aULL,
0x890c907302461006ULL,
0xb3fc881f197f89ccULL,
0x7fdae8088af55610ULL,
0xdbc1cffa7528794dULL,
0xf2fa09044a93cf53ULL,
0x667116e81074f9d7ULL,
0xa7cafcc3ee2b398dULL,
0x1e6943e7ae3fddd0ULL,
0xf4e21ca97d41a661ULL,
0x1935dcfe64916c98ULL,
0x3f4c5af99082c210ULL,
0xbb744ac4cdc12d37ULL,
0x24eba0152fe2f36bULL,
0xf66718cf3c9e6ff4ULL,
0x24ba5c4b0a8fd186ULL,
0x902a814ebc78cbb0ULL,
0xfb54e6afd7677377ULL,
0x3395462cb323dafcULL,
0x1765f64979059089ULL,
0x4f2503711b114ce4ULL,
0x1b2850a9a86db30fULL,
0x0ed33d0703e54b81ULL,
0x59e6911707d9a1e3ULL,
0xe15b68a6fa2dddb3ULL,
0x7d6cb238f25b4ec3ULL,
0x83bd75004f015be4ULL,
0x29d098736ebe7ea9ULL,
0xf7df7c3827638900ULL,
0x2c8392e222782637ULL,
0xaf8507f658939e9bULL,
0x1daeea4ff6332658ULL,
0xd523564746edb11bULL,
0xb44d4164ff8cda55ULL,
0xe9c76e93e2f60bdfULL,
0x004296289d0163bfULL,
0xbcb1c00839246844ULL,
0xba5300e273fc5c86ULL,
0x9f91c9fa91d72febULL,
0xe5bee2fb6e6fdeaaULL,
0x5ce33bb2d7474df8ULL,
0x9999761a31aef55aULL,
0xd09af91e66c718beULL,
0xeabe4ab34b9cd70dULL,
0xeb733d53f5b1d5b8ULL,
0x26ee2cceb9691e80ULL,
0xb81bec7e2de8f781ULL,
0x7e7925c145a6f484ULL,
0x41f2fda8abcf13a5ULL,
0x8217cdc62f8b0dccULL,
0x6ed89e51ddfc7343ULL,
0x9d4ffdd5dcf3b9d3ULL,
0x5b186539f5d4943bULL,
0xe76f6ffd5620ce53ULL,
0xc7b22abde412c37cULL,
0xa96ec0c950b59508ULL,
0x137cbf65b24f4027ULL,
0xfb977aed83e0efefULL,
0x29cc9eefdb0f1943ULL,
0x46d418cb4ff6da58ULL,
0xa654b9d497dd8aacULL,
0x7b522b71b23ccf2bULL,
0xd71887ed8381de65ULL,
0x54df226dfd47d14aULL,
0x60531b3859a2a8ccULL,
0xa6a6103b2372fc42ULL,
0x3c0f2c19ceccd159ULL,
0xf32c645f12397f84ULL,
0x95627043b646e8e3ULL,
0xdbea0fd2793c84b7ULL,
0x379a3b0b0b4e64e8ULL,
0xcecfc440122f2e06ULL,
0xc78e330a77c6d50dULL,
0x32d4abc39e1bfff3ULL,
0xd1672a2f4fc4fbe0ULL,
0x7ca7f9d91a0461d3ULL,
0xdb9f979f25e5fbc4ULL,
0x39be4cf8eb863eefULL,
0x6865fb9352d21828ULL,
0x6061368e4d3958f8ULL,
0xe580eab1009b64edULL,
0x90362dcc34f6659fULL,
0x83687ef60931b711ULL,
0x27e46692eb95ff7bULL,
0xe6840eae1418215aULL,
0x4b627eae25b4f08eULL,
0x9cd44859e2bd104bULL,
0x9b173a39761b1dbcULL,
0x4a329a5510e3c086ULL,
0xf13ccb53cc3907e8ULL,
0xff95257fabca3edcULL,
0xda4b7f1cf1ed9805ULL,
0x3a331c82d2924378ULL,
0x7686df1e66fa9655ULL,
0xb1c4ccc5565019f4ULL,
0x39b1fc9947ff6d37ULL,
0xba82db523c13640dULL,
0x91645d38c420b220ULL,
0xcb1a0a6c79fe9feaULL,
0x667fe176012925f0ULL,
0xf2b8446b585294f5ULL,
0x0691117ae0abb50eULL,
0x5eb6118ca2e62872ULL,
0xc924fbaf71c315dfULL,
0xf842177b71c6f22aULL,
0xc80754b46448ee6aULL,
0x21d3ff566b098e01ULL,
0xb149b5d9a0eee677ULL,
0x9b73429d2da4c233ULL,
0x9f885ddc498851abULL,
0xb22eda7ca1b9784cULL,
0xce09c914771d0ed9ULL,
0xe7139893ede5e68fULL,
0x8a1075b14e9fa79eULL,
0x47f16a5941c7e3c5ULL,
0x900a683d7bf56ee7ULL,
0xbff7f284ac239f94ULL,
0xaa6058650a798c9cULL,
0x66d60ffba7c059acULL,
0xa858d85aa9a0083fULL,
0xc28826779a21e0dfULL,
0x5f35efa1b5fe99d5ULL,
0x2fc8244af685d9b4ULL,
0x09a0108475a964d7ULL,
0x31024f713b9f20bbULL,
0xd970efd90cc18400ULL,
0xd61969558d72253fULL,
0xa78ee57a609e07a5ULL,
0xf2f7827f64199028ULL,
0x52c7eeaf8e3e6e1aULL,
0xd661e5ab6b0e254bULL,
0x3e05b4c701bc2852ULL,
0xd31acb22f296d220ULL,
0x342d8b1f90505e5cULL,
0xfc2348b58fd655a2ULL,
0x5a57c7ce5f310a34ULL,
0xa843c5acaaa2dd7dULL,
0xf7b1f0c5dc5c5a10ULL,
0xf4a1e7100c6c8bbfULL,
0x10faf8e33c1b0090ULL,
0x2881d5f64e455310ULL,
0x261dcd7c8bfedd46ULL,
0xfd423849dcdb645aULL,
0x13402769dc9da361ULL,
0x35832a72d7867b05ULL,
0xc3d4c4727b4c30a1ULL,
0x5b5179801ab877ffULL,
0xfd7d1c8f8702501aULL,
0x94605dfe134fe4beULL,
0x5ed44f84153de6c3ULL,
0x75558925a53502baULL,
0xd0abd43d349ae531ULL,
0x7e5c7ca2048f9fefULL,
0xe7cddce1d99ab42bULL,
0x05827d13bde355d6ULL,
0x01c0593caf195d0fULL,
0xe641a40c5afcee19ULL,
0x4f9b7fd1a856b701ULL,
0xdce3eea6efb1853bULL,
0xe28244e9c4e63acaULL,
0x3ef4b139cb56597dULL,
0x7fac5a181c687422ULL,
0x23ea86e377a1a003ULL,
0x14e089a655b2ce4eULL,
0xe215e3bd72cc0a97ULL,
0xf45af26303d5c581ULL,
0x7777f058896f9a73ULL,
0x99aec0374d142a5fULL,
0x552c8546d98e8584ULL,
0x89728b9d11317b9aULL,
0x7464d56911346f28ULL,
0xb19fc6c46914f6f0ULL,
0x15f4e2350578d40dULL,
0x1ddfb4b328b248efULL,
0x8418c3028fd170f6ULL,
0x25046319c34ed2a3ULL,
0x3e018dac9d47fa1eULL,
0x4f1f19bb2fbc34d5ULL,
0x0fba70b5df282972ULL,
0x02df13f0e30ec8b6ULL,
0xdd92d00049da4df1ULL,
0x49026d77fb069f9dULL,
0xdbaae0696329da50ULL,
0x361ba249c6ef3834ULL,
0x3f8d4469ca3868e3ULL,
0xc3ea9e0ea2008a95ULL,
0xee989a98e0c27f84ULL,
0xcbda49dbf8e7f17dULL,
0x42ed85724d734af3ULL,
0x0216234c8107208cULL,
0x97dc33f37554264bULL,
0x63a275b249f2a36dULL,
0x71db0720516bf741ULL,
0x08e4ecb1fef9519dULL,
0x6029a9fc387d3ebeULL,
0x0a55be6aaac4f34dULL,
0xec75d1821df80754ULL,
0x7a8e9282125cd050ULL,
0x688330ce6f0a95c5ULL,
0xf86a39a8ce48c8c4ULL,
0xf04459ab9abb2122ULL,
0xb848403544a7d883ULL,
0x40870758da58c40bULL,
0x5a4a69d56457824aULL,
0x6350619c1b5fbd00ULL,
0xbe46a30362255ca9ULL,
0x3563642107194153ULL,
0xd4549f6d5548f391ULL,
0x49a74dd8304b99dcULL,
0x8f0ce2b2e9235071ULL,
0x0e2ccf5ded9a8b7bULL,
0xcd987e088c2e0809ULL,
0x85ef9bc7ed0152d6ULL,
0xbe35677eff8341bfULL,
0x28b88cd720f7dd5aULL,
0x17c5479731a406acULL,
0x371ed4c130db5662ULL,
0x3bd87aa02d5ac70aULL,
0xfc01994f7de10985ULL,
0x442c4ac382a5aeb6ULL,
0xa34fa4b48d0c5f2fULL,
0x510400b5b016d4ccULL,
0x3b689912720d376dULL,
0x9ec6ea60cf14e2c4ULL,
0xd044145163329affULL,
0x0117185d6b9486acULL,
0x5573ea7a7aa8498aULL,
0x952bd0abd1044727ULL,
0x0f17a52dd8c101cbULL,
0x78b50fccf5c59e79ULL,
0xabacefe6dfe40ea9ULL,
0xca57246ba322697aULL,
0x5fd7df6eb1988ac8ULL,
0x3789eefa5041b684ULL,
0x5ede25e031ab43dcULL,
0x95819a9854f69430ULL,
0x33e3ed56011a727eULL,
0xef113c7fc6ae83a7ULL,
0x33fddf7b3a32eb42ULL,
0xa30cde8d9d71ddebULL,
0xfe60cc7fe3f32cf2ULL,
0x817692be4c6d02c0ULL,
0xfe5609a2f815b73eULL,
0x6d22f1de40a7ee20ULL,
0x77ce3eca9ab12b57ULL,
0x89cd08b7a9b89852ULL,
0x4c2a4a065c147fecULL,
0xce1b2ec486f59d8fULL,
0x0eceda66be6bc4aaULL,
0x7c7732a3c728fc77ULL,
0x1f6b965b48ce8947ULL,
0x11ecc7bc40cf72dfULL,
0x0cdbb71074783cdcULL,
0x6b71e2b1b20073c1ULL,
0x4660e9846cdb6d96ULL,
0xe5f2b31a4a1a3362ULL,
0x20a0b2f0cf3f4f4aULL,
0xef6aa63353c396edULL,
0xa5a596009f79a04dULL,
0x58f772dcd6d17555ULL,
0x7957ccbb31af0b61ULL,
0xb78429d6762f68b7ULL,
0x5d56c1985fe7a77aULL,
0xa7c39cbaeedbcf38ULL,
0x65995fc6feda19dbULL,
0x86bd2842e58c1abfULL,
0x6b8f580e7f95a512ULL,
0x04702eee85556f24ULL,
0x7d03323b15770702ULL,
0x7142db6082e23f0eULL,
0xa7187369f53d799bULL,
0x33ac09c9ef8b5011ULL,
0xa7215e563a441b86ULL,
0x719d08af2d6bbe27ULL,
0x411169b3cc4d2938ULL,
0xac27a7a1de0b5506ULL,
0x6a22863807d7a858ULL,
0x39ee2d2990d69bd2ULL,
0xa4532bde73a403f0ULL,
0x93140026ce0f907fULL,
0x3ee28286b7fb6bd9ULL,
0x9a764f034f6612c3ULL,
0x64a2aebf4bcc603eULL,
0xe3a52379d46f760dULL,
0x177bffaf24689dabULL,
0x50cae3da45597fe0ULL,
0x20965d5b98702278ULL,
0x2216f521a928cc88ULL,
0x66abbd80b4225632ULL,
0x4deb85d7906c2b68ULL,
0x086c679450374d70ULL,
0xda4dcd508b82c799ULL,
0x10d7894a856495d7ULL,
0x0da56c0076c24fbaULL,
0x0e326b797a477812ULL,
0xef6bd63cc63df6c4ULL,
0x79bc5723426d1f76ULL,
0xb75d3b456282beb3ULL,
0xae6e33cfa8828989ULL,
0x6ab76312f343be84ULL,
0xdc8f5b9ac09ecab9ULL,
0x431d138d0462179eULL,
0x52ef096bb35e1c0dULL,
0xf66a0311c0456476ULL,
0x096d359977f58b8eULL,
0xfe552ed33c46d0fbULL,
0x30de400c07364d98ULL,
0xb7b1f521b2cffd09ULL,
0x1ff582472dd69760ULL,
0x269542702e92e3a8ULL,
0x74cc87913e8fc54dULL,
0xfb2690d45bcc2646ULL,
0xc0d6a127b1e95606ULL,
0xa5fb89708bb60bddULL,
0x32c3cbfd9af652f4ULL,
0xe693fa7b4c6820d5ULL,
0x14183f649e3488f4ULL,
0x2a493ed4e84d01e9ULL,
0x5033458942015a8bULL,
0x08e7eafa81e22990ULL,
0xe61a4c18db1aa3d6ULL,
0xe884ae998f479eb4ULL
&#125;;
unsigned long long zobvalh23&#40;unsigned i&#41;
&#123;
return ham23bit&#91;i % 999&#93;;
&#125;

#ifdef UNIT_TEST
#include <stdio.h>
int             main&#40;void&#41;
&#123;
unsigned        i;
unsigned        j;
int             bits;
unsigned long long mask = -1;
for &#40;bits = 0; bits< 64; bits++)
&#123;
// Trim off top bits.
for &#40;i = 0; i < 999; i++)
&#123;
&#125;
for &#40;i = 0; i < 999; i++)
&#123;
for &#40;j = 0; j < 999; j++)
&#123;
if &#40;i != j&#41;
&#123;
if &#40;ham23bit&#91;i&#93; == ham23bit&#91;j&#93;)
&#123;
printf&#40;"bits=%d\n", bits&#41;;
printf&#40;"zobvalh23&#40;%u&#41;=%llu\n", i, zobvalh23&#40;i&#41;);
printf&#40;"zobvalh23&#40;%u&#41;=%llu\n", j, zobvalh23&#40;j&#41;);
exit&#40;EXIT_FAILURE&#41;;
&#125;
&#125;
&#125;
&#125;
&#125;
return 0;
&#125;
#endif

Dann Corbit
Posts: 9280
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

### Re: Transposition table random numbers

The upshot of the analysis of my table is that possibly it should not be used for tables of 16 bits in length or less.