## Mate score in TT

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

### Mate score in TT

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

Code: Select all

``````  // value_to_tt&#40;) 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&#40;Value v, int ply&#41; &#123;

if &#40;v >= VALUE_MATE_IN_PLY_MAX&#41;
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&#40;) is the inverse of value_to_tt&#40;)&#58; It adjusts a mate score from
// the transposition table to a mate score corrected for the current ply.

Value value_from_tt&#40;Value v, int ply&#41; &#123;

if &#40;v >= VALUE_MATE_IN_PLY_MAX&#41;
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
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

### Re: Mate score in TT

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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

### Re: Mate score in TT

sje wrote: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
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

### Shifting scores down and up

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&#40;n&#58; Integer&#41;&#58; svtype; inline;
begin
SynthLoseInN &#58;= svlosein0 + n
end; &#123; SynthLoseInN &#125;

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

function IsSvLosing&#40;sv&#58; svtype&#41;&#58; 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
Posts: 26434
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

### Re: Mate score in TT

sje wrote: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
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

### Score definitions

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

Code: Select all

``````    &#123; Scoring&#58; pawn conversion factor &#125;

scorefactor = 1000000; &#123; All scores in micropawn units &#125;

&#123; Scoring&#58; absolute bound &#125;

scoreabsbound = 1 shl 30;

&#123; Scoring&#58; checkmates margin and distance; used for score interpretation &#125;

matemarginlen = 1 shl 10; &#123; Must be greater than maximum search depth &#125;
matedistlen   = 1 shl 13; &#123; Must be greater than the maximum mate length &#125;

&#123; Scoring&#58; score value constants; millipawn units &#125;

svbroken = 0 - scoreabsbound; &#123; Broken score &#125;
svneginf = 1 - scoreabsbound; &#123; Negative infinity score &#125;
svposinf = scoreabsbound - 1; &#123; Positive infinity score &#125;
sveven   = 0;                 &#123; Even score &#125;

&#123; Scoring&#58; basic mate/lose scores &#125;

svlosein0 = svneginf + matemarginlen;     &#123; Lose in 0 score &#40;checkmated&#41; &#125;
svmatein1 = svposinf - matemarginlen - 1; &#123; Mate in 1 score &#125;

&#123; Scoring&#58; checkmated synonym &#125;

svcheckmated = svlosein0;

&#123; Scoring&#58; more mate/lose scores &#125;

svlosein1 = svlosein0 + 1; &#123; Lose in 1 score &#125;
svmatein2 = svmatein1 - 1; &#123; Mate in 2 score &#125;
svlosein2 = svlosein1 + 1; &#123; Lose in 2 score &#125;
svmatein3 = svmatein2 - 1; &#123; Mate in 3 score &#125;
svlosein3 = svlosein2 + 1; &#123; Lose in 3 score &#125;
svmatein4 = svmatein3 - 1; &#123; Mate in 4 score &#125;

&#123; Scoring&#58; mate/lose maxima &#125;

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

&#123; Scoring&#58; piece values &#125;

svpvpawn   = 1000000;
svpvknight = 3200000;
svpvbishop = 3350000;
svpvrook   = 5000000;
svpvqueen  = 9500000;
svpvking   =       0;
``````
Last edited by sje on Wed Dec 28, 2011 12:40 pm, edited 1 time in total.

Sven
Posts: 4004
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

### Re: Shifting scores down and up

sje wrote: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
Posts: 720
Joined: Tue May 22, 2007 9:13 am

### Re: Shifting scores down and up

sje wrote: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&#40;)
&#123;
return SHRT_MAX;
&#125;

inline int loss_min&#40;)
&#123;
return -&#40;infinity&#40;) - 1&#41;;
&#125;
``````
Mate adjustment is done like this:

Code: Select all

``````// loss and win values are "stretched" one step towards the edges of the &#91;-INF, +INF&#93; interval
inline int stretch&#40;int value&#41;
&#123;
return value - is_loss&#40;value&#41; + is_win&#40;value&#41;;
&#125;

// loss and win values are "squeezed" one step towards the center of the &#91;-INF, +INF&#93; interval
inline int squeeze&#40;int value&#41;
&#123;
return value + is_loss&#40;value&#41; - is_win&#40;value&#41;;
&#125;
``````
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
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

### Re: Shifting scores down and up

Sven Schüle wrote:
sje wrote: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
Posts: 3218
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

### Re: Mate score in TT

mcostalba wrote: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&#40;) is the inverse of value_to_tt&#40;)&#58; It adjusts a mate score from
// the transposition table to a mate score corrected for the current ply.

Value value_from_tt&#40;Value v, int ply&#41; &#123;

if &#40;v >= VALUE_MATE_IN_PLY_MAX&#41;
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 ?