Questions on SMP search

[bob]

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.

I would not exclude anything, since all nodes searched are a part of the tree. Clearly, if you compare current programs to older programs, the older programs have a shorter/fatter tree shape. Current programs are doing reductions and forward pruning which "squeezes" the shape of the tree into a narrow vertical area, which drives the depth deeper.

I don't think the picture is going to reveal anything unexpected at all. You can go shallow/fat or deep/skinny, or anything in between... If you get too skinny you introduce too many errors by failing to search key moves at some or many plies. If you get too fat, you fail to go deep enough and miss tactical threats. Got to be just right...

[mcostalba]

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.

I would suggest to avoid positions with tactical shots that produce a huge cut-off at some point in the search.

I would suggest to use quiet positions where the best move at depth 1 is still the best move at the end of the search.

[Laskos]

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.

Bob, you seem to be totally out of depth here. You missed the most important word in my sentence, which is "almost".

I took Marco's model (which by any means is correct) and simplified it to just having two different in selectivity prunings, one when there are more than 5 plies remaining, another when when there are 5 or less plies. One needs an integration on depth to cumulate nodes, and even this simplified model propagates this important "almost" all the way down, not just last 5 plies.

The formula for wideness of the tree (formal "nodes" as a function of _target_ Depth) is (on logarithmic in base 10 scale)

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) ]

The graph below presents how Marco's tree is widening when setting a higher target depth. Your "tree" is not widening in any way if you constantly say that it's purely exponential (the same straight line on the logarithmic scale for every target depth).

Maybe that's the main difference between Stockfish and Crafty, leaving apart the strength, of course



Kai

[bob]

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.

Bob, you seem to be totally out of depth here. You missed the most important word in my sentence, which is "almost".

I took Marco's model (which by any means is correct) and simplified it to just having two different in selectivity prunings, one when there are more than 5 plies remaining, another when when there are 5 or less plies. One needs an integration on depth to cumulate nodes, and even this simplified model propagates this important "almost" all the way down, not just last 5 plies.

The formula for wideness of the tree (formal "nodes" as a function of _target_ Depth) is (on logarithmic in base 10 scale)

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) ]

The graph below presents how Marco's tree is widening when setting a higher target depth. Your "tree" is not widening in any way if you constantly say that it's purely exponential (the same straight line on the logarithmic scale for every target depth).

Maybe that's the main difference between Stockfish and Crafty, leaving apart the strength, of course



Kai

Now try the interesting case, tree to depth 25 to depth 26. You pick a shallow depth where the 4 plies of pruning are a significant part of the total search. At depth 24, vs 25, you are not going to see much change.

For a normal search, a 1-ply search has mostly q-search. By the time you get to depth 6, the shape of the tree has drastically changed. As for Marco's tree widening differently from a normal tree, No I do not see anything significant. The term "widening" is the wrong term, as I have _repeatedly_ said. "widening" has to do with width. Width as in N = W ^ D, or N = 2 * W ^ (D / 2) for AB. W is not changing in any significant way if the EBF is constant. Unless you have a completely new system of mathematics at work...

[Laskos]

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.

Bob, you seem to be totally out of depth here. You missed the most important word in my sentence, which is "almost".

I took Marco's model (which by any means is correct) and simplified it to just having two different in selectivity prunings, one when there are more than 5 plies remaining, another when when there are 5 or less plies. One needs an integration on depth to cumulate nodes, and even this simplified model propagates this important "almost" all the way down, not just last 5 plies.

The formula for wideness of the tree (formal "nodes" as a function of _target_ Depth) is (on logarithmic in base 10 scale)

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) ]

The graph below presents how Marco's tree is widening when setting a higher target depth. Your "tree" is not widening in any way if you constantly say that it's purely exponential (the same straight line on the logarithmic scale for every target depth).

Maybe that's the main difference between Stockfish and Crafty, leaving apart the strength, of course



Kai

Now try the interesting case, tree to depth 25 to depth 26. You pick a shallow depth where the 4 plies of pruning are a significant part of the total search. At depth 24, vs 25, you are not going to see much change.

I tried depth 25 to 22, as compared with depth 15 to 12, assuming the same model. I will explain below that you miss the point, here is the graph (please don't be fooled by the logarithmic scale)

The term "widening" is the wrong term, as I have _repeatedly_ said. "widening" has to do with width. Width as in N = W ^ D, or N = 2 * W ^ (D / 2) for AB. W is not changing in any significant way if the EBF is constant. Unless you have a completely new system of mathematics at work...

Your confusion seems to arise from EBF and the shape of the tree. EBF here is given by the endpoints of each shape curves, not their proper shape. The shape of the tree is a completely different matter.

Analyzing the endpoints, in both cases the number of nodes is ~12 times higher for 3 plies deeper (EBF ~2.3). The term "widening" is a very correct one noted here by Marco, I got to explain you for the last time the issue. As it is with a logarithmic scale, this factor of 12 is composed from 2 sources in both cases, depth 15 to 12 and 25 to 22. WIDENING accounts for a factor of ~3, deepening by a factor of ~4 (agreed that 3x4=12?). The shape of the tree (not EBF) is determined with a comparable effort by both widening and deepening. Where did you get this rule N = W^D? - this is an empirical, inaccurate rule of thumb even for EBF, without talking of the shape of the tree.

Kai

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

If you want to say "OK, but when we go to depth N+1 we are adding more width because we are now pruning one ply farther away from the root..." I completely agree. But that is constant whether you go from 11 to 12, or 21 to 22. There is nothing "wider" about 22 compared to 21, than there is when comparing 12 to 11.

I don't see what this argument is supposed to be about. My objection is absolutely mangling a well-known and well-understood term, namely "width". It took me quite a while here to get everyone off of the "BF" rather than "EBF" bandwagon, because BF can't be changed, that is a property of the game itself. One can adjust the EBF by pruning, reductions, extensions, and so forth. One can only adjust the BF by changing the actual rules of the game.

That's my perspective. We are not "increasing the width" as is continually mentioned. It just isn't happening. Each additional iteration certainly increases the accuracy, and increases the size of the tree (typically 2.0 x larger, or so). But we aren't increasing the EBF or each iteration would get progressively harder to search, in an exponential manner. I have not measured EBF to any great extent, but I have been thinking about doing this measurement inside Crafty and writing the results into the log files. Then we can get off the arguments with a lot of real data that can measure the EBF move to move, and across chunks of the game or even across an entire game. I did a couple of these by hand, and it is tedious. But if the discussion is going to rage on, I'll be happy to take Crafty, and make it compute the EBF, iteration by iteration, move by move, for some long games on ICC, and then post those numbers (probably graphically) here...

Then, at least for my case, we can analytically determine whether this "widening" idea applies or not. If you want to claim Stockfish is doing the widening where I am not, then somebody (not me) is going to have to instrument that program to offer some proof. And that proof would actually be something that shows where a change ought to be made, because there is no rational justification for increasing the EBF iteration by iteration. We'd _rather_ see the opposite. In fact, I believe that is what _every_ program is doing today. Compare version N to version N+3 or whatever, and I would claim and expect that N+3 has a significantly reduced EBF. So that it goes deeper. An additional ply on a narrower EBF tree is not as significant as an additional ply on a wider tree. But a wider tree loses plies that are traded for increased width and reduced error. A narrower tree increases depth and error. And the question becomes, is the program that is reducing the EBF doing so by reducing more worthless things than good things, so that there is a net gain, or not?

The only way I know to answer that is through testing. Which is what I do. All the time...

[Evert]

Where did you get this rule N = W^D? - this is an empirical, inaccurate rule of thumb[...]

It's neither.
It's simply the number of nodes N in a tree of with (an average of) W children per node and depth D.

Of course, when picturing a tree like that, my mental image is always for a well-balanced tree, which the trees searched by a chess program are not. Don't think that changes the meaning of that formula, but you may need to properly define what interpretation you give to W and D.

[Laskos]

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

[mcostalba]

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.

This is very interesting, if I have understood correctly you say that the extra effort that we need to move the search at depth N+1 is due for a good 45% (1,4 vs 1,6) by additional search at the inner nodes and only for 55% by an additional search at the new deeper leaf nodes.

[Laskos]

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.

This is very interesting, if I have understood correctly you say that the extra effort that we need to move the search at depth N+1 is due for a good 45% (1,4 vs 1,6) by additional search at the inner nodes and only for 55% by an additional search at the new deeper leaf nodes.

Yes, for going from N to N+1 the proportion is given by Log(~1.4)/Log(~1.6), which will result in ~40% for inner nodes and ~60% for deeper leaf nodes. This is just a model, a real engine would probably have different numbers, but qualitatively the result should be correct.

Kai