Re: [computer-go] A superko paradox

[Don Dailey <drd@xxxxxxx>]

Hi Gunnar,

Yes, my answer was flawed.  Telling him to use bigger hash keys didn't
seem like a reasonable response since he knows about zobrish hashing
already and I assumed he was either a purist, or he needed 100%
admissibility.

As you say, repetitions are not that rare and you would be forced to
make the check in that case too.  The second point you mentioned I
just considered an implementation detail that would be obvious.

This idea is probably still good if one requires a fully admissible
program.  In that case, you should cover the simple cases with the
fast tests as you suggest.

There are probably improvements (if you assume hash keys are taboo)
based on undoing moves (instead of starting at the beginning) until
you reach some state where you can prove it is safe to stop.

- Don






   Date: Sat, 12 Feb 2005 01:14:02 +0100
   From: Gunnar Farnebäck <gunnar@xxxxxxxxxxxxxxxxx>
   X-Virus-Scanned: by amavisd-new-20030616-p10 (Debian) at lysator.liu.se
   X-Amavis-Alert: BAD HEADER Non-encoded 8-bit data (char E4 hex) in message header 'From'
	   From: Gunnar Farneb\344ck <gunnar@lysa... ^
   X-Spam-Score: -4.9
   X-Spam-Flag: NO
   X-Scanned-By: MIMEDefang 2.42

   Don wrote:
   > The solution is based on the fact that these collisions are very rare
   > if you are using a reasonable hash key size.  Since this is a very
   > rare situation, you only have to recreate the positions you have
   > already encountered.  Presumably you have stored the list of moves
   > that get to the current position.  Initialize the board to the
   > starting position and play back the move list, comparing each new
   > position encountered with the current position.   
   > 
   > This is very expensive when it happens, but it should be a truly rare
   > situation and amortized over the computing time of your program it
   > should be unnoticeable.    And there will not be the overhead of storing
   > every position encountered.  

   There are two things I don't understand here.

   1. This code can be triggered either by a genuine repetition or a hash
      collision. You don't know beforehand which it is so you have to do
      the full check in both situations. While repetitions may be
      infrequent (I take for granted that length 2 cycles are detected by
      a cheap simple ko test) I doubt that they count as "truly rare" in
      contrast to hash collisions.

   2. Why compare each new position encountered and not only the ones
      where the hashes match?

   But it's not really important. Like everybody else I recommend using
   64-bit Zobrist hashes and forget about collisions. They won't happen.

   /Gunnar

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