Mate score in TT

[mcostalba]

An almost universal accepted way to storing mate scores in the TT is the following:

Code: Select all

  // value_to_tt() adjusts a mate score from "plies to mate from the root" to
  // "plies to mate from the current ply". Non-mate scores are unchanged. The
  // function is called before storing a value to the transposition table.

  Value value_to_tt(Value v, int ply) {

    if (v >= VALUE_MATE_IN_PLY_MAX)
      return v + ply;

    if &#40;v <= VALUE_MATED_IN_PLY_MAX&#41;
      return v - ply;

    return v;
  &#125;

In this way we always store in TT the number of moves to mate (to be mated) counted form the root. This is ok as far as root does not change, but suppose I find a mate in 7 for a given position P0, I will store it as (VALUE_MATE - 7). Now I do the move and go to position P1, the opponent replies and goes to position P2 from where I search again. I find a TT hit immediately and I read back the TT value with:

Code: Select all

  // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
  // the transposition table to a mate score corrected for the current ply.

  Value value_from_tt(Value v, int ply) {

    if (v >= VALUE_MATE_IN_PLY_MAX)
      return v - ply;

    if &#40;v <= VALUE_MATED_IN_PLY_MAX&#41;
      return v + ply;

    return v;
  &#125;

And I read (VALUE_MATE - 7) while instead, because in the meantime I have moved and the opponent has replied the correct value should be (VALUE_MATE - 5) because I am at 5 move to mate, no more 7.

Am I missing something ?

[sje]

In my program Symbolic, a mate/lose score is always assigned from the viewpoint of the current position and has nothing to do with the distance from the root. When moving up or down in the tree, mate/lose scores are adjusted accordingly. With this scheme, there is no need to adjust mate/lose scores when doing transposition table stash/fetch operations.

[mcostalba]

In my program Symbolic, a mate/lose score is always assigned from the viewpoint of the current position and has nothing to do with the distance from the root. When moving up or down in the tree, mate/lose scores are adjusted accordingly. With this scheme, there is no need to adjust mate/lose scores when doing transposition table stash/fetch operations.

Ooops, this is what actually happens ! Aftee a better looking I see that in TT is always stored the plies to mate from the current position, not from the root.

Sorry for the noise

[sje]

When moving one ply down (away from the root), the window bounds are swapped and then shifted down. When moving one ply up (towards the root), the result score is shifted up.

Note: It is possible to get scores better than mate in one or worse than checkmated, so there has to be a safety range between mate in one and +infinity and also between checkmated and -infinity. This safety margin length has to be at least as long as the greatest possible search ply.

Code: Select all

  function SynthLoseInN(n: Integer): svtype; inline;
  begin
    SynthLoseInN := svlosein0 + n
  end; { SynthLoseInN }

  function SynthMateInN(n: Integer): svtype; inline;
  begin
    SynthMateInN := svmatein1 - n + 1
  end; { SynthMateInN }

  function IsSvLosing(sv: svtype): Boolean; inline;
  begin
    IsSvLosing &#58;= &#40;sv <> svbroken&#41; and &#40;sv <= svlonglose&#41;
  end; &#123; IsSvLosing &#125;

  function IsSvMating&#40;sv&#58; svtype&#41;&#58; Boolean; inline;
  begin
    IsSvMating &#58;= &#40;sv <> svbroken&#41; and &#40;sv >= svlongmate&#41;
  end; &#123; IsSvMating &#125;

  function IsSvLosingOrMating&#40;sv&#58; svtype&#41;&#58; Boolean; inline;
  begin
    IsSvLosingOrMating &#58;= &#40;sv <> svbroken&#41; and (&#40;sv <= svlonglose&#41; or &#40;sv >= svlongmate&#41;)
  end; &#123; IsSvLosingOrMating &#125;

  function IsSvInRange&#40;sv&#58; svtype&#41;&#58; Boolean; inline;
  begin
    IsSvInRange &#58;= &#40;sv > svlonglose&#41; and &#40;sv < svlongmate&#41;
  end; &#123; IsSvInRange &#125;

  function IsSvInfinite&#40;sv&#58; svtype&#41;&#58; Boolean; inline;
  begin
    IsSvInfinite &#58;= &#40;sv = svneginf&#41; or &#40;sv = svposinf&#41;
  end; &#123; IsSvInfinite &#125;

  function CalcLosingDistance&#40;sv&#58; svtype&#41;&#58; Integer; inline;
  begin
    CalcLosingDistance &#58;= sv - svlosein0
  end; &#123; CalcLosingDistance &#125;

  function CalcMatingDistance&#40;sv&#58; svtype&#41;&#58; Integer; inline;
  begin
    CalcMatingDistance &#58;= svmatein1 - sv + 1
  end; &#123; CalcMatingDistance &#125;

  function CalcSvDn&#40;sv&#58; svtype&#41;&#58; svtype;
    var
      myresult&#58; svtype;
  begin
    if sv = svbroken then
      myresult &#58;= sv
    else
      if IsSvInRange&#40;sv&#41; then
        myresult &#58;= -sv
      else
        if IsSvInfinite&#40;sv&#41; then
          if sv = svneginf then
            myresult &#58;= svposinf
          else
            myresult &#58;= svneginf
        else
          if IsSvLosing&#40;sv&#41; then
            myresult &#58;= SynthMateInN&#40;CalcLosingDistance&#40;sv&#41;)
          else
            myresult &#58;= SynthLoseInN&#40;CalcMatingDistance&#40;sv&#41; - 1&#41;;
    CalcSvDn &#58;= myresult
  end; &#123; CalcSvDn &#125;

  function CalcSvUp&#40;sv&#58; svtype&#41;&#58; svtype;
    var
      myresult&#58; svtype;
  begin
    if sv = svbroken then
      myresult &#58;= sv
    else
      if IsSvInRange&#40;sv&#41; then
        myresult &#58;= -sv
      else
        if IsSvInfinite&#40;sv&#41; then
          if sv = svneginf then
            myresult &#58;= svposinf
          else
            myresult &#58;= svneginf
        else
          if IsSvLosing&#40;sv&#41; then
            myresult &#58;= SynthMateInN&#40;CalcLosingDistance&#40;sv&#41; + 1&#41;
          else
            myresult &#58;= SynthLoseInN&#40;CalcMatingDistance&#40;sv&#41;);
    CalcSvUp &#58;= myresult
  end; &#123; CalcSvUp &#125;

  procedure WindowShiftDn&#40;var window0, window1&#58; windowtype&#41;; inline;
  begin
    window1.alfa &#58;= CalcSvDn&#40;window0.beta&#41;;
    window1.beta &#58;= CalcSvDn&#40;window0.alfa&#41;
  end; &#123; WindowShiftDn &#125;

[hgm]

In my program Symbolic, a mate/lose score is always assigned from the viewpoint of the current position and has nothing to do with the distance from the root. When moving up or down in the tree, mate/lose scores are adjusted accordingly. With this scheme, there is no need to adjust mate/lose scores when doing transposition table stash/fetch operations.

That is what I have always done too. I never adjust scores when I store to or read them from the TT. The delayed-loss bonus takes care of accounting the DTM in the nodes downstream automatically.

[sje]

In CookieCat, scores are stored as 32 bit signed integers. Here are the definitions of special score values and ranges:

Code: Select all

    { Scoring: pawn conversion factor }

    scorefactor = 1000000; { All scores in micropawn units }

    { Scoring: absolute bound }

    scoreabsbound = 1 shl 30;

    { Scoring: checkmates margin and distance; used for score interpretation }

    matemarginlen = 1 shl 10; { Must be greater than maximum search depth }
    matedistlen   = 1 shl 13; { Must be greater than the maximum mate length }

    { Scoring: score value constants; millipawn units }

    svbroken = 0 - scoreabsbound; { Broken score }
    svneginf = 1 - scoreabsbound; { Negative infinity score }
    svposinf = scoreabsbound - 1; { Positive infinity score }
    sveven   = 0;                 { Even score }

    { Scoring: basic mate/lose scores }

    svlosein0 = svneginf + matemarginlen;     { Lose in 0 score (checkmated) }
    svmatein1 = svposinf - matemarginlen - 1; { Mate in 1 score }

    { Scoring: checkmated synonym }

    svcheckmated = svlosein0;

    { Scoring: more mate/lose scores }

    svlosein1 = svlosein0 + 1; { Lose in 1 score }
    svmatein2 = svmatein1 - 1; { Mate in 2 score }
    svlosein2 = svlosein1 + 1; { Lose in 2 score }
    svmatein3 = svmatein2 - 1; { Mate in 3 score }
    svlosein3 = svlosein2 + 1; { Lose in 3 score }
    svmatein4 = svmatein3 - 1; { Mate in 4 score }

    { Scoring: mate/lose maxima }

    svlonglose = svlosein0 + matedistlen;
    svlongmate = svmatein1 - matedistlen + 1;

    { Scoring: piece values }

    svpvpawn   = 1000000;
    svpvknight = 3200000;
    svpvbishop = 3350000;
    svpvrook   = 5000000;
    svpvqueen  = 9500000;
    svpvking   =       0;

[Sven]

Note: It is possible to get scores better than mate in one or worse than checkmated, so there has to be a safety range between mate in one and +infinity and also between checkmated and -infinity. This safety margin length has to be at least as long as the greatest possible search ply.

I don't quite understand that part, can you please elaborate a bit more on it? To my current understanding it would be sufficient to have something like "-infinity == checkmated - 1" and "+infinity == (mate in one) + 1", can you show a case where that would cause trouble?

How can evaluation or search return a score better than mate in one? And why does the greatest possible search ply influence the safety range you are referring to?

Sven

[Rein Halbersma]

When moving one ply down (away from the root), the window bounds are swapped and then shifted down. When moving one ply up (towards the root), the result score is shifted up.

Note: It is possible to get scores better than mate in one or worse than checkmated, so there has to be a safety range between mate in one and +infinity and also between checkmated and -infinity. This safety margin length has to be at least as long as the greatest possible search ply.

In my draughts program, I also use distance-to-mate with respect to the leaf node, not to the root. However, I don't have a safety margin between the smallest loss/win and infinity:

Code: Select all

inline int infinity()
{
        return SHRT_MAX;
}

inline int loss_min()
{
        return -(infinity() - 1);
}

Mate adjustment is done like this:

Code: Select all

// loss and win values are "stretched" one step towards the edges of the [-INF, +INF] interval
inline int stretch(int value)
{
        return value - is_loss(value) + is_win(value);
}

// loss and win values are "squeezed" one step towards the center of the [-INF, +INF] interval
inline int squeeze(int value)
{
        return value + is_loss(value) - is_win(value);
}

which is called as

Code: Select all

value = -squeeze&#40;pvs<PV>&#40;pos, -stretch&#40;beta&#41;, -stretch&#40;alpha&#41;, depth - 1,...));

Of course, you have to be careful not to let the search window collapse when one of the bounds crosses over to infinity. This is done by mate distance pruning:

Code: Select all

        // alpha < beta <= +INF implies alpha <= win_min 
        // with equality, any finite score will fail low
        if &#40;alpha == win_min&#40;))
                return alpha;

        // -INF <= alpha < beta implies loss_min <= beta
        // with equality, any finite score will fail high
        if &#40;beta == loss_min&#40;))
                return beta;

What the above code does is to cutoff null-window nodes with either alpha or beta equal to plus/minus infinity. I have the same assert() statements as Stockfish to check the sanity of the alpha-beta window (as a function of the node type). I use automated unit tests to run mate searches on dozens of tablebase positions without error.

[sje]

Note: It is possible to get scores better than mate in one or worse than checkmated, so there has to be a safety range between mate in one and +infinity and also between checkmated and -infinity. This safety margin length has to be at least as long as the greatest possible search ply.

I don't quite understand that part, can you please elaborate a bit more on it? To my current understanding it would be sufficient to have something like "-infinity == checkmated - 1" and "+infinity == (mate in one) + 1", can you show a case where that would cause trouble?

How can evaluation or search return a score better than mate in one? And why does the greatest possible search ply influence the safety range you are referring to?

Example:

The search discovers a a checkmated position that when backed up to the root gets a mate-in-3 score for the corresponding root move. Later in the search and much deeper than the ply where the checkmated position was located, either alpha will be better than mate-in-1 or beta will be worse than checkmated (lose-in-0). So if there isn't some kind of protective pruning, the score values will be incorrect if there is no safety range margin as described above.

[lucasart]

suppose I find a mate in 7 for a given position P0, I will store it as (VALUE_MATE - 7). Now I do the move and go to position P1, the opponent replies and goes to position P2 from where I search again. I find a TT hit immediately and I read back the TT value with:

Code: Select all

  // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score from
  // the transposition table to a mate score corrected for the current ply.

  Value value_from_tt(Value v, int ply) {

    if (v >= VALUE_MATE_IN_PLY_MAX)
      return v - ply;

    if &#40;v <= VALUE_MATED_IN_PLY_MAX&#41;
      return v + ply;

    return v;
  &#125;

And I read (VALUE_MATE - 7) while instead, because in the meantime I have moved and the opponent has replied the correct value should be (VALUE_MATE - 5) because I am at 5 move to mate, no more 7.

Am I missing something ?

Not sure I'm following, but if you've played 2 ples along the mating line, then your zobrist key will have changed and you should read a MATE-5 score in your hash table for this (different) position, no ?