Page 4 of 4

Re: How do you build a chess cluster?

Posted: Sat May 16, 2009 3:20 pm
by bob
It is not hard to find a _position_ where splitting at the root will work. However, a single position does not win a game. You have to play a move in _every_ position, and splitting at the root simply does not work. Regardless of all the hyperbole, exaggeration, and fiction you might read here. If using 9 nodes (or whatever) and getting a performance speedup of < 1.5x is acceptable, then you are in luck. Otherwise it is all hyperbole and irrelevant to performance discussions.

Re: How do you build a chess cluster?

Posted: Sat May 16, 2009 3:22 pm
by bob
Gian-Carlo Pascutto wrote:
Zach Wegner wrote:Rybka cluster algorithm: divide moves into N groups, where N is the number of nodes. In each group, search the moves as normal, as if the root position had only those moves. The master then picks the move with the best score.
This will fail completely if one group of nodes fails, which is contrary to what Vas stated (works as long as the master works).

It's also going to work quite badly because you cannot redistribute work.

What makes you believe this is what he's doing?
Comments he made here after I carefully explained the output I had seen and the only way it could be produced.. He divides the root moves up into sets, and then searches each set independently. No depth synchronization or anything. Which means you can search one set to depth M and another set to depth N.

It's not a very useful approach, obviously.

Re: How do you build a chess cluster?

Posted: Sat May 16, 2009 5:29 pm
by M ANSARI
bob wrote:It is not hard to find a _position_ where splitting at the root will work. However, a single position does not win a game. You have to play a move in _every_ position, and splitting at the root simply does not work. Regardless of all the hyperbole, exaggeration, and fiction you might read here. If using 9 nodes (or whatever) and getting a performance speedup of < 1.5x is acceptable, then you are in luck. Otherwise it is all hyperbole and irrelevant to performance discussions.

That might be true in general terms, but you have to remember that the Master is playing passively and the slaves only get involved if an evaluation jump triggers the Master to be non passive. The Master is not splitting at the root ... a slave is dedicated to this task. This way you will have the best of both worlds. In chess a game is usually won in a critical position, usually most of the moves could probably handled by even a single core engine. It is being able to take advantage of that critical point in the game which can make a differene. This is difficult to enumerate in Knps, but you cannot but be impressed by the results.

Re: How do you build a chess cluster?

Posted: Sat May 16, 2009 8:36 pm
by diep
bob wrote:It is not hard to find a _position_ where splitting at the root will work. However, a single position does not win a game. You have to play a move in _every_ position, and splitting at the root simply does not work. Regardless of all the hyperbole, exaggeration, and fiction you might read here. If using 9 nodes (or whatever) and getting a performance speedup of < 1.5x is acceptable, then you are in luck. Otherwise it is all hyperbole and irrelevant to performance discussions.
Bob you can statistical measure quickly that root splitting won't give a genius speedup. maximum factor 2 in fact you can theoretical prove.

Reason for that is that if you measure in your search tree where all nodes searched get spent, that usually 50-90% of all nodes goes to mainline search and just 10-50% to the other moves.

It varies from position to position, but on average 80%-90% or so goes to mainline in most engines, especially those which reduce.

Note that i do not doubt your proof on what Rybka was doing in the afternoon cover-up.

Vincent

Re: How do you build a chess cluster?

Posted: Sun May 17, 2009 3:41 am
by bob
M ANSARI wrote:
bob wrote:It is not hard to find a _position_ where splitting at the root will work. However, a single position does not win a game. You have to play a move in _every_ position, and splitting at the root simply does not work. Regardless of all the hyperbole, exaggeration, and fiction you might read here. If using 9 nodes (or whatever) and getting a performance speedup of < 1.5x is acceptable, then you are in luck. Otherwise it is all hyperbole and irrelevant to performance discussions.

That might be true in general terms, but you have to remember that the Master is playing passively and the slaves only get involved if an evaluation jump triggers the Master to be non passive. The Master is not splitting at the root ... a slave is dedicated to this task. This way you will have the best of both worlds. In chess a game is usually won in a critical position, usually most of the moves could probably handled by even a single core engine. It is being able to take advantage of that critical point in the game which can make a differene. This is difficult to enumerate in Knps, but you cannot but be impressed by the results.
I have absolutely no idea what you are talking about. Slaves do work for the master in the normal chess game. In the case of cluster rybka, each node searches a small sub-set of the root moves. And they all continue searching until time runs out and Vas applies whatever rule he uses to choose the best move from among the various "best moves" returned from each cluster node, each of which gets searched to a different depth.

I have no idea what it is you are trying to describe, but it doesn't have anything to do with "cluster chess"

Re: How do you build a chess cluster?

Posted: Sun May 17, 2009 3:46 am
by bob
diep wrote:
bob wrote:It is not hard to find a _position_ where splitting at the root will work. However, a single position does not win a game. You have to play a move in _every_ position, and splitting at the root simply does not work. Regardless of all the hyperbole, exaggeration, and fiction you might read here. If using 9 nodes (or whatever) and getting a performance speedup of < 1.5x is acceptable, then you are in luck. Otherwise it is all hyperbole and irrelevant to performance discussions.
Bob you can statistical measure quickly that root splitting won't give a genius speedup. maximum factor 2 in fact you can theoretical prove.

Reason for that is that if you measure in your search tree where all nodes searched get spent, that usually 50-90% of all nodes goes to mainline search and just 10-50% to the other moves.

It varies from position to position, but on average 80%-90% or so goes to mainline in most engines, especially those which reduce.

Note that i do not doubt your proof on what Rybka was doing in the afternoon cover-up.

Vincent
You can easily beat 2x. All you need is a position where your program changes its mind 2 times in the last iteration. You search each of those moves in parallel, at the same time, and you will just about finish the last one when you finish the first one, which is a > 2x speedup. Doesn't happen that often. And in about 80% of the moves (or higher) where we do _not_ change our mind on the last iteration, the speedup is close to nothing...

Which leaves us with the recursive math where in 80+% of the positions, you get no speedup, in maybe 15% you get maybe 2x, and in the remaining 5% you might get beyond 2x. Averaged together that is close to no speedup.

Re: How do you build a chess cluster?

Posted: Sun May 17, 2009 5:20 am
by peter
Honored Mr. Diepeveen, dear Vincent!

Am I allowed to thank you very much considering me a substitute for all these poor little users out there?
Your posting is very informative and clear even to an amateur in computing like me.
:)