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'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. But I did misunderstand you. I think we both agree that you cannot expect to utilize the full power of N processors and the problem gets worse with more processors. And of course even if ideal move ordering made it possible, you wouldn't need to do the search. - 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/
