Re: computer-go: MF architecture

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

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?



At 04:25 PM 5/23/2001 -0400, you wrote:
> Yep, it's been quiet lately.  Lets see if we can get something going.  This is
> really just a question for Mr. Fotland, but it's right on topic, so I'll post
> it.  I've been reading through the archives and I'm trying to understand the
> architecture in Many Faces.  David, you have given some great descriptions of
> the techniques you are using in each main component, but I'm unsure how 
> they fit
> together and what calls what.  You speak a lot about these three things:
>
> Full board evaluator
> Life/Death reader
> String tactics
>
> So does the first one call the second one which calls the third one?  Or 
> is that
> totally wrong?
>
>
>
> -----Original Message-----
> From: Grajdeanu, Adrian [mailto:adrian.grajdeanu@xxxxxxxxxxxxxxxxx]
> Sent: Wednesday, May 23, 2001 2:03 PM
> To: 'computer-go@xxxxxxxxxxxxxxxxx'
> Subject: computer-go: Test. Please ignore
David Fotland