Evaluation Function

    Keywords: Theory, Software

Kosh One of the most important (and difficult) parts of a Computer Go program is the Evaluation Function (EF). It has to assign scores to board positions. A simple, clear and efficient EF has not been invented yet! Unlike chess where the weighted count of the number of pieces on the board serves as a first approximation of an evalution function, the same method fails for Go due the value of pieces being strongly affected by their life and death status as well as usefulness in creating aji.

There are different kind of evaluation functions (EF):

  • Concrete EF: analyze board as a whole. This kind of EF is hard to implement, it usually requires a very big search tree. Neural networks applied to Go usually implements a concrete EF.
  • Conceptual EF: analyze different concepts of the game (string status, group status, connectivity, etc.) How do we relate these different concepts to the whole board?

Put your ideas for EF's here! I'm trying to get a good idea :)

See Also: Bouzy's Artificial Intelligence Survey at ComputerGoProgramming.

Bear in mind that I don't do programming and so I can't express myself the proper way.

It may be possible for a program to have values for both at the same time. Imagine compiling a database on the connectivity of every node on an empty board. This would be the concrete EF with references to it's connections (via a list of strings (node intersections)). Example on a 5x5:

Section>> Board Reference A5'

Connectivity listing to Node A1'

string#00 (A4', A3', A2', A1'); length=4; liberties=5 string#01 (A4', A3', A2', B2', B1', A1'); length=6; liberties=5 string#02 (A4', A3', A2', B2', C2', C1', B1', A1'); length=8; liberties=6 ...

Connectivity listing to Node A2'

string#00 (A4', A3', A2'); length=3 ...

Connectivity listing to Node A3' ... Connectivity listing to Node A4' ... Connectivity listing to Node B1' ... Connectivity...

Such a database would be huge -- although CPU cycles could be saved by finding cross-referencing nodes contained in the strings by using pointers. (written in an ordered format and/or given a value that can be quickly identified with certain nodes)

example pointer: "Contains A3' A4' A5' B3' B4' B5' C3' C4' C5' ..."> string# *blah blah*

The "length" data assigned to each string is useful in determining if such a move is miai or for determining urgentness.

Did you notice that Node A5' to Node A4', string#01 and #02 only vary slightly and make dumpling shapes which fill their own liberties? It is important to remember that multiple strings can be written for stone shapes that are exactly the same (which can be eliminated from the database). One reason why a computer won't make ugly dumpling moves will be correct use of the "length" value. If a stone needs to connect to a point on the board (including the destination placing), X many strings with "length" of X means that the connection is garanteed even if an opponent moves first.

Group status is a bit harder... I am trying to understand how to determine "life", or better yet -- knowing when a group is dead without actual liberties being reduced. For best results; it needs to be written in a way that doesn't use "patterns". An eye is a concept that follows primal logic. What is that logic in a larger context?

Evaluation Function last edited by on July 11, 2008 - 20:37
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Login / Prefs
Sensei's Library