computer-go: ko [was: Applying Moore's Law to Computer Go]

[John Aspinall <jga@xxxxxxx>]

At 8:50 AM -0700 11/23/99, Jeff Massung wrote:
> I have this problem, too.  Especially calculating for "ko", because 
> every call I make to IsValid() basically places the piece on the 
> board, updates everything, and then checks to see if it is the same 
> baord position-2.  This takes way too much time.  Anyone found 
> something better?
For "simple" ko, that is returning to the same board position with a 
cycle length of 2 (as opposed to longer) you can do much better.  At 
the time of any one-stone capture,  where the capturing stone forms a 
single-stone group, (at time N-2, say) record the position of the 
captured stone on the time N-1 board.  A move there at time N is a ko 
violation.   This works when there is only one active ko on the 
board; it won't detect cycles made from multiple kos.  There are 
generalizations too, of course, the basic invariants being that a 
non-[single-stone-capture] is always permissible, and resets the "ko 
state" to "none".

Note: Even the generalization is not strictly correct.  (Playing 
"under the stones" captures can fool it.) But it can be programmed so 
that it will not give you false positives.  (I.e. tells you that a 
move would be a ko violation, when it isn't.)  All its errors are 
false negatives.  (I.e. tells you that a move is permissible, when 
the resulting board position has been seen.)  So you can use it as a 
fast filter before you apply stricter checking.