[computer-go] The global search myth

[Don Dailey]

David Doshay wrote:
> On 22, Nov 2007, at 9:35 AM, Don Dailey wrote:
>
>> This is one of many things in life that people refuse to believe -
>> regardless of the evidence.   ...
>> Instead,  people focused on highly selective searches.   In order to
>> play strong it was clear that computers would have to look 20 or 30 ply
>> ahead
>
> Our experience with SlugGo is that playing strength peaked only
> a few ply deep in global lookahead. Our conclusion was that for
> deeper lookahead the evaluation function that was used at the
> leaf nodes became irrelevant because the real game was off in a
> different branch than any of our expected paths. I would call our
> tree "somewhat selective" near the top, but increasingly selective
> deeper into the tree, so I am not sure how our results map onto
> your argument.
If your program is inadmissibly selective (you prune off a branch that
will never be recovered again)  then your program will peak out at some
depth well below perfect play.     You cannot recover if you prune away
an important move.     

There is something that the latest Monte Carlo programs have in common
with the best chess programs - and seems to be the right way to
structure a game tree search.    Your selectivity should be
progressive.     In order to do this correctly you must re-visit nodes
many times.  Chess programs do it iteratively and Monte Carlo UCT type
programs do it "best first" fashion.  So the decision to prune any given
move is a decision that is considered many times in the course of a
search - each time taking advantage of additional information.

I think you are exactly correct when you say the "real game was off in a
different branch" - it is a branch that get's pruned away forever in SlugGo.

I think you probably do get more strength with each depth increase,  but
the extra strength approaches some limit (that you are already very
close to) asymptotically.   Ok, maybe it's not technically asymptotic
because Go is not infinite, but you get the point.

- Don





>
> If your argument is that it is worth exploring the entire tree to
> whatever depth is possible, then our results are probably not
> really evidence to the contrary.
>
>
> Cheers,
> David
>
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>