Author: Dieter Buerssner
Date: 03:35:17 09/17/00
Go up one level in this thread
On September 16, 2000 at 23:54:19, Robert Hyatt wrote:
>On September 16, 2000 at 22:40:05, Larry Griffiths wrote:
>
>>On September 16, 2000 at 19:25:56, Robert Hyatt wrote:
>>
>>>
>>>This last thing suggests that maybe your hash keys are not as random as they
>>>should be. I have done some hash testing and I don't see any "holes". IE I
>>>can quickly write over nearly *every* position. I detect this by simply running
>>>a search, then counting how many entries are from this search, vs previous
>>>searches. I can get 99% easily...
>>
>>I did some testing and I believe you are correct, Bob.
>>
>>I changed the following in my code...
>>
>>// hrandom=random(HASHTABLEENTRIES);
>> hrandom=random(4000000000);
>>
>>I dont know why I was using HASHTABLEENTRIES (the number of) as my
>>input to random, but changing it to 4000000000 made the bands go away.
>>
>>Thanks Bob :)
>>
>>Larry.
>
>what random() function are you using? IE stock random() doesn't have any
>arguments. If it is a seed, there are known good and bad seeds. In almost
>_all_ cases, you want the seed to be odd, and usually prime.
Hmm. I don't believe this. Almost all Pseudo random number generators I know
(there are *many*) don't depend on the seed. Even the toy PRNGs, like the
linear congruential generator, that often is the system rand(), doesn't depend
on the seed. It has an internal state which is initialize by the seed. Then it
will walk through all possible numbers, independent of the initial seed.
A different seed just means, that you start at a different point in the
produced sequence of pseudo random numbers.
There are a few exceptions, like you must not seed a shift register generator
with zero.
I believe Larry thinks of something different by random() than you. You probably
think of the BSD function random (which is a lagged Fibonacci generator,
similar to the one you use in Crafty). Some Borland compilers had a macro
random(n), which yielded a random number between 0 and n-1. The maximum n
is 2^15.
So I think Larry's problem is, that he doesn't use 64 bit hash values, but
rather uses only 15 bit hash values and has 49 zero bits.
I made some experiments with different PRNGs for hash tables. I didn't get any
significant differences for very good PRNGs and "toy PRNGs". Of course, care
must be taken, to use 64 bits, i.e. by shifting more than one call to rand
together.
Larry might want to try this:
The following PRNG was suggested by George Marsaglia, and should be more
than adequate for chess programming (but may fail in demanding
statistical simulations).
There are some masks (&0xffffffffUL) that are redundant for many environments.
They are only needed when ULONG_MAX is > 0xffffffffUL, but they won't hurt
and should make the PRNG portable to all ISO-C environments.
static unsigned long zseed = 0x12345678UL; /* almost anything will do fine here
*/
static unsigned long wseed = 0x23456789UL;
/* Return random number between 0 and 0xffffffffUL inclusive.
Paste together 2 multiply with carry generators suggested by
George Marsaglia */
unsigned long mwc1616(void)
{
unsigned long t = zseed;
zseed=30903*(t&0xffff)+(t>>16);
t = wseed;
wseed=18000*(t&0xffff)+(t>>16);
return ((wseed<<16)&0xffffffffUL) + (zseed&0xffff);
}
/* For the purpose of hash in chess programming, you don't need to seed me */
void seed_mwc1616(unsigned long s)
{
zseed = s&0xffffffffUL;
wseed = (s*1103515245UL + 12345)&0xffffffffUL;
}
Then if you have 64 bit hashkeys paste together two calls to mwc1616.
unsigned long r1, r2;
r1 = mwc1616();
r2 = mwc1616();
hasharray[whatever_indices_you_need] = ((BITBOARD)r1 << 32) | r2;
- Dieter
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.