On Aug 12, 2008, at 11:49 AM, terry mcintyre <[EMAIL PROTECTED]>
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.
Distributing work at a high level would allow MTD(f)'s to do a more
localized search, which may alleviate the need for such large
transposition tables. Maybe the best method is to mix the top down
style of MTD(f) to drive localized alpha beta searches. I definitely
don't have all the answers.
Therefore, most modern chess engines still implement Negascout,
which is considered by many chess programmers to be the best search
algorithm in practice.
Modern chess programs also run on single core or very few cores.
Terry McIntyre <[EMAIL PROTECTED]>
“Wherever is found what is called a paternal government, there is fo
und state education. It has been discovered that the best way to ins
ure 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/
