[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: computer-go: Graph Theory


I use this heuristic in Many Faces as well (the eye point with
the most adjacent points also in the eye). But it's not the
only heuristic by far. In some shapes the eye point which is
an atari is more important. In big eyes there are often more
than one point with the largest number of adjacent points. In the
corner it often helps to break such ties in favor of a 1-2 point.

My approach is to extract a set of features of the eye, and
classify by the features. Features include things like

size,
perimeter,
linear or not (all eye points have exactly two neighbors)
number of ends (points with stones on 3 sides and an eye point on the 4th).
internal atari
internal point on the corner
internal point with the most adjacent eye points ( a key point) (and how many)
etc.

In general I avoid directly pattern matching the shape.

so I might have code like:

if ( eye.size == 5 && eye.num_ends == 1 ) { // a bulky 5 shape
if ( /* the point at the end is a false eye */ ) // look at the diagonals. if enemy controls 2, it's false
eye.num_eyes = 1;
else {
eye.num_eyes = 1.5
eye.add_vital_point ( eye.key_point );
}
}

It seems simple, but the special cases keep adding up, and the total eye classification
code is about 4000 lines of C, including comments and whitespace.

The actual bulky 5 code is quite different, and is here. There are only two special cases,
an enemy stone on the vital point, and 4 enemy stones inside with none on the vital point.
In this implementation, size has already been reduced by one if the end is false:

// 8 is one eye
char minp[] = { 0,0,0,0,0,8,8, 8, 8, 8, 8, 8,16,16,20 }; // eyes if opponent moves twice
char valp[] = { 0,0,0,0,0,8,8, 8, 8, 8,16,16,20,20,24 }; // eyes if opponent moves once
char potp[] = { 4,4,8,8,8,8,8,16,16,16,20,20,24,24,24 }; // eyes if I move first

eyemin[rn] = minp[perim]; // perim is the perimeter of the eye shape
eyeval[rn] = valp[perim];
eyepot[rn] = potp[perim];

...
else if(perim == 9){
...
else if(size == 5 && board[bestvit] != NOGROUP)
eyepot[rn] = 8; /* bulky 5 with stone already on the vital point */
else if(size == 5 && !deadvital && fullperim && deadinside == 4)
eyeval[rn] = 16; /* bulky 5, almost full, can't play on vital */
}

There are about 50 such special cases for classifying completely surrounded multipoint
eyes. Most of the code is handling the more difficult eye shapes.

David

At 12:50 PM 5/2/2002 +0200, you wrote:
In the 8-point big eye

*--*
|  |
*--o--*
|  |  |
*--*--*

the vital point 'o' is not a cut vertex.  A heuristic I've been using
for vital points in big eyes is "the point with the most liberties".
Any counterexamples to that?

- Nici.

--
    Dr. Nicol N. Schraudolph               http://www.inf.ethz.ch/~schraudo/
    Institute of Computational Science             mobile:  +41-76-585-3877
    ETH Zentrum, WET D3                            office:      -1-632-7942
    CH-8092 Zuerich, Switzerland                      fax:            -1374

David Fotland