mate distance pruning

[Zach Wegner]

check the second post Here's a recursionified version:

Code: Select all

        /* mate-distance pruning */
        alpha = MAX(alpha, -MATE + ply);
        beta = MIN(beta, MATE - ply - 1);
        if (alpha >= beta)
            return alpha;

[Sven]

Code: Select all

#define MATE 10000

Search(alpha, beta, depth)
{
  int bestScore = dept >0 ? -MATE : Evaluate();

  alpha -= &#40;alpha < -MATE+100&#41;;
  beta -= &#40;beta <= -MATE+100&#41;;
  if&#40;bestScore >= beta&#41; goto cutoff; // stand pat

  // rest of alpha-beta search routine
  ...

cutoff&#58;
  bestScore += &#40;bestScore < -MATE+100&#41;;
  return bestScore;
&#125;

Sorry, I don't understand that code, could you please explain it? "alpha -= (alpha < -MATE+100);" means you subtract the value of a boolean expression from alpha, i.e. you subtract either 0 or 1? Is that the intent? I would not think so in the first place.

Sven

[hgm]

Yes, that is the intent. It is a more compact way of writing

if(alpha < -MATE+100) alpha--;

And on my compiler it is also faster, as it uses the setcc instruction in stead of mispredictable branches.

The algorithm in words would be: before returning the score, you add 1 point if you are to be checkmated (the delayed-loss bonus), to make distant losses in the root less valuable than quick losses (and quick mates more valuable than slow mates).

But when you modify the score from a search afterwards, you must pre-adjust the sarch window fo the modification that you will be making, or scores that where obtained from an out-of-window search (fail low or high) might be returned in window by the modification, and be mistaken for an exact score. So when a to-be-mated score is shifted up, window limits in the to-be-mated score range will have to be shifted down by the same amount.

Of course most of this has not really to do with mate distance pruning per se, just with determining the mate distance (without which mate-distance pruning would be impossible). The mate distance pruning itself is really te statement

if(bestScore >= beta) goto cutoff;

[Tord Romstad]

check the second post Here's a recursionified version:

Code: Select all

        /* mate-distance pruning */
        alpha = MAX(alpha, -MATE + ply);
        beta = MIN(beta, MATE - ply - 1);
        if (alpha >= beta)
            return alpha;

That's almost 100% identical to my code. For PV nodes:

Code: Select all

    alpha = Max(value_mated_in(ply), alpha);
    beta = Min(value_mate_in(ply+1), beta);
    if(alpha >= beta)
      return alpha;

For non-PV nodes:

Code: Select all

    if(value_mated_in(ply) >= beta)
      return beta;
    if&#40;value_mate_in&#40;ply+1&#41; < beta&#41;
      return beta-1;

Tord

[Zach Wegner]

check the second post Here's a recursionified version:

Code: Select all

        /* mate-distance pruning */
        alpha = MAX(alpha, -MATE + ply);
        beta = MIN(beta, MATE - ply - 1);
        if (alpha >= beta)
            return alpha;

That's almost 100% identical to my code. For PV nodes:

Code: Select all

    alpha = Max(value_mated_in(ply), alpha);
    beta = Min(value_mate_in(ply+1), beta);
    if(alpha >= beta)
      return alpha;

For non-PV nodes:

Code: Select all

    if(value_mated_in(ply) >= beta)
      return beta;
    if&#40;value_mate_in&#40;ply+1&#41; < beta&#41;
      return beta-1;

Tord

Indeed, they are semantically identical. Mine of course has the search block pointer (as in the second post in the thread). This is the way that makes most sense to me, Fruit's is rather confusing IMO. I've wanted to add mate_in macros, I might not anymore now that I see you have them.

[Tord Romstad]

I've wanted to add mate_in macros, I might not anymore now that I see you have them.

What? Am I so unpopular that something automatically becomes bad programming style just because I use it?

They are not macros, but inline functions, by the way.

Tord

[sje]

#define BX(n) (1 << n)

typedef signed int est;

Code: Select all

#ifndef IncludeScore
#define IncludeScore

#define ScoringScale 1000000 // Micropawn units

#define ScoringRangeLen BX(30)
#define MateMarginLen   BX(10)
#define MateDistanceLen BX(13)

#define SVBroken     ((est) (0 - ScoringRangeLen))
#define SVPosInf     ((est) (ScoringRangeLen - 1))
#define SVNegInf     ((est) (1 - ScoringRangeLen))
#define SVEven       ((est) 0)
#define SVMateIn1    ((est) (SVPosInf - MateMarginLen - 1))
#define SVLoseIn0    ((est) (SVNegInf + MateMarginLen))
#define SVCheckmated SVLoseIn0

#define BrokenScore     Score(SVBroken)
#define PosInfScore     Score(SVPosInf)
#define NegInfScore     Score(SVNegInf)
#define EvenScore       Score(SVEven)
#define MateIn1Score    Score(SVMateIn1)
#define LoseIn0Score    Score(SVLoseIn0)
#define CheckmatedScore LoseIn0Score

#define SVLongMate ((est) (SVMateIn1 - MateDistanceLen + 1))
#define SVLongLose ((est) (SVLoseIn0 + MateDistanceLen))

class Score
{
  public:
    Score(void) {}
    Score(const est es) {sv = es;}
    ~Score(void) {}

    est GetSV(void) const {return sv;}
    void PutSV(const est es) {sv = es;}

    void SynthMateInN(const ui n) {sv = SVMateIn1 - n + 1;}
    void SynthLoseInN(const ui n) {sv = SVLoseIn0 + n;}

    bool IsBroken(void) const {return sv == SVBroken;}
    bool IsPosInf(void) const {return sv == SVPosInf;}
    bool IsNegInf(void) const {return sv == SVNegInf;}
    bool IsEven(void)   const {return sv == SVEven;}

    bool IsInfinite(void) const {return IsPosInf() || IsNegInf();}
    bool IsSpecial(void)  const {return IsBroken() || IsInfinite();}

    bool IsMating(void) const {return !IsBroken() && (sv >= SVLongMate);}
    bool IsLosing&#40;void&#41; const &#123;return !IsBroken&#40;) && &#40;sv <= SVLongLose&#41;;&#125;

    bool IsMateOrLose&#40;void&#41; const &#123;return IsMating&#40;) || IsLosing&#40;);&#125;

    bool IsMateIn1&#40;void&#41; const &#123;return sv == SVMateIn1;&#125;
    bool IsLoseIn0&#40;void&#41; const &#123;return sv == SVLoseIn0;&#125;

    bool IsInRange&#40;void&#41; const &#123;return &#40;sv > SVLongLose&#41; && &#40;sv < SVLongMate&#41;;&#125;

    bool IsPositive&#40;void&#41; const &#123;return sv > 0;&#125;
    bool IsNegative&#40;void&#41; const &#123;return sv < 0;&#125;

    ui FullMoveMatingDistance&#40;void&#41; const &#123;return SVMateIn1 - sv + 1;&#125;
    ui FullMoveLosingDistance&#40;void&#41; const &#123;return sv - SVLoseIn0;&#125;

    void UpShift&#40;void&#41;;
    void DownShift&#40;void&#41;;

    std&#58;&#58;string FmtScore&#40;void&#41; const;

  private&#58;
    est sv; // Signed integral score value
&#125;;

inline void Score&#58;&#58;UpShift&#40;void&#41;
&#123;
  if (!IsBroken&#40;))
  &#123;
    if &#40;IsInRange&#40;)) sv = -sv;
    else
    &#123;
      if &#40;IsInfinite&#40;))
      &#123;
        if &#40;IsPosInf&#40;)) sv = SVNegInf; else sv = SVPosInf;
      &#125;
      else
      &#123;
        if &#40;IsMating&#40;))
          SynthLoseInN&#40;FullMoveMatingDistance&#40;));
        else
          SynthMateInN&#40;FullMoveLosingDistance&#40;) + 1&#41;;
      &#125;;
    &#125;
  &#125;;
&#125;

inline void Score&#58;&#58;DownShift&#40;void&#41;
&#123;
  if (!IsBroken&#40;))
  &#123;
    if &#40;IsInRange&#40;)) sv = -sv;
    else
    &#123;
      if &#40;IsInfinite&#40;))
      &#123;
        if &#40;IsPosInf&#40;)) sv = SVNegInf; else sv = SVPosInf;
      &#125;
      else
      &#123;
        if &#40;IsMating&#40;))
          SynthLoseInN&#40;FullMoveMatingDistance&#40;) - 1&#41;;
        else
          SynthMateInN&#40;FullMoveLosingDistance&#40;));
      &#125;;
    &#125;
  &#125;;
&#125;

class Window
&#123;
  public&#58;
    Window&#40;void&#41; &#123;&#125;
    Window&#40;const Score lowerscore, const Score upperscore&#41; &#123;alfa = lowerscore; beta = upperscore;&#125;
    ~Window&#40;void&#41; &#123;&#125;

    Score GetAlfa&#40;void&#41; const &#123;return alfa;&#125;
    void PutAlfa&#40;const Score score&#41; &#123;alfa = score;&#125;

    Score GetBeta&#40;void&#41; const &#123;return beta;&#125;
    void PutBeta&#40;const Score score&#41; &#123;beta = score;&#125;

    void SetFullWidth&#40;void&#41; &#123;alfa.PutSV&#40;SVNegInf&#41;; beta.PutSV&#40;SVPosInf&#41;;&#125;

    void DownShift&#40;void&#41;;

    bool IsFailLow&#40;const Score score&#41;  const &#123;return score.GetSV&#40;) <= alfa.GetSV&#40;);&#125;
    bool IsFailHigh&#40;const Score score&#41; const &#123;return score.GetSV&#40;) >= beta.GetSV&#40;);&#125;

    bool IsInside&#40;const Score score&#41; const &#123;return !IsFailLow&#40;score&#41; && !IsFailHigh&#40;score&#41;;&#125;

    bool IsCutoff&#40;void&#41; const &#123;return alfa.GetSV&#40;) >= beta.GetSV&#40;);&#125;

    std&#58;&#58;string FmtWindow&#40;void&#41; const;

  private&#58;
    Score alfa; // Lower bound score
    Score beta; // Upper bound score
&#125;;

#endif

[sje]

And:

Code: Select all

#include <iomanip>
#include <sstream>
#include <string>

#include "Definitions.h"
#include "Score.h"

std&#58;&#58;string Score&#58;&#58;FmtScore&#40;void&#41; const
&#123;
  std&#58;&#58;ostringstream oss;

  if &#40;IsSpecial&#40;))
  &#123;
    if &#40;IsBroken&#40;)) oss << "Broken";
    else
    &#123;
      if &#40;IsPosInf&#40;)) oss << "PosInf"; else oss << "NegInf";
    &#125;;
  &#125;
  else
  &#123;
    if &#40;IsMateOrLose&#40;))
    &#123;
      if &#40;IsMating&#40;)) oss << "MateIn" << FullMoveMatingDistance&#40;);
      else
      &#123;
        if &#40;IsLoseIn0&#40;))
          oss << "Checkmated";
        else
          oss << "LoseIn" << FullMoveLosingDistance&#40;);
      &#125;;
    &#125;
    else
    &#123;
      if &#40;IsEven&#40;)) oss << "Even";
      else
      &#123;
        est alt;

        if &#40;IsPositive&#40;)) &#123;alt = sv; oss << '+';&#125; else &#123;alt = -sv; oss << '-';&#125;;
        oss <<
          &#40;alt / ScoringScale&#41; << '.' <<
          std&#58;&#58;setw&#40;3&#41; << std&#58;&#58;setfill&#40;'0') << (&#40;alt % ScoringScale&#41; / 1000&#41; << std&#58;&#58;setfill&#40;' ');
      &#125;;
    &#125;;
  &#125;;
  return oss.str&#40;);
&#125;

void Window&#58;&#58;DownShift&#40;void&#41;
&#123;
  Window aux&#40;*this&#41;;

  alfa = aux.GetBeta&#40;); alfa.DownShift&#40;); beta = aux.GetAlfa&#40;); beta.DownShift&#40;);
&#125;

std&#58;&#58;string Window&#58;&#58;FmtWindow&#40;void&#41; const
&#123;
  std&#58;&#58;ostringstream oss;

  oss << '&#91;' << alfa.FmtScore&#40;) << '&#58;' << beta.FmtScore&#40;) << '&#93;';
  return oss.str&#40;);
&#125;