Crude parallel search

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

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

Right. But there IS a significant difference between reducing the depths of some moves, letting the branches peter out of their own accord a bit earlier, and just whacking them off at some point without any further analysis. IE dropping into q-search is much less abrupt than outright pruning something away.

I am not sure I understand why it would "thicken" nearer to the root. LMR applies at every last ply. After the first move for (say) white, you will always reduce the last move by black significantly at ply=2, regardless of the search depth. Without giving it a ton of thought, I would expect the tree to continue in a normal "fan shape" since there are more and more nodes as you get farther out into the tree on each successive iteration...

[Werewolf]

So despite all that has been said I had this thought:

Usually in a chess game there are several good moves to chose from, say 3. In the opening phase there may be as many as 5 moves which are roughly equal.

So why wouldn't Mr. Rich's setup give at least 3x speedup? Since he's looking at every move on a different machine...

[syzygy]

So despite all that has been said I had this thought:

Usually in a chess game there are several good moves to chose from, say 3. In the opening phase there may be as many as 5 moves which are roughly equal.

So why wouldn't Mr. Rich's setup give at least 3x speedup? Since he's looking at every move on a different machine...

Because if it takes T seconds to search 1 move to depth D, it takes alpha-beta much less than 3T seconds to search 3 more or less equally good moves to depth D. But search them on separate machines, without communicating bounds, and it will take at least T seconds. The speed up is therefore much less than 3T / T = 3.

[bob]

So despite all that has been said I had this thought:

Usually in a chess game there are several good moves to chose from, say 3. In the opening phase there may be as many as 5 moves which are roughly equal.

So why wouldn't Mr. Rich's setup give at least 3x speedup? Since he's looking at every move on a different machine...

Because two of those will be searched far quicker after seeing how good the best move is. The beauty of alpha/beta.

Now if you talk about a case where a program changes its mind and produces three different best moves on the final iteration, then for that case, Mr. Rich would in fact see a 3x speedup. But that is not a "common case". A much more common case is you don't change your mind at all, and there he sees at most that original 2x speedup, where he spends 1/2 the time searching the first move, 1/2 the time searching all the others. Now he will do that in 1/2 the total time given enough processors.