RE: computer-go: MF architecture

["Fant, Chris" <chris.fant@xxxxxxxxxx>]

In item 2, why are you doing full board evaluations during the life/death
reading.  I thought this phase would just return whether the group is
alive/dead/unsettled and suggest a move (if necessary) to accomplish the
result.  Actually, I thought the full board evaluation was doing life/death
readings, not life/death readings doing full board evaluations.  I thought
your life/death reader did a local narrow search to determine if the group
was killed or if it attained 5 "effective" liberties at which point the
search has become too big and is abandoned.  Maybe my info is outdated, I
have been reading some pretty old posts (several years old).


-----Original Message-----
From: David Fotland [mailto:fotland@xxxxxxxxxxxxxxxxx]
Sent: Thursday, May 24, 2001 1:19 AM
To: computer-go@xxxxxxxxxxxxxxxxx
Subject: Re: computer-go: MF architecture



The architecture is pretty simple:

1) try a pass move and do a full board quiescence search.  Record the best 
move(s) for the opponent, which will be used
         during full board quiescence search.

2) decide on strategy
         - adjust running factors and aggressiveness based on handicap
         - find game phase (opening, middle, endgame)
         - estimate size of taking sente
         - decide if ahead or behind
         - do all of the life and death reading (with my own original 
search algorithm), using up to about 100 full board evaluations
         - assign bonus values for attack and defense of all groups
         - these strategy values are used by the move generators

3) generate moves, with reasons, bonuses, and score estimates
         - fuseki database - single move
         - joseki database - sequence
         - pattern database - sequence
         - moves that work from life/death reading - single move
         - various other move generators (for running, surrounding, 
attacking, defending, filling dame, making big moves, junction points, etc)

4) sort the generated moves

5) until allocated time runs out (about 200 full board evaluations)
         - try a generated move or sequence, followed by full board 
quiescence search (using alpha-beta, depth first searching)

6) return the best move found (including the evaluated pass)


The full board quiescence search considers:
         - local tactical responses
         - local pattern responses
         - tactical and pattern follow-ups to the second-last move
         - global one move life/death/tactical moves
         - global moves from the pass search
         - taking sente at any time

It has variable depth, from 1 to about 7 ply.  Some of the sequences in the 
joseki database are 20 or 30 ply long, so
the full board search depth can be quite deep.

I've described the full board evaluation before.  Basically, I evaluate the 
strength of all groups statically, looking at eyes, connections,
relative liberty counts, running ability, etc, then evaluate the score, 
using radiated influence, and adding bonuses for all reasons
that were satisfied.

String tactics are used as part of the full board evaluation for string 
tactical stability and evaluating cutting points and control
of eye-diagonals.  For each move made, the program examines about 50K to 
300K tactical nodes.

The most complex and frequently changing code is the tactical move 
generator and the static eye evaluator.  Each is about
4000 lines of C.  The code to incrementally change the low level board data 
structures is moderately complex, but has been
stable for at least 10 years :)  The total size of the engine is just under 
50K lines of C.

David

Any other strong programs care to share their high level architecture?