Re: computer-go: Graph Theory

[Tyler D Sellon <tsellon@xxxxxxxxxxxxx>]

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