Re: [computer-go] False Eyes

["Paul Tabor" <paul@xxxxxxxxx>]

Christoph

Considering this further, there are a number of other things to take into account.

I believe you are right on point 1 - I had misunderstood, and a region with only one cluster is a real eye even on the edge.

On point 2, I believe I have a counter example, illustrated (redundantly) with enemy stones placed at the appropriate cutting points:

.........
.xxxoxxx.
.xoo.oox.
.xo.ooox.
.xoo.oox.
.xxxoxxx.
.........

The three 'eyes' here all exhibit the property that two of their clusters are linked by another region; but clearly there is only one real eye.

Similarly, in the following example, both 'eyes' meet the criterion but only one is real: 

.oxx.
o.ox.
xoox.
xxxx.
.....

The is the counter-example I was suggesting for point 3:

..........
.xxooxxxx.
.xo..ooox.
.xo..o.ox.
.xxooxoox.
.xxxxxxxx.
..........

No matter who plays first, it is impossible to avoid elimination of the 'false' eye (assuming optimal play).

Regarding enemy stones, surely they need to be brought into the model as otherwise it isn't possible to evaluate a lot of potential leaf node positions. The idea presumably is that it is ok to ignore them, as an opponent continuing to place them inside a real eye cannot fill the space entirely when the group has another real eye. However, the possible creation of eyes within eyes should be considered.

The following is ok, as there are two real eyes:

x.o.ox.
x.ooox.
x.oxx..
ooox...
xxxx...

but this has only one real eye:

.xo.ox.
.xooox.
xxoxx..
ooox...
xxxx...

I'm also a little unclear on how it is possible to determine that regions are linked for the purpose of counting eyes when they are do not share a common cluster. For example:

.........
.xxxxx...
.xooox...
.xo.oxxx.
.xoo.oox.
.xxxo.ox.
...xooox.
...xxxxx.
.........

Regards

Paul

----- Original Message -----
From: "Christoph Vielhauer"
To: "computer-go"
Subject: Re: [computer-go] False Eyes
Date: Fri, 22 Jul 2005 06:56:19 -0700 (PDT)

Paul,

 

thanks for your reply. I must agree with your counter-example: Eyes with size > 3 are not necessarily "safe". 

But I don't want to give up too soon and still stick to rules 1 and 2. In your counter-example there are two clusters that are not linked via any other region, so the the eye would be considered false - which is obviously is.

 

To answer your last questions:

 

1. I have not taken into account the effect of  enemy-stones here. I am aware that in many cases it is possible to capture a "living" group, when one side is not playing optimal (say passing or playing elsewhere too many times). 

2. I only consider regions that are completely shut off.

 

My approach is these two aspects are questions of investigating the game-tree. I was looking to find rules that allow some kind of "static" evaluation of a group's status. Something to be done at the leafes of the game-tree.  

 

Christoph

Paul Tabor <paul@xxxxxxxxxxxxxxxxx> wrote:

First thoughts on this as a player - I haven't tried to code anything like this for many years:

1. This wouldn't work on the edge of the board - which is where many life an death situations need to be resolved. One potential cutting point is all it needs for the eye to become false.

2. Linking two or more clusters via another cluster might be considered to render them equivalent to a single cluster. E.g. 3 clusters where 2 are linked would behave as 2 clusters. However, captures need to be considered - it might be possible to place stone in the region linking them, thereby capturing a cluster forming the link. Again, there are different considerations at the edge of the board.

3. A counter-example: 8 stones could be arranged to face each other on 4 sides and surround a box 2x2. If enemy stones surround 2 adjacent sides, and wedge in on the outside at the 3 points where the 2 sides join each other and the other 2 sides, the eye can be completely destroyed by the enemy placing a stone inside where the 2 sides join.

Have you considered the effect of enemy stones in the regions? Also, what about eyes that aren't completely closed off, so don't form a region?

Paul

----- Original Message -----
From: "Christoph Vielhauer"
To: computer-go@xxxxxxxxxxxxxxxxx
Subject: [computer-go] False Eyes
Date: Fri, 22 Jul 2005 03:28:08 -0700 (PDT)

Hi all,

 

here is a proposal for a set of rules to tell "false eyes" from "real eyes". I am not yet 100% sure, if these rules do work or if there are any good for implementation in a go-program.  But I would be happy to know your thoughts on them.

 

Thanks and best regards

Christoph

 

============================================

First some terminology....

A  "cluster" is a set of connected black or white stones
A "region" is a set of connected empty vertices surrounded by one or more clusters or the border of the board.

 

Two clusters are "linked", if they share at least one common region. I will then say that the clusters are "linked via this region".

 

A "group" is a set of linked clusters. I consider "life or death" a property of a group.

When looking for eyes of a group, all regions belonging to this group are candidates.

 

Now the question: Which regions are real eyes and which regions are false eyes?

 

I propose this rule:
1. A region having only one cluster is a real eye.
2. A region having more than one cluster is a real eye, if any two of its clusters are linked via another region. (the region in question does not count).
3. A region of size >3  is a real eye in any case.

What would you say. Are these rules correct? Can you find any counter-examples?

 

Example 1: Take this position:
..........
.oooooooo.
.oxxoxxxo.
.ox.xx.xo.
.oxxoxxxo.
.oooooooo.
..........
o = white, x = black, . = empty

In the above terms, this position translates to:

..........
.00000000.
.01102220.
.01a22b20.
.01102220.
.00000000.
..........

0 = white cluster #0
1 = black cluster #1  linked to cluster #2 via region a
2 = black cluster #2  linked to cluster #1 via region a

 

a = black region #1
b = black region #2

 

Region a is a false eye: It has two clusters #1 and #2 and those are only linked via region a.
Region b is a real eye: I has only one cluster #2.

 

Example 2:

..........
.oooooooo.
.oxxooooo.
.oxaxxxxo.
.oxxoooxo.
.ox.o.oxo.
.ox.oooxo.
.ox.o.oxo.
.ox.oooxo.
.oxxo..xo.
.oxbxxxxo.
.oxxooooo.
.oooooooo.
.........

x = black, o = white, . = empty, a = empty, b = empty

Regions a and b both look like false eyes first because they have two clusters. But in both cases, the two clusters are linked via a different region, so both eyes are in fact real and the black group is alive.

 

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
>
>
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://www.computer-go.org/mailman/listinfo/computer-go/

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
>
>
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://www.computer-go.org/mailman/listinfo/computer-go/

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/