Re: Shallow Or Deep Search?

[David Fotland <fotland@xxxxxxxxxxxxx>]

The tactical search is called from within the full board evaluation, so
I never apply the full board eval at tactical terminals.  The tactician
only uses a subset of the data structures, so the data is not even valid
at the end of a tactical search if I wanted to do a full eval. 

Have you done any tests of your life and death engine?  Mine is not very
strong.  Gets all of graded vol1 and about 90% of vol II, when I let it
have about 20-50 nodes per search.  This is mostly due to bugs in accurately
evaluating eyes, especially when they have dead enemy stones in them.

David

At 02:59 PM 4/24/98 +0100, P.J.Leonard wrote:
>David Fotland wrote:
>> 
>> The full board evaluation uses the tactician a lot:  to
>> evaluate tactical stability of strings, to evaluate some
>> connections, to evaluate the control of eye-diagonals.
>> 
>> Thus the full board evaluation is quite slow.  The tactician is
>> pretty fast - I'd guess about 20K nodes per second, but the full board
>> evaluator is maybe only 3-5 nodes per second.
>> 
>> So, I use two different search algorithms.  For tactics, I use
>> alpha-beta, depth first, without iterative deepening.  There is
>> no fixed depth.  Instead I fix a node count, and allocate the remaining
>> nodes among the subtrees at each ply.  I search more cantidate moves
near the
>> root and fewer cantidates deep in the tree.  This falls into the deep
>> search category.  Maximum search depth is 80 ply, and 20-30 ply is typical.
>
> Do you ever re-apply the full board engine at terminals of a tactical
>search ?
>For example if your candidate move was suggested for tactical reasons
>you could 
>examine the terminals of forcing sequences as if they where the seed of
>a search.
>
>> For life and death reading I use a different search algorithm that is more
>> "best first" in nature.  The evaluation is so slow that the overhead of
>> switching around within the tree is negligable.  The tree sizes are small,
>> at most a few hundred nodes, so there is no problem with keeping the whole
>> tree around.  My thinking here is to guide the search as much as possible
>> by things learned during the search.  Usually if you search a few lines,
>> you can discover the keys points, and try them next.  Similar to the
>> history heuristic used
>> in computer chess.  This is not a breadth first search since I search each
>> line
>> until I get a good live/dead answer.  I have good life and death heuristics
>> and
>> good move generation heuristics already, so PN search is not a good
>> cantidate for
>> me since it doesn't use this information to guide the search.
>
> My version of PN can use ordering information to incremental expand a
>node.
>This allows heuristically good moves to be explored first. You can also
>use heuristics
>to assign  the initial proof numbers (a high initial proof number will
>discourage the searching of 
>a node) but I found incremental expansion of the tree more satisfactory.
>
> cheers Paul.
>
>