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?