> 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 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. -- GCP _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
