computer-go: Re: your mail

[Heikki Levanto <heikki@xxxxxx>]

On Fri, Feb 23, 2001 at 12:25:20PM -0800, comp go wrote:
> Does anyone have an algorithm for determining whether or not a
> group of stones is unconditionally alive (i.e. cannot be captured
> by the opponent even if the player does nothing but pass for the
> rest of the game)?  If so, would you be kind enough to explain it?


I don't have a formal algorithm for it, but I think something along the
lines of
  repeat
    fill a liberty, unless the move is a suicide
  until (no more liberties left) or (group has been captured)
  if (group has been captured)
  then 
    it is not unconditionally alive
  else
    it must be alive

should be a good starting point. I believe it captures all
not-alive groups. Of course the matter gets much more complex if you allow
the opponent to make even a single move - this brings in sekis and ko's, and
what not...

-- 
Heikki Levanto     LSD Levanto Software Development   heikki@xxxxxxxxxxxxxxxxx
               "In Murphy we Turst"