Author: Robert Hyatt
Date: 07:11:19 09/17/00
Go up one level in this thread
On September 17, 2000 at 06:35:17, Dieter Buerssner wrote:
>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.
Most do some sort of multiplication. If the seed is even, you just cut
the period of the rng by 50%.
However, it is speculation, since the normal C library routine random() doesn't
have an argument.
>
>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.
That will certainly kill him. My rng came directly from "Numerical Recipes"
and doesn't generate 15 bit numbers at all. It generates a full 32 bit
number that I call twice to make a 64 bit value.
>
>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.