Mate score in TT

[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.

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;

Your squeeze/stretch seem to be about the same as my CalcSvUp/CalcSvDn except that you negate the results. If you always prune at the right time when generating a new window one ply down, then I suppose it will work without having the safety range margins.

[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.

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;

Your squeeze/stretch seem to be about the same as my CalcSvUp/CalcSvDn except that you negate the results. If you always prune at the right time when generating a new window one ply down, then I suppose it will work without having the safety range margins.

I used to have a minus sign inside the stretch/squeeze, but I like it better to have the minus side outside. That way, it's slightly easier to search/replace (in the past I did distance to root scoring).

The pruning is not just to avoid bogus search windows. It also saves nodes (although the difference is never really big).

[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?

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.

But how should alpha become better than mate-in-1 or beta worse than checkmated, or vice versa?

In my engines I take care to never let alpha and beta bounds take values outside the interval [checkmated - 1 .. mate-in-1-ply + 1]. The only place where I think this might become an issue is if you use aspiration windows and define bounds for the next iteration after the previous one returned a mate score.

Sven

[sje]

The pruning is not just to avoid bogus search windows. It also saves nodes (although the difference is never really big).

The savings can be large if there are a lot of mate/lose nodes. I've seen this with my dedicated mate finder routine.

[hgm]

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.

I don't think this is a problem. In fact it is desirable, because it is simply mate-distance pruning.

In micro-Max I have no safety margin (except that it counts from King capture rather than mate, so +INF = capture of King, -INF = illegal move, INF-1 = mate-in-1, 1-INF = mated-in-1,etc). The search starts with bestScore = -INF, and when beta <= -INF this gives an immediate stand-pat cutoff even outside QS, whih effects the mate distance pruning. Even giving your King away in 1 move would not be good enough for the opponent here, because he can already force earlier capture of your King in another branch.

[bob]

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 ?

Yes. You don't store the right value if I read your post correctly. What you want to store is some constant MATE - current ply. This turns the mate in N from the root to "mate in M from the current position." Now when you get that hit, you have to adjust the score again, buy ADDING ply, to convert it from mate in M from the current ply, to mate in N from the root, once again.

This works and has always worked flawlessly for me...

[bob]

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;

You gave a couple of the many reasons I always have simply adjusted the score when I store/retrieve, and don't bother adjusting anything otherwise. One also has to deal with adjusting mate bounds that get stored... but it all works out easily enough...

[hgm]

But how should alpha become better than mate-in-1 or beta worse than checkmated, or vice versa?

From the micro-Max code:

Code: Select all

Search(alpha, beta)
{
 alpha -= alpha < curEval;
 beta -= beta <= curEval;

// usual code
 ...

 return bestSore += bestScore < curEval;
&#125;

The first statement of the routine will eventually shift a mated-in-N alpha (which is always smaller than the current evaluation) to below -INF, when you go deep enough in recursion, and by the time you are at a depth where you cannot find a mate that is faster than in the branch supplying the alpha value, cause an automatic cutoff before searching any moves.