computer-go: How Many Faces decides on a move

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

Attached is a description I wrote about Many Faces' move selection algorithm.


David Fotland
Move Selection Stragey of Many Faces of Go.


Many Faces generates a set of cantidate moves and sorts them by hueristic value
estimates.  It evaluates a pass move, then evaluates moves from the sorted list until it 
runs out of the node budget.  It makes the move with the highest evaluation, which might be
the pass move.

Heuristic values and evaluations are in units of 1/50 of a point, and attempt to estimate the
score on the board, plus a strategic value, which represents future potential value, and the
amount of damage the opponent can do locally if this move was not made.  I use a resolution of
1/50 of a point so that the maximum score fits in 16 bits.

Moves are generated with variety of techniques:
 - A Fuseki database built from strong player's games
 - A Joseki library with about 60,000 moves
 - A pattern library with about 1700 patterns
 - Life and death reading of unstable groups
 - Tactical reading of unstable strings
 - C coded modules for fuseki extensions
 - C coded modules for attack and defense of unstable or weak groups
 - making ko threats
 - playing safe moves when ahead and risky moves when behind

Each point on the board ends up with a list of move generation records, each
containing the move reason (one of about 200), the heuristic value, and the strategic
bonus.  Reasons and classified by type (about 8 types), and values are combined
in a way that avoids double counting strategic bonuses or heuristic values.  For example,
if the lifea dn death reading suggests a move to kill a group and the pattern database suggests
the same move to attack the same group, only the largest heuristic value is used, since the
moves have the same purpose.  But if the fuseki extension suggests a move, which is also
suggested by a pattern as an attacking move, the values are added.

After the values are combined, the move cantidates are sorted by heuristic value.

Then a pass move is evaluated.  Good responses to the pass move are saved for
later use during the quiescence search.

Moves are tried in order, until a limit on nodes evaluated is reached.  This limit is
about 200 full board evaluations.   Up to half of these evaluations may have already been used
during life and death reading.  The total number of moves tried is not fixed, and may be as
little as 3 or as many as 75 or more.

Joseki and pattern reasons suggest move trees rather than single moves.   For these reasons
a single move suggestion will have several terminal positions to evaluate.  Moves
with other reasons are made on the board, generating just one terminal position.

Each terminal position is evaluated with a quiescence search.  This search is variable depth
and width, and does local responses first, then full board responses.  It is depth first, alpha-beta,
and a "take sente" option is evaluated at each ply.  The value of sente varies linearly from
7 points at the start of the game to 1 point in the endgame.