Questions on SMP search

[bob]

N = W ^ D is a well-known formula. No, it doesn't fit today's trees. It doesn't fit _any_ tree except the "theoretical tree." But it gives a mathematical representation of the idea. And that is a useful thing because it gives us a way to discuss issues.

EBF is a _very_ specific concept. It is an estimate of how much effort it takes to do an N+1 ply search, knowing how long it took to do the N ply search. It is not accurate. You can have 20 2.1's in a row and then a 6.0. But it is an estimate. And from that, you can deduce characteristics of the tree and what is going on inside the thing.

If the EBF is not increasing, ply by ply, then the "width" of the tree is also _not_ increasing. It is simply mathematically impossible. Since "width" and EBF are synonyms in the world of tree search.

Wrong, EBF as you define it as N to N+1 is not the same as the width of the tree. To show you how they are different in Marco's (Stockfish) model simplified and put to integration by me with the formula for the wideness of the tree

NormalizationFactor * Integrate (d depth_x) [ (Depth - 5 - depth_x) * Theta (Depth - 5 - depth_x) * Log (EBF1) + (5 - (depth_x + 5 - Depth) * Theta (depth_x + 5 - Depth)) * Log (EBF2) ]

Here is the plot:



EBF in this model seems a pretty straight (blue) line with a value of ~2.2. I linked the endpoints of tree shapes by hand, and exactly this blue line is EBF in tree widening model. The EBF line doesn't seem to widen even here.

Tree shape is a completely different matter, and as you can see, it is widening going to 5,10,15,20,25 _target_ depth. I can clearly separate EBF into two components: EBF_widening, which is ~1.4, and EBF_deepening, which is ~1.6, for a total EBF of 1.4*1.6 ~ 2.2. As I already wrote, going from target N to target N+1 requires a comparable effort in both deepening and widening. To see more clearly the effect of the widening, I substracted the EBF (blue) almost straight line (plane in my 3D plot):



As you can see, the main widening effort occurs towards the middle of the tree to target depth. Here we differ dramatically, your "non-widening" tree shape would be a flat horizontal plane at 0 in this plot. Certainly, this is just a model built from Marco's remarks, but I think it could be replicated in a real engine (at least in Stockfish, maybe not in Crafty )

This is my last try on the subject, hope some people will gather data from real engines.

Kai

Have it your way. I'm going to continue to use the traditional definition of "width" (W in the well-known minimax / alpha-beta formulas) and EBF. If you increase W, and EBF doesn't change, you are screwing up your math. It really is that simple...

The tree is exponential with respect to D, the degree of increase is with respect to W. There is absolutely no way to increase W and have the EBF remain the same, if the search remains constant iteration to iteration. And for stockfish, crafty, and any other program I am aware of, the search does _not_ change as we go deeper.

We use the same rules to extend, reduce and prune. We apply them deeper into the tree as the tree goes deeper, for sure. But for pruning, we only prune in the last N plies.

All of this chatter about increased width you are showing is _solely_ based on increased depth. If you simply draw the graph of the tree you search, root at top, tips at the bottom, all nodes searched left to right. Then for an N ply search, you measure the width across the left-to-right axis. You get X. Then you go one ply deeper. And measure the widest point of the tree. You get Y. And Y > X. And this has _always_ been true since we started doing iterated searches. It is not an "intentional widening" it is that the tree grows in two directions as it goes deeper. The branches get longer (depth) and you get more branches (wider).

your plots show this nicely. But that is _all_ they show...

[wgarvin]

All of this chatter about increased width you are showing is _solely_ based on increased depth. If you simply draw the graph of the tree you search, root at top, tips at the bottom, all nodes searched left to right. Then for an N ply search, you measure the width across the left-to-right axis. You get X. Then you go one ply deeper. And measure the widest point of the tree. You get Y. And Y > X. And this has _always_ been true since we started doing iterated searches. It is not an "intentional widening" it is that the tree grows in two directions as it goes deeper. The branches get longer (depth) and you get more branches (wider).

your plots show this nicely. But that is _all_ they show...

Suppose you search to a depth 25, and at ply 24 you had N nodes. Now you repeat the search to depth 26 and at ply 24 you have M nodes, M > N. You seem to be saying that you expect M = N (the straight line on the logarithmic graph) and the others are saying that in Stockfish, M > N. (Or maybe you just disagree with the way the word "width" is being used when talking about this M > N effect).

I think all they're saying is that ply 24 got "wider" because there was more remaining depth and the effects of pruning, LMR etc. were different. The extra nodes are not all along the bottom of the tree. If Kai's calculation is correct, 40% of them are new interior nodes spread across the other plies of the tree. [Edit: and it sounds like LMR helps spread this effect across nearly all plies of the tree, not just the last few.]

If EBF is an average measure of the branching factor across the whole tree, then it doesn't say anything about the shape of the tree at all. These graphs show a self-similarity between tree shapes to different depths, but they also show that for a certain ply P, deeper searches are going to have more nodes at that ply than shallower searches.

[Edit: maybe we should avoid the word "wider" and use something else, e.g. call the M > N effect a "larger" ply 24].

[Laskos]

Have it your way. I'm going to continue to use the traditional definition of "width" (W in the well-known minimax / alpha-beta formulas) and EBF. If you increase W, and EBF doesn't change, you are screwing up your math. It really is that simple...

Really tired with you. Look at the slopes (first derivative), and less at absolute values on this issue.

[bob]

All of this chatter about increased width you are showing is _solely_ based on increased depth. If you simply draw the graph of the tree you search, root at top, tips at the bottom, all nodes searched left to right. Then for an N ply search, you measure the width across the left-to-right axis. You get X. Then you go one ply deeper. And measure the widest point of the tree. You get Y. And Y > X. And this has _always_ been true since we started doing iterated searches. It is not an "intentional widening" it is that the tree grows in two directions as it goes deeper. The branches get longer (depth) and you get more branches (wider).

your plots show this nicely. But that is _all_ they show...

Suppose you search to a depth 25, and at ply 24 you had N nodes. Now you repeat the search to depth 26 and at ply 24 you have M nodes, M > N. You seem to be saying that you expect M = N (the straight line on the logarithmic graph) and the others are saying that in Stockfish, M > N. (Or maybe you just disagree with the way the word "width" is being used when talking about this M > N effect).

Yes I disagree with using "width" in this way. Width normally applies to a single node. As you go deeper, the overall tree _must_ grow wider, unless you have somehow managed to limit with EBF to 1.0 or less. But that "wider" is not something that happens at any specific ply, it is something that is a product of the extra layer of nodes added on at the tips.

I see nothing at all that suggests that for StockFish, M > N, so far. I only see some made-up numbers to produce graphs that support a claim that is based on no data of any kind, just "intuition."

If you are only diddling around with the "width" at the last 4 plies (current forward pruning) then you are not widening the tree as you go deeper. When you go from depth D to depth D+1, yes, at some point in the tree you take some ply (say 20 when you get to depth 24) and now you apply no forward pruning at depth 20, because you only do this in the last 4 plies. So 20 got "wider" this time around than the last time around. But 21 - 24 are just as narrow this time around as 20-23 were the last iteration, and all we are doing is going a ply deeper, which supposedly gains us increased knowledge.

If you were tweaking all widths at all points in the tree, then this terminology might make sense. But in fact, we are tweaking _no_ widths at all. We are just going deeper and letting that change the rules for one ply, each time we go one ply deeper. We are not adjusting the pruning rules so that we prune less as we go deeper. We are actually pruning more, to offset the exponential growth, because there are more nodes at the last 4 plies, when you go one ply deeper.

Mangling terminology makes communication of real ideas impossible. Most now use BF and EBF correctly (BF is not changed by anything other than the characteristics/rules of the game, EBF can be greatly reduced via pruning and/or reductions. Now we re-open the mangled usage debate with the term "width" and "widening".

I think all they're saying is that ply 24 got "wider" because there was more remaining depth and the effects of pruning, LMR etc. were different. The extra nodes are not all along the bottom of the tree. If Kai's calculation is correct, 40% of them are new interior nodes spread across the other plies of the tree. [Edit: and it sounds like LMR helps spread this effect across nearly all plies of the tree, not just the last few.]

I have never argued against that point, as it is obvious that as the depth advances, with pruning only at the last 4 plies, or with reductions, that as you go deeper, you always keep N plies of pruned search, where N is constant, which means each new iteration adds a fuller ply just before the ply where the pruning starts. But if you use that as "widening" then what about a program that has _no_ pruning_ or reductions? The same thing happens. You do a 5 ply search, you get 5 plies of all moves, followed by additional plies of just captures or checks. When you go to depth 6, now you get 5 plies of all moves, and additional plies of just captures or checks. What is different? (a) you went one ply deeper; (b) the first ply of just captures was replaced by a full-width ply.

Do we _really_ want to call that "widening" the search? Makes absolutely no sense since that is how the basic tree search works if you use iterative deepening, as we have since Slate/Atkin...

If EBF is an average measure of the branching factor across the whole tree, then it doesn't say anything about the shape of the tree at all. These graphs show a self-similarity between tree shapes to different depths, but they also show that for a certain ply P, deeper searches are going to have more nodes at that ply than shallower searches.

As it does in a pure brute-force alpha/beta search, with no reductions, no pruning, no null-move, etc. Each new iteration expands the first q-search ply from the previous iteration into a full-blown search everything ply. My point is, "so what?" This is how iterative deepening has always worked. It is not something "new" or "different". You go one ply deeper, you learn more stuff. Because you go one ply deeper.

[Edit: maybe we should avoid the word "wider" and use something else, e.g. call the M > N effect a "larger" ply 24].

"larger" than what? That's the issue. That this is somehow new is wrong. See previous explanations above as to why. This has been a characteristic of searching game trees since minimax and day 1, even prior to alpha/beta. As a real (oak, maple, etc) tree grows taller (deeper) the branches grow wider. It is a property of the tree, if this didn't happen, lower branches would be cut off from sunlight by higher branches, and they could not contribute to the photosynthesis reaction needed for the tree to grow/survive...

[bob]

Have it your way. I'm going to continue to use the traditional definition of "width" (W in the well-known minimax / alpha-beta formulas) and EBF. If you increase W, and EBF doesn't change, you are screwing up your math. It really is that simple...

Really tired with you. Look at the slopes (first derivative), and less at absolute values on this issue.

Get as tired as you want. You are no more tired than I am.

DO the _same_ plot for a pure minimax tree to fixed depth, no extensions, no reductions, no pruning. And see what happens when you go one ply deeper. Voila' The tree gets wider. Because it is a tree, not a straight line...

[Laskos]

Have it your way. I'm going to continue to use the traditional definition of "width" (W in the well-known minimax / alpha-beta formulas) and EBF. If you increase W, and EBF doesn't change, you are screwing up your math. It really is that simple...

Really tired with you. Look at the slopes (first derivative), and less at absolute values on this issue.

Get as tired as you want. You are no more tired than I am.

DO the _same_ plot for a pure minimax tree to fixed depth, no extensions, no reductions, no pruning. And see what happens when you go one ply deeper. Voila' The tree gets wider. Because it is a tree, not a straight line...

Bob, my last my sentences on the subject: what YOU are proposing is YOUR tree in my plots:

Integral [d x] A * Exp(B*x) = A/B Exp(B*x)

a pure exponential in x which is YOUR tree. Marco's tree is different.

I am done!
Kai

[bob]

Have it your way. I'm going to continue to use the traditional definition of "width" (W in the well-known minimax / alpha-beta formulas) and EBF. If you increase W, and EBF doesn't change, you are screwing up your math. It really is that simple...

Really tired with you. Look at the slopes (first derivative), and less at absolute values on this issue.

Get as tired as you want. You are no more tired than I am.

DO the _same_ plot for a pure minimax tree to fixed depth, no extensions, no reductions, no pruning. And see what happens when you go one ply deeper. Voila' The tree gets wider. Because it is a tree, not a straight line...

Bob, my last my sentences on the subject: what YOU are proposing is YOUR tree in my plots:

Integral [d x] A * Exp(B*x) = A/B Exp(B*x)

a pure exponential in x which is YOUR tree. Marco's tree is different.

I am done!
Kai

Not sure what you mean by "MY" tree. I do reductions, extensions, and 4 plies of forward pruning also. The problem I have is you are absolutely mangling a well-defined term "width/widening." That is _not_ happening...

[wgarvin]

Maybe it would be worthwhile to instrument Stockfish to record the actual number of nodes it explores at each ply during a search, and print those statistics after each iteration?

Then for a chosen FEN, we could plot what that actual tree looks like at various depths and see if it resembles the model or not.

[bob]

Maybe it would be worthwhile to instrument Stockfish to record the actual number of nodes it explores at each ply during a search, and print those statistics after each iteration?

Then for a chosen FEN, we could plot what that actual tree looks like at various depths and see if it resembles the model or not.

These kinds of discussions don't need to be obfuscated by real data.

[kranium]

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)