Re: Sharing Secrets (was: [computer-go] Computer Go hardware)

[Don Dailey <drd@xxxxxxx>]

Zobrist hashing's particular strength  is BOTH fantastic speed (due to
easy  incremental updating) and  exceptionally good  key distribution.
You say, "Which they never are,  not even close."  But I think Zobrist
hashing is VERY close.

Even if  you use a  fairly poor random  number generator to  build the
table of values used for zobrist hashing, you probably will generate a
set of reasonble keys.  That's because  a zobrist key is like (in some
sense  of the word)  a random  number generator  too.  Often  when you
combine  two  random  number  generators  you  get  a  superior  third
generator.

But I'm not proposing that you use weak generators.  There are several
easy things you can do to ensure excellent zobrish keys:

   1.  Use well known high quality pseudo random number generators for
       your zobrist table.    These are freely available.

   2.  Use actual random number generated from physical sources.
       2.1  These are avaiable on the web.
       2.2  You can generate truly random numbers from you computer too.

   3.  Use  any psuedo random  number generator  and apply  a "hamming
       distance" analysis and correction on them.

       The  basic procedure is  to make  multiple passes  through your
       table  of  psuedo random  numbers  and correctively  regenerate
       elements in the table  with low hamming distances between them.
       The hamming distance is the number of bits NOT in common.

       The end result is a table where you have maximized the "hamming
       distance" between any two values in the table.

       In  theory  this procedure  will  improve  the  quality of  the
       Zobrist keys.   In practice, if  you random numbers  are pretty
       good  anyway,  it will  be  difficult  to  actually measure  an
       improvement, because Zobrist hashing is excellent anyway.


- Don








   X-Original-To: computer-go@xxxxxxxxxxxxxxxxx
   From: "Frank de Groot" <frank@xxxxxxxxxxxxxxxxx>
   Date: Thu, 21 Oct 2004 16:18:10 +0200
   X-Priority: 3
   X-MSMail-Priority: Normal
   X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180
   Reply-To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
   Sender: computer-go-bounces@xxxxxxxxxxxxxxxxx
   X-Scanned-By: MIMEDefang 2.42

   > Most programmers conveniently ignore the issue. And they might as well.
   > Even if they store 2^24 positions in a hashtable, and do a search of 2^24
   > positions, the collision probability is at most 2^(24+24-64) = 1/65536,
   > which can be considered negligable.

   Your statement is only true when the hashes are generated with best
   statistical distribution. Which they never are, not even close. We're
   talking several-orders-of magnitude-not-even-close with traditional methods.
   Hint: Most random generators *totally suck*. Any programmer who conveniently
   ignores this issue is in for a nasty surprise.

   _______________________________________________
   computer-go mailing list
   computer-go@xxxxxxxxxxxxxxxxx
   http://www.computer-go.org/mailman/listinfo/computer-go/

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/