I want to correct my statement in view of a private discussion with Gian-Carlo. It turns out that in theory, with a perfectly ordered search tree, Gian-Carlo is correct that a parallel alpha beta searcher would search the same number of nodes as a serial searcher.
It's not what David Fotland was talking about and not what the intent of my response was to him, but I DID make a technically inaccurate statement because I was only right in the case of actual real life programs that do not have perfectly ordered trees. It turns out that a hypothetical program with perfect move ordering would be inefficient for other reasons, but they would not do "wasted work." So my correction to the statement I made is this: 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. So the point is that real programs do not have perfectly ordered move trees and if they did, they still wouldn't speed up in linear fashion with the number of processors. - Don On Mon, 2008-08-11 at 23:45 -0400, Don Dailey wrote: > On Mon, 2008-08-11 at 20:39 -0700, David Fotland wrote: > > Yes, my alpha-beta searcher still has the big slow evaluation function > > (about 50 to 100 evaluations a second). > > > > When I get some free computer time I'll put it on the 19x19 server. I > > think it will be much closer to the 1 cpu uct many faces than to the older > > version 11 many faces. > > > > Uct also has the advantage that it is much easier to use with multiple > > CPUs. I know parallel alpha-beta exists, but my evaluation function is not > > designed to be thread safe. If I put a big lock around it, there will be > > almost no SMP scaling, since almost all the time is in the evaluation, not > > in the search. > > This is not the case with alpha-beta. With additional processors, > alpha-beta always does wasted work, and the more processors the more > wasted work. It still always benefits from additional CPU's. > > - Don > > > > > > David > > > > > -----Original Message----- > > > From: [EMAIL PROTECTED] [mailto:computer-go- > > > [EMAIL PROTECTED] On Behalf Of Don Dailey > > > Sent: Monday, August 11, 2008 8:31 PM > > > To: computer-go > > > Subject: RE: [computer-go] Re: mogo beats pro! > > > > > > On Mon, 2008-08-11 at 20:10 -0700, David Fotland wrote: > > > > Sorry, but I can�t let this statement go past. The go programs in > > > the > > > > 90s did local search, but not much global search. For example Many > > > > Faces did a one ply global search, with a variable depth quiescence > > > > search. I added an alpha-beta search to Many Faces last year, and it > > > > made a huge improvement in strength. So it is not true that > > > > alpha-beta pruning hit a roadblock. > > > > > > > > > > I never doubted alpha-beta but when you say alpha-beta and GO in the > > > same sentence, people automatically believe the program is going from > > > 99% evaluation to 1% evaluation and 99% stupid. In fact you are still > > > spending most of your time evaluating positions. > > > > > > I'm still not convinced that you can't make a strong alpha beta GO > > > program if you have some imagination. It cannot just be a converted > > > chess program, it has to be different, but still alpha beta at heart. > > > It would have to be extremely selective. > > > > > > - Don > > > > > > > > > > > > > > > > > > > > > > > > For me, the big advantage of UCT/MC is that it eliminates the huge, > > > > slow, buggy evaluation function. Simple playouts are much much > > > easier > > > > to make bug free. Bugs in the evaluation function caused many > > > losses, > > > > and are almost impossible to eliminate in traditional programs, since > > > > the evaluation functions are so complex. > > > > > > > > > > > > > > > > David > > > > > > > > > > > > > > > > > > > > > > > > It seems that alpha/beta pruning hit a roadblock a long time ago in > > > > go. Now we have MC... which as you increase the number of samples.. > > > > you start to get closer to an equivalent alpha/beta. But... there are > > > > still huge groups of samples that are not checked... and if you want > > > > to somehow prove you have the best move... how will you do it? Will > > > > you make the sample size equivalent to the number of possible > > > samples? > > > > How will you do this practically? You can only state with a certain > > > > confidence that you did make the best move and this would be bound by > > > > our computational resources. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > _______________________________________________ > > > > 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/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
