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

["Antoine de Maricourt" <antoine.de-maricourt@xxxxxxx>]

> > All this "I'll show you mine if you show me yours" is like kindergarten.
> Not really.
[...]
> I respect the Open Source community but I see a lack of respect from the 
> OS community to the professional Go researchers (that still occasionally 
> publish stuff or give very strong hints like I just did).
Entering the "competitors" area, and willing to win money is a perfectly
respectable choice, and I've never seen lack of respect for professional
Go programers on this list.

But yes, I'm affraid this entire thread looks like kindergarten... If you 
have
something to say, just say it. If you don't want to say anything, well don't
say anything...

> > I have begun to write a paper on all this with Antoine but got bogged
> > down for too little time and too much perfectionism (wishing to be
> > mathematically precise about how such defects arise, how to prove that a
> > particular scheme is free of them, etc).
Nic, I'm sorry I had not enough time to continue on this. I've made a (very 
boring)
analysis in order to find out collision probabilities, and came to the 
conclusion
that it could be high, even if the hashing scheme had no builtin defect.

BTW, everybody is arguing about collision probability: we shall be more
precise about this.

Definition 1:
let P1 and P0 two randomly chosen positions, H1=hash(P1) H2 = hash(P2)
and p1 = "probability that H1 = H2 knowing P1 not equal P2"

is not really the same as:

Definition 2:
let Pi (0 <= i < N) be a set of different positions (for instance,
belonging to a pattern database?) and p2 = "probability that there are 2
different positions Pi and Pj within this set, leading to the same hash
value, i.e. hash(Pi) = hash(Pj)"

Definition 2 is similar to the birthday example. Perfect hash key
generation is a known problem that try to generate a hashing scheme,
such that, for a predefined set of items, p2 = 0.

It's pretty obvious that if we add some constraints such as:
1- the hashing scheme shall be based on Zobrist method
2- the set of positions can be very large (N=10^6, 10^7, ...)
3- the length of the key is restricted (64 bits)
then choosing random keys is probably a bad strategy (we want p2 = 0).
On the other hand, if the set is large enough, you probably cannot
construct the keys in a predefined way. So you probably need to use
some kind of random generation (possibly with additional constraints) +
key reworking based on hamming distance computation (other ways
to do it may also exist).

BUT, this does not mean that random keys are not good for definition 1,
and I see absolutly no reason (from a theoritical point of view) to spend
time on some "hamming distance" (or any other similar idea) optimisation
provided your random generator is good enough, and provided your
problem matches definition 1.

Of course if positions P0 and P1 are not random (that is, if you have extra
information), things might change: I  guess the "spiral" idea accounts for 
the
fact that positions with stones in the center are expected to be more 
probable
than other positions?

Feel free to provide other definitions so that we can discuss on the same
basis.

> First show me real earth-shattering proprietary intellectual property 
> patentable trade secrets, not Kindergarten stuff :)
Well, here they are (no specific order):
#1 : forget alpha-beta
#2 : forget move pruning
#3 : forget hash-keys
#4 : forget pattern matching (I mean, based on visual shape recognition)
#5 : adopt a more mathematical point of view
#6 : ... :-)

As you can see, my last boy (3-years old) helps me to keep a child's mind...

Good luck.

   Antoine.

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