On Tue, 2008-08-12 at 08:49 -0700, terry mcintyre wrote: > >From the wikipedia: > > > Implementations of the MTD(f) algorithm have been proven to be more > efficient (search fewer nodes) than other search algorithms (e.g. Negascout) > in games such as chess[1]. > However, in practice, MTD(f) has some issues such as heavy dependence > on the transposition table, search instability, and many others. > Therefore, most modern chess engines still implement Negascout, which is > considered by many chess programmers to be the best search algorithm in > practice.
I've never been able to beat MTD(f) in my own chess programs. There are some issue's as you say, but I don't think it has been written off entirely. It's still at heart just an aspiration search, like PVS or negascout. - Don > Terry McIntyre <[EMAIL PROTECTED]> > > > “Wherever is found what is called a paternal government, there is found state > education. It has been discovered that the best way to insure implicit > obedience is to commence tyranny in the nursery.” > > Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] > > > > ----- Original Message ---- > From: Jason House <[EMAIL PROTECTED]> > To: "[EMAIL PROTECTED]" <[EMAIL PROTECTED]>; computer-go > <computer-go@computer-go.org> > Sent: Tuesday, August 12, 2008 8:17:35 AM > Subject: Re: [computer-go] Re: mogo beats pro! > > On Aug 12, 2008, at 10:44 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > > > We need to define terms so we don't end up arguing about something we > > probably agree on. > > > > Here is my assertion (which I admit needs to be checked): > > > > Given perfect move ordering, but not a-priori knowledge of this, a > > parallel program will search more nodes on average than a serial > > program. And more processors will "waste" more work in this sense. > > That's my definition of "wasted work." > > > > I'm sure there are also synchronization issues and other overheads, > > but > > let's just deal with the tree size. I think you agree with this, > > but > > I'm not sure. > > > > I have to run but I will try to dig up a paper on this later today. > > > > - Don > > This focus on bashing alpha-beta seems rather unjust. Any best-first > algorithm, including UCT/MCTS will have waste since spreading work > introduces latency and what's best becomes unclear. > > I'm not trying to throw in a vote for how much waste occurs with > different algorithms but I will say that looking at MCTS scalability > in terms of playouts per second is like looking at nodes evaluated per > second with alpha beta. The statistics and scalability arguments are > fundamentally flawed. > > PS: I wonder how well alpha beta's cousin MTD(f) scales. I know chess > abandoned it because of its memory usage, but I think it's easier to > distribute... > > > > > > > > On Tue, 2008-08-12 at 16:26 +0200, Gian-Carlo Pascutto wrote: > >>> On Tue, 2008-08-12 at 15:40 +0200, Gian-Carlo Pascutto wrote: > >>>> Even in the theorethical case of a perfectly ordered game tree? > >>> > >>> I'll have to check my facts, but I remember seeing actual numbers on > >>> this. It has something to do with the minimial tree and it was a > >>> proof > >>> think that alpha-beta could not be fully parallel. I will see > >>> what I > >>> can dig up. > >> > >> This is very different from being forced to do wasted work. > >> > >> To put it extremely, I can run the entire problem on just 1 CPU. > >> No work wasted. No speedup either, but hey, no work wasted :) > >> > >> If you split off work only when you are positive it will not get > >> aborted, you will still get a speedup, but it will be limited by > >> the critical tree (or minimal tree or mandatory work...I forgot the > >> name). > >> > >> I think you have this last case in mind. > >> > >> In practise things are very different from theory. You would rather > >> do very questionable work (which is likely to get aborted) rather > >> than have a CPU sit idle. > >> > > > > _______________________________________________ > > 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/
