Re: computer-go: Most simple Go rules

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   Date: Wed, 27 Jun 2001 14:24:06 -0500
   From: William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
   Mime-Version: 1.0

   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?:-)

Don't even know what USPTO is.


   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. 

I don't try to refute that, in fact I agree.  Few ideas just spring up
out of nowhere, they  are usually based on  "standing on the shoulders
of others."

When Einstein came up with relativity, it was said that this was truly
remarkable and advanced for it's time, and that  perhaps it would have
taken a few decades to come around to this by someone  else.  I have a
feeling even this isn't true, but I don't doubt his genius.

I'm not saying Zobrist is a genius but I still have to  say that I see
the beauty of a simplicity that is taken  for granted when you already
know the answer.  It's like a riddle or magic  trick, once it's solved
it doesn't seem amazing at all and you quickly get bored with it.


                       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..)

This in not flawed,  it  only demonstrates  that good chess  technique
need not be flashy.  Fischer of course was capable of truly flashy and
impressive moves,  but most good players admit  that he  "made it look
easy", which  is the exact point.  A  lot of players would  have found
his flashy   moves   but commplain  that   they  don't  those kind  of
positions!

Don



   -- 
   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