Should reduction depend on depth?

[lkaufman]

... but do you also agree that SF has a higher EBF WITHIN the last four plies?

It is hard to compare, but I think not. SF uses a bit wider margins, but throws out moves based on either of move count / value conditions. Critter throws out moves only when both conditions are true.

SF pruning condition (schematic):

Code: Select all

if &#40;move_count > n || futility_value < beta&#41; 
  skip_move;

Critter condition:

Code: Select all

if &#40;move_count > n && futility_value < beta&#41;
  skip_move;

Just think a bit about consequences of this difference.

Unless I'm mistaken, Critter (as well as Ippo and Rybka) also throw out quiet moves in low depth when the score is below a futility margin (which I believe starts at half a pawn under beta in Ippo and Critter and grows only very slowly with depth). Regarding the move-count based pruning, it is true that Critter (and Ippo) also require a score condition (which we found to be useless for Komodo), but our experience with it indicates that the score condition is only a mild restriction, far less significant than looking at less moves than SF. I think this is because when the score is good, you are probably at a CUT node where looking at less moves is not always a speedup.
Also, SF uses much higher static null margins.

Overall, I don't think it's even close. SF prunes far less than Critter or Ippo until you reach the depth where LMR becomes important. Just time 7 ply searches to see what I mean. SF is much slower.

[mcostalba]

Overall, I don't think it's even close. SF prunes far less than Critter or Ippo until you reach the depth where LMR becomes important. Just time 7 ply searches to see what I mean. SF is much slower.

One thing that differentiates SF from the Rybka/Ippo family is that we don't prune in advance captures, while the ippos build up the move generation 'target' in a dynamic way, so to generate less and less captures as long as the score is low.

I don't know (read: can you tell ?) if Komodo has adopted the same approach.

[rvida]

Unless I'm mistaken, Critter (as well as Ippo and Rybka) also throw out quiet moves in low depth when the score is below a futility margin (which I believe starts at half a pawn under beta in Ippo and Critter and grows only very slowly with depth).

Critter does not generate quiet moves when much bellow beta, only quiet checks. The margin is 0.66 pawns at depth 1 and grows to 1.32 pawns at depth 5. There is very little chance for a quiet non-checking move to rise score that much. Note that this margin is more generous than what is used later in value based pruning.

Code: Select all

depth	margin [cp]
1	 	66,41
2	 	82,81
3	 	99,22
4		115,63
5		132,03

Regarding the move-count based pruning, it is true that Critter (and Ippo) also require a score condition (which we found to be useless for Komodo), but our experience with it indicates that the score condition is only a mild restriction, far less significant than looking at less moves than SF.

Critter does look at far far more moves than SF, at least when the eval is close to scout (where it matters most).

Overall, I don't think it's even close. SF prunes far less than Critter or Ippo until you reach the depth where LMR becomes important. Just time 7 ply searches to see what I mean. SF is much slower.

Sorry, what has _time_ to do with this??? You should measure _nodes_ if anything. But due to different node counting it still isn't a good comparison.

Anyway, I have no idea what you are trying to prove here. LMP and LMR are not completely separate things. With more aggresive LMR you reach LMP nodes quicker and you cannot afford prune overaggresively. With more conservative LMR you can prune more.

[mcostalba]

Critter does look at far far more moves than SF, at least when the eval is close to scout (where it matters most).

Yes this is a natural and logical idea. We have tried hard to make it work in SF, namely to modulate movecount threshold above which move is pruned also with score distance to beta (now it depends just on depth), but we failed to produce something better than what we have now, although I think the idea "has to work" and perhaps we have missed something in the implementation.

[lkaufman]

Unless I'm mistaken, Critter (as well as Ippo and Rybka) also throw out quiet moves in low depth when the score is below a futility margin (which I believe starts at half a pawn under beta in Ippo and Critter and grows only very slowly with depth).

Critter does not generate quiet moves when much bellow beta, only quiet checks. The margin is 0.66 pawns at depth 1 and grows to 1.32 pawns at depth 5. There is very little chance for a quiet non-checking move to rise score that much. Note that this margin is more generous than what is used later in value based pruning.

I guess this is changed since the version you sent me, which according to my notes has a margin that starts at .5 pawn and rises to 1.12 I think, which matched Ippo. Anyway, this difference is not important.

Code: Select all

depth	margin [cp]
1	 	66,41
2	 	82,81
3	 	99,22
4		115,63
5		132,03

Regarding the move-count based pruning, it is true that Critter (and Ippo) also require a score condition (which we found to be useless for Komodo), but our experience with it indicates that the score condition is only a mild restriction, far less significant than looking at less moves than SF.

Critter does look at far far more moves than SF, at least when the eval is close to scout (where it matters most).

As I understand it, Critter either looks at all the moves or very few (much less than SF) depending on whether the score is above or below certain thresholds (both before and after the move in question). It looks at all the moves when it is unlikely to need to do so because the score is good enough to expect a cutoff quickly, at very few when it is likely to need to look at all of them otherwise. So I think the result is that it looks at fewer moves. Do you disagree with this analysis?

Overall, I don't think it's even close. SF prunes far less than Critter or Ippo until you reach the depth where LMR becomes important. Just time 7 ply searches to see what I mean. SF is much slower.

Sorry, what has _time_ to do with this??? You should measure _nodes_ if anything. But due to different node counting it still isn't a good comparison.

Yes, nodes is better. My point is that the time differential is too large to be attributed to the differences between the programs in (comparably measured) nodes per second. SF is a very efficient program too so I don't think this difference can be huge, not like a factor of two that would be needed to explain the times.

Anyway, I have no idea what you are trying to prove here. LMP and LMR are not completely separate things. With more aggresive LMR you reach LMP nodes quicker and you cannot afford prune overaggresively. With more conservative LMR you can prune more.

OK, this is a very intelligent and helpful observation! It is completely consistent with what I am saying. Stockfish is more aggressive than Critter in LMR, so it makes sense that Critter can be more aggressive in LMP, and vice-versa. It also explains why Komodo would be in between Critter and SF in terms of aggressiveness of both LMR and LMP. Thanks for helping clear up this mystery. I was not trying to "prove" something, but rather to get an explanation of why Critter would be more aggressive at low depth but less so at high depth. Now I have it.

[lkaufman]

Critter does look at far far more moves than SF, at least when the eval is close to scout (where it matters most).

Yes this is a natural and logical idea. We have tried hard to make it work in SF, namely to modulate movecount threshold above which move is pruned also with score distance to beta (now it depends just on depth), but we failed to produce something better than what we have now, although I think the idea "has to work" and perhaps we have missed something in the implementation.

We have found in Komodo that the ideal number of moves to look at has little to do with score. I won't say that there is no connection, but getting this right won't be worth more than a couple elo points.

[lkaufman]

Overall, I don't think it's even close. SF prunes far less than Critter or Ippo until you reach the depth where LMR becomes important. Just time 7 ply searches to see what I mean. SF is much slower.

One thing that differentiates SF from the Rybka/Ippo family is that we don't prune in advance captures, while the ippos build up the move generation 'target' in a dynamic way, so to generate less and less captures as long as the score is low.

I don't know (read: can you tell ?) if Komodo has adopted the same approach.

We tried it and found it worthless. Maybe if done perfectly it could be worth one or two elo points. Tiny return for a lot of work.

[rvida]

As I understand it, Critter either looks at all the moves or very few (much less than SF) depending on whether the score is above or below certain thresholds (both before and after the move in question). It looks at all the moves when it is unlikely to need to do so because the score is good enough to expect a cutoff quickly, at very few when it is likely to need to look at all of them otherwise. So I think the result is that it looks at fewer moves. Do you disagree with this analysis?

In other words: if the eval is not far below beta it is very probable that we can find a quiet move that causes a cutoff, therefore the effort spent to find it is not worthless. If the eval is far below, searching hard for a cutoff is in most cases just a lot of wasted nodes.

You can easily measure this. Instrument your engine in such a way that it searches all quiet moves in all cases until either cutoff or fail-low. Set up a pair of counters for each range of beta-eval (say with 15cp granularity). Increment counter1 for each tried move, increment counter2 for each cutoff. After search then print out the ratio of successful moves / tried moves for each score range. You should see a nice trend.

[lkaufman]

As I understand it, Critter either looks at all the moves or very few (much less than SF) depending on whether the score is above or below certain thresholds (both before and after the move in question). It looks at all the moves when it is unlikely to need to do so because the score is good enough to expect a cutoff quickly, at very few when it is likely to need to look at all of them otherwise. So I think the result is that it looks at fewer moves. Do you disagree with this analysis?

In other words: if the eval is not far below beta it is very probable that we can find a quiet move that causes a cutoff, therefore the effort spent to find it is not worthless. If the eval is far below, searching hard for a cutoff is in most cases just a lot of wasted nodes.

You can easily measure this. Instrument your engine in such a way that it searches all quiet moves in all cases until either cutoff or fail-low. Set up a pair of counters for each range of beta-eval (say with 15cp granularity). Increment counter1 for each tried move, increment counter2 for each cutoff. After search then print out the ratio of successful moves / tried moves for each score range. You should see a nice trend.

What you say is quite true, and the experiment you propose would obviously show that the higher the score, the higher the percentage of successful moves will be. But it does not contradict what I said; namely that when the score is good, you usually won't need more than a couple moves to get the cutoff. So your method, although it COULD look at many more nodes when the score is high, will in practice look at far fewer nodes than SF does, because it is only when the score is bad that it is likely that you will actually reach your (low) limit of number of moves. In other words, when the score is good, a limit on the number of moves has very little actual effect. Whether you use it or not in such cases doesn't seem to matter very much.