[computer-go] The global search myth

[David Doshay]

Yes, in its present instantiation, SlugGo is inadmissibly selective.
In this case, we clearly see that after some small number, more
plies of global search result in worse play.

I do not have any expectation of perfect play, only improvement
over the present state of things.

Cheers,
David



On 3, Dec 2007, at 1:46 PM, Don Dailey wrote:

>
>
> 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/
>>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/