Clustering etc. thread

[Tony]

One of us is not getting it.

If at the root there are 30 moves, and after move 1 en 2 each has again 30 moves and we send those 88 positions to cluster clients, the total search will not speed up by 2.5 compared to a single client ?

Tony

[Vasik Rajlich]

Hi guys,

as you know I spent a lot of time on Go programs and part of this involved working with UCT and parallelizing it.

I think few people realize it because there's not many people working on both chess and go, but a strong implementation of UCT and alpha-beta with heavy pruning and LMR are much closer than one would expect, or at least, they are converging.

Very simply explained, UCT switches between exploiting the best move (extending the mainline) and exploring alternates. I've found (and so did some of the other top teams) that UCT is the strongest when you do not explore at all, but just keep hammering on the mainline until the score drops below an alternative. This is a somewhat counterintuivite result. As a result of this, despite the branching factor, top UCT Go programs search as deep or deeper as top chess programs.

In my opinion, this is almost the same as we ended up with alpha-beta, i.e. when using LMR heavily (e.g. with N=0), you just hammer the mainline until it fails low compared to another move (which might have a lot smaller depth), then you start hammering on that one, etc.

Now, in Beijing one of the top Go teams announced a result which blew my socks off. They were parallelizing UCT in several ways, some of which more fit for clustering than others. My amazement was about the result of 2 approaches:

1) Tree splitting, comparable to YBW/DTS in chess. This is what I had implemented for my Go program, and I was almost certain that this was "obviously" the approach that gave the most speedup.

2) Multiple runs. This exploits that fact that UCT has some randomness. They just ran the entire algorithm several times in parallel (with nothing shared!), and "added" the scores (this is something you cannot do directly with alphabeta, but methods to achieve the effect have been described in this thread).

Now, coming from computer chess, I would never have believed this (2) could work, because searching deep(er than your opponent) is what wins games, also in go, and multiple runs obviously doesn't help you search deeper at all.

Unfortunately for me, the results were the opposite. The multiple runs system exhibits much better speedups (not just in NPS, but in strength) than classical tree parallelization.


Because of this reason, I have no problem believing that in a program that's pruning as insanely as Rybka, just searching non-PV moves with an open(er) window gives a strength increase much more than would be normally expected. (cue Bob here with this "we did that 20 years ago and it doesn't work rant")

The thing is that I think this means our SERIAL systems (LMR and UCT minus exploration) are suboptimal. But how to fix them? Or can we get closer to optimal speedups by making our parallel implementation fundamentally different from our serial ones?

Food for thought!

What were the UCT speedups for tree splitting and multiple runs?

It is quite possible that our serial searches are somehow too "structured" and not soft/stochastic enough. It is a little insane to build alpha-beta trees around 30-move main lines.

Vas

[Vasik Rajlich]

The lack of shared memory imposes new constraints on your search and changes the things you need to do. In particular, without shared memory, you need to split the search tree into chunks which will remain relatively stable from iteration to iteration.

Vas

I don't get why you guys are not doing shared memory on a cluster. You can't distribute all hash entries, but you can share the deep ones, which should be the most important. I'm broadcasting them over UDP... (which means there is no actual remote-lookup-latency on hash probes! of course you want a high-bandwidth network for this)

This debate about root splitting without shared memory was just a theoretical one. My actual algorithm is more complex than that.

In practice, sharing high-depth entries doesn't really change the situation that much. You want the full search state for whatever part of the tree you are searching or your performance will plummet. Try disabling the lowest-depth 98% of your hash writes in Sjeng and see what happens.

Vas

[Vasik Rajlich]

I _did_ an algorithm like that in 1983. I put it together in under 2 weeks and won the 1983 WCCC championship with it. And I _know_ how it works and how the PVs look.

Actually, I'd be curious to hear more about it. How did you split the root moves? Which moves got PV searches and which ones got scout (null-window) searches? What beta did you use for the scout searches?

I couldn't find anything useful in the public domain about splitting work without shared memory, except for the Cluster Toga algorithm, which wasn't really suitable for Rybka (among other things, it doesn't apply to analysis and would be useless for users).

Vas

What we did back then was more dynamic that that. I had the root move list sorted just as I do today (previous iteration node count). Processor 1 searched the first move with a normal aspiration window. Processor 2 did the same. When one of them reported back with a new best move, the alpha/beta value was shipped to the other processor, which would take a short "break", update all the bounds, and then check to see if anything will now cutoff where it didn't when we started. We then searched the root moves one at a time, whenever a processor finished a move it grabbed another (dynamic load balancing) until the list was gone.

We always did an aspiration-type search in CB, where the root window was very narrow, something like +/- 0.25 pawns, for the first move. At the time we were using PVS (this was something from the late 70's and was used by belle and ourselves as well as others) which is (I assume) what you mean by "scout" (which is not quite the same as PVS but close enough for discussion).

I should add that both the univac 1100 and Cray were both shared-memory. I'm looking at cluster-based search right now because of this 70 node 8-core cluster we have. I can search about 20M nodes per sec on one node, which gives a potential for something faster than deep blue (we could possibly hit 1400M nodes per second although there are great issues to overcome. But Hsu and I did talk a lot about his parallel search and I like his two-level approach (split at early plies among the nodes, each node splits at late plies among the local processors)...

Aha, thanks. Like many things, this won't work without shared memory. Without shared memory, if 'processor A' (to use your terminology) takes moves x at some iteration, it needs to take the same move at the next iteration as well.

Basically, without shared memory, you want to have the same units processing the same parts of the tree throughout the entire search. I agree with Hsu's comment - without shared memory, work needs to be split at or near the root.

Vas

ps. I use the term "scout search" to refer to any search with a zero-width window.

That's what I thought (scout search).

The way I am looking at splitting on a cluster is to use a "split hash table". I store the hash signature and node ID when I split, so that the same node searches the same sub-tree each time to take advantage of the hash, killers, etc. There are issues with this as the next iteration can greatly alter the shape of the tree and give one node a set of moves that are much harder to search than others, producing an imbalance. I'm working on sorting out the details for this kind of stuff as the code gets written...

That's right. You'll need to consider whether you want to change the shape of your search tree to maximize the stability of the work distribution (ie. the degree to which the same cluster units handle the same parts of the search tree).

This is where root splitting is special. Root moves have the unique property that they are guaranteed to require searching.

Of course, root splitting alone isn't the answer.

Vas

I'm working on the "two-level" approach, although I am also considering the more complicated issues encountered on a cluster that has NUMA (AMD) nodes. Because you also have issues on a single node dealing with trying to maximize local memory accesses...

But my current cluster approach (good way from working yet however) is to split everywhere (although not too far from the root due ot the overhead of a cluster split even with infiniband interconnect) but try to repeat with respect to which node searches which position so that at least the hash info they have will be as helpful as possible, even though it is way less efficient than a pure shared-memory "share everything" search.

My problem with this kind of algorithm is that it will start to choke when the search tree starts to change, which is exactly when you want to be efficient.

Vas

[Vasik Rajlich]

I don't buy the "this hurts Rybka" idea, because the cluster rybka is a joke. And a poor joke at that. There have been some decent cluster-based programs. But Rybka is simply not one of them.

Where did that come from ??

Vas

There is something of an explanation here.

I read this post and I can say 2 things.

1)I think that it is impossible to know the algorithm rybka is using based on output from a single position.

It is possible that something similiar that is not exactly the same is used
when some illogical moves that lose the queen are analyzed but this is not all the story and the algorithm is based partly on "split only at the root" and partly on another idea.

2)I remember that Vas said 100 elo based on testing at fast time control and I suspect that at fast time control you get clearly more than 50 elo per doubling so practically 5 nodes do not give 4:1 speed improvement but clearly less than it(maybe 2.5:1).

Uri

The effective speedup is probably somewhere between 2.5:1 and 3:1 for 5 nodes, which is what Lukas had when he tested all of this.

Now he's up to 9 nodes BTW

Vas

Can we stay in the real world? Splitting at the root can not produce a 2.5x speedup, when the best move at the root takes _way_ over 50% of the total search time. There is theory. There is practice. And there is nonsense. For the event I am talking about, this claim is "nonsense". You might get the uninformed to buy this stuff, but not someone that has been doing it for 30+ years now (my first parallel search played its first ACM event in 1978....)

By effective speedup I mean the time handicap you could give to the original entity and score 50%. So, even if you do nothing other than split at the root and if the first move typically takes 50% of your search time, you could still get an effective speedup of >2. Not that that's what Rybka is doing

Vas

Here's what you need to make that happen.

(1) you need to change your mind at least once at the root during the last couple of iterations. More changes is better.

Sure. If you're not changing your mind, it doesn't matter what kind of speedup you have.

(2) you have to hope that the hash information from the first move does not affect any other move. Fine 70 is a good example of where this can be a problem.

That's just life without shared memory. Any cluster implementation is going to have problems in a position like that.

I think you'd be very lucky to get a speedup of 1.5x with any number of processors, which is not zero of course, but it is not something that will make me quake in my boots either.

With infinite # of processors and splitting only at the root, you will get a lot more than 1.5x.

Vas

No program today have search that is good enough but in theory
if you have a good search the speed up may be smaller from splitting at the root for the simple reason that the value of 1.5x speed improvement is bigger than the value of one ply with no pruning.

I think that
some type of bad evaluation also can cause the speed up to be smaller
or even negative.

Imagine that you search with no pruning and extensions and no qsearch and imagine that you have an evaluation that gives no bonus for the side to move so practically you often evaluate even depth as better than odd depths(maybe it should be the opposite and I did not think about it but the idea is the same)

If you split at the root you may get depth 7 for move A and depth 8 for move B and prefer move B not because it is better but only because you searched to even depth.

This problem does not happen without splitting at the root because without splitting at the root you always get the same depth for all moves.

Uri

You are badly misusing terminology.

1. "splitting at the root" does not mean each root move gets searched to different depth. I split at the root in current crafty. that only means that I do a parallel search on the root moves as well as deeper moves, because this is a far more efficient way to search.

2. You are using what is called "unsynchronized search" where each node searched a different move (or set of moves) at the root, and when iteration N is done, N+1 is started without regard for how the other moves are progressing on other nodes.

this is useless.

How can you choose between depth 21, eval=+1.3, and depth 19, eval +2.5?? You can't. This has been tried in the past, by Newborn, by Schaeffer, and by others. There is no way to compute any sort of equivalence function so that you can decide which of the above is better. The depth 19 move might be even higher at depth 21. Or it might be way lower. The only way to discover this is to search both moves to the same depth. Anything else is beyond hopeless and is a coin flip. You can't even choose between depth 21, +1.5, and depth 19, -2.0, because by depth 21 the -2.0 score might be +5.0...

I can certainly choose and the simplest choice is to choose higher score is better.
depth 19 eval=+2.5 is better than depth 21 eval=+1.3 for the simple reason that 2.5>1.3

I believe that with relatively good evaluation it is not so bad choice(not that splitting at the root is good but it may give effective speed improvement of 2 or more than 2 assuming that all root moves are searched).

I may be wrong and the only way to know is by testing.

Uri

There is absolutely no doubt you are wrong. How many times have you seen a program search a move to depth N with a + score, then at depth n+1 the score drops off the map and it switches to a new move? If you believe what you wrote, why not stop your search when the eval gets to a good point? Why continue to search deeper?

As far as a speedup of > 2, it simply will not/can not happen. Amdahl's law says that the overall speedup for an algorithm is:

speedup = time(N) / T(P)

T(P) = sequential_processing_time + parallel_processing_time / N

where N = number of processors.

If the first move takes 50% of the time, and that is the usual case, then you absolutely can not get a speedup > 2.0. It is impossible. Except for those cases where the first move is not best. Now you search the second move. And it takes the same amount of time. So you do get a bigger boost there. But that only happens about 15% of the time. 85% of the time the speedup is going to be way below 2.0 no matter how many CPUs you use. And there is simply no way to escape the basic sequential property of the alpha/beta algorithm.

Of course the score may change but by the same logic you also cannot compare between scores at the same depths because the program may change its mind in later depth.

I don't see where this nonsense comes from. Two moves, different scores, equal depths. I most certainly can compare them. And choose the largest. But if the depths are different, and the scores are different, I can only flip a coin to choose one. Choosing the best is wrong. Choosing the deepest depth is wrong. Choosing one of the two moves with different depths is just a purely random choice.

You do not know the best move and you always guess based on information and hope to be right.

I trust the search to at least search the two moves in an equal way, so that the resulting backed-up scores can be compared. That's what minimax and alpha/beta is all about.

If it is not the case then you cannot also compare scores at the same depth because practically one move is searched to normal depth and another move is searched to smaller depth because of late move reductions.

It may be bad to compare score in different depth with
bad evaluation and no reductions but it is not the practical case(maybe it was the case 20 or 30 years ago).

Uri

It is still the case today. And I am amazed you don't understand why...

1)With late move reductions even searching to the same depth can be practically different depth so if you cannot compare different depth then you also cannot compare the same depth.

2)I think that an interesting experiment that everybody can do may be to test A against B when A search at fixed number of nodes without splitting the root(let say 100,000 nodes per move) and B search after every root move at 50,000 nodes per move.

B choose a move simply by comparing the scores without caring about the fact that depths are different.

I do not know if A wins or B wins and it may be dependent on the program but I see no reason to assume that it is obvious that B cannot win.

Assuming nodes are nearly proportional to time if
B wins then it suggests that splitting at the root can give speed up of more than 2:1.

Uri

Yes, exactly. I could not have said it better. This is even (slightly) better than the experiment I suggested above. Uri, you should build a cluster.

Of course, nobody is arguing that the best algorithm is pure root splitting. It's a very important building block, though. And data on this phenomenon (which I actually don't have) would be very interesting.

Vas

I suppose I could run this test easily enough. I could use 8 nodes and only split at the root, and modify how the search works so that each node just keeps searching (unsynchronized) until time expires.

Yes, that would be really good. You don't need 8 nodes, just do the root moves in sequence on one node.

And what I get would not be doable on a cluster because I would still have a fully shared hash.

Just clear the hash between root move searches.

Even better, try it both ways (with hash clearing & without). The difference will also be interesting.

Vas

[Vasik Rajlich]

I don't buy the "this hurts Rybka" idea, because the cluster rybka is a joke. And a poor joke at that. There have been some decent cluster-based programs. But Rybka is simply not one of them.

Where did that come from ??

Vas

There is something of an explanation here.

I read this post and I can say 2 things.

1)I think that it is impossible to know the algorithm rybka is using based on output from a single position.

It is possible that something similiar that is not exactly the same is used
when some illogical moves that lose the queen are analyzed but this is not all the story and the algorithm is based partly on "split only at the root" and partly on another idea.

2)I remember that Vas said 100 elo based on testing at fast time control and I suspect that at fast time control you get clearly more than 50 elo per doubling so practically 5 nodes do not give 4:1 speed improvement but clearly less than it(maybe 2.5:1).

Uri

The effective speedup is probably somewhere between 2.5:1 and 3:1 for 5 nodes, which is what Lukas had when he tested all of this.

Now he's up to 9 nodes BTW

Vas

Can we stay in the real world? Splitting at the root can not produce a 2.5x speedup, when the best move at the root takes _way_ over 50% of the total search time. There is theory. There is practice. And there is nonsense. For the event I am talking about, this claim is "nonsense". You might get the uninformed to buy this stuff, but not someone that has been doing it for 30+ years now (my first parallel search played its first ACM event in 1978....)

By effective speedup I mean the time handicap you could give to the original entity and score 50%. So, even if you do nothing other than split at the root and if the first move typically takes 50% of your search time, you could still get an effective speedup of >2. Not that that's what Rybka is doing

Vas

Here's what you need to make that happen.

(1) you need to change your mind at least once at the root during the last couple of iterations. More changes is better.

Sure. If you're not changing your mind, it doesn't matter what kind of speedup you have.

(2) you have to hope that the hash information from the first move does not affect any other move. Fine 70 is a good example of where this can be a problem.

That's just life without shared memory. Any cluster implementation is going to have problems in a position like that.

I think you'd be very lucky to get a speedup of 1.5x with any number of processors, which is not zero of course, but it is not something that will make me quake in my boots either.

With infinite # of processors and splitting only at the root, you will get a lot more than 1.5x.

Vas

Sorry, but no you won't. The math is simple and comes directly from Amdahl's law and the original alpha/beta analysis by knuth and moore, followed by the parallel analysis I did in the Journal of parallel computing. The first move takes 50% of the time. And that is going to be done on one processor. if you can somehow solve the "window" problem, so that you can search the remainder of the ply-1 moves in parallel with a correct alpha/beta window, then you can shrink those to the time required to search one of them. But you have no alpha/beta window, so all moves searched in parallel (ignoring the first move) are going to take about as long as the first move (each one will take that long) because you do _not_ yet have the alpha bound from the first move to let you get the quick cutoffs on the rest of the move.

Best case is 2x faster, since you could assume that any root move takes as long as any other when you do not have a good alpha bound. And what you can get "peak" is not going to be what you get "on average". >2x is just not going to happen except for rare cases. I have a position somewhere where you can get a 20x speedup like that. First move takes forever to find a very deep mate. Second move is a shorter mate in 1/20th the total nodes searched. Searching both at the same time finds the second mate before the first has even been "sniffed". But that is simply an exception. For the general case, 2x is the very best you can hope for, and it is not going to happen often...

I can give you a citation for the paper I wrote that uses the math from Knuth / Moore and extends it to cover alpha/beta in parallel. It is easy enough to understand and explains exactly why >2x is a rare case, not the norm...

The point is that that 2x is not the upper bound. You'll have 2x more time to dedicate to searching the best move and maybe 20x more time to dedicate to searching alternative moves.

Let's keep this mathematically valid. You already stated, and I agree, that the first move at the root for iteration N takes about 50% of the total search time. And it is quite often much more than this:

Here are a couple of examplles:

Code: Select all

               20->   3:22  -0.01   14. ... O-O 15. Bb2 f5 16. Bd3 c5 17.
                                    Qe2 cxd4 18. Bxd4 Qe7 19. Bxa7 Bxf3
                                    20. gxf3 Bxh2+ 21. Kxh2 Qh4+ 22. Kg2
                                    Qg5+ 23. Kh1 Qh4+ 24. Kg1 Qg5+ 25.
                                    Kh1 (s=2)
               21     5:01  -0.05   14. ... O-O 15. Bb2 f5 16. Bd3 c5 17.
                                    Qe2 Qe7 18. Rfd1 Rfd8 19. Nd2 cxd4
                                    20. Bxd4 Ne5 21. Nc4 Nxd3 22. Nxd6
                                    Qxd6 <HT>
               21->   5:11  -0.05   14. ... O-O 15. Bb2 f5 16. Bd3 c5 17.
                                    Qe2 Qe7 18. Rfd1 Rfd8 19. Nd2 cxd4
                                    20. Bxd4 Ne5 21. Nc4 Nxd3 22. Nxd6
                                    Qxd6 <HT>

First move at depth 21 took 1:39, rest of the moves took 10 seconds total.

Code: Select all

               20->   1:24  -0.03   14. ... O-O 15. Bd2 c5 16. Bxb7 Rxb7
                                    17. Rfb1 Qc7 18. Rxb7 Qxb7 19. Rc1
                                    Rc8 20. dxc5 Rxc5 21. Rxc5 Bxc5 22.
                                    Bb4 Nf6 23. Qa5 Bxb4 24. axb4
               21     2:40   0.05   14. ... O-O 15. Bd2 c5 16. Bxb7 Rxb7
                                    17. Rfb1 Qc7 18. Rxb7 Qxb7 19. Rc1
                                    Rc8 20. dxc5 Rxc5 21. Rxc5 Bxc5 22.
                                    Bb4 Nf6 23. Qa5 Bxb4 24. axb4 Qe7
               21->   2:55   0.05   14. ... O-O 15. Bd2 c5 16. Bxb7 Rxb7
                                    17. Rfb1 Qc7 18. Rxb7 Qxb7 19. Rc1
                                    Rc8 20. dxc5 Rxc5 21. Rxc5 Bxc5 22.
                                    Bb4 Nf6 23. Qa5 Bxb4 24. axb4 Qe7
               22     4:08   0.02   14. ... O-O 15. Bd2 c5 16. Bxb7 Rxb7

first move at depth 21 took 1:16, rest of the moves took 15 seconds. All you can get there is a speedup on that extra 15 seconds. You will barely run faster at all. Here is a third case where Crafty actually changes its mind (these are from the same game, consecutive moves to be fair. The following case preceeds the previous two.

Code: Select all

               18->   1:01   0.23   13. ... O-O 14. Rb1 Rb8 15. Qa4 f5
                                    16. Bc2 c5 17. dxc5 Bxc5 18. Bb2 Qe7
                                    19. Rfd1 Rfd8 20. e4 Nf6 21. Rxd8+
                                    Rxd8 22. exf5 Bxf3 23. gxf3 (s=2)
               19     1:34   0.31   13. ... O-O 14. Qc2 Nf6 15. Rb1 Ba6
                                    16. Bd3 Bxd3 17. Qxd3 Rb8 18. Rxb8
                                    Qxb8 19. e4 Be7 20. e5 Nd5 21. Ng5
                                    Bxg5 22. Bxg5 Qb5
               19     2:18   0.16   13. ... Rb8 14. Rb1 O-O 15. Qa4 f5
                                    16. Bc2 c5 17. dxc5 Bxc5 18. Bb2 Qe7
                                    19. Rfd1 Nb6 <HT>
               19->   2:18   0.16   13. ... Rb8 14. Rb1 O-O 15. Qa4 f5
                                    16. Bc2 c5 17. dxc5 Bxc5 18. Bb2 Qe7
                                    19. Rfd1 Nb6 <HT> (s=2)

First move at 19 took 33 seconds, next move took 44 seconds, rest of the moves are buried in the time for the second move. Here you might actually get a speedup of almost 2, assuming your split at the root algorithm is good enough to make sure those two moves are given to different clusters (there is no indication that they are the two best moves, the second never appeared in previous searches.)

So > 2x is simply not going to happen except in very rare cases. Most of the time, if you don't change your mind, you are looking at 1.1x or so as the above cases show. I have several long games I can post if someone wants to go thru them as I did above and compute the average speedup for the entire game...

It's not hard to do a simulation. Crafty A always plays its move after 10 seconds of search using his normal algorithm, while Crafty B spends 10 seconds on every single root move and then plays the one with the best score.

I would be curious to know the result here.

Vas

I assume you mean "pure best score" without regard to depth? I can probably pull this off easily enough.

I might even be able to find monty's old test results as he did exactly this on his data general "better-than-a-cluster cluster" years ago (he had a shared I/O bus that was way faster than net-based communication.

I would expect the split at the root version to win, because there is some performance to be gained, although there is some lost as well due to no shared hash. I'd expect the difference to be in the 20-30 Elo range based on the expected speedup. Remember, in many searches the best move is the best move for all searches, and the extra searching on other moves produces zero.

Bob -

yes, you'll want to take the best score without regard to depth.

The math you quote applies to the time available for the first move. That's different than total effective speedup.

Vas

[Vasik Rajlich]

Well it actually can if you use what GCP suggested.

Code: Select all

nodes = 1 << depth; // rough approximation based on ebf=2
prob = 1 / (1 + pow(10, -score/4)); // floating point score, see http://chessprogramming.wikispaces.com/Pawn+Advantage%2C+Win+Percentage%2C+and+ELO
ucb = score + k*sqrt(log(nodes)/total_nodes);
best_score = max(ucb);

The last line (choosing) can use some modification, but that's just a basic formula. GCP is the real expert there...

UCB only tells you what move to explore next (=to search deeper). There's no (mathematical) rule to pick the final move. But as hinted in an earlier post, you can do:

a) Pick the most explored (=deepest searched move). This works because UCB explores the best scoring moves most.
b) Pick the best scoring move. This works because UCB explores good scoring moves a lot, so if they quickly get a lot of depth if their score stays good.


The annoying case is the one I posted earlier, but you get a strong program no matter which of the above you do, though.

You should not just play the move with the best UCB, that's mathematically guaranteed to be a blunder once in a while.

It's not a hard problem, but it's easy to screw it up anyway. Take a look at the game Rybka vs the Baron from the last Beijing, and her move 25. Rxf6.

Now, in case of chess, if you split the set of moves equally between CPUs, each move is guaranteed to get pretty much the same effort spent to it. This might result in different depths, but who cares if the effort spent is equal? So, in the clustering-root-unsynchronised case, it seems totally obvious to me that you would just pick the best scoring move, ignoring depth totally.

Depth is a poor measure of search quality, time is much better.

Vas

[Vasik Rajlich]

I personally don't think there's that much potential in it, since you would always want to be searching the best evaluated (by UCB) move, not the "best out of the set of moves that we chose for this node at iteration 1 so we can have some hash table consistency".

Correct. I do agree with Bob that just splitting at the root looks like a dead end. I'm not terribly surprised Vasik is claiming better results than could be naively expected, because changing a null-window to an open window search can have some nice side effects, which was also observed by the guys parallelizing UCT. I wonder if Vasik wants to tell us what exactly he does with the windows when distributing moves.

But in the grand scheme of things it (=root splitting) looks like a dead end.

And in a lot of cases you want multiple nodes searching the same root move. I'm going the YBW-like route, though with DTS it gets _extremely_ complicated.

My cluster program also just splits the tree.

FWIW - I'm not claiming better results, I expect them based on my understanding of the issues.

Vas

[Vasik Rajlich]

In a worst-case on my cluster here, you can have 560 broadcasts per hash store since every processor will need to broadcast when it updates the hash.

I don't understand how you get to 560.

I do agree keeping system overhead low is a problem. At some point you see the OS networking stack using CPU...would be a nice thing for hyperthreading CPUs

I have 70 nodes, so I have 70 low-level splitters running at the same time. On each node, I have 8 cpus, and each one of those will be storing stuff into the hash, many at low levels. And they will need to broadcast. 70 x 8 = 560. yes, the traditional cluster has one cpu per node, but this is not a traditional cluster. I've run some simulations while planning and writing code and broadcasts were an issue. I had decided that lost packets were irrelevant and did not try to do a time-out / retry in the test code. And I could not determine how deep into the tree I can go before I turn broadcasting off. That will have to wait until I have working code, since it is impossible to estimate for the general case how many hash stores per second happen at depth N in the tree... and I suspect this is going to have to be dynamically adjusted during the game anyway as the tree goes from shallow/bushy to deep/narrow.

I have not decided that this is the best way either. The alternative is to do asynchronous hash table probes, again limited by depth so that nodes near the tips avoid driving the network traffic to insane levels. That is, do a probe, and while waiting on the result either (a) try to fire off the probe as soon as physically possible, such as right after a MakeMove() at the previous ply or (b) start the search here as though it were a miss and if we get a success packet back later, take whatever action is necessary to use that information then.

Again, both of those are possibilities, with a couple of others thrown in for good measure. Others have tried the idea of having a single "probe" thread on all nodes that handle the remote communication, and then truly distributing the hash table by using some set of bits in the signature for the node address where that entry gets stored.

Since I haven't done any of that in the past, it is going to be a time for pure experimental science it seems...

I think that any clustering algorithm should be designed for really high latencies. This is what users will have at home. It will also enable remote computers to participate (via normal global internet).

When I designed my current algorithm, the original plan was to play in Beijing with 25 remote nodes all around the world.

Vas

[Gian-Carlo Pascutto]

What's the difference between UCT with a tiny exploration term (=current top go programs) and an alpha-beta search with very heavy LMR (=current top chess programs), in terms of nodes explored?

Not quite the same thing IMHO. While we are certainly reducing, we are not doing any sort of MC analysis (which is based on very fast game speeds). (...)

MC analysis is just the evaluation function, or the quiescent search, if you wish. I asked a question about nodes explored and you give a (flawed) argument that the evaluation is not the same.

MC analysis with a varying number of samples is equivalent to an evaluation function with lazy exits, from the point of view of the tree search.

And growing the tree based on a sort of probability model. In chess, at least my program, I am not doing any probabilistic analysis,

Really? What is LMR you think? You're probabilistically reducing moves besides the first (few), on the observation that in general your move ordering is likely to be correct. How is this different from UCT favoring the PV and exploring the alternates less?

I am just dynamic/static criteria to decide what looks interesting to search and what appears to be almost useless. But rather than giving up on a move as useless, it just gets reduced in depth to decrease effort required to dismiss it.

Exactly as UCT does.