computer-go: Re: your mail

[Frédéric Zgud <frederic.zgud@xxxxxxx>]

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...
>
> --
> Heikki Levanto     LSD Levanto Software Development   heikki@xxxxxxxxxxxxxxxxx
>                "In Murphy we Turst"

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.
______________________________________________________________
Frederic Zgud