RE: computer-go: Graph Theory

["Cuijpers, P.J.L." <P.J.L.Cuijpers@xxxxxx>]

OK. Now I know what you mean I guess, and I think you are right, but I also
feel that your method is a little restricted.

1) It is theory about one large eye only, and does not take the liberties of
the group around it into account. For example, a box of six empty spaces in
the corner does not have a cutvertex, but can be killed if the group around
it does not have any liberties except the four resulting of this big eye. In
the diagram, x kills 0 by playing the sequence 1 upto 5.

x x x x x 
x o o o o 
x o 4 1 3
x o 5 2 .

2) For large eyes, we already know that every large eye bigger than 6 lives
at least in seki (See John Davies book on life and death).

3) There are eye shapes of size 6 that have two cut-vertices, so your
algorithm has a problem again. See example below. 

x x x x x
x x . x x
x x . . x
x . . . x
x x x x x

Conclusion: if there is exactly one cut-vertex and there is a vital point,
then the vital point is the cut-vertex. If there is no cut-vertex there
might still be a vital point, if there are more cut-vertices there is no
vital point. 

> -----Original Message-----
> From: Tyler D Sellon [mailto:tsellon@xxxxxxxxxxxxxxxxx]
> Sent: donderdag 2 mei 2002 7:30
> To: computer-go@xxxxxxxxxxxxxxxxx
> Subject: Re: computer-go: Graph Theory
> 
> 
> On Wed, May 01, 2002 at 08:35:33AM +0200, Cuijpers, P.J.L. wrote:
> > 
> > Sounds interesting, although I have no idea what a cut-vertex is.
> > Can you explain what you mean?
> > 
> > > 
> > > I was noticing that key points of eye shapes fall on a 
> > > cut-vertex, I've been unable to find a counter example.  Does 
> > > anyone know anything more about this property, or other graph 
> > > theory related Go theorems?  Thanks.
> > > 
> > >               -Tyler Sellon
> > > 
> >
> 
> 
> I was looking at methods for solving simple life and death problems,
> and noticed this odd property of large eye shapes.
> 
> Treat the eye shape as a graph.  Each empty point is a vertex, points
> adjacent on the board are adjacent in the graph (draw the intuitive
> graph).  The critical poin to play on each of the undecided eye shapes
> is a cut vertex in our graph.  In other words, it's an 
> articulation point
> between two biconnected components of the graph.  If this 
> point is removed,
> the graph is separated into two, or more, unconnected graphs.  Playing
> on this point is important if no other eyes are available.  It seems
> that a similar methods can be used to find ko threats, but it's less
> reliable, and more complicated.
> 
> The reason I found this interested is that there is an 
> effecient algorithm
> for finding the cut vertices of a given connected graph.  This allows
> one to ignore specific properties of the shape in favor of 
> more general
> ones.  This allows me to avoid using pattern recognition, 
> which is good
> since I don't know anything about it.
> 
> I'm guessing others have already notices this property, but I 
> wasn't able to
> find any literature.  Thought I'd bring it up so someone 
> could point me
> in the right direction.  Thanks!
> 
>              -Tyler Sellon
>