Re: Using partial plys

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

I haven't published anything yet, although I started writing
once, but ran out of time.  I'll describe it in detail
sometime.  I have pretty good move ordering using my move
generation heuristics, so I hate to throw all that information
away in PNS.

And I am trying to solve a different problem.  I want to find the
highest confidence move(s) to solve the problem given a fixed search
time.  I can only explore a small part of the tree, but with
good cantidate move ordering and cantidate move evaluation.

For example, if a group has 1.5 eyes, and there are 2 moves to
make the second eye, and 5 more moves that threaten to make a
second eye, but don't actually make it, and 10 other moves that
make some shape, but don't make eyes directly, it's pretty clear
that I have to look at the two eye making moves first, even if
they have bushier descendents.  If the first two moves don't work,
I'm pretty confident that this line should be abandoned and I should search 
elsewhere until I have no moves left anywhere in the tree that
look like they make two eyes directly.

If my move generator is good, I will try the actual best line first, then
spend 
the rest of the time increasing the confidence in the result by trying
all possible refutations and proving that each doesn't work.  I'll
try the most likely refutation first, rather that going depth first or
best first.  Usually I only get through a few refutations before I run out
of time.  A typical life and death search only has about 20 or 30 positions.

I think PNS is good in search spaces where there is a lot of variation
in the number of moves generated from one node to another.  It focusses
attention in the forcing sequences.  The trouble with go is that there
may only be one move that looks good, but there are 20 other moves that
are very unlikely to work.  You can't ignore the other 20, since there
are always hard problems where the oddball move is the right answer.

David

At 09:33 AM 3/22/99 +0000, P.J.Leonard wrote:
>David Fotland wrote:
>> 
>> Many Faces uses best first search without depth limitation for
>> life and death searching.  (well, actually there is a depth
>> limitation as I implemented it, but lines can end at any depth,
>> and most lines don't reach the depth limitation.)
>> 
>> It's not proof number search, since PNS only uses the number of
>> reasonable move at each node to guide the search. 
>
> Actually the information is the number decendent nodes that need to
>be proved in order to prove the node in question. It also uses the
>number of
>nodes required to refute the node. The initial proof/refute guess can
>use heuristics.
>I also inceremental expand nodes which can be used to add the most
>promising
>nodes first. This does something to get around the problem you are
>hinting at.
>
>> My move generator
>> has much better move confidence values that it uses instead.
>
>  Is this published ?  What information is stored for each search node
>and how is this information used to update ancestor nodes and direct the
>search. 
>Sometimes it is better to explore a less promising node if you know it
>will only
>require a little work to prove/refute compared promising nodes that
>would require much work
>to prove because there are so many oponent responses to refute.
>
>
>-- 
> Cheers Paul.                                        
>               __         __                  
>              (  ) _ - _ (  )                 
>               ~~         ~~                  
>                (  0   0  )                   
>----------ooO----(       )----Ooo------------ 
>          '''     (     )     '''             
>                   (   )                      
>                    \ /                       
>                   ~~O~~                      
>
>  Tel: +44 1225 826108
>  Fax: +44 1225 826305
>snail: P.J.Leonard
>       Applied Electromagnetic Research Centre
>       Bath University,
>       BATH, UK   BA2 7AY
>
>