[computer-go] C++ random numbers

[Chrilly]

The original rand() function of K&R is very bad for hashing. It produces in the low-bits clear patterns. E.g. in one of my first chess programms the hash-numbers with a last positon of "0" or "5 where much more frequent than the other numbers. As a consequence only about 30% of the hashtable was effectively used. Don Beal has published an article were an entry is not necessarily placed on the calculated position, but one searches k-entries in the hashtable further to replace the worst (minimum-depth) entry. He got big improvements with k==4. I assume he used the same bad random generator and the factor k==4 eliminates the effects of rand().
You should therefore check the numbers. Not the directly generated ones for the Squares+Stones, but the hashnumber generated during search for the position. My check was rather trivial. I just printed out the number every 1023th position and inspected them by hand. This was sufficient to see at the first glance the bad distribution. 
One can/should make also statistics about the filling of the hashtable. This was in fact the first test. I got much more collisions than expected and then printed out the Hash-Numbers to check whats going on. Afterwards I noticed that. the CACM has already published articles about the bad behaviour of rand() "Random number generators: Good ones are hard to find". After all one is according to Janos Margittai 
already in a state of sin when one wants to produce with an algorithm random numbers.

Chrilly
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20060808/9e80476a/attachment.htm