Not an expert on AB-search or UCT search but there's a subtle
difference I think. In AB search, if some processors have been
searching in a branch that is subsequently cut off, the work is 100%
wasted. In UCT there's no such black-and-white cutting. If you do
sampling in what then turns out not to be the optimal branch, further
sampling in the optimal branch may cause the UCT-value to drop to a
point where you'd otherwise start sampling the sub-optimal branch
again. So in that case you gain back part of the 'wasted' work.
I'm also inclined to think that the 'chunks' of work that are wasted
tend to be larger for AB-search than for UCT. But I'm not 100% sure.
Mark
On 13-aug-08, at 12:07, Don Dailey wrote:
I don't know the answer, but it wouldn't surprise me if it turned out
that the same theoretical issues exist for most reasonable tree search
schemes. So it is possible that UCT has no superiority over alpha-
beta
when it comes to making a parallel program. But I don't really know.
- Don.
On Wed, 2008-08-13 at 16:58 +0200, Magnus Persson wrote:
Quoting Don Dailey <[EMAIL PROTECTED]>:
Yes, UCT is easier to use with multiple CPU's because with
additional
processors alpha-beta programs do wasted work, unless you are
talking
about theoretical programs with perfect move ordering, which you
aren't.
Nice that all is clear about alpha-beta programs.
But... does not UCT with additional processors waste a lot of
simulations because what would be the optimal path through the search
tree depends on the threads that have not finished yet?
Some people reported that more processors helps a lot on large
boards,
whereas on smaller one there is not much gain.
It wouldn't surprise me if it turned out that UCT has no superiority
over alpha-beta when it comes to making a parallel program. It has
it's own issues, maybe they reduce to the same issue but just in a
different context? I don't really know.
- Don
-Magnus
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
