Re: computer-go: Most simple Go rules

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

> Do you need anything as clever as Zobrist hashing?  Can't you just hash
> on the number of stones on the board, and then check for collisions?

Yes,  you  could implement   this  differently  and  if  you were  not
including  this  inside  a search,   you would  probably  not notice a
performance  penalty   for the full board   comparisons  that would be
required.

A virtue of your method is that it would never be wrong.

However ... 

Zobrist  hashing would be  superfast  and is  actually  very simple to
implement.  As William mentioned, if you  used a wide enough signature
key, you are quite safe.


Don



   Date: Mon, 25 Jun 2001 16:06:31 +0100
   From: Nick Wedd <nick@xxxxxxxxxxxxxxxxx>

   In message <20010625092030.B16165@rootless>, William Harold Newman
   <william.newman@xxxxxxxxxxxxxxxxx> writes
   >On Mon, Jun 25, 2001 at 09:58:58AM +0100, Nick Wedd wrote:
   >> __ Standard ko rule, i.e. 2-cycles forbidden.
   >>     Implementing superko is difficult.  Some of the programs at Dublin
   >> will not be world leaders, they will be newcomers to CG.  I do not want
   >> to make things difficult for them.
   >
   >In my experience, minimal support for superko is not very difficult to
   >implement. Make some sort of reasonably wide hash (e.g. 64 bit Zobrist
   >hash) of each board position. Maintain a collection of hashes of
   >positions which have occurred so far in the game. Disallow moves which
   >collide with previous hashes.

   Do you need anything as clever as Zobrist hashing?  Can't you just hash
   on the number of stones on the board, and then check for collisions?

You can implement it any way you choose,  but Zobrist is actually
trivial and fast.  



   >In a language with library support for sparse collections with
   >efficient collision detection (e.g. C++, Java, Perl, Common Lisp..)
   >this could be about two dozen lines of code. Maybe it's a little more
   >if the language makes 64-bit arithmetic unwieldy (Java or Perl, maybe?
   >I dunno).
   >
   >This is only a probabilistic algorithm, but at 64 bits of hash, I
   >expect false collisions to be less likely than tripping over the power
   >cord; and if that isn't safe enough for your tastes, you can make the
   >error probability exponentially smaller by using a wider hash.
   >
   >How do you plan to deal with situations like triple ko without a
   >superko rule? Do you have an alternative rule which is easier to
   >implement than superko? Or do you just figure that triple ko is
   >sufficiently uncommon that you don't need to worry about it in your
   >tournament?

   I plan to deal with triple-ko in the same way as it is dealt with in
   human Go events in these islands.  Count it as half a win to each
   player, and make the most of the opportunity for publicity!

   Though your suggestion also has a publicity opportunity - "Why didn't
   black play there, even a beginner would find that obvious?"  "Because it
   thought it was illegal, its Zobrist hash collided."

   Nick
   -- 
   Nick Wedd