On Tue, 2008-08-12 at 15:40 +0200, Gian-Carlo Pascutto wrote: > > On Tue, 2008-08-12 at 09:15 +0200, Gian-Carlo Pascutto wrote: > >> > >> Aside from that, it's not theorethically necessary for alpha-beta to do > >> wasted work (although it will in practise), and more CPUs can make the > >> program worse on any practical architecture (mostly due to locking and > >> memory bandwidth). > > > > What??? I think you need to catch up on theory. A parallel alpha beat > > searcher will always do some extra work that a serial searcher won't do. > > You cannot expect to get a 10X speedup with 10x more processors. > > Even in the theorethical case of a perfectly ordered game tree?
I just thought about this a little more - I'm starting to remember things. I think the point is that unless you have a-priori knowledge that the tree is perfectly ordered, you will waste work. It seems to me that if the moves are perfectly ordered and you KNOW that, then you could probably do the search (as a fun exercise) and get a perfect speedup (assuming of course ideal conditions, no overheads, etc.) You would use the "young brothers wait" algorithm and only spawn off work when you knew for sure that it couldn't be aborted. You could do the exact amount of work a serial searching program would do but do it in parallel. I'll look for the paper on this. I have one specifically in mind, a Supertech paper by Bradley Kuszmaul of MIT at the time and other follow up papers. - Don > > I understand that in practise this is unreachable. > I was talking about theory and explicitly stated so. > > It is most certainly not the case that this is an advantage of UCT > over alpha beta. UCT will either also waste work, or suffer a terrible > synchronisation overhead. > > I'm not attacking the point that alpha-beta can't scale perfectly - I'm > sure we agree on that one. I'm attacking the point that UCT would be > any better in this regard compared to alpha-beta. > > (In fact, as I stated, I'm willing to attack ANY argument based around a > state of the art UCT searcher being different from a state of the art > alpha-beta searcher.) > > You either suffer synchronisation overhead or do wasted work. > > You cannot avoid both in a high performance implementation of alpha beta > or UCT. > > > even if you could idealize > > this away, with a simulation for instance, you are going to have some > > processors have to abort work because a beta cutoff has invalidated the > > search some thread is doing. > > This only happens if the move ordering (and hence the split decision) > was wrong, which is a practical problem, not a theorethical one (with > perfectly ordered trees). > > The point about memory and locking is specifically a practical one. > You can very easily lose performance by adding more CPUs. > > We either talk about theory, in which case you speed up perfectly, and > CPUs always help, or we talk about practise, in which case adding CPUs can > slow you down, and you won't speed up linearly. > > But you cannot have both. > > I suggest we talk about practise, because that is actually interesting. > > In this case, adding CPUs can be dangerous and can slow you down. > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
