>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. 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/