Re: computer-go: Most simple Go rules

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

William,

My  program does exacty   this, but I  am  uncertain whether this rule
concerns itself with color to move.  Are 2 identical configurations to
be considered the same positions if the color to move is different?

In my program, you can repeat a configuration if on the second visit a
different player  is on the move.   I think  that is logically correct
but I'm not sure how superko is defined in this respect.

Don




   Date: Mon, 25 Jun 2001 09:20:31 -0500
   From: William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
   References: <200106242123.RAA23378@xxxxxxxxxxxxxxxxx> <001701c0fd3a$192883f0$0300a8c0@xxxxxxxxxxxxxxxxx> <V0YcDAPS1vN7EwtH@xxxxxxxxxxxxxxxxx>
   Mime-Version: 1.0
   X-Mailer: Mutt 1.0.1i
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   Content-Type: text/plain; charset=us-ascii
   Content-Length: 1762

   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.

   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?

   -- 
   William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
   As usual, this being a 1.3.x release, I haven't even compiled this
   kernel yet.  So if it works, you should be doubly impressed. 
     -- Linus Torvalds, announcing kernel 1.3.3 on the linux-kernel mailing list.
   PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C