StockFish question

[lucasart]

Hello,

In the sources of StockFish, there is something rather intriguing (search.cpp):

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 = 0.33 + log(double(hd)) * log(double(mc)) / 4.5;
      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);
  }

  // Init futility margins array
  for (d = 1; d < 16; d++) for (mc = 0; mc < 64; mc++)
      FutilityMarginsMatrix[d][mc] = Value(112 * int(log(double(d * d) / 2) / log(2.0) + 1.001) - 8 * mc + 45);

  // Init futility move count array
  for (d = 0; d < 32; d++)
      FutilityMoveCountArray[d] = int(3.001 + 0.25 * pow(d, 2.0));
}

So the LMR reduction was calibrated as an affine function of log(depth)log(move_count), and the futility margin was calibrated as an affine function of (log(depth), move_count). I believe most other programs use a much more basic approach there.

I am just wondering:
* were these formulas built to get something that just gives good results in practice ?
* or is there a more profound reason for such a parametrisation ? I know that Tord is a mathematician, so there could a more theoretical reason for this.

[mcostalba]

I am just wondering:
* were these formulas built to get something that just gives good results in practice ?

Yes, this is our only metrics.


The idea come just because a linear function seemed to much at higher depth /move counts, so we wanted to limitate the increase rate while preserving a good value at low depths, IOW we wanted to limit the span range and so moved to some log's family functions then we tested and results were not bad....

....I guess there is nothing more then this

[lucasart]

The idea come just because a linear function seemed to much at higher depth /move counts, so we wanted to limitate the increase rate while preserving a good value at low depths, IOW we wanted to limit the span range and so moved to some log's family functions then we tested and results were not bad...

I see, so it's empirical then. While I'm at it: two possible improvements could be tested in SF. Perhaps you've already tested them, and they didn't perform as well, but anyway:

1/ SEE: adding promotions
It wouldn't be difficult to modify your swap algorithm in the SEE computation to handle the promotion case (on the first move as well as in the loop when considering pawn recaptures). It would have the added benefit to remove the condition "move is not a promotion" from the futility pruning in the QS, and perhaps in other areas of the search. The speed shouldn't be affected much, and if it is, then templatizing the SEE could fix it (calling the "slow" 8th rank version when the to_square is 8th rank only, otherwise the usual one).

2/ SEE pruning of check evasions (in qsearch)
The condition "bestValue > value_mated_in(PLY_MAX)" could be removed from "evasionPrunable", so long as you are careful to return alpha-1 in such cases to avoid returning fase mate score. This idea is from Richard Vida (developer of Critter).

What do you think ?

[zamar]

1/ SEE: adding promotions
It wouldn't be difficult to modify your swap algorithm in the SEE computation to handle the promotion case (on the first move as well as in the loop when considering pawn recaptures). It would have the added benefit to remove the condition "move is not a promotion" from the futility pruning in the QS, and perhaps in other areas of the search. The speed shouldn't be affected much, and if it is, then templatizing the SEE could fix it (calling the "slow" 8th rank version when the to_square is 8th rank only, otherwise the usual one).

Promotions are so rear that I think it really shouldn't matter...

2/ SEE pruning of check evasions (in qsearch)
The condition "bestValue > value_mated_in(PLY_MAX)" could be removed from "evasionPrunable", so long as you are careful to return alpha-1 in such cases to avoid returning fase mate score. This idea is from Richard Vida (developer of Critter).

bestValue > value_mated_in(PLY_MAX)

This is true >99.9% of time and returning bestValue instead of alpha is advantageous to get more TT hits in future (this is called fail soft)