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:
(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.
Well the code that I posted above will generate random numbers that have a hamming distance of at least 4 for every pair of numbers. Basically it uses Knuth shuffle to select unique 16bit numbers. I then use shifting to make a 64bit number out of 4 of them. Henceforth, because the 16bit numbers have a hamming distance of at least 1 and there's four 16bit for every 64bit number, the result is a 4bit hamming distance between every pair of numbers.
You say not to use rand(). But what about using with the Knuth shuffle and shifting? I'm guaranteed to have a minimal hamming distance for every pair. And from my reasoning, using the same algorithm the best hamming distance possible for the needed 769 numbers is 5.
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:
(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.
Well the code that I posted above will generate random numbers that have a hamming distance of at least 4 for every pair of numbers. Basically it uses Knuth shuffle to select unique 16bit numbers. I then use shifting to make a 64bit number out of 4 of them. Henceforth, because the 16bit numbers have a hamming distance of at least 1 and there's four 16bit for every 64bit number, the result is a 4bit hamming distance between every pair of numbers.
You say not to use rand(). But what about using with the Knuth shuffle and shifting? I'm guaranteed to have a minimal hamming distance for every pair. And from my reasoning, using the same algorithm the best hamming distance possible for the needed 769 numbers is 5.
The minimum hamming distance of all the numbers in my table between each of the others is 23.
So I am not sure what you mean by 5 is the best possible.
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.
That is correct, IF a single entry is 8 bytes long. If you use the lower 19 bits, you are addressing entries of 2^3 bytes to come up with 2^22 bytes of hash. Unless I am not understanding what you are writing...
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.
The lower bits only contribute to the hash index, but all are important for collision detection. Whether they are unique or not in the low order N bits is not so important, because you end up XORing up to 32 of these numbers to make a signature... You'd like to have each _signature_ unique in the low order bits, but that is obviously impossible.
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 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...
Worse in what way? There are a series of tests, poker test, runs test, uniformity test, etc, that should _all_ be used to screen PRNGs. The MT algorithm has been pretty thoroughly tested. Particularly since we only need a few numbers and not millions.
bob wrote:Worse in what way? There are a series of tests, poker test, runs test, uniformity test, etc, that should _all_ be used to screen PRNGs. The MT algorithm has been pretty thoroughly tested. Particularly since we only need a few numbers and not millions.
PRNG tests are pretty standard. But does it necessarily mean that something that is better in PRNG tests is better strength wise?
Not necessarily, at least according to what I've tested.
I've tested with 3 different hash sizes (8MB, 32MB, 128MB) and 3 different TCs (1'+1'', 40/4', 40/20') and never got a version with MT (I used the default seed) outperforming the original version (within error margins - it was 2k games self-test). As a matter of fact, the original version was almost always better (on one occasions even with LOS over 95%).
bob wrote:Worse in what way? There are a series of tests, poker test, runs test, uniformity test, etc, that should _all_ be used to screen PRNGs. The MT algorithm has been pretty thoroughly tested. Particularly since we only need a few numbers and not millions.
PRNG tests are pretty standard. But does it necessarily mean that something that is better in PRNG tests is better strength wise?
Not necessarily, at least according to what I've tested.
I've tested with 3 different hash sizes (8MB, 32MB, 128MB) and 3 different TCs (1'+1'', 40/4', 40/20') and never got a version with MT (I used the default seed) outperforming the original version (within error margins - it was 2k games self-test). As a matter of fact, the original version was almost always better (on one occasions even with LOS over 95%).
A couple of years ago we had a PRNG debate here. I tried several and found _zero_ differences with respect to Elo. You will find one set of random numbers that works better on a given set of positions, another set of random numbers that works best on a different set of positions. There is hardly any PRNG around that can't spit out 1,000 decent random numbers. The issues come way later when you get into cycles. I've never seen one that would think about cycling after just 1,000.
I think trying to measure effectiveness is hopeless for such tiny potential changes... 2K games is nowhere near enough as the potential gain is in the +/- 1 Elo or less, unless you have some horrible PRNG. The twister is hardly horrible. I use the PRNG from Knuth's book since the source (in C) was publicly available.
#include <stdio.h>
#ifndef true
#define true 1
#define false 0
#define bool int
#endif
typedef unsigned __int64 uint64;
typedef unsigned int uint32;
#define HDMIN 21//the required minimum hamming distance
#define HDMAX 40//the maximum hamming distance
#define HS 4096 //the history stack size
#define MS 10 //the count of separated groups of numbers
//int max_size[MS] = {1920, 16, 128, 2, 0, 0, 0, 0, 0, 0};//the divided sizes of the groups
int max_size[MS] = {1792, 15, 127, 1, 0, 0, 0, 0, 0, 0};
uint64 __inline rand64()
{//generates 64-bit rnd number
return ((uint64)rand()
^ ((uint64)rand() << 15)
^ ((uint64)rand() << 30)
^ ((uint64)rand() << 45)
^ ((uint64)rand() << 60));
}
bool __inline long_enough(uint64 rn)
{//checks if the number has a 16 digits and not less
int x;
char strbuff[24] = {0};
sprintf(&strbuff[0], "%#llx", rn);
x = strlen(strbuff);
if (x < 18) return false;
return true;
}
uint32 __inline hamdist(uint64 x, uint64 y)
{//returning the hamming distance between the 2 bitstrings:
uint32 dist = 0;
uint64 val = x ^ y;
while(val)
{ ++dist;
val &= val - 1;
}
return dist;
}
int main()
{
int i,j,k; //loop counters;
FILE *f; //the 'numbers.txt' file descriptor
int tab = 0; //'4 on a line' counter
uint64 rnd_number; //the current rnd number
uint64 history_stack[HS] = {0};//stack of generated numbers, the 1s element is independent - 'to compare with'
int hs_pos = 1; //current position in the history stack
bool num_ok = false;
int hd = 0;//hamming distance returned value
uint32 num_count = 0;
uint32 total_num_count = 0;
//calculating the total
for(i = 0; i < MS; i++)
total_num_count += max_size[i];
printf("total: %d\n",total_num_count);
printf("current:\n");
//setting the first element (separately from the rest)
do{rnd_number = rand64();
}while(!long_enough(rnd_number));
history_stack[0] = rnd_number;
//start:
f = fopen("numbers.txt", "w");
for(i = 0; i < MS; i++)
{
for(j = 0; j < max_size[i];j++)
{
do
{ num_ok = true;
//checking the lenght after generate:
do{rnd_number = rand64();
}while(!long_enough(rnd_number));
//checking the hd with the rest numbers in stack:
for(k = 0; k < hs_pos; k++){
//check if the number exists (duplicate)
if(rnd_number == history_stack[k])
{ num_ok = false;
break;
}
hd = hamdist(rnd_number, history_stack[k]);
if((hd < HDMIN) || (hd > HDMAX))
{ num_ok = false;
break;
}
}
}while(!num_ok);
//the number is ok now, so increase the position in stack and record it:
history_stack[++hs_pos] = rnd_number;
//saving:
tab++;
fprintf(f, "\t%#llx", rnd_number);
fprintf(f, "%s", "ULL");
if((j + 1) != max_size[i]) fprintf(f,"%s",",");
//the line of 4 is ended ?:
if(tab == 4) {
fprintf(f, "%s", "\n");
tab = 0;
}
//printing out the recorded count so far:
num_count++;
printf("\r%d",num_count);
}
//separating the portions in file:
fprintf(f, "%s", "\n\n\n\n");
}//exit:
fclose(f);
printf("\n\n");
system("pause");
return 0;
}
bob wrote:Worse in what way? There are a series of tests, poker test, runs test, uniformity test, etc, that should _all_ be used to screen PRNGs. The MT algorithm has been pretty thoroughly tested. Particularly since we only need a few numbers and not millions.
PRNG tests are pretty standard. But does it necessarily mean that something that is better in PRNG tests is better strength wise?
Not necessarily, at least according to what I've tested.
I've tested with 3 different hash sizes (8MB, 32MB, 128MB) and 3 different TCs (1'+1'', 40/4', 40/20') and never got a version with MT (I used the default seed) outperforming the original version (within error margins - it was 2k games self-test). As a matter of fact, the original version was almost always better (on one occasions even with LOS over 95%).
A couple of years ago we had a PRNG debate here. I tried several and found _zero_ differences with respect to Elo. You will find one set of random numbers that works better on a given set of positions, another set of random numbers that works best on a different set of positions. There is hardly any PRNG around that can't spit out 1,000 decent random numbers. The issues come way later when you get into cycles. I've never seen one that would think about cycling after just 1,000.
I think trying to measure effectiveness is hopeless for such tiny potential changes... 2K games is nowhere near enough as the potential gain is in the +/- 1 Elo or less, unless you have some horrible PRNG. The twister is hardly horrible. I use the PRNG from Knuth's book since the source (in C) was publicly available.
I guess maximizing the minimal hamming distance makes the Zobrist keys collapse in on itself. I guess that also means that my key generator is also useless?
bob wrote:Worse in what way? There are a series of tests, poker test, runs test, uniformity test, etc, that should _all_ be used to screen PRNGs. The MT algorithm has been pretty thoroughly tested. Particularly since we only need a few numbers and not millions.
PRNG tests are pretty standard. But does it necessarily mean that something that is better in PRNG tests is better strength wise?
Not necessarily, at least according to what I've tested.
I've tested with 3 different hash sizes (8MB, 32MB, 128MB) and 3 different TCs (1'+1'', 40/4', 40/20') and never got a version with MT (I used the default seed) outperforming the original version (within error margins - it was 2k games self-test). As a matter of fact, the original version was almost always better (on one occasions even with LOS over 95%).
A couple of years ago we had a PRNG debate here. I tried several and found _zero_ differences with respect to Elo. You will find one set of random numbers that works better on a given set of positions, another set of random numbers that works best on a different set of positions. There is hardly any PRNG around that can't spit out 1,000 decent random numbers. The issues come way later when you get into cycles. I've never seen one that would think about cycling after just 1,000.
I think trying to measure effectiveness is hopeless for such tiny potential changes... 2K games is nowhere near enough as the potential gain is in the +/- 1 Elo or less, unless you have some horrible PRNG. The twister is hardly horrible. I use the PRNG from Knuth's book since the source (in C) was publicly available.
I guess maximizing the minimal hamming distance makes the Zobrist keys collapse in on itself. I guess that also means that my key generator is also useless?
class Rand64 {
private:
uint64 box[65536];
int size;
inline uint64 block()
{
if (size < 2)
size = 65535;
swap(box[rand() % size], box[size]);
size--;
return box[size + 1];
}
public:
Rand64()
{
size = 65535;
for (int i = 0; i < 65536; i++)
box[i] = i;
srand(time(NULL));
}
uint64 next()
{
uint64 val = 0;
for (int i = 0; i < 4; i++)
val |= block() << (16 * i);
return val;
}
};
I guess I should use the Mersenne Twister PRNG.
Burton Wendroff and Tony Warnock wrote a paper in the JICCA, somewhere in the late 80's I think, and covered this subject. When I went back and looked at it, it became apparent that (1) yes, there probably is a way to optimize the PRN's to work best with chess; but (2) it will be extremely painful and possibly sensitive to particular time controls. What you want is a set of PRNs that when XORed together to make a Zobrist key, that the key is as unique as possible. For example, for a single knight move, you really care about the hamming distance between the source and 8 possible destination squares, and then recursively do that for the 8 destination squares. At today's search depths, it is probably futile, since we can easily go 24+ plies deep nominal depth + checks and q-search. That entire set of PRNs needs to be optimized so that keys along the path don't collide. Doesn't seem to be a simple and direct way to solve that, and once Cozzie and I showed that it takes a _lot_ of collisions before they are a problem, anyway, I decided that this was wasted effort and moved on.
I think HGM first questioned the idea of trying to optimize the numbers via hamming distance, and he was correct.
If anyone is concerned about the randomness of the numbers in the Zobrist table (although I agree with Bob that it doesn't matter), you can come up with several tables using different methods and then XOR them together. The result will be at least as random as the most random "ingredient" you put in there.
The only randomness test that I think matters in this context is some modification of the "birthday test". You take all the positions in a search tree, filter out repeated ones, compute their Zobrist keys and count how many of the positions map to each entry in the hash table. Now measure the deviation between these numbers and the expected Poisson distribution.
