|
The
searchers are completely independent at the moment. The life and death
search is run first, before the full board alpha-beta search. Its results
are used for some of the move generation for the full board search. I plan
to integrate the life/death and full board search, so the full board search can
use move sequences proven good by the life/death search. Today the
life/death search result just provides moves for the first
ply.
Local
tactics is very fast and has only 2 goals, remove stones from board, or 5
liberties/2 single point eyes. It operates on blocks, and only uses a
small subset of the board data, mostly data that is incrementally
updated.
LIfe/Death operates on groups and uses the same evaluation function as
the full board search, which understands eyes, conenctions, running, etc.
The full board evaluation calls the local tactics module for status on blocks as
part of the group strength evaluation.
Actually, I don't try to prune bad moves. I try to just generate
good moves. Going wider means making the move generator generate more
moves, which usually means writing more code, or adding more
patterns.
David
Interesting. I wonder to what
degree if any these searchers are integrated.
David Fotland wrote:
Searching is clearly the key to strong go play. Many Faces has three
searchers in it.
A fast alpha-beta searcher for local tactics that decides if a block can be
captured or
get 5 liberties/two eyes to escape.
A full board alpha-beta searcher.
A best-first search life and death module.
When is the best-first life and death module used vs. the
local tactics deciding if a block can be captured or can escape. Are
these results similar?
Neither alpha-beta searcher uses iterative deepening since the search depths
are so irregular.
The tactician looks typically 5 ply and up to 80 ply deep, with a budget of
a few hundred nodes
per search. It has a transposition table, and it remembers the best move at
the root from move
to move, along with a list of board points that invalidate the search, to
reduce re-searching time.
The full board search looks 1 to 30 ply deep, with a budget of a few hundred
nodes. The tree near
the root is taken from patterns or joseki library, and can be 1 to 20 or so
ply deep. Then comes
a local quiescence search, then a global quiescence search.
Your node count budget seems very low, which implies you
must do extreme pruning and look at only very few moves from the move
generators. Is there a reason you can't let it be a bit more free to
search broader with todays hardware?
Have you ever considered combining
tactical and full board, for example, the full board searcher using local
tactical move sequence results from the tactical searcher (acting as a move
generator) as its "nodes" to expand and search on? This would be one example
of what I would call a multi-level search.
I don't use null move because the evaluation and move generators understand
threats already.
The best first search is similar to PN search except that it uses
probability of success from
the move generator rather than number of generated moves to pick a node to
expand.
Most of my time goes into tuning the move generators.
Are the move generators using hand-tunded pattern
recognition and some kind move-ordering?
Maybe the move generators are
hindering the searches ability to find appropriate tactical sequences in some
situations.
Regards,
David
-----Original Message-----
From: computer-go-bounces@xxxxxxxxxxxxxxxxx
[mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of Matt Gokey
Sent: Tuesday, December 07, 2004 11:10 PM
To: computer-go
Subject: Re: [computer-go] Learning : was Chess programs
versus go programs
Vincent, I don't necessarily disagree with you (about
search). As you recall in my message, I summarized my point
like this:
There is little question in my mind that searching is a key to
computer-go just as it was in chess. It may not be the
same kind of
search (muti-level for example), and the evaluations
(including life
and death) may not be as easy but I think its the most promising
direction to pursue in combination with pattern based concepts for
move generation and help in evaluation.
So, the search technique is primary, of course paired with
other things including solid evaluation. Pattern or rule
based module components could be hand coded, or auto
generated/learned, or even coded by a 1000 monkeys as long as
they work reasonably well. But I've done enough hand tuning
to know that intuition after a few iterations is as often
wrong as it is right. There is a lot of trial and error and
guessing, albeit educated guessing. Each method has its pros
and cons. I'm well aware that you don't see value in
automated learning or pattern harvesting. And I certainly
don't expect any learning system to "beat" human learning
capacity. That's not the goal or the expectation, however.
There is something appealing about the objective and
statistical nature of the pattern harvesting technique that
Frank has developed over the ad-hoc and "expert" tuned
pattern/rule sets commonly used. I would not discount it as
a useful part of a go-playing program. As Frank has said
it's designed to be a better Joseki/Fuseki database, not the
holy grail. There is nothing preventing combining it with
other modules using other techniques for handling some
tactical issues, local search, ladders, ko fights, life/death
analysis, etc.
You seem to have a tendency to try to frame things as black
and white only, then attack the extreme case, when no-one is
really talking about the extreme case.
Regards,
Matt
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/
|