Crude parallel search

[Werewolf]

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?

[Eelco de Groot]

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.

[Werewolf]

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]

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]

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]

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.

[bob]

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.

[Laskos]

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]

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]

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..