PLEASE HELP with MATING scores adjustments in TT

[maksimKorzh]

Hi guys

I'm incredibly suffering from a dumbness to understand how the mating scores
are handled within a TT. Here's the implementation I came up with.

QUESTION 1: Is this correct? (It seems like it's working, at least finds mates)

Code: Select all

// read hash entry data
static inline int read_hash_entry(int alpha, int beta, int depth)
{
    // create a TT instance pointer to particular hash entry storing
    // the scoring data for the current board position if available
    tt *hash_entry = &hash_table[hash_key % hash_size];
    
    // extract current score from hash entry
    int score = hash_entry->score;
        
    // make sure we're dealing with the exact position we need
    if (hash_entry->hash_key == hash_key)
    {
        // make sure that we match the exact depth our search is now at
        if (hash_entry->depth >= depth)
        {
            int score = hash_entry->score;
            if (score < -48000) score += ply;
            if (score > 48000) score -= ply;
        
            // match the exact (PV node) score 
            if (hash_entry->flag == hash_flag_exact)
                // return exact (PV node) score
                return score;
            
            // match alpha (fail-low node) score
            if ((hash_entry->flag == hash_flag_alpha) &&
                (score <= alpha))
                // return alpha (fail-low node) score
                return alpha;
            
            // match beta (fail-high node) score
            if ((hash_entry->flag == hash_flag_beta) &&
                (score >= beta))
                // return beta (fail-high node) score
                return beta;
        }
    }
    
    // if hash entry doesn't exist
    return no_hash_entry;
}

// write hash entry data
static inline void write_hash_entry(int score, int depth, int hash_flag)
{
    // create a TT instance pointer to particular hash entry storing
    // the scoring data for the current board position if available
    tt *hash_entry = &hash_table[hash_key % hash_size];

    if (score > 48000) score -= ply;
    if (score < -48000) score += ply;

    // write hash entry data 
    hash_entry->hash_key = hash_key;
    hash_entry->score = score;
    hash_entry->flag = hash_flag;
    hash_entry->depth = depth;
}

...

// here's how I score mated value
if (legal_moves == 0)
{
    // king is in check
    if (in_check)
        // return mating score (assuming closest distance to mating position)
        return -49000 + ply;
    
    // king is not in check
    else
        // return stalemate score
        return 0;
}

...

so

INFINITY = 50000
MATED_VALUE = 49000
MATE_SCORE = 48000

and the values for mating scores are within a range from 48000 to 49000
I'm using FAIL-HARD framework.

I'm confused by the logic of adding and substracting plies.
I'm referencig this post by Harald as a source of theory:

Writing TT:
if current score > MATE_SCORE store score - ply
if current score < -MATE_SCORE store score + ply

Reading TT:
if stored score > MATE_SCORE return score + ply
if stored score < -MATE_SCORE return score - ply

It seems like if we have a score of say mate in 8 at ply 5
49000 - mate in 0
48999 - mate in 1
...
48992 - mate in 8

than instead of storing 48992 we actually store 48992 - 5 = 48987
and then restore it back when reading TT via 48987 + 5 = 48992

QUESTION 2: If above is TRUE (it seems for it works) then WHY this works??????
Please explain as if you were explaining to idiot.

[Ras]

In your search, the mate distance is relative to the root position. If you store it like that in the hash tables, and you have a hit in the next move turn, the mate score is wrong.

Example. You are at move 20 and see a mate in 8 plies. You store that position. Next move turn, so you are at move 21, and the mate is in 6 plies. Well but you stored it as mate in 8 plies!

So what you do is that when storing into the hash table, you take the mate distance relative to your current node, not to the root. And the other way around when retrieving.

[maksimKorzh]

In your search, the mate distance is relative to the root position. If you store it like that in the hash tables, and you have a hit in the next move turn, the mate score is wrong.

Example. You are at move 20 and see a mate in 8 plies. You store that position. Next move turn, so you are at move 21, and the mate is in 6 plies. Well but you stored it as mate in 8 plies!

So what you do is that when storing into the hash table, you take the mate distance relative to your current node, not to the root. And the other way around when retrieving.

Thank you, this at least clarifies the issue itself even though doesn't answer directly non of 2 questions asked. Anyway, I'll keep trying to understand it basing on your example. Good answer, but not enough for idiots... unfortunately.

[Sven]

In your search, the mate distance is relative to the root position. If you store it like that in the hash tables, and you have a hit in the next move turn, the mate score is wrong.

Example. You are at move 20 and see a mate in 8 plies. You store that position. Next move turn, so you are at move 21, and the mate is in 6 plies. Well but you stored it as mate in 8 plies!

So what you do is that when storing into the hash table, you take the mate distance relative to your current node, not to the root. And the other way around when retrieving.

Thank you, this at least clarifies the issue itself even though doesn't answer directly non of 2 questions asked. Anyway, I'll keep trying to understand it basing on your example. Good answer, but not enough for idiots... unfortunately.

You want to read more, so here you are ...

In write_hash_entry() you write:

Code: Select all

if (score > 48000) score -= ply;
if (score < -48000) score += ply;

In read_hash_entry() you write:

Code: Select all

if (score < -48000) score += ply;
if (score > 48000) score -= ply;

I guess now you see that both are the same, except for the order of the two lines of code ... The bug is in write_hash_entry() which should have:

Code: Select all

if (score > 48000) score += ply;
if (score < -48000) score -= ply;

while the mate score handling code in read_hash_entry() is ok.

So the answers to your questions are:
1) No
2) Irrelevant since your question is only related to 1)="Yes"

Explanation:
The origin of detecting a mate score for the first time is when the moving side S is mated in the current position P (mate is on the board). If we are at ply N, i.e. the current position is N plies away from the root, then the typical implementation (to which you refer here) is to return -(MATED_VALUE - N) at that point. The parent node, due to negamax, sees this as (MATED_VALUE - N) from the viewpoint of O, the opponent of S. Either the negative or the positive version of that score (depending on whose turn it is) is propagated to any node on the path from the root to P unless a better move is found that results in a shorter mate (for O) or a longer one (for S), or the mate can even be avoided for S.

Now suppose you are done with a node Q and store a score in TT, and it happens to be a mate score. You are at ply K (K < N) and the two cases are:

a) N-K is even (so it is again S to move): the score resulting from the search is still negative and of the form -(MATED_VALUE - N), but it means that S is mated in (N-K) plies from the current node Q;

b) N-K is odd (so it is O to move): the score resulting from the search is positive and of the form (MATED_VALUE - N), and it means that O can mate in (N-K) plies from the current node Q.

In both cases the score resulting from the search still reflects the distance of N plies between the root and P, the position where the mate actually happened.

Now position Q might occur somewhere else in the tree, or even during the next search. You want to save time and read the mate score from TT. But the distance to root may be different from what it was when the score was stored. The essential information you want to store shall be independent from the actual path from root to Q, it shall only reflect the distance from the current node Q (where you store the score) to P (the terminal node of the forced mating variation). Therefore N must be replaced by (N - K) when storing, so you always store "mated in (N - K) plies from here" or "mate in (N - K) plies from here".

You can figure out what "replacing N by (N - K)" means in the two cases above but nevertheless I'll also show the result of figuring it out ...

a) When storing a negative score -(MATED_VALUE - N) it is transformed into -(MATED_VALUE - (N - K)) by subtracting K:
-(MATED_VALUE - N) - K = -(MATED_VALUE - N + K) = -(MATED_VALUE - (N - K))

b) When storing a positive score (MATED_VALUE - N) it is transformed into (MATED_VALUE - (N - K)) by adding K:
(MATED_VALUE - N) + K = MATED_VALUE - (N - K)

Now it should be obvious what you do when retrieving a mate score from TT. You do exactly the opposite: at a node Q2 that is (supposedly) identical to Q and has a distance of K2 to the root, a negative TT score is transformed into a tree score by adding K2, and a positive TT score by subtracting K2. In both cases you "replace (N - K2) by N".

For the implementation it may be a good idea to have two small functions that return the transformation result, like in this example:

Code: Select all

int scoreToTT(int score, int ply) { return (score > MATE_SCORE) ? score + ply : (score < -MATE_SCORE) ? score - ply : score; }
int scoreFromTT(int score, int ply) { return (score > MATE_SCORE) ? score - ply : (score < -MATE_SCORE) ? score + ply : score; }

You would use scoreToTT() for storing and scoreFromTT() for retrieving scores, and you would not have to bother with the details of mate score transformation anywhere else outside these two functions.

Now to your practical example. You wrote you are at ply 5 and your search returns a "mate in 8" (plies). That cannot happen since 8 is even and you could only detect either a "mated in 8 plies" (case A) or, say, a "mate in 9 plies" (case B). You store the following:

A) Distance from root to mate is 5+8 = 13 so search returns -(49000 - 13) = -48987. You store a "mated in 8 plies" which is -48987 - 5 = -48992 = -(49000 - 8).

B) Distance from root to mate is 5+9 = 14 so search returns (49000 - 14) = +48986. You store a "mate in 9 plies" which is +48986 + 5 = +48991 = +(49000 - 9).

Now let's say you encounter the same position through a different path at ply 3. The terminal node of the mating line is (3+8) and (3+9) plies away from the root, depending on the two cases A and B:

A) TT returns -48992 which you transform into a tree score of -48992 + 3 = -48989 = -(49000 - 11).

B) TT returns +48991 which you transform into a tree score of +48991 - 3 = +48988 = +(49000 - 12).

Note also that mate scores occurring in the tree are within the following ranges (assuming your constants):

a) negative mate scores (mated in even number of plies at any ply):
-49000 = "mated at root" (this would usually not happen since you don't start a search when you are already mated)
-48999 = "mated in 0 at ply 1"
-48998 = "mated in 0 at ply 2" or "mated in 2 at root"
-48997 = "mated in 0 at ply 3" or "mated in 2 at ply 1"
...
-48001 = "mated in 0 at ply 999" or "mated in 2 at ply 997" or ... or "mated in 998 at ply 1"

b) positive mate scores (mate in odd number of plies at any ply):
+49000 can never happen
+48999 = "mate in 1 at root"
+48998 = "mate in 1 at ply 1"
+48997 = "mate in 1 at ply 2" or "mate in 3 at root"
...
+48001 = "mate in 1 at ply 998" or "mate in 3 at ply 996" or ... or "mate in 999 at root"

In contrast to that, mate scores stored in TT can only have the following values:

a) negative mate scores (mated in even number of plies):
-49000 = "mated" (some engines do not store "mated in 0" scores in TT, though)
-48998 = "mated in 2"
-48996 = "mated in 4"
...
-48002 = "mated in 998"

b) positive mate scores (mate in odd number of plies):
+48999 = "mate in 1"
+48997 = "mate in 3"
+48995 = "mate in 5"
...
+48001 = "mate in 999"

[maksimKorzh]

In your search, the mate distance is relative to the root position. If you store it like that in the hash tables, and you have a hit in the next move turn, the mate score is wrong.

Example. You are at move 20 and see a mate in 8 plies. You store that position. Next move turn, so you are at move 21, and the mate is in 6 plies. Well but you stored it as mate in 8 plies!

So what you do is that when storing into the hash table, you take the mate distance relative to your current node, not to the root. And the other way around when retrieving.

Thank you, this at least clarifies the issue itself even though doesn't answer directly non of 2 questions asked. Anyway, I'll keep trying to understand it basing on your example. Good answer, but not enough for idiots... unfortunately.

You want to read more, so here you are ...

In write_hash_entry() you write:

Code: Select all

if (score > 48000) score -= ply;
if (score < -48000) score += ply;

In read_hash_entry() you write:

Code: Select all

if (score < -48000) score += ply;
if (score > 48000) score -= ply;

I guess now you see that both are the same, except for the order of the two lines of code ... The bug is in write_hash_entry() which should have:

Code: Select all

if (score > 48000) score += ply;
if (score < -48000) score -= ply;

while the mate score handling code in read_hash_entry() is ok.

So the answers to your questions are:
1) No
2) Irrelevant since your question is only related to 1)="Yes"

Explanation:
The origin of detecting a mate score for the first time is when the moving side S is mated in the current position P (mate is on the board). If we are at ply N, i.e. the current position is N plies away from the root, then the typical implementation (to which you refer here) is to return -(MATED_VALUE - N) at that point. The parent node, due to negamax, sees this as (MATED_VALUE - N) from the viewpoint of O, the opponent of S. Either the negative or the positive version of that score (depending on whose turn it is) is propagated to any node on the path from the root to P unless a better move is found that results in a shorter mate (for O) or a longer one (for S), or the mate can even be avoided for S.

Now suppose you are done with a node Q and store a score in TT, and it happens to be a mate score. You are at ply K (K < N) and the two cases are:

a) N-K is even (so it is again S to move): the score resulting from the search is still negative and of the form -(MATED_VALUE - N), but it means that S is mated in (N-K) plies from the current node Q;

b) N-K is odd (so it is O to move): the score resulting from the search is positive and of the form (MATED_VALUE - N), and it means that O can mate in (N-K) plies from the current node Q.

In both cases the score resulting from the search still reflects the distance of N plies between the root and P, the position where the mate actually happened.

Now position Q might occur somewhere else in the tree, or even during the next search. You want to save time and read the mate score from TT. But the distance to root may be different from what it was when the score was stored. The essential information you want to store shall be independent from the actual path from root to Q, it shall only reflect the distance from the current node Q (where you store the score) to P (the terminal node of the forced mating variation). Therefore N must be replaced by (N - K) when storing, so you always store "mated in (N - K) plies from here" or "mate in (N - K) plies from here".

You can figure out what "replacing N by (N - K)" means in the two cases above but nevertheless I'll also show the result of figuring it out ...

a) When storing a negative score -(MATED_VALUE - N) it is transformed into -(MATED_VALUE - (N - K)) by subtracting K:
-(MATED_VALUE - N) - K = -(MATED_VALUE - N + K) = -(MATED_VALUE - (N - K))

b) When storing a positive score (MATED_VALUE - N) it is transformed into (MATED_VALUE - (N - K)) by adding K:
(MATED_VALUE - N) + K = MATED_VALUE - (N - K)

Now it should be obvious what you do when retrieving a mate score from TT. You do exactly the opposite: at a node Q2 that is (supposedly) identical to Q and has a distance of K2 to the root, a negative TT score is transformed into a tree score by adding K2, and a positive TT score by subtracting K2. In both cases you "replace (N - K2) by N".

For the implementation it may be a good idea to have two small functions that return the transformation result, like in this example:

Code: Select all

int scoreToTT(int score, int ply) { return (score > MATE_SCORE) ? score + ply : (score < -MATE_SCORE) ? score - ply : score; }
int scoreFromTT(int score, int ply) { return (score > MATE_SCORE) ? score - ply : (score < -MATE_SCORE) ? score + ply : score; }

You would use scoreToTT() for storing and scoreFromTT() for retrieving scores, and you would not have to bother with the details of mate score transformation anywhere else outside these two functions.

Now to your practical example. You wrote you are at ply 5 and your search returns a "mate in 8" (plies). That cannot happen since 8 is even and you could only detect either a "mated in 8 plies" (case A) or, say, a "mate in 9 plies" (case B). You store the following:

A) Distance from root to mate is 5+8 = 13 so search returns -(49000 - 13) = -48987. You store a "mated in 8 plies" which is -48987 - 5 = -48992 = -(49000 - 8).

B) Distance from root to mate is 5+9 = 14 so search returns (49000 - 14) = +48986. You store a "mate in 9 plies" which is +48986 + 5 = +48991 = +(49000 - 9).

Now let's say you encounter the same position through a different path at ply 3. The terminal node of the mating line is (3+8) and (3+9) plies away from the root, depending on the two cases A and B:

A) TT returns -48992 which you transform into a tree score of -48992 + 3 = -48989 = -(49000 - 11).

B) TT returns +48991 which you transform into a tree score of +48991 - 3 = +48988 = +(49000 - 12).

Note also that mate scores occurring in the tree are within the following ranges (assuming your constants):

a) negative mate scores (mated in even number of plies at any ply):
-49000 = "mated at root" (this would usually not happen since you don't start a search when you are already mated)
-48999 = "mated in 0 at ply 1"
-48998 = "mated in 0 at ply 2" or "mated in 2 at root"
-48997 = "mated in 0 at ply 3" or "mated in 2 at ply 1"
...
-48001 = "mated in 0 at ply 999" or "mated in 2 at ply 997" or ... or "mated in 998 at ply 1"

b) positive mate scores (mate in odd number of plies at any ply):
+49000 can never happen
+48999 = "mate in 1 at root"
+48998 = "mate in 1 at ply 1"
+48997 = "mate in 1 at ply 2" or "mate in 3 at root"
...
+48001 = "mate in 1 at ply 998" or "mate in 3 at ply 996" or ... or "mate in 999 at root"

In contrast to that, mate scores stored in TT can only have the following values:

a) negative mate scores (mated in even number of plies):
-49000 = "mated" (some engines do not store "mated in 0" scores in TT, though)
-48998 = "mated in 2"
-48996 = "mated in 4"
...
-48002 = "mated in 998"

b) positive mate scores (mate in odd number of plies):
+48999 = "mate in 1"
+48997 = "mate in 3"
+48995 = "mate in 5"
...
+48001 = "mate in 999"

OMG.... What can I say.... Sir.... Ahhhh..... Thanks you so much. I've stored this reply into a local text file and would be researching it until understand.
I didn't yet, but feel like when I read this 10 more times I will and then reference some parts again and again.
Now this is a true explanation for idiots) So even I would get it eventually.

Thank you SO SO MUCH Sven for taking your time to explain this. Some paragraphs are especially brilliant to me...
Thank you, thank you, thank you.

[hgm]

There really is nothing mysterious in this. A mate score for a given position should reflect the Distance To Mate for that position. A mate in 3 remains a mate in 3 no matter how many moves it takes to reach it. The nodes on a path to a forced mate get progressively get closer to the mate, and thus should each have a different score in the mating score range.

But standard alpha-beta search does not adapt scores when it propagates them through the root, and one solution to that is use the root score already at the leaf. This is why you add or subtract 'ply', which is the distance to the root. If in a certain node you see a mate in 3, 5 ply away from the root, that mate is 3 + 5 = 8 ply removed from the root.

[maksimKorzh]

There really is nothing mysterious in this. A mate score for a given position should reflect the Distance To Mate for that position. A mate in 3 remains a mate in 3 no matter how many moves it takes to reach it. The nodes on a path to a forced mate get progressively get closer to the mate, and thus should each have a different score in the mating score range.

But standard alpha-beta search does not adapt scores when it propagates them through the root, and one solution to that is use the root score already at the leaf. This is why you add or subtract 'ply', which is the distance to the root. If in a certain node you see a mate in 3, 5 ply away from the root, that mate is 3 + 5 = 8 ply removed from the root.

Mr. Muller can you please also clarify this question:
If I don't clear hash table every time when I call search position (where iterative deepening is calling alpha beta function is and best score is returned)
my engine either plays some weird/not strong moves (compared to if I reset hash table every new search) or even does not return a move at all (because I take moves from triangular PV and if hash is not cleared I can't even see the PV for all depths)

example output (no TT reset):

Code: Select all

info score cp 30 depth 1 nodes 25 time -1388662595 pv d2d4 
info score cp 0 depth 2 nodes 99 time -1388662595 pv d2d4 d7d5 
info score cp 30 depth 3 nodes 264 time -1388662594 pv d2d4 d7d5 b1c3 
info score cp 0 depth 4 nodes 2217 time -1388662587 pv d2d4 d7d5 b1c3 b8c6 
info score cp 30 depth 5 nodes 4776 time -1388662577 pv d2d4 d7d5 b1c3 b8c6 g1f3 
info score cp 10 depth 6 nodes 26920 time -1388662503 pv b1c3 d7d5 e2e4 d5e4 c3e4 g8f6 
info score cp 20 depth 7 nodes 73370 time -1388662370 pv d2d4 b8c6 g1f3 g8f6 b1c3 d7d5 c1f4 
info score cp 10 depth 8 nodes 247443 time -1388661910 pv e2e4 b8c6 g1f3 g8f6 e4e5 f6d5 c2c4 d5f4 
info score cp 20 depth 9 nodes 548010 time -1388661173 pv e2e4 b8c6 b1c3 g8f6 g1f3 d7d5 e4d5 f6d5 d2d4 
info score cp 10 depth 10 nodes 1410634 time -1388659026 pv e2e4 b8c6 b1c3 g8f6 g1f3 d7d5 e4e5 d5d4 e5f6 d4c3 
bestmove e2e4

  8  ♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜
  7  ♟︎ ♟︎ ♟︎ ♟︎ ♟︎ ♟︎ ♟︎ ♟︎
  6  . . . . . . . .
  5  . . . . . . . .
  4  . . . . ♙ . . .
  3  . . . . . . . .
  2  ♙ ♙ ♙ ♙ . ♙ ♙ ♙
  1  ♖ ♘ ♗ ♕ ♔ ♗ ♘ ♖

     a b c d e f g h

     Side:     black
     Enpassant:   e3
     Castling:  KQkq

     Hash key:  e31eb47239560bd3

info score cp -10 depth 1 nodes 0 time -1388659026 pv 
info score cp -10 depth 2 nodes 0 time -1388659026 pv 
info score cp -10 depth 3 nodes 0 time -1388659026 pv 
info score cp -10 depth 4 nodes 0 time -1388659026 pv 
info score cp -10 depth 5 nodes 0 time -1388659026 pv 
info score cp -10 depth 6 nodes 0 time -1388659026 pv 
info score cp -10 depth 7 nodes 0 time -1388659026 pv 
info score cp -10 depth 8 nodes 0 time -1388659026 pv 
info score cp -10 depth 9 nodes 0 time -1388659026 pv 
info score cp -25 depth 10 nodes 5674784 time -1388645074 pv d7d6 g1f3 g8f6 b1c3 b8c6 d2d4 e7e5 f1e2 e5d4 f3d4 
bestmove d7d6

TT reset every new search, e.g. search() { clear_hash_table(); // then go through iterative deepening}

Code: Select all

info score cp 30 depth 1 nodes 25 time -1388572524 pv d2d4 
info score cp 0 depth 2 nodes 99 time -1388572523 pv d2d4 d7d5 
info score cp 30 depth 3 nodes 264 time -1388572522 pv d2d4 d7d5 b1c3 
info score cp 0 depth 4 nodes 2217 time -1388572509 pv d2d4 d7d5 b1c3 b8c6 
info score cp 30 depth 5 nodes 4776 time -1388572490 pv d2d4 d7d5 b1c3 b8c6 g1f3 
info score cp 10 depth 6 nodes 26920 time -1388572343 pv b1c3 d7d5 e2e4 d5e4 c3e4 g8f6 
info score cp 20 depth 7 nodes 73370 time -1388572033 pv d2d4 b8c6 g1f3 g8f6 b1c3 d7d5 c1f4 
info score cp 10 depth 8 nodes 247443 time -1388570868 pv e2e4 b8c6 g1f3 g8f6 e4e5 f6d5 c2c4 d5f4 
info score cp 20 depth 9 nodes 548010 time -1388568933 pv e2e4 b8c6 b1c3 g8f6 g1f3 d7d5 e4d5 f6d5 d2d4 
info score cp 10 depth 10 nodes 1410634 time -1388563290 pv e2e4 b8c6 b1c3 g8f6 g1f3 d7d5 e4e5 d5d4 e5f6 d4c3 
bestmove e2e4

  8  ♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜
  7  ♟︎ ♟︎ ♟︎ ♟︎ ♟︎ ♟︎ ♟︎ ♟︎
  6  . . . . . . . .
  5  . . . . . . . .
  4  . . . . ♙ . . .
  3  . . . . . . . .
  2  ♙ ♙ ♙ ♙ . ♙ ♙ ♙
  1  ♖ ♘ ♗ ♕ ♔ ♗ ♘ ♖

     a b c d e f g h

     Side:     black
     Enpassant:   e3
     Castling:  KQkq

     Hash key:  e31eb47239560bd3

info score cp 0 depth 1 nodes 31 time -1388563241 pv d7d5 
info score cp -30 depth 2 nodes 138 time -1388563240 pv d7d5 b1c3 
info score cp 0 depth 3 nodes 606 time -1388563236 pv d7d5 b1c3 g8f6 
info score cp -15 depth 4 nodes 3120 time -1388563218 pv g8f6 b1c3 d7d5 d2d3 
info score cp -10 depth 5 nodes 7465 time -1388563190 pv g8f6 e4e5 f6d5 c2c4 d5f4 
info score cp -10 depth 6 nodes 38109 time -1388562985 pv d7d5 e4d5 d8d5 b1c3 d5e6 g1e2 g8f6 
info score cp -15 depth 7 nodes 90859 time -1388562646 pv d7d5 d2d3 d5e4 d3e4 g8f6 d1d8 e8d8 b1c3 
info score cp -10 depth 8 nodes 252381 time -1388561623 pv d7d5 d2d3 g8f6 e4e5 f6g4 d3d4 b8c6 g1f3 
info score cp -10 depth 9 nodes 755558 time -1388558507 pv d7d5 e4d5 d8d5 d2d4 b8c6 g1e2 g8f6 b1c3 d5d8 
info score cp -20 depth 10 nodes 4762332 time -1388533269 pv e7e5 g1f3 b8c6 d2d4 
bestmove e7e5

The second search is the same as the search WITHOUT TT.
I feel this is NOT OK. Could you please assume WHY is this happening?

P.S. I use ALWAYS REPLACE schema in TT
I read TT at the very beginning of alpha beta search and return score if found.
I write beta score on fail high (with beta flag)
I change hash flag from alpha to exact if score > alpha and then write alpha to TT with either alpha or exact flag (depending on whether alpha fails low or getting increased respectively)

[maksimKorzh]

In your search, the mate distance is relative to the root position. If you store it like that in the hash tables, and you have a hit in the next move turn, the mate score is wrong.

Example. You are at move 20 and see a mate in 8 plies. You store that position. Next move turn, so you are at move 21, and the mate is in 6 plies. Well but you stored it as mate in 8 plies!

So what you do is that when storing into the hash table, you take the mate distance relative to your current node, not to the root. And the other way around when retrieving.

Thank you, this at least clarifies the issue itself even though doesn't answer directly non of 2 questions asked. Anyway, I'll keep trying to understand it basing on your example. Good answer, but not enough for idiots... unfortunately.

You want to read more, so here you are ...

In write_hash_entry() you write:

Code: Select all

if (score > 48000) score -= ply;
if (score < -48000) score += ply;

In read_hash_entry() you write:

Code: Select all

if (score < -48000) score += ply;
if (score > 48000) score -= ply;

I guess now you see that both are the same, except for the order of the two lines of code ... The bug is in write_hash_entry() which should have:

Code: Select all

if (score > 48000) score += ply;
if (score < -48000) score -= ply;

while the mate score handling code in read_hash_entry() is ok.

So the answers to your questions are:
1) No
2) Irrelevant since your question is only related to 1)="Yes"

Explanation:
The origin of detecting a mate score for the first time is when the moving side S is mated in the current position P (mate is on the board). If we are at ply N, i.e. the current position is N plies away from the root, then the typical implementation (to which you refer here) is to return -(MATED_VALUE - N) at that point. The parent node, due to negamax, sees this as (MATED_VALUE - N) from the viewpoint of O, the opponent of S. Either the negative or the positive version of that score (depending on whose turn it is) is propagated to any node on the path from the root to P unless a better move is found that results in a shorter mate (for O) or a longer one (for S), or the mate can even be avoided for S.

Now suppose you are done with a node Q and store a score in TT, and it happens to be a mate score. You are at ply K (K < N) and the two cases are:

a) N-K is even (so it is again S to move): the score resulting from the search is still negative and of the form -(MATED_VALUE - N), but it means that S is mated in (N-K) plies from the current node Q;

b) N-K is odd (so it is O to move): the score resulting from the search is positive and of the form (MATED_VALUE - N), and it means that O can mate in (N-K) plies from the current node Q.

In both cases the score resulting from the search still reflects the distance of N plies between the root and P, the position where the mate actually happened.

Now position Q might occur somewhere else in the tree, or even during the next search. You want to save time and read the mate score from TT. But the distance to root may be different from what it was when the score was stored. The essential information you want to store shall be independent from the actual path from root to Q, it shall only reflect the distance from the current node Q (where you store the score) to P (the terminal node of the forced mating variation). Therefore N must be replaced by (N - K) when storing, so you always store "mated in (N - K) plies from here" or "mate in (N - K) plies from here".

You can figure out what "replacing N by (N - K)" means in the two cases above but nevertheless I'll also show the result of figuring it out ...

a) When storing a negative score -(MATED_VALUE - N) it is transformed into -(MATED_VALUE - (N - K)) by subtracting K:
-(MATED_VALUE - N) - K = -(MATED_VALUE - N + K) = -(MATED_VALUE - (N - K))

b) When storing a positive score (MATED_VALUE - N) it is transformed into (MATED_VALUE - (N - K)) by adding K:
(MATED_VALUE - N) + K = MATED_VALUE - (N - K)

Now it should be obvious what you do when retrieving a mate score from TT. You do exactly the opposite: at a node Q2 that is (supposedly) identical to Q and has a distance of K2 to the root, a negative TT score is transformed into a tree score by adding K2, and a positive TT score by subtracting K2. In both cases you "replace (N - K2) by N".

For the implementation it may be a good idea to have two small functions that return the transformation result, like in this example:

Code: Select all

int scoreToTT(int score, int ply) { return (score > MATE_SCORE) ? score + ply : (score < -MATE_SCORE) ? score - ply : score; }
int scoreFromTT(int score, int ply) { return (score > MATE_SCORE) ? score - ply : (score < -MATE_SCORE) ? score + ply : score; }

You would use scoreToTT() for storing and scoreFromTT() for retrieving scores, and you would not have to bother with the details of mate score transformation anywhere else outside these two functions.

Now to your practical example. You wrote you are at ply 5 and your search returns a "mate in 8" (plies). That cannot happen since 8 is even and you could only detect either a "mated in 8 plies" (case A) or, say, a "mate in 9 plies" (case B). You store the following:

A) Distance from root to mate is 5+8 = 13 so search returns -(49000 - 13) = -48987. You store a "mated in 8 plies" which is -48987 - 5 = -48992 = -(49000 - 8).

B) Distance from root to mate is 5+9 = 14 so search returns (49000 - 14) = +48986. You store a "mate in 9 plies" which is +48986 + 5 = +48991 = +(49000 - 9).

Now let's say you encounter the same position through a different path at ply 3. The terminal node of the mating line is (3+8) and (3+9) plies away from the root, depending on the two cases A and B:

A) TT returns -48992 which you transform into a tree score of -48992 + 3 = -48989 = -(49000 - 11).

B) TT returns +48991 which you transform into a tree score of +48991 - 3 = +48988 = +(49000 - 12).

Note also that mate scores occurring in the tree are within the following ranges (assuming your constants):

a) negative mate scores (mated in even number of plies at any ply):
-49000 = "mated at root" (this would usually not happen since you don't start a search when you are already mated)
-48999 = "mated in 0 at ply 1"
-48998 = "mated in 0 at ply 2" or "mated in 2 at root"
-48997 = "mated in 0 at ply 3" or "mated in 2 at ply 1"
...
-48001 = "mated in 0 at ply 999" or "mated in 2 at ply 997" or ... or "mated in 998 at ply 1"

b) positive mate scores (mate in odd number of plies at any ply):
+49000 can never happen
+48999 = "mate in 1 at root"
+48998 = "mate in 1 at ply 1"
+48997 = "mate in 1 at ply 2" or "mate in 3 at root"
...
+48001 = "mate in 1 at ply 998" or "mate in 3 at ply 996" or ... or "mate in 999 at root"

In contrast to that, mate scores stored in TT can only have the following values:

a) negative mate scores (mated in even number of plies):
-49000 = "mated" (some engines do not store "mated in 0" scores in TT, though)
-48998 = "mated in 2"
-48996 = "mated in 4"
...
-48002 = "mated in 998"

b) positive mate scores (mate in odd number of plies):
+48999 = "mate in 1"
+48997 = "mate in 3"
+48995 = "mate in 5"
...
+48001 = "mate in 999"

It WORKS!
I still keep rereading your posts and also stored it on github along with one of my tutorials:
https://github.com/maksimKorzh/chess_pr ... ing_scores
So now many people would make use of it!

THANK YOU AGAIN AND AGAIN!

[Harald]

May be in my original post below the video I confused the signs of +-ply. And the example I gave may be slightly wrong. Sorry for that.
But at least I initiated this discussion.

[maksimKorzh]

May be in my original post below the video I confused the signs of +-ply. And the example I gave may be slightly wrong. Sorry for that.
But at least I initiated this discussion.

Otherwise I wouldn't get that deep)