Questions on SMP search

[Eelco de Groot]

IMHO the intellectual effort needed to understand this matter is the following:

Let's say I search at depth 20, then I search at depth 21. What have been changed between the two searches ?

Intuitively and also assuming very low LMR the answer is: "in the second case I search at higher depth".

IMHO, with today very aggressive LMR and pruning the most realistic answer is:"in the second case I search a wider tree" (not necessarly deeper).

The "depth" parameter in the iterative deepening loop is actually misleading, it should be called "wideness".

If we got this concept then everything comes more easier. But I understand that this concept requires some intelelctual effort especcialy for traditionally minded people.

I only read this last post of the whole thread, so I probably miss what exactly is being discussed, but I was just wondering if, in the case of Stockfish, this is true. It is true that with any additional ply there is less futility pruning and especially if we are talking about ALL nodes, more moves leaving the node will be searched, unless one of the moves searched leads to a beta cutoff.

But there is to my knowledge very little code that can say "We have searched this node to N-1 plies and now we should search it to depth N, but the chances that a new search in this node will change anything at the root are so infinitesimally small that it is safe to stop now and accept the N-1 result from the transposition table. Back up this N-1 result to the parent node and proceed with the next move from the parent node."

The only thing that comes close to this is the Reduction Matrix in Stockfish that determines the reduced search depth for moves without any extension, they will be searched with reduced depth only unless they fail high in this reduced search, and where the reduction is based solely on depth and move count. In theory these moves only need a positional evaluation + already reached tactical depth and there is no need for iterative deepening anymore. But even here the reduction does not halt iterative deepening. Reduced search to depth N will always be deeper than Reduced search to depth N - 1.

Code: Select all

  // Step 14. Reduced search

  // Reduction lookup tables (initialized at startup) and their getter functions
  int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber]

  template <NodeType PV>
  inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; }

Code: Select all

void init_search() {

  int d;  // depth (ONE_PLY == 2)
  int hd; // half depth (ONE_PLY == 1)
  int mc; // moveCount

  // Init reductions array
  for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++)
  {
      double    pvRed = log(double(hd)) * log(double(mc)) / 3.0;
      double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25;
      ReductionMatrix[PV][hd][mc]    = (int8_t) (   pvRed >= 1.0 ? floor(   pvRed * int(ONE_PLY)) : 0);
      ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0);
  }

In theory you could have a reduction with a derivative function >= 1, I have not really made tables of the reduction but I don't think Stockfish code does this?

Regards, Eelco

[bob]

Given that, let's move on. We have two programs A and B. My program is A and can search to depth 12. It is new and doesn't do all the bells and whistles. Your program is B and typically searches to depth 24. We both start to work on a parallel search at the same time. After 3 months, we compare notes and I produce a gain of +70 Elo, while you produce a gain of +35. Is my SMP more efficient? That is, if I take my SMP search and graft it perfectly into your program, will I get +70?

Unlikely. It takes (at depths around 12) a ply to gain 70 Elo. It takes more than a ply to gain 70 Elo at depth 24, by the law of diminishing returns. So comparing the Elo of the two programs does not say a thing about the efficiency of the parallel implementation. Which is _exactly_ what I have been saying from the get-go. And that is _exactly_ why any parallel algorithm text book or paper discusses speedup as _the_ measure of parallel algorithm efficiency.

Ok so far so good, but there is one thing that you are constantly missing from the equation.
At higher depth you progress faster through plies in terms of speed up than at lower depth!

No you don't, and that is a purely ridiculous statement. As I go deeper I go faster?

Why? Because at higher depth EBF is smaller than on lower depth (because of more selectivity in search at higher depths and less pieces on the board).

No it isn't and there is a ton of data supporting this. EBF remains fairly constant. It _must_. We don't prune more at deeper depths.

So the same program at depth lets say 20 takes 2x speed up to reach depth 21 and at depth 30 only 1.8x speed up to reach depth 31. Or in other words if it takes 2x more time to reach depth 21 than to reach depth 20, it will take only 1.8x more time to reach depth 31 than to reach 30.
So when you apply your SMP at depth 24 instead of 12 you will gain more than a ply (assuming that you gain one ply at depth 12), how much more and will that be enough to gain 70 Elo that's another question.

And exactly that (smaller EBF at higher depths) is the reason why time to depth metric is wrong!

It's important to notice that this effect of reduction of EBF at higher depths is more pronounced at programs that have high selectivity (strong LMR) and that reach higher depths quicker, therefore the effect is much more easily observable with Stockfish than with Crafty!
And the effect is almost non-existing at programs older than 2000.

The real deal is a diminishing return defined as (delta)Elo/(delta)speed-up. That one is the interesting one and so far we do not know the answer.
So to repeat what I wrote many post back (and what you obviously failed to read) if speed up of processor from 1x to 2x brings 50 Elo, will speed up from 512x to 1024x also bring 50 Elo, or it will bring less (or maybe even more)?

Definitely less. Again, diminishing return is a fact, not a conjecture. How much less is both debatable and irrelevant. But less, for certain.

It's not definitive and I've never seen data that support that claim (data from 2005 onwards, not before).

[bob]

IMHO the intellectual effort needed to understand this matter is the following:

Let's say I search at depth 20, then I search at depth 21. What have been changed between the two searches ?

Intuitively and also assuming very low LMR the answer is: "in the second case I search at higher depth".

IMHO, with today very aggressive LMR and pruning the most realistic answer is:"in the second case I search a wider tree" (not necessarly deeper).

The "depth" parameter in the iterative deepening loop is actually misleading, it should be called "wideness".

If we got this concept then everything comes more easier. But I understand that this concept requires some intelelctual effort especcialy for traditionally minded people.

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.

[mcostalba]

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.

[mcostalba]

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.

[mcostalba]

In theory you could have a reduction with a derivative function >= 1, I have not really made tables of the reduction but I don't think Stockfish code does this?

Sorry but I don't think I have understood the question...

[Eelco de Groot]

In theory you could have a reduction with a derivative function >= 1, I have not really made tables of the reduction but I don't think Stockfish code does this?

Sorry but I don't think I have understood the question...

Hi Marco,

What I meant was that theoretically there are positions where searching is not very productive, because you need a positional move. If your evaluation function was good enough, a one ply search would suffice. In practice the evaluation function can't be relied upon, and search has to aid the positional evaluation. I don't think it is very good at this, but on the other hand if you have searched to depth D the aditional effort for depth D+1 is not so large anymore, so in practically every node you will just pile on more depth, just to make the positional eval more precise. There are still tactics involved of course but they only bring positional gains, in these "positional" positions. That is another reason for keeping going deeper (i.e. iterative deepening).

If you have a node with a D-1 transposition table result and an acceptable bound, but at this iteration you should search to depth D you will always do this (search deeper). I think for the above reasons. There are alternatives, for instance you could search to depth D-1 again but only wider. Or search to depth D but because the node is not likely to change the root, search narrower than at depth D-1. Or you could make a decision related to the bound; if you have searched to depth D-1 with a lower bound than necessary, or the searchresult was with the necessary bound but the result much worse than the bound, accept the D-1 result in the transposition table. Or you could have code in the ReductionMatrix that gives a Reduction X at depth D and a Reduction X+1 plies at depth D+1 plies, if depth D+1 is deep enough. Then the Reduction rises as fast as the depth D increases, the derivative function == 1 (Derivative of the function used to compute the reduction depth in ReductionMatrix) and iterative deepening stops, in nodes with a reduced search.

The fact that there is almost no code like this in Stockfish is probably because of the reasons stated in the first paragraph, well at least that is my explanation Iterative deepening works just too well and the evaluation functions just suck too much to do otherwise:? At least for the moment.

Marco I hope I made the 'derivative function == 1' statement a bit clearer now?

I said none of the ideas in paragraph 2 are in Stockfish for now but that does not mean they are all bad ideas, just probably at the moment the combination of search and evaluation function is not evolved enough to deviate much from alpha beta, + "normal" reductions and pruning. And I think that some of these schemes become more plausible at higher depths, where testing is harder... Well this post is more meant to provoke/invite some discussion.

Eelco

[Albert Silver]

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.

Correct me if I'm wrong, but you haven't really changed the fact that it is greater depth, merely the consequences of greater depth. If I understand, you are saying it is not merely like adding an extension cord to a wire, but more like adding a layer to a pyramid. Ply one is the base of the pyramid, and the top brick is the last ply. When you add a ply, you are increasing the depth, but not simply adding a brick at the top, but rather a full layer so that everything else is proportionately increased as well. This is a very rough analogy, but it is how I understood what you are saying.

[mcostalba]

Correct me if I'm wrong, but you haven't really changed the fact that it is greater depth, merely the consequences of greater depth. If I understand, you are saying it is not merely like adding an extension cord to a wire, but more like adding a layer to a pyramid. Ply one is the base of the pyramid, and the top brick is the last ply. When you add a ply, you are increasing the depth, but not simply adding a brick at the top, but rather a full layer so that everything else is proportionately increased as well. This is a very rough analogy, but it is how I understood what you are saying.

Your example is good but should be reversed.

Suppose that bricks correspond to searched nodes (say one brick is 1000 nodes).

Now the tip of the pyramid is ply one, while the basis of the pyramid are the qsearch nodes.

When you advance the depth to D+1 you add a brick on the top but also a full layer of briks all around the pyramid that increases its lateral area, and finally, also of course a layer at the bottom.

But when the branch factor is very high the layer at the bottom is not the biggest part that has been added, the biggest part are the lateral walls that have been increased.

[Eelco de Groot]

What I meant was that theoretically there are positions where searching is not very productive, because you need a positional move. If your evaluation function was good enough, a one ply search would suffice. In practice the evaluation function can't be relied upon, and search has to aid the positional evaluation (reason °1). I don't think it is very good at this, but on the other hand if you have searched to depth D the aditional effort for depth D+1 is not so large anymore (reason °2), so in practically every node you will just pile on more depth, just to make the positional eval more precise. There are still tactics involved of course but they only bring positional gains, in these "positional" positions. That is another reason (°3) for keeping going deeper (i.e. iterative deepening).

Another reason (°4) for always searching deeper is I think that you refresh the TT entries this way. So there is less chance that the information is overwritten. Maybe you could consider separate small hashtables for nodes you do not want to re-search or deepen right now or may not want to search deeper after the present search. There is no risk the information is overwritten then. Or prevent overwriting some of these entries by refreshing them without searching them deeper.

Another reason (°5) is the assumption you make that this search should work in analysis mode, where you don't know at which iteration the search will stop. So assuming you will do at least two more iterations, Iteration N+2 will probably go better if there also is a full Iteration N+1. Searching under time constraints will change this, also searching to fixed depth. So there the last iterations probably could be made more selective, for instance by not re-searching/deepening the PV at high depths, only the other rootmoves, which goes much faster unless there is a Fail High in one of the other rootmoves. You might just save enough time to re-search/resolve the Fail High.