Re: computer-go: Most simple Go rules

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Wed, Jun 27, 2001 at 11:31:37AM -0400, Don Dailey wrote:
> 
>    > Zobrist is a "superfast" method of incrementally updating the hash key
>    > for the position.  It's not really  a different hashing method, just a
>    > way of computing a key.  It's based on a  table of random numbers that
>    > you create offline.  It's strengths are many, it's not only very fast,
>    > but it  also gives you high  quality keys (like excellent distribution
>    > properties.)
>    >
> 
>    Ah, Zobrist seems to have a knack of having his name attached to ideas that
>    come very naturally to many people. I'm sure the same method of hashing is
>    also used in many  Chess and Draughts programs, do they call it Zobrist
>    hashing too?
> 
> This is one of those very simple ideas that seem intuitive and natural 
> once someone else has already figured it out and published it.  
> 
> Many of Donald Knuth's ideas are like this,  but there is great genius
> in coming up with simple ideas that others have never thought of.
> 
> I know that Bobby Fischers chess games have often been described as so
> natural and logical that you feel you  could have played the very same
> moves.  And yet not very people were able to manage it.

Do you work for the USPTO by any chance?:-)

It's true that a useful idea, sometimes even a simple useful idea,
sometimes sits undiscovered and unused for a long time. But drug
research is the only field I can think of where long-undiscovered
useful ideas are the rule instead of the exception. In software and
related fields, many examples exist suggesting the opposite tendency,
that useful ideas are spontaneously, independently invented at a
rather high rate. For a fairly extreme example, look how many times
fast Fourier transform algorithms -- a far more subtle and surprising
idea than Zobrist hashing IMHO -- were independently invented. Or look
at the way that public key encryption -- surely not an obvious idea!
-- was independently invented at least twice within a decade after the
required hardware became cheap enough that it might be economical to
use it instead of distributing secret keys.

I would think it's probably pretty easy to reinvent Zobrist hashing,
since summing/XORing components is a common way to hash collections,
and it's a small step from there to arrange the sum/XOR so that you
don't need to recompute most of it when you make a move. It's an
especially small step in Go programming, since the board is big enough
that people are motivated to try to find ways to update everything
incrementally. Even though Zobrist's hashing method is pretty well
known, I wouldn't be much surprised to find that the number of people
who have implemented Zobrist hashing based on an independent invention
of it was comparable to the number who got the idea (indirectly) from
Zobrist. But as usual on the net, Your Mileage May Vary, of course.

(Incidentally, I think the comparison to Fischer's Chess is flawed.
Playing Fischer-quality moves 80% of the time will get you nowhere in
a good tournament, and there's no efficient algorithm to tell which of
your moves are the good 80%. But generally it only takes polynomial
time to verify that an algorithm is good. So coming up with good
algorithms 80% as often as a specialist would be enormously more
useful than coming up with first-rate Chess moves 80% as often as a
specialist..)

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
whose coworkers received a sizable bonus for applying for a US patent
covering any use of <Foobar> with a new proposed IETF protocol, when
the use of <Foobar> was standard in the protocol it was based on
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C