Questions on SMP search

[bob]

Again you didn't get it.
The point is that "green" and "blue" searches are exactly the same algorithm. The only difference is that in the "blue" search the target depth is 15, while in the "green" search the target depth is 12.
And at depth 12, "green" search tree is wider than the "blue" one despite both of them applying exactly the same algorithm, just because the target depth is not the same.
The second thing related to EBF that you don't realize since you behave like there is no chess outside of Crafty probably having an equality in your head that says "doesn't work in Crafty=doesn't work at all", is that the amount of LMR and NMR increases with the search depth. And it's usually a logarithmic function of the depth. The deeper you search the more you prune (you start pruning at higher remaining depth), ergo your EBF is reducing.
You certainly don't do that in Crafty and that's why for the same time amount Crafty hardly reaches depth 20, while Stockfish reaches depth 30, and both of them have almost the same NPS.

You are right. I don't get it. I don't want to get it. Because it is nonsense. You can have the last word as this is really pointless.

??
Bob-
Milos is a talented programmer currently working for IBM research?

He makes a lot of sense (to me anyway)...
but I'm biased considering the fact that he wrote an excellent and unique SMP implementation for Fire (Bird)...

I can understand perfectly you "don't want to get it"...and are 'done'.
Good idea BTW, (IMO) to give him the last word.

What, no personal insults?
('nonsense' mud-slinging aside)

Maybe one day we will take a look to see how "unique" his SMP implementation is, eh? Wonder what that will reveal? OF course, I didn't find any firebird source available anywhere via google. Is there a link or is it "closed source"??

[Sven]

but I'm biased considering the fact that he wrote an excellent and unique SMP implementation for Fire (Bird)...

The Fire 1.31 SMP source looks very close to the IvanHoe code, so do you imply that he wrote the IvanHoe SMP, too, and later on did some renaming and reformatting for Fire? And even if that were true (although unlikely considering the type of changes - the complete naming style of identifiers was changed for instance which usually does not occur with the same author), what would make this Fire SMP implementation "unique", apart from the fact that it has no Linux support - as opposed to IvanHoe?

Sven

[Rein Halbersma]

Just to abstract from the name-calling and confusion.

Bob's definition of EBF (depth) = nodes(depth) / nodes(depth-1). For a perfectly regular tree, nodes(depth) = width^depth and EBF(depth) = width, independent of depth. So far so good. Marco's observation was that in irregular trees the extra nodes at the next depth iteration are not all leaf nodes. The pyramid analogue really explains this nicely: adding a layer to the sides, some stones to the bottom etc. In such irregular trees, a single EBF doesn't contain all the information about the shape of the tree.

Generalizing slightly, you can define an EBF at each ply level of the tree as EBF(depth, ply) = nodes(depth, ply) / nodes(depth-1, ply). The claim is that for fixed ply, EBF(depth, ply) is increasing in depth, simply because LMR and NMR are reducing more heavily at lower remaining depth. This is what people mean with "widening the tree". A better term would perhaps be that high in the tree, the tree is "thicker" or "denser". Similarly, for fixed depth, EBF(depth, ply) is decreasing in ply. So lower in the tree (near the leafs), the tree is quite "thin".

So at ply=1, (the root moves) the EBF is probably around 30+, whereas at ply=depth (the leaf nodes) the EBF might be 1. The overall EBF of a tree can still remain fairly constant around 2.

I guess these observations are fairly trivial and could have been made a lot earlier if people were to take the courtesy of interpreting each other words a bit more constructively...

Thanks.

Rein

[Laskos]

Just to abstract from the name-calling and confusion.

Bob's definition of EBF (depth) = nodes(depth) / nodes(depth-1). For a perfectly regular tree, nodes(depth) = width^depth and EBF(depth) = width, independent of depth. So far so good. Marco's observation was that in irregular trees the extra nodes at the next depth iteration are not all leaf nodes. The pyramid analogue really explains this nicely: adding a layer to the sides, some stones to the bottom etc. In such irregular trees, a single EBF doesn't contain all the information about the shape of the tree.

Generalizing slightly, you can define an EBF at each ply level of the tree as EBF(depth, ply) = nodes(depth, ply) / nodes(depth-1, ply). The claim is that for fixed ply, EBF(depth, ply) is increasing in depth, simply because LMR and NMR are reducing more heavily at lower remaining depth. This is what people mean with "widening the tree". A better term would perhaps be that high in the tree, the tree is "thicker" or "denser". Similarly, for fixed depth, EBF(depth, ply) is decreasing in ply. So lower in the tree (near the leafs), the tree is quite "thin".

So at ply=1, (the root moves) the EBF is probably around 30+, whereas at ply=depth (the leaf nodes) the EBF might be 1. The overall EBF of a tree can still remain fairly constant around 2.

I guess these observations are fairly trivial and could have been made a lot earlier if people were to take the courtesy of interpreting each other words a bit more constructively...

Thanks.

Rein

Try to talk that to Bob, he doesn't even know how to read a plot, where the slopes (first derivatives) are giving EBF(target depth, ply) on the tree, not the absolute values, and those slopes are both larger and smaller for different plies than the general EBF(target depth), giving a total pretty constant EBF(target depth) i.e. from target depth N to N+1 (different trees). I am really eager to see someone plot the tree shape of Stockfish for different target depths, there is no way it's not widening compared to the purely exponential, his "widening", which is not a widening at all (he seems to be confused about what widening of the tree is). Bob's theoretical tree shape is the purely exponential, non-widening W^D, how silly is that? I don't think he knows the tree shape even of his Crafty.

Kai

[Sven]

Bob's definition of EBF (depth) = nodes(depth) / nodes(depth-1). For a perfectly regular tree, nodes(depth) = width^depth and EBF(depth) = width, independent of depth. So far so good. Marco's observation was that in irregular trees the extra nodes at the next depth iteration are not all leaf nodes. The pyramid analogue really explains this nicely: adding a layer to the sides, some stones to the bottom etc. In such irregular trees, a single EBF doesn't contain all the information about the shape of the tree.

Generalizing slightly, you can define an EBF at each ply level of the tree as EBF(depth, ply) = nodes(depth, ply) / nodes(depth-1, ply). The claim is that for fixed ply, EBF(depth, ply) is increasing in depth, simply because LMR and NMR are reducing more heavily at lower remaining depth. This is what people mean with "widening the tree". A better term would perhaps be that high in the tree, the tree is "thicker" or "denser". Similarly, for fixed depth, EBF(depth, ply) is decreasing in ply. So lower in the tree (near the leafs), the tree is quite "thin".

So at ply=1, (the root moves) the EBF is probably around 30+, whereas at ply=depth (the leaf nodes) the EBF might be 1. The overall EBF of a tree can still remain fairly constant around 2.

I guess these observations are fairly trivial and could have been made a lot earlier if people were to take the courtesy of interpreting each other words a bit more constructively...

If I assume your "depth" is the maximum search depth of an iteration and "ply" the distance of a node to the root node then I can follow you, except for one question: What does "overall EBF of a tree" mean for you?

Furthermore, I repeat a proposal that was made by Gerd Isenberg few months ago, to use an improved definition for EBF that tries to address the "odd/even ply" properties of an alpha-beta search tree and to avoid jumping up and down of EBF numbers between subsequent iterations:

Code: Select all

EBF(iterationNo) := sqrt(nodes(iterationNo) / nodes(iterationNo - 2))

Another recent interesting thread about EBF was this one.

Back to your summary of arguments, you wrote:

The claim is that for fixed ply, EBF(depth, ply) is increasing in depth, simply because LMR and NMR are reducing more heavily at lower remaining depth.

Are you sure about NMR in this case? Don't we reduce null moves more at higher remaining depth? Basic Stockfish formula (taken from 2.0.1), for instance, is

Code: Select all

        // Null move dynamic reduction based on depth
        int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);

which means R=3 for "remaining depth < 5" and R=3+"remaining depth" / 8 otherwise, which is more reduction at higher remaining depth.

Maybe I misunderstood your point?

Sven

[bob]

Just to abstract from the name-calling and confusion.

Bob's definition of EBF (depth) = nodes(depth) / nodes(depth-1). For a perfectly regular tree, nodes(depth) = width^depth and EBF(depth) = width, independent of depth. So far so good. Marco's observation was that in irregular trees the extra nodes at the next depth iteration are not all leaf nodes. The pyramid analogue really explains this nicely: adding a layer to the sides, some stones to the bottom etc. In such irregular trees, a single EBF doesn't contain all the information about the shape of the tree.

Generalizing slightly, you can define an EBF at each ply level of the tree as EBF(depth, ply) = nodes(depth, ply) / nodes(depth-1, ply). The claim is that for fixed ply, EBF(depth, ply) is increasing in depth, simply because LMR and NMR are reducing more heavily at lower remaining depth. This is what people mean with "widening the tree". A better term would perhaps be that high in the tree, the tree is "thicker" or "denser". Similarly, for fixed depth, EBF(depth, ply) is decreasing in ply. So lower in the tree (near the leafs), the tree is quite "thin".

So at ply=1, (the root moves) the EBF is probably around 30+, whereas at ply=depth (the leaf nodes) the EBF might be 1. The overall EBF of a tree can still remain fairly constant around 2.

I guess these observations are fairly trivial and could have been made a lot earlier if people were to take the courtesy of interpreting each other words a bit more constructively...

Thanks.

Rein

This "pyramid shape" has been a fact of tree searching since the early days. The first trees widened until max depth was reached and the search became highly selective (captures only, then captures + checks, and even captures + checks + some types of threats such as passed pawn pushes.)

Today we have pushed the ply where the "narrowing occurs" back 4 plies due to forward pruning (futility pruning). It doesn't change the fact that for each ply, the "overall width" goes up. It is still a tree. But the term "width" has a specific meaning, and using it to describe something that happens in all trees as the depth increases doesn't make a lot of sense...

[bob]

Just to abstract from the name-calling and confusion.

Bob's definition of EBF (depth) = nodes(depth) / nodes(depth-1). For a perfectly regular tree, nodes(depth) = width^depth and EBF(depth) = width, independent of depth. So far so good. Marco's observation was that in irregular trees the extra nodes at the next depth iteration are not all leaf nodes. The pyramid analogue really explains this nicely: adding a layer to the sides, some stones to the bottom etc. In such irregular trees, a single EBF doesn't contain all the information about the shape of the tree.

Generalizing slightly, you can define an EBF at each ply level of the tree as EBF(depth, ply) = nodes(depth, ply) / nodes(depth-1, ply). The claim is that for fixed ply, EBF(depth, ply) is increasing in depth, simply because LMR and NMR are reducing more heavily at lower remaining depth. This is what people mean with "widening the tree". A better term would perhaps be that high in the tree, the tree is "thicker" or "denser". Similarly, for fixed depth, EBF(depth, ply) is decreasing in ply. So lower in the tree (near the leafs), the tree is quite "thin".

So at ply=1, (the root moves) the EBF is probably around 30+, whereas at ply=depth (the leaf nodes) the EBF might be 1. The overall EBF of a tree can still remain fairly constant around 2.

I guess these observations are fairly trivial and could have been made a lot earlier if people were to take the courtesy of interpreting each other words a bit more constructively...

Thanks.

Rein

Try to talk that to Bob, he doesn't even know how to read a plot, where the slopes (first derivatives) are giving EBF(target depth, ply) on the tree, not the absolute values, and those slopes are both larger and smaller for different plies than the general EBF(target depth), giving a total pretty constant EBF(target depth) i.e. from target depth N to N+1 (different trees). I am really eager to see someone plot the tree shape of Stockfish for different target depths, there is no way it's not widening compared to the purely exponential, his "widening", which is not a widening at all (he seems to be confused about what widening of the tree is). Bob's theoretical tree shape is the purely exponential, non-widening W^D, how silly is that? I don't think he knows the tree shape even of his Crafty.

Kai

I would bet I know the shape of Crafty's tree far better than you know the shape of _any_ tree, even those in your back yard.

[bob]

This is a possible experiment to test the "search wideer" idea.

Take an engine as is (call it verions A) and search up to depth 15

Then modify it (call it version B) so that when remaining depth is lower then 2 plies it goes staright to qsearch (normally this happens when remaining depth is lower then one ply), namely this means to skip depth one altogheter.

Now search at depth 16 with version B

According to the "increase depth" idea the two engine should search approximately the same nodes because version B search one ply deeper but then last ply is skipped so end result is the same.

But accordingly to "wider search", engine B searches more nodes because it reaches a given node with an higher remaining depth of engine A and so searches more moves on that node.

That test shows _nothing_. Because now you lop off the last two plies of "narrower" search (two plies of futility pruning). So we do one search pruning in last 4 plies, compared to a one ply deeper search pruning in last 3 plies? What, exactly, will that show, other than the EBF climbing since the tree is now wider at each iteration. While in a _real_ program we always prune in the last 4 plies, and nothing changes from iteration to iteration with respect to pruning decisions. If you have an unbounded reduction formula, the tree might get _narrower_ as you go deeper, if the reduction value R is proportional to depth, but that's not wider, that's narrower.


How hard is this stuff to understand, really???

[wgarvin]

I'm no expert on tree searching, so I don't have much to contribute to this discussion. I can't actually tell if the two camps are in "violent agreement" or not.

On another note though, I would like to thank everyone who has contributed to this highly entertaining thread !

[Rein Halbersma]

If I assume your "depth" is the maximum search depth of an iteration and "ply" the distance of a node to the root node then I can follow you, except for one question: What does "overall EBF of a tree" mean for you?

Yes, depth = maximal remaining depth, i.e. the iterative deepening parameter, and ply = distance to root. With "overall EBF" I simply mean EBF(depth) = nodes(depth) / nodes(depth-1), i.e. the overall growth rate in nodes going from one depth iteration to the next. You can also define share(depth-1, ply) = nodes(depth-1, ply) / nodes(depth-1) as the share of nodes at a given ply level for the previous depth iteration, and leafs(depth) as the number of nodes encountered at the maximal ply level during the current depth iteration. It's then a simple exercise to show that the overall EBF decomposes into

Code: Select all

EBF(depth) = leafs(depth) / nodes(depth-1) + sum_{ply = 0 to depth-1} EBF(depth, ply) * share(depth-1, ply)

This means that the overall growth rate in nodes (EBF) is the sum of the ratio of leaf nodes to previous total nodes, plus the weighted EBF at all ply levels above the leafs, where the weight per ply is the share of each ply level in the previous total nodes. For a completely regular tree, the EBF per ply is equal to 1 (nothing changes from one depth iteration to the next), and the shares all add to one. So for a regular tree, the overall EBF is simply 1 plus the ratio of leaf nodes to previous total nodes.

Obviously qsearch and search extensions complicate this formula a bit, since e.g. leaf nodes occur at different ply levels, but the principle remains the same: EBF decomposes into growth of leafs and "inner growth", aka "widening" or "thickening" depending on your taste

Furthermore, I repeat a proposal that was made by Gerd Isenberg few months ago, to use an improved definition for EBF that tries to address the "odd/even ply" properties of an alpha-beta search tree and to avoid jumping up and down of EBF numbers between subsequent iterations:

Code: Select all

EBF(iterationNo) := sqrt(nodes(iterationNo) / nodes(iterationNo - 2))

Another recent interesting thread about EBF was this one.

The previous formula for the decomposition of EBF has an economics analogue in the GDP growth index from one year to the next, which decomposes into the weighted growth indices of goods that already existed the previous year, plus a term accounting for the availability of new goods (i.e. the leafs in tree search). The square root correction of Gerd is an example of seasonal adjusting. E.g. GDP growth indices are often corrected for the same quarter or month (i.e. the depth-2 comparison to correct for the same side to move). This makes them more reliable but also complicates their decomposition a bit.

Back to your summary of arguments, you wrote:

The claim is that for fixed ply, EBF(depth, ply) is increasing in depth, simply because LMR and NMR are reducing more heavily at lower remaining depth.

Are you sure about NMR in this case? Don't we reduce null moves more at higher remaining depth? Basic Stockfish formula (taken from 2.0.1), for instance, is

Code: Select all

        // Null move dynamic reduction based on depth
        int R = 3 + (depth >= 5 * ONE_PLY ? depth / 8 : 0);

which means R=3 for "remaining depth < 5" and R=3+"remaining depth" / 8 otherwise, which is more reduction at higher remaining depth.

Maybe I misunderstood your point?

Sven

Ah but no! You have to look at remaining depth-R, not just R.

Code: Select all

nullValue = -search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY);

If you look carefully at the Stockfish formula, then going from say remaining depth = 7 to depth = 8, the null move search actually stays the same! However, there is a strong effect from the verification search which gets skipped for remaining depth < 6, so this makes NMR reduce more heavily at lower remaining depth.

Anyway, my point is that I agree with Bob that EBF is a simple statistic, and I find it strange that people can get confused about it. Where I disagree with Bob is that I think that EBF is not a useful statistic because of the high degree of irregularity of search trees, and that having EBF(depth, ply) available at all ply levels in the tree is much more informative, because it explains that the effects of reductions such as LMR occur in different parts of the tree.

Rein