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/
