TalkChess.com

[Vincent Diepeveen]

Srdja,

Diep already since 2002 implements YBW in a total SMP way, there is no master and there are no slaves. Everywhere it can split, in fact it can split simultaneously at the ATOMIC same time at several spots in the tree.

You can prove of course that otherwise it wouldn't run on a 512 processor supercomputer very well if you do master-slave relationships inside the search.

In a well implemented YBW search the search is only for a very short time frame at just 1 core until you divide it over the rest, after that the same thing happens in parallel everywhere. If you do *that* also as a master slave, like Crafty/SF and most YBW implementations do, that won't work well at a supercomputer of course.

Crafty avoids some problems for more than 4 cores there by splitting very little. Bad for speedup however. In diep i quickly split and happily keep doing that.

You can also mathematically prove that the concept of YBW, not necessarily to the full implemented, but at least the starting concept, is a manner to preserve the branching factor *a little* (not fully) and so far no other algorithm it's easy to prove that for and no other algorithm so far exists that's doing exactly that.

What we do know however is that, take my cluster as an example, aborting cpu's there takes microseconds as a minimum. The switching inside a GPU goes way faster than that. You can abort it in nanoseconds in theory.

In practice of course you need to do that very little at cpu's, so effectively it's milliseconds at each cpu, yet it can be microseconds at GPU's.

At gpu you just accept the overhead of cores that searched without having a job and each X nodes redivide search tree within 1 SIMD.

Another major advantage at gpu's, is that it's nonstop alternating each few cycles different threads, so you can do at gpu's a few things you can't do at CPU's which avoid some of the damage done by running that many threads

CPU's really suffer everywhere from the runqueue latency which fires each 10 milliseconds. In reality it's slower than that of course.

GPU's do not have this problem at all. Within 1 SIMD in fact you have complete deterministic search in fact. That's a HUGE advantage when debugging for performance and bugs.

You shouldn't ask yourself at a GPU: "can Monte Carlo with UCT play chess a tad?" as it will be 800 elo worse of course (i picked an arbitrary elo difference that it's worse. Could be 1000, could be 500, it's too much in short). The question is simply: "How do i get YBW to work in a fast manner without too much of an overhead?"

Same thing for Go of course - UCT there is a joke as well of course. Just because they don't know how to search there and some of the 'top engines' at the time were forward pruning even in the root, the UCT type engines won suddenly.

UCT is overrated in that sense. UCT is the most trivial form of selective search that isn't brute force, yet requires huge overhead.

At GPU's already in advance going for something total inferior is not a rather good idea.

My advice at the gpu's would be: whatever the hell you do on it, even if it is a tiny thing, try to get good performance out of that tiny thing.

The fact that you can very quickly run different kernels there is a huge advantage, which is total impossible at CPU's. Use that.

By accepting overhead you reduce the inefficiency.

But now i really have posted enough on this subject.

GPU programming is not for beginners, that's the whole problem.