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

RE: computer-go: MF architecture




The narrow search for 5 effective liberties is the tactical analyzer. It reads a
single string/block of stones to see if it can be removed from the board or not.

The life/death reader reads a group (set of connected strings), to see if it can
be killed or survive. The evaluation of life and death for a group is the same as the
full board evaluation. Actually the final territory evaluation is not needed, but it
doesn't take much time. I don't just read fully surrounded groups like some programs.
I read any group, so the group might survive by running away, or by making two eyes, or winning
a semeai, etc. It's too hard for me to figure out which parts of the full board evaluation can
be ignored in this kind of fight, so I just do it all. Since the full board evaluation is partially
incremental, and caches local results, it's not a huge amount of overhead. For example I can't
evaluate the ability to run well, unless I know the strength of the group on the other
side of the board that I am running towards...

David

At 04:57 PM 5/24/2001 -0400, you wrote:
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?
David Fotland