Questions on SMP search

[bob]

I do not believe that is a rational explanation. If I advance to depth D+1, I _definitely_ search deeper. "Wider" is not a function of depth, it is a function of pruning. And none of us, stockfish included, is searching more at each ply as we go deeper, the EBF wouild be increasing rather than remaining constant, were that true...

And it is absolutely false, per Milos statement, that EBF reduces as we go deeper. It would be nice, because we could solve chess. But it isn't true.

To understand the deal please think for a moment on the fact that pruning is a function of depth.

If I reach a node when remaining depth 5 then I will start to prune quite aggresivly already after few moves.

If I reach the _same_ node but when remaining depth is 6 then I will start pruning later and it means to search more moves of that same node and so search wider.

Here the key words to think upon are:

1) Remaining depth

2) Quantity of pruning is a function of remaining depth

Now the last step: advancing to depth D+1 it means to reach a given node with an higher remaining depth (be it 5, 10, 20, it does not matter, it is not the root search depth, it is the remaining depth when search reaches a given intermediate node that counts) and reaching a given node with an higher remaining depth it means to search wider, to search more moves of that node.

That's a very twisted definition of "width". Because using that definition, each successive search iteration is wider, with or without reductions, since each depth multiplies the nodes horizontally by a huge amount, while increasing the depth only 1 ply.

But if your EBF is fairly constant at 2.0, then you can't be going wider at depth 20 than you do at 10, unless you use that rather strange definition of wide. I would call today's programs exactly the opposite of that. They are probing quite deeply and narrowly along what we hope are important, and aggressively reduce (or even prune near the tips) those that are less important. All with the goal of going deeper than ever before, knowing we are giving up some accuracy to gain depth along selected pathways.

[Milos]

I do not believe that is a rational explanation. If I advance to depth D+1, I _definitely_ search deeper. "Wider" is not a function of depth, it is a function of pruning. And none of us, stockfish included, is searching more at each ply as we go deeper, the EBF wouild be increasing rather than remaining constant, were that true...

And it is absolutely false, per Milos statement, that EBF reduces as we go deeper. It would be nice, because we could solve chess. But it isn't true.

To understand the deal please think for a moment on the fact that pruning is a function of depth.

If I reach a node when remaining depth 5 then I will start to prune quite aggressively already after few moves.

If I reach the _same_ node but when remaining depth is 6 then I will start pruning later and it means to search more moves of that same node and so search wider.

Here the key words to think upon are:

1) Remaining depth

2) Quantity of pruning is a function of remaining depth

Now the last step: advancing to depth D+1 it means to reach a given node with an higher remaining depth (be it 5, 10, 20, it does not matter, it is not the root search depth, it is the remaining depth when search reaches a given intermediate node that counts) and reaching a given node with an higher remaining depth it means to search wider, to search more moves of that node.

You are absolutely right Marco. But as you said, you need "a fresher state of mind" to understand it...

Just as in illustration here is a graph that illustrates what you are saying.



We have in red line a search tree up to depth 15, when there is no LMR, and no aggressive pruning or NMR.
We have in green line a search tree up to depth 12, where aggressive pruning kicks in at remaining depth 3.
We have in blue line a search tree up to depth 15, where aggressive pruning kicks slightly before (since searched depth is bigger) at remaining depth 4.
What we can see is that "blue" tree at depth 12 is wider than the "green" tree (even though it's narrower than the "red" tree).

EBF of the "red" tree (in the constructed example) is num_nodes^(1/depth)=2.5.
EBF of the "blue" tree is 2.18.
EBF of the "green" tree is 2.20.

[Laskos]

I do not believe that is a rational explanation. If I advance to depth D+1, I _definitely_ search deeper. "Wider" is not a function of depth, it is a function of pruning. And none of us, stockfish included, is searching more at each ply as we go deeper, the EBF wouild be increasing rather than remaining constant, were that true...

And it is absolutely false, per Milos statement, that EBF reduces as we go deeper. It would be nice, because we could solve chess. But it isn't true.

To understand the deal please think for a moment on the fact that pruning is a function of depth.

If I reach a node when remaining depth 5 then I will start to prune quite aggressively already after few moves.

If I reach the _same_ node but when remaining depth is 6 then I will start pruning later and it means to search more moves of that same node and so search wider.

Here the key words to think upon are:

1) Remaining depth

2) Quantity of pruning is a function of remaining depth

Now the last step: advancing to depth D+1 it means to reach a given node with an higher remaining depth (be it 5, 10, 20, it does not matter, it is not the root search depth, it is the remaining depth when search reaches a given intermediate node that counts) and reaching a given node with an higher remaining depth it means to search wider, to search more moves of that node.

You are absolutely right Marco. But as you said, you need "a fresher state of mind" to understand it...

Just as in illustration here is a graph that illustrates what you are saying.



We have in red line a search tree up to depth 15, when there is no LMR, and no aggressive pruning or NMR.
We have in green line a search tree up to depth 12, where aggressive pruning kicks in at remaining depth 3.
We have in blue line a search tree up to depth 15, where aggressive pruning kicks slightly before (since searched depth is bigger) at remaining depth 4.
What we can see is that "blue" tree at depth 12 is wider than the "green" tree (even though it's narrower than the "red" tree).

EBF of the "red" tree (in the constructed example) is num_nodes^(1/depth)=2.5.
EBF of the "blue" tree is 2.18.
EBF of the "green" tree is 2.20.

Very nice, could you put a logarithmic scale on the horizontal axis? That would show the widening of the tree at even lower depths, and the lines will be almost straight.

Kai

[bob]

ANY tree gets wider as it goes deeper. Otherwise you can search it in O(1) time. Your graph is pointless and uninformative to the max...

Who doesn't get N = W^D? The deeper you go, the more terminal nodes you have and the wider the tree. But that is not a recognized usage of "wider". One normally uses EBF as a synonym for "width", and EBF doesn't change as the search goes deeper... Unless something significant changes, such as the program has to change its mind, which wrecks move ordering and the EBF does, by definition, get larger when changes occur. That's not exactly 6:00 news material, it was known when "How to program a computer to play chess" was first written, explaining minimax, by Claude Shannon. I think this was around either the late 1940's or right around 1950. I have an autographed copy of that paper in my office files that I can check Monday.

[bob]

I do not believe that is a rational explanation. If I advance to depth D+1, I _definitely_ search deeper. "Wider" is not a function of depth, it is a function of pruning. And none of us, stockfish included, is searching more at each ply as we go deeper, the EBF wouild be increasing rather than remaining constant, were that true...

And it is absolutely false, per Milos statement, that EBF reduces as we go deeper. It would be nice, because we could solve chess. But it isn't true.

To understand the deal please think for a moment on the fact that pruning is a function of depth.

If I reach a node when remaining depth 5 then I will start to prune quite aggressively already after few moves.

If I reach the _same_ node but when remaining depth is 6 then I will start pruning later and it means to search more moves of that same node and so search wider.

Here the key words to think upon are:

1) Remaining depth

2) Quantity of pruning is a function of remaining depth

Now the last step: advancing to depth D+1 it means to reach a given node with an higher remaining depth (be it 5, 10, 20, it does not matter, it is not the root search depth, it is the remaining depth when search reaches a given intermediate node that counts) and reaching a given node with an higher remaining depth it means to search wider, to search more moves of that node.

You are absolutely right Marco. But as you said, you need "a fresher state of mind" to understand it...

Just as in illustration here is a graph that illustrates what you are saying.



We have in red line a search tree up to depth 15, when there is no LMR, and no aggressive pruning or NMR.
We have in green line a search tree up to depth 12, where aggressive pruning kicks in at remaining depth 3.
We have in blue line a search tree up to depth 15, where aggressive pruning kicks slightly before (since searched depth is bigger) at remaining depth 4.
What we can see is that "blue" tree at depth 12 is wider than the "green" tree (even though it's narrower than the "red" tree).

EBF of the "red" tree (in the constructed example) is num_nodes^(1/depth)=2.5.
EBF of the "blue" tree is 2.18.
EBF of the "green" tree is 2.20.

Very nice, could you put a logarithmic scale on the horizontal axis? That would show the widening of the tree at even lower depths, and the lines will be almost straight.

Kai

Of course they will. the tree _is_ exponential, remember. This shows exactly nothing that wasn't known 60+ years ago...

Yes the EBF is lower. Yes we are going deeper. That's been happening since the 60's.

[mcostalba]

ANY tree gets wider as it goes deeper. Otherwise you can search it in O(1) time. Your graph is pointless and uninformative to the max...

Who doesn't get N = W^D? The deeper you go, the more terminal nodes you have and the wider the tree. But that is not a recognized usage of "wider". One normally uses EBF as a .

Ok, this is my last attempt, after this I'll give up

We are _not_ talking of terminal nodes !

If there is no pruning the three don't get wider in the meaning I tried to explain. Again, what I said is that a given node searched when reamining depth is 5 is not as the same node searched when remaining depth is 6, this is because you prune more at depth 5 than 6. What I am talking about (hopelessy) is of "moves per each node" not total nodes.

Please read back my post about possible experiment. If even that does not clarify the idea then I throw in the towel !

[bob]

ANY tree gets wider as it goes deeper. Otherwise you can search it in O(1) time. Your graph is pointless and uninformative to the max...

Who doesn't get N = W^D? The deeper you go, the more terminal nodes you have and the wider the tree. But that is not a recognized usage of "wider". One normally uses EBF as a .

Ok, this is my last attempt, after this I'll give up

We are _not_ talking of terminal nodes !

If there is no pruning the three don't get wider in the meaning I tried to explain.

Is not the purpose of pruning/reductions to force some of that "width" into more "depth"? That's why _I_ am doing those things. It is an effect of doing things like they are done, not a reason for doing them that way...

If we don't push the breadth out into "depth" then we can't go deep enough.

Again, what I said is that a given node searched when reamining depth is 5 is not as the same node searched when remaining depth is 6, this is because you prune more at depth 5 than 6. What I am talking about (hopelessy) is of "moves per each node" not total nodes.

Please read back my post about possible experiment. If even that does not clarify the idea then I throw in the towel !

It doesn't clarify the idea at all. Of course, if we go deeper, we get a better result. Is it caused by doing less pruning close to the root (assuming your reduction or pruning decisions are based on remaining depth, which is not a given)? Or is the better result caused by more depth? If width is important, it is easy to do full-width. If depth is more important, then we have to sacrifice width because our search space is fixed for specific hardware and software. All we can do is alter the shape of the search space. Deeper and narrower, or shallower and wider. But to go deeper, and talk about getting wider is really stretching what is going on. Each ply has a fixed cost. The EBF. The EBF does not get bigger or smaller as depth increases. At least mine doesn't. yes, there is always variability. But there is no trend up or down from iteration 1 to 30, consistently... There can't be.

So exactly what is the point of such a rambling description? Of course you do more 6 plies from the root than at 5, and so forth. But as you advance the depth, you _keep_ those plies near the tip. This is the definition of exponential growth. Yes we have driven the EBF from 6+ with plain alpha/beta to around 2.0 with LMR + futility-type pruning near the tips. But it EBF remains constant. Which means the tree is not getting wider in any normal sense. The last N plies are always pretty "scant" due to forward pruning. All LMR/pruning does is keep the last N plies pretty "thin" so that we can go deeper...

But mixing wider and deeper in this context is a _real_ big stretch. In the 60s we were doing a tapered search similar to that used in MacHack. At the root we searched N moves, at ply 2, N - something, at ply 3, N - something_bigger, etc.

If you want to say that when you go from a 5 ply search, assuming N is 2^d, so that at the root (5 plies) you look at 32, then 16, then 8, then 4 and finally 2 at depth 5, and you advance to a 6 ply search where you would search with N=64, 32, 16, 8, 4 and 2, then yes you got wider at the root. So what? You still have 5 plies of search with the same error. And it still costs you a bunch to go from 5 to 6, not 2x like today...

You can make this same argument about accuracy. searches near the root provide more accurate info than searches near the tips. Because of the mechanics of the search, not by design or intent...

[Milos]

ANY tree gets wider as it goes deeper. Otherwise you can search it in O(1) time. Your graph is pointless and uninformative to the max...

Who doesn't get N = W^D? The deeper you go, the more terminal nodes you have and the wider the tree. But that is not a recognized usage of "wider". One normally uses EBF as a synonym for "width", and EBF doesn't change as the search goes deeper... Unless something significant changes, such as the program has to change its mind, which wrecks move ordering and the EBF does, by definition, get larger when changes occur. That's not exactly 6:00 news material, it was known when "How to program a computer to play chess" was first written, explaining minimax, by Claude Shannon. I think this was around either the late 1940's or right around 1950. I have an autographed copy of that paper in my office files that I can check Monday.

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.

[bob]

ANY tree gets wider as it goes deeper. Otherwise you can search it in O(1) time. Your graph is pointless and uninformative to the max...

Who doesn't get N = W^D? The deeper you go, the more terminal nodes you have and the wider the tree. But that is not a recognized usage of "wider". One normally uses EBF as a synonym for "width", and EBF doesn't change as the search goes deeper... Unless something significant changes, such as the program has to change its mind, which wrecks move ordering and the EBF does, by definition, get larger when changes occur. That's not exactly 6:00 news material, it was known when "How to program a computer to play chess" was first written, explaining minimax, by Claude Shannon. I think this was around either the late 1940's or right around 1950. I have an autographed copy of that paper in my office files that I can check Monday.

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. Nobody compares two different programs, with two different EBFs, and two different depths, and tries to conclude anything about the "width" of the tree. May as well compare the number of letters in the moves that produce the tree, or whatever...

[UncombedCoconut]

I'm inspired to try drawing superimposed Stockfish search trees at varying depths. Hopefully it will be pretty and/or useful on CPW.
Several questions though, if anyone else is interested:
Are similar pictures from older programs available?
Is the starting position a good choice for the root?
Should I try to draw deep enough trees to show features like recursive nullmove?
Should I treat subtrees of a nullmove in a special way, or even omit them?
Is there any harm in neglecting transpositions (and simply tracing make/unmake)?

I guess some of these will become obvious once I start generating the pictures.