Re: computer-go: Re: your mail

[Antti Huima <huima@xxxxxxx>]

On Mon, 26 Feb 2001, Frédéric Zgud wrote:

> Heikki Levanto a écrit :
>
> > 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...

> This algorythm doesn't work because it depends on the order you fill the
> liberties :
>
>  . . * * * *  D
>  . * * o o *  C
>  . * o . o o  B
>  . * o o . .  A
>  6 5 4 3 2 1

> If you start by taking the (1,A) liberty, the white group is judge
> unconditionally alive. If you start by taking the (2,A) liberty, the
> white group can be killed. It needs some backtrack to give always the
> same answer.

Backtracking is not necessary. It is enough to consider opponent's strings
(here white's) one after another, and check if some of them can be
captured.  That is, if the string has at most one isolated liberty.  If a
string can be captured in this sense, remove it from the board, and then
iterate this until no more strings can be removed.  There is no need even
to actually "put" the stones on the board during the algorithm is run.

Thus we get:

  1. Let X be a white group that has at most one singular liberty
  2. If X was found
     2.1 Remove X from the board
     2.2 Restart from 1.
  3. Terminate

-- 
Antti Huima