Re: Shallow Or Deep Search?

[David Fotland <fotland@xxxxxxxxxxxxx>]

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.

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.

David

At 10:03 AM 4/23/98 +0100, P.J.Leonard wrote:
>David Fotland wrote:
>> 
>> For tactics I go deep.  But the evaluation is very simple: just
>> count liberties, 2nd order liberties, enemy nbrs with 1 or 2 liberties.
>> I guess most tactics reading has at least one line of 20 ply or more
>> deep.
>> 
>> On full board, in quiet positions I only look one ply.  In busy positions
>> I look as deep as needed to find quiet positions (up to about 9 ply).  I
>> only do about 100 evaluations, so the deep searches are very narrow.
>> 
>> David
>
> Does your full board evaluation search use your tactical engine at
>candidate nodes
>or is your tactical search limited to local evaluations from the root ?
> 
> cheers Paul.
>
>