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

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

They do uncover, at a total rate of 2x effective speed-up. If there were ways to uncover things at faster rate for shallow lines, then the optimal for an engine branching factor would be say 6 instead of 1.8. In fact Bob's argument about effective branching factor is the simplest and most sound.

[Werewolf]

Ah OK, maybe this is where my lack of programming shows. So you're saying that pruned lines will EVENTUALLY be uncovered by deeper searches and that the pruning is temporary in some ways?

[Laskos]

Ah OK, maybe this is where my lack of programming shows. So you're saying that pruned lines will EVENTUALLY be uncovered by deeper searches and that the pruning is temporary in some ways?

Yes, the tree always widens too with new iteration, not only deepens.

[hgm]

Ah OK, maybe this is where my lack of programming shows. So you're saying that pruned lines will EVENTUALLY be uncovered by deeper searches and that the pruning is temporary in some ways?

Modern engines do not really prune. They just reduce the search depth of moves that seem less interesting, e.g. search them two ply less deep than moves in the same position that do qualify as intrinsically interesting (such as captures). So as the nominal depth increases, the the depth on the uninteresting moves increses as well, just lagging two steps behind. Until such a reduced search does find the tactics that unmask it as a brilliant sacrifice, rather than a moronic blunder. At that point the engine realizes its mistake, and re-searches the move at the full, unreduced depth.

[Werewolf]

Thanks to you both, it's getting (a little) clearer in my head.

[bob]

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

That would have an effect. I assume you could measure this by taking a program that uses LMR at the root and disabling it just at the root. Only advantage is that this would have no negative effect in the case of Mr. Rich, where a normal program might play stronger by reducing late root moves in the usual way.

How much of a benefit that might be is hard to guess, but I'd suspect "minimal" myself.

[bob]

Ah OK, maybe this is where my lack of programming shows. So you're saying that pruned lines will EVENTUALLY be uncovered by deeper searches and that the pruning is temporary in some ways?

Yes, the tree always widens too with new iteration, not only deepens.

Be cautious with terms. "Pruning" means cutting away branches and never searching them. But we have two kinds of pruning in chess, normal alpha/beta (or backward) pruning where you only prune by proving the branch can't improve things, and forward-pruning where you throw away moves in the last few plies because the current score is so far outside the alpha/beta window the moves being pruned have very little hope of bringing the score back into the window.

Then there are reductions, which is more what your idea is about. For example, let's do a very simple LMR at the root. The first 1/4 of the moves are searched to normal depth. The next 1/4 are searched to normal depth - 1, the next 1/4 are searched to depth-2, and the last 1/4 are searched to depth-3. That is not exactly pruning, but it is certainly reducing the size of the tree by limiting the depth.

Mr. Rich won't have that problem, since every root move will be searched to depth, and not reduced. The question is, what is the reduction stuff doing? It is making the tree more error-prone by reducing the depth, but it is making the search go by much quicker, allowing us to search even deeper, which more than offsets the inaccuracy introduced by the original reductions.

So Mr. Rich gets the best of both worlds, possibly one extra ply over Mr. reasonable, AND more accurate search results due to the lack of LMR at the root. How big is that? Unknown. But LMR has gotten very good, so the loss is not huge for sure.

When a normal program goes a ply deeper, it typically pushes the LMR reductions off just a bit, because of the way LMR is tuned to reduce based on both depth remaining and order a move is searched. So as you search deeper, you push the error-prone stuff out a bit further, making the moves closer to the root just a bit more accurate. I don't like the term "widening" but it does sort of explain what is happening in a primitive way.

[Dann Corbit]

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.

The search you describe is (at some level) a mini-max search, which is horrifyingly inefficient.

You would want the cluster to be directed by some kind of coordinating software.

In general there are usually 1-4 good moves and 30+ bad moves for a given position. Why study:
"Shall I set my rook on the square attacked by his h-pawn?"
and things of that nature with enormous compute resources when bad moves are easily refuted?

Daniel Shawul has written software that allows search coordination via SMP, NUMA, and MPICH clusters. You can even search using a combination.

Imagine if you asked someone to get you a glass of milk and they spent hours searching in the bathroom. True, someone might just have left a glass and carton of milk in the bathroom. But it would be better to look in the kitchen, and specifically in the refrigerator.

[Laskos]

Ah OK, maybe this is where my lack of programming shows. So you're saying that pruned lines will EVENTUALLY be uncovered by deeper searches and that the pruning is temporary in some ways?

Yes, the tree always widens too with new iteration, not only deepens.

Be cautious with terms. "Pruning" means cutting away branches and never searching them. But we have two kinds of pruning in chess, normal alpha/beta (or backward) pruning where you only prune by proving the branch can't improve things, and forward-pruning where you throw away moves in the last few plies because the current score is so far outside the alpha/beta window the moves being pruned have very little hope of bringing the score back into the window.

Then there are reductions, which is more what your idea is about. For example, let's do a very simple LMR at the root. The first 1/4 of the moves are searched to normal depth. The next 1/4 are searched to normal depth - 1, the next 1/4 are searched to depth-2, and the last 1/4 are searched to depth-3. That is not exactly pruning, but it is certainly reducing the size of the tree by limiting the depth.

Mr. Rich won't have that problem, since every root move will be searched to depth, and not reduced. The question is, what is the reduction stuff doing? It is making the tree more error-prone by reducing the depth, but it is making the search go by much quicker, allowing us to search even deeper, which more than offsets the inaccuracy introduced by the original reductions.

So Mr. Rich gets the best of both worlds, possibly one extra ply over Mr. reasonable, AND more accurate search results due to the lack of LMR at the root. How big is that? Unknown. But LMR has gotten very good, so the loss is not huge for sure.

When a normal program goes a ply deeper, it typically pushes the LMR reductions off just a bit, because of the way LMR is tuned to reduce based on both depth remaining and order a move is searched. So as you search deeper, you push the error-prone stuff out a bit further, making the moves closer to the root just a bit more accurate. I don't like the term "widening" but it does sort of explain what is happening in a primitive way.

This was a discussion some years ago. The thing is NMR and LMR reduce in such a away, that near the leafs the tree is sparse, near the root, with higher searched depths, the tree thickens, becoming almost full width.
I once plotted the shape of the tree with logarithmic reductions
http://www.talkchess.com/forum/viewtopi ... &start=261

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

The search you describe is (at some level) a mini-max search, which is horrifyingly inefficient.

You would want the cluster to be directed by some kind of coordinating software.

In general there are usually 1-4 good moves and 30+ bad moves for a given position. Why study:
"Shall I set my rook on the square attacked by his h-pawn?"
and things of that nature with enormous compute resources when bad moves are easily refuted?

Daniel Shawul has written software that allows search coordination via SMP, NUMA, and MPICH clusters. You can even search using a combination.

Imagine if you asked someone to get you a glass of milk and they spent hours searching in the bathroom. True, someone might just have left a glass and carton of milk in the bathroom. But it would be better to look in the kitchen, and specifically in the refrigerator.

Your last point made me laugh because in our house looking in the bathroom is not such a stupid idea if you want to find a drink!



I accept what you're saying, just two points though:

a) in some cases we don't know what is and isn't worth searching until we actually do the search. We know the bathroom is a strange place to find milk because we've been there before. But if you went to a house where the rooms were not clearly marked somehow, you'd systematically search each one.
b) In this (silly) example above Mr.Rich is so rich he doesn't care about efficiency and spending a million dollars to get +50 elo over his opponents is acceptable to him. I would have thought this setup would have yielded more elo than that, but evidently not.