Questions on SMP search

[Milos]

Searching to greater depth can only ever be an elo boost if it means that every once in a while it causes you to change your mind. If there is any diminishing return from greater search depth, then it has to be that you're less likely to change the root move.
Even if there's no immediate causal relationship, then one must surely be a proxy for the other, right? Or am I missing something?

Causality exists, but direction can be different. Basically what you are saying is Newborn's hypothesis which cannot be proven even with the old (Crafty 19.6) data. Just read the conclusion from "New Results in Deep-Search Behaviour" paper.

The simple answer is without LMR no, with LMR (more aggressive Null Move Pruning and other stuff from 2005 onwards) most probably yes.

Why would that be the case?
Not saying it's right or wrong, I don't know, but I don't understand why that would be true.

It's not that LMR is a magic thing. It's about selectivity of the search. With more selective search diminishing return is smaller. There is also no reason why diminishing return could not be negative so that when you double your search time (attention not when you increase depth!) you actually gain more Elo than before.

[bob]

The simplest refutation of your nonsense is "what happens when the hardware is fast enough to search to a forced mate from the initial position?" What will _another_ ply get you then?

Nope, your refutation is wrong as usual. You don't know the rating of "perfect play"=forced mate from the initial position (if there is a forced mate, high probability is that chess is a draw game from the initial position).
Because chess is a finite game, final rating (which is of course just relative to your starting rating) must also be finite so when you reach it you reach a discontinuity point. There is absolutely no reason why elo vs. speed curve must have a derivative in that point.

Completely beyond hopeless... Once I see a forced mate, or a forced draw, additional plies produce zero increase. Backing up just one ply is not going to produce a player that is measurably weaker than the perfect player. While back at depth 1-2-3-4-5 each additional ply produces a significant gain. Diminishing returns is a fact, not a theory.

[bob]

Searching to greater depth can only ever be an elo boost if it means that every once in a while it causes you to change your mind. If there is any diminishing return from greater search depth, then it has to be that you're less likely to change the root move.
Even if there's no immediate causal relationship, then one must surely be a proxy for the other, right? Or am I missing something?

Causality exists, but direction can be different. Basically what you are saying is Newborn's hypothesis which cannot be proven even with the old (Crafty 19.6) data. Just read the conclusion from "New Results in Deep-Search Behaviour" paper.

The simple answer is without LMR no, with LMR (more aggressive Null Move Pruning and other stuff from 2005 onwards) most probably yes.

Why would that be the case?
Not saying it's right or wrong, I don't know, but I don't understand why that would be true.

It's not that LMR is a magic thing. It's about selectivity of the search. With more selective search diminishing return is smaller. There is also no reason why diminishing return could not be negative so that when you double your search time (attention not when you increase depth!) you actually gain more Elo than before.

I know there is no point in trying to educate you, but for the record, for those that actually want to see facts, LMR _increases_ diminishing return. It doesn't eliminate it. We get less from a single extra ply today than we did 20 years ago, and that is trivially provable. But don't let facts get in the way of imagination and nonsense...

[bob]

Diminishing return is not about how often I change best move at different depth.

How can it not be?
Searching to greater depth can only ever be an elo boost if it means that every once in a while it causes you to change your mind. If there is any diminishing return from greater search depth, then it has to be that you're less likely to change the root move.
Even if there's no immediate causal relationship, then one must surely be a proxy for the other, right? Or am I missing something?

The simple answer is without LMR no, with LMR (more aggressive Null Move Pruning and other stuff from 2005 onwards) most probably yes.

Why would that be the case?
Not saying it's right or wrong, I don't know, but I don't understand why that would be true.

It isn't true, and you are wasting your time reading the nonsensical answers you are getting from him...

[Milos]

I know there is no point in trying to educate you, but for the record, for those that actually want to see facts, LMR _increases_ diminishing return. It doesn't eliminate it. We get less from a single extra ply today than we did 20 years ago, and that is trivially provable. But don't let facts get in the way of imagination and nonsense...

Diminishing return in terms of (delta)Elo vs. (delta)depth certainly exists, and ofc gets larger with more selectivity because there is more chance you'll miss something when advancing through plies.
However, that is not the point at all.
The point of diminishing return is to answer the question will speeding of hardware bring the same improvement in rating as before. So we want to know if there is a diminishing return of speed-up not of increased depth of search.
There is also an additional effect there but that one is (currently) negligible. The effect is that EBF is actually reduced as you progress deeper and deeper in the search since you have less and less pieces on the board. So you are progressing even faster.

[bob]

I know there is no point in trying to educate you, but for the record, for those that actually want to see facts, LMR _increases_ diminishing return. It doesn't eliminate it. We get less from a single extra ply today than we did 20 years ago, and that is trivially provable. But don't let facts get in the way of imagination and nonsense...

Diminishing return in terms of (delta)Elo vs. (delta)depth certainly exists, and ofc gets larger with more selectivity because there is more chance you'll miss something when advancing through plies.
However, that is not the point at all.
The point of diminishing return is to answer the question will speeding of hardware bring the same improvement in rating as before. So we want to know if there is a diminishing return of speed-up not of increased depth of search.
There is also an additional effect there but that one is (currently) negligible. The effect is that EBF is actually reduced as you progress deeper and deeper in the search since you have less and less pieces on the board. So you are progressing even faster.

You are correct, that _is_ the point. And the answer to the question is "no". Each additional ply does _not_ provide the same gain as the previous additional ply. That is something intuitively obvious to the casual observer, and every test to date has supported the idea. Additional plies definitely help. But on a decreasing scale.

[Milos]

Completely beyond hopeless... Once I see a forced mate, or a forced draw, additional plies produce zero increase. Backing up just one ply is not going to produce a player that is measurably weaker than the perfect player. While back at depth 1-2-3-4-5 each additional ply produces a significant gain. Diminishing returns is a fact, not a theory.

Probably you are not making even the smallest effort to understand what I am writing.
Diminishing return in terms of depth defined as (delta)Elo/(delta)depth certainly exists. But this one is completely useless research topic because it doesn't provide us any useful information (we already know the answer intuitively).
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)?
The fact is that EBF reduces as you progress deeper and deeper (due to more selectivity in search at higher depths - recursive nature of some prunings, etc. and due to less pieces on the board) so you actually gain more plies for the same speed up. The plies you gain have less value than before (in terms of Elo), but there are more of them. And the question is which effect is dominant (if any). And we don't know the answer.

[bob]

Completely beyond hopeless... Once I see a forced mate, or a forced draw, additional plies produce zero increase. Backing up just one ply is not going to produce a player that is measurably weaker than the perfect player. While back at depth 1-2-3-4-5 each additional ply produces a significant gain. Diminishing returns is a fact, not a theory.

Probably you are not making even the smallest effort to understand what I am writing.
Diminishing return in terms of depth defined as (delta)Elo/(delta)depth certainly exists. But this one is completely useless research topic because it doesn't provide us any useful information (we already know the answer intuitively).

OK, do we agree that if we go from depth D to depth D+1 we get more (Elo) than when going from depth G to depth G+1, so long as G > D? Because I believe that to be an absolute fact.

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. Not abstract things like Elo gain, or reduced error margins, just pure speedup. How much faster does the same algorithm run using N processors than when run using 1 processor.

Why we have to have this nonsensical kind of discussion is beyond me. I teach parallel programming. I have probably every text book written on the subject in my office. I actually read them. And know what the authors are doing/saying/measuring.

Is that so hard to grasp?

I'm not interested, when discussing parallel search, in comparing both the parallel algorithm _and_ the underlying chess engine skill level. I only care about the parallel search implementation. Measuring Elo gain gives a number that one can certainly draw conclusions from. But not a number I can compare to another program's number to decide which parallel implementation is better...

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.

The fact is that EBF reduces as you progress deeper and deeper (due to more selectivity in search at higher depths - recursive nature of some prunings, etc. and due to less pieces on the board) so you actually gain more plies for the same speed up. The plies you gain have less value than before (in terms of Elo), but there are more of them. And the question is which effect is dominant (if any). And we don't know the answer.

Actually, some of us do... You get the same Elo gain by doubling the speed of the hardware naturally, or with a parallel search that reaches the same depth in 1/2 the time. Because both will reach exactly the same depth, at exactly the same time, and there's no difference.

[Milos]

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!
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).
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).

[mcostalba]

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.