Don Dailey 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 disagree with it. The system you mentioned earlier (YBWC or Jamboree
search) would work fine here in avoiding any unnecessary work. The fact
that you don't know for sure in advance that the tree is perfectly
ordered does not actually change anything, since you work from the
assumption that it is anyway (that's even true in practise!).
You simply always split after you have searched the first move. In a
perfectly ordered tree, there will be no beta cuts and no alpha updates,
so there will be no wasted work. But there will also be no perfect
scaling because of critical tree issues.
This system will work reasonably well on a real, non-perfectly ordered
tree, and will not waste work in a perfectly ordered one.
(All assuming no hashtables)
--
GCP
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
