Re: [computer-go] An [open] question on game tree search theory

[Erik van der Werf <E.vanderWerf@xxxxxxxxxxxxx>]

Antti Huima wrote:

> is just a random number attached to every node in the tree, search
> is meaningless---any min-max value over the tree is just a min-max value
> of random numbers, and hence worthless.
Not worthless, it is well known that in many games minimaxing random 
evaluations is stronger than randomly playing moves. Adding noise to 
your evaluation function can improve performance because it will favor 
lines with more possibilities to achieve an equal value. (i.e., it is 
better to have 3 different options to win than only 1, unless of course 
when you're absolutely sure).

> It is common knowledge that increasing search depth when evaluation
> function is kept fixed raises game play strength. But what is the
> mathematical reason for that?
This is not necessarily the case. It is theoretically possible that 
deeper search decreases performance.
See: http://www.cs.umd.edu/~nau/papers/pathology-aaai80.pdf

My idea about the whole thing is simply that some positions are 
difficult to understand (mostly because of tactical complications) 
without looking ahead, whereas other positions can be understood quite 
well without further expansion of the tree. Which positions require 
deeper search directly depends on the confidence you have in the 
evaluation for that position, and the probability that it will have any 
effect on your move selection in the root.

Erik


_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/