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

RE: computer-go: board evaluation


There are many components to a static full board evaluation. Ultimately, you
are trying to estimate the final score, and perhaps estimate the safety or riskiness
or thickness of the position.

Before you can get the score you must find the group strength. so:
- string tactics
- connectivity analysis (to find larger groups of associated stones)
- static eye evaluation
- estimate of degree of surroundedness
- estimate of ability to win semeai against nearby groups
- estimate of possibility to get new eyes (for example by expanding along an edge)

Finally, you should estimate the solid and potential territory for each color.

For each of these there are several popular techniques. All strong programs do each of these,
but the algorithms are quite varied.

For eyes, most programs extract features and try to generalize. Features include the size,
presence of dead enemy stones inside, perimeter, solidness of the boundary, enemy control of
diagonals, etc. Some programs have large pattern databases to match common shapes. Many
Faces extracts features, and does very local one-ply evaluation after plays on vital points, using
about 5000 lines of code. I find static eye evaluation to be one of the more difficult areas.

For degree of surroundedness, some programs count second or 3rd order liberties. Some find
sector lines. Many Faces compares black and white influence patterns near each liberty.

For territory, some programs find boundaries and use computer-vision algorithms. Some radiate
influence (Many Faces), with a variety of influence functions. Some look at connectivity of each
empty point to nearby stones of each color (go4++). Others iterate on each point, adjusting the territory
value based on the surrounding values (Zobrist published this I think, and Goliath has a very fast
version of this algorithm). Some use and expansion and contraction algorithm. There is more
variety here than most other areas, and many algorithms seem to work good enough.

For connectivity, you can use a pattern database to recognize shapes. There is often some
tactical reading required. Connectivity is not transitive, so strong programs look at connections
in pairs. Many Faces only understands this issue when one of the connections is a kosumi or
1 point jump, and the other is kosumi, one point jump, or knight's move.

In many cases it is impossible to get an accurate answer, so programs estimate ranges, or
degrees of confidence. Often programs estimate not just one value, but separate values depending
which side goes first.


At 10:07 AM 5/16/2001 -0400, you wrote:
I would like to know what type of board evaluations people are trying.  The
most effective, I'm sure, begins with a local tactics searcher trying to
determine life/death status of groups,
Most programs use local tactics to determine string stability (can it be removed from the
board, or does it get enough liberties (4 or 5), or 2 eyes, or seki).

Life and death reading is so slow that few programs do it during board evaluation.

but I'm mostly interested in faster,
static evaluations.  I know there is the radiating influence idea.  What
else have people tried?

David Fotland