How do you build a chess cluster?

Discussion of anything and everything relating to chess playing software and machines.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: How do you build a chess cluster?

Post by bob » Sat May 16, 2009 3:20 pm

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
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: How do you build a chess cluster?

Post by bob » Sat May 16, 2009 3:22 pm

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.

User avatar
M ANSARI
Posts: 3408
Joined: Thu Mar 16, 2006 6:10 pm

Re: How do you build a chess cluster?

Post by M ANSARI » Sat May 16, 2009 5:29 pm

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.

diep
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: How do you build a chess cluster?

Post by diep » Sat May 16, 2009 8:36 pm

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

bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: How do you build a chess cluster?

Post by bob » Sun May 17, 2009 3:41 am

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"

bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: How do you build a chess cluster?

Post by bob » Sun May 17, 2009 3:46 am

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.

peter
Posts: 1782
Joined: Sat Feb 16, 2008 6:38 am
Full name: Peter Martan

Re: How do you build a chess cluster?

Post by peter » Sun May 17, 2009 5:20 am

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.
:)
Peter.

Post Reply