Crude parallel search

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.
Werewolf
Posts: 1193
Joined: Thu Sep 18, 2008 8:24 pm

Crude parallel search

Post by Werewolf » Tue Apr 07, 2015 3:16 pm

Two chess enthusiasts, Mr. Reasonable and Mr. Rich agree to play a correspondence machine-match against each other. They have to rely on their hardware to come up with the moves, one new move per day.

Mr. Reasonable has quite a lot of money. He decides to spend $25,000 on the latest Intel Workstation, a fast dual Xeon machine, and he installs the latest version of Stockfish on it. Every time his opponent sends him a move he lets Stockfish think for 24 hours and then plays its chosen move, emailing it to Mr. Rich.

Mr. Rich is stinking rich. He decides to buy exactly the same Workstation Mr. Reasonable has, except he buys 100 of them. He also installs the latest Stockfish on all of them. This is his plan: Every time he receives a move from his opponent (Mr. Reasonable) he enters in every possible legal move that he could make into one of his workstations. So, if Mr.Reasonable plays 1.e4 Mr.Rich would get one machine looking at 1...e5, another machine looking at 1...c5, another machine looking at 1...a6 etc etc. He also lets the machines analyse for 24 hours and plays the move with the score most favourable to himself.

Here's my question: How much stronger is Mr. Rich's setup than Mr. Reasonable's?

User avatar
Eelco de Groot
Posts: 4156
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Crude parallel search

Post by Eelco de Groot » Tue Apr 07, 2015 4:06 pm

I think the 100 computers of Mr. Rich would be less strong than Mr. Reasonable borrowing his wife's credit card and buying a machine Reasonable 2.0 with double the number of processors that is twice as fast, or with the old hardware, but having the option of thinking for 48 hours instead of 24 and the opponent just 24. So that means the 100 machines would be less than 70 Elo stronger than the single dual Xeon.
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

Werewolf
Posts: 1193
Joined: Thu Sep 18, 2008 8:24 pm

Re: Crude parallel search

Post by Werewolf » Tue Apr 07, 2015 5:43 pm

You think that giving every possible legal move 24 hours worth of attention is not even worth 70 elo, compared with one machine using 24 hours to look at whatever it wants?

You may be right. But I'd be surprised if you were.

zullil
Posts: 5667
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

Re: Crude parallel search

Post by zullil » Tue Apr 07, 2015 5:51 pm

Werewolf wrote:You think that giving every possible legal move 24 hours worth of attention is not even worth 70 elo, compared with one machine using 24 hours to look at whatever it wants?

You may be right. But I'd be surprised if you were.
That would certainly be a horrible way to parallelize a tree search. Do you really want to spend 24 hours searching a reply that would normally be instantly pruned? I mean, if a move immediately loses a queen, would searching that portion of the tree for a day reveal anything of value?

Werewolf
Posts: 1193
Joined: Thu Sep 18, 2008 8:24 pm

Re: Crude parallel search

Post by Werewolf » Tue Apr 07, 2015 5:59 pm

zullil wrote:
Werewolf wrote:You think that giving every possible legal move 24 hours worth of attention is not even worth 70 elo, compared with one machine using 24 hours to look at whatever it wants?

You may be right. But I'd be surprised if you were.
That would certainly be a horrible way to parallelize a tree search. Do you really want to spend 24 hours searching a reply that would normally be instantly pruned? I mean, if a move immediately loses a queen, would searching that portion of the tree for a day reveal anything of value?
Mr.Rich could be accused of having more money than sense. But sometimes, just occasionally, that move which loses a queen and gets instantly pruned turns out to be a very deep and brilliant sac. Such cases, though rare, would be detected.

zullil
Posts: 5667
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

Re: Crude parallel search

Post by zullil » Tue Apr 07, 2015 6:07 pm

Werewolf wrote:
zullil wrote:
Werewolf wrote:You think that giving every possible legal move 24 hours worth of attention is not even worth 70 elo, compared with one machine using 24 hours to look at whatever it wants?

You may be right. But I'd be surprised if you were.
That would certainly be a horrible way to parallelize a tree search. Do you really want to spend 24 hours searching a reply that would normally be instantly pruned? I mean, if a move immediately loses a queen, would searching that portion of the tree for a day reveal anything of value?
Mr.Rich could be accused of having more money than sense. But sometimes, just occasionally, that move which loses a queen and gets instantly pruned turns out to be a very deep and brilliant sac. Such cases, though rare, would be detected.
Sure, once in a while a miracle might occur. But the whole goal of searching is to look as deeply as possible in portions of the tree that are meaningful. Mr. Rich's approach seems extremely wasteful of resources. He should spend a bit more, network the machines, and hire someone to create a Stockfish fork called ClusterFish. :wink:

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

Re: Crude parallel search

Post by bob » Tue Apr 07, 2015 6:20 pm

Werewolf wrote:Two chess enthusiasts, Mr. Reasonable and Mr. Rich agree to play a correspondence machine-match against each other. They have to rely on their hardware to come up with the moves, one new move per day.

Mr. Reasonable has quite a lot of money. He decides to spend $25,000 on the latest Intel Workstation, a fast dual Xeon machine, and he installs the latest version of Stockfish on it. Every time his opponent sends him a move he lets Stockfish think for 24 hours and then plays its chosen move, emailing it to Mr. Rich.

Mr. Rich is stinking rich. He decides to buy exactly the same Workstation Mr. Reasonable has, except he buys 100 of them. He also installs the latest Stockfish on all of them. This is his plan: Every time he receives a move from his opponent (Mr. Reasonable) he enters in every possible legal move that he could make into one of his workstations. So, if Mr.Reasonable plays 1.e4 Mr.Rich would get one machine looking at 1...e5, another machine looking at 1...c5, another machine looking at 1...a6 etc etc. He also lets the machines analyse for 24 hours and plays the move with the score most favourable to himself.

Here's my question: How much stronger is Mr. Rich's setup than Mr. Reasonable's?
My guess would be about 50-70 Elo. Why? By searching all root moves in parallel, you get them all searched in about the same time it takes to search the first one, while most parallel searches today have an effective branching factor of about 2.0... this means Mr Rich will be about 2x faster than the single box, which is one extra ply. That 50-70 is just a wild guess at the gain per ply today, which might actually be significantly less than that with today's selective search.

User avatar
Laskos
Posts: 9441
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Crude parallel search

Post by Laskos » Tue Apr 07, 2015 6:24 pm

Werewolf wrote:You think that giving every possible legal move 24 hours worth of attention is not even worth 70 elo, compared with one machine using 24 hours to look at whatever it wants?

You may be right. But I'd be surprised if you were.
Eelco is right, and the speed-up can be derived. Ponder hit SF-SF is about 70%, and the engine spends ~60% of time on PV move. So, the efficiency of 1 machine compared to 100 used this stupid way is ~0.6*0.7 + 0.2*0.3 (non-PV) ~0.50. So, 100 machines used this way are equivalent to only factor of 2 speed-up, or less than 70 Elo points at LTC. As for suggestion: use manually something like IDeA, if there is no SF cluster.

Werewolf
Posts: 1193
Joined: Thu Sep 18, 2008 8:24 pm

Re: Crude parallel search

Post by Werewolf » Tue Apr 07, 2015 6:39 pm

bob wrote:
Werewolf wrote:Two chess enthusiasts, Mr. Reasonable and Mr. Rich agree to play a correspondence machine-match against each other. They have to rely on their hardware to come up with the moves, one new move per day.

Mr. Reasonable has quite a lot of money. He decides to spend $25,000 on the latest Intel Workstation, a fast dual Xeon machine, and he installs the latest version of Stockfish on it. Every time his opponent sends him a move he lets Stockfish think for 24 hours and then plays its chosen move, emailing it to Mr. Rich.

Mr. Rich is stinking rich. He decides to buy exactly the same Workstation Mr. Reasonable has, except he buys 100 of them. He also installs the latest Stockfish on all of them. This is his plan: Every time he receives a move from his opponent (Mr. Reasonable) he enters in every possible legal move that he could make into one of his workstations. So, if Mr.Reasonable plays 1.e4 Mr.Rich would get one machine looking at 1...e5, another machine looking at 1...c5, another machine looking at 1...a6 etc etc. He also lets the machines analyse for 24 hours and plays the move with the score most favourable to himself.

Here's my question: How much stronger is Mr. Rich's setup than Mr. Reasonable's?
My guess would be about 50-70 Elo. Why? By searching all root moves in parallel, you get them all searched in about the same time it takes to search the first one, while most parallel searches today have an effective branching factor of about 2.0... this means Mr Rich will be about 2x faster than the single box, which is one extra ply. That 50-70 is just a wild guess at the gain per ply today, which might actually be significantly less than that with today's selective search.
Thanks Bob.

Werewolf
Posts: 1193
Joined: Thu Sep 18, 2008 8:24 pm

Re: Crude parallel search

Post by Werewolf » Tue Apr 07, 2015 6:55 pm

Laskos wrote:
Werewolf wrote:You think that giving every possible legal move 24 hours worth of attention is not even worth 70 elo, compared with one machine using 24 hours to look at whatever it wants?

You may be right. But I'd be surprised if you were.
Eelco is right, and the speed-up can be derived. Ponder hit SF-SF is about 70%, and the engine spends ~60% of time on PV move. So, the efficiency of 1 machine compared to 100 used this stupid way is ~0.6*0.7 + 0.2*0.3 (non-PV) ~0.50. So, 100 machines used this way are equivalent to only factor of 2 speed-up, or less than 70 Elo points at LTC. As for suggestion: use manually something like IDeA, if there is no SF cluster.
Yes IDeA / Cluster etc. would be better, but I just wanted to ask a question.

I am not totally convinced yet that this is purely a question of speedup. Isn't it the case that by being so brute-force the search shape changes and moves that got virtually no attention before (not all of them silly blunders) are now being looked at in serious depth? I would have thought that could uncover something..

Post Reply