Mate scores in the hash table

[Eduardo Waghabi]

Hi there,

Please help the rookie.

I?m trying to get rid of my engine?s ridiculous behavior when giving mate. The first obvious change was to give a different mate score depending on the depth (like it?s probably implemented in all other engines), so I simply subtract ply from MATE (which is 9999).

That work wonders in the absence of transposition tables (like you all already know) or if I clean the transposition table in the beginning of every search, as if in analysis, but then I lose too much performance.

So I decided to translate mate scores from and to the ttables. Firstly I decided to do something like this, both in beta and alpha nodes:

Code: Select all

hashScore = beta;
if (hashScore >= LIM_MATE && hashScore < INFINITO)   
  hashScore += ply;
if (hashScore <= -LIM_MATE && hashScore > -INFINITO)
  hashScore -= ply;    
UpdateTTable();


Where LIM_MATE is something to make sure this is a mate score, so it?s actually MATE ? 100 (I?m assuming my engine will never find a mate in 50). Of course this is the beta cut-off code, so I do the exact same thing in the alpha update.

This correctly stores the mate scores in the hash table for the first mate found, but during the search if I?m at ply 10, and I find it?s a mate in one (score == 9997), I?ll store 10007 in the ttable.

So I figured out I should also translate back the mate scores when I find them in the ttable, by doing the opposite operation. So, if I?m at ply 10 and searching the ttable I find out it?s a mate in one (9997), I translate it into mate in 6 (9987).

Code: Select all

if (hashValue >= LIM_MATE && hashValue < INFINITO)   
  hashValue -= ply;
if (hashValue <= -LIM_MATE && hashValue > -INFINITO)
  hashValue += ply;    


This ALMOST works. For some reason, the engine actively search for the fastest mate, but always showing a slightly wrong score, and effectively misses the quickest mate by one or two moves.

It wouldn?t be so bad if the moves where missed while somewhere between mate in 10 and mate in 5, but for my despair and embarrassment it always misses the mate in one.

So I?m officially out of ideas. Can you please give/rent/sell me some?

[milix]

Hi Eduardo.

I am not totally sure that my algorithm is ok. First, note that I use pv search with null window, I don't use transposition cutofs in pv nodes - namely when beta > alpha+1.

When i have a lower bound (score >= beta) I store MATE-MATE_LIMIT because I just care that this position is a mate.
When i have an upper bound (score <= alpha) I store -MATE+MATE_LIMIT because I just care that in this position I got mated.
In exact scores, beta>score>alpha, I do exactly what you did (I 'shorten' the mate by current ply).

[Sven Schüle]

Hi Eduardo,

I have similar problems with my engine Surprise, at least they are in the same area of mate scoring and hash table. Surprise misses the shortest mate in many cases, too, and I did not find the bug yet.

But in your case I'll try to find the problems in your description first.

so I simply subtract ply from MATE (which is 9999)
[...]
but during the search if I?m at ply 10, and I find it?s a mate in one (score == 9997), I?ll store 10007 in the ttable.

If you are at depth 10 and you find a mate in one (for the moving side), then your search should return (MATE - (depth+1)) which is 9988 in your case, and you store (MATE - 1) in the hash table. When retrieving this value later at some depth d (different from previous 'depth' or not), you translate this back into (MATE - (d+1)), i.e. you subtract d from the retrieved value. Similar for negative scores (mate against moving side).

I assume you are doing it like this but your description was not clear to me. If my assumption is wrong then maybe this already helps you.

Now there is another issue, when retrieving a mate score from hash table you might want to use the information whether the score had been stored as an upper bound (failed low), as a lower bound (beta cutoff) or an "exact" value (within window).

This is exactly the area where my problems begin. I read what Bruce Moreland writes about this and also how e.g. Fruit implements it (quite similar I think?), and I tried to adapt it for my engine but still it does not work.

So you are not alone when asking for help

Sven

[Ilari Pihlajisto]

Hi, I'm also very inexperienced at chess programming and this is my first post here (Hi there people!) but maybe I can help here.

I'm not exactly sure what you should do because I haven't seen the rest of the code of your search function, but here's a very very simple example that I just wrote:

Code: Select all

int Search(int alpha, int beta, int depth) {

  int val;
  /* Search the transposition table */
  if ((val = ProbeHash(depth, alpha, beta)) != UNKNOWN) return val;

  /* Leaf node, return static evaluation */
  if (depth <= 0) return Eval();

  /* If a king capture is generated (return value of GenerateMoves() is 0), */
  /* return score MATE + 1                                                  */
  if (GenerateMoves() == 0) return MATE + 1;

  while (MovesLeft()) {
    MakeNextMove();
    val = -Search(-beta, -alpha, depth - 1);
    UnmakeMove();

    /* If a mate is detected deeper in the search, increment the distance */
    /* to the mate by one ply                                             */
    if (val > MATE - 100 && val < INFINITY) val--;
    else if (val < -MATE + 100 && val > -INFINITY) val++;

    /* Beta cut-off */
    if (val >= beta) {
      RecordHash(depth, beta);
      return beta;
    }

    if (val > alpha)
      alpha = val;
  }

  /* If the current position has a negative mate score (the friendly king  */
  /* gets captured in the opponents next move), check whether the position */
  /* is a mate or a stalemate                                              */
  if (alpha == -MATE) {
    /* If the opponent cannot capture the friendly king in this position,  */
    /* it's a stalemate so 0 is returned                                   */
    if (GenerateOpponentsMoves() != 0)
      alpha = 0;
  }

  /* Save the value in the transposition table */
  RecordHash(depth, alpha);
  return alpha;
}

This is probably the segment you might be interested in:

Code: Select all

if (val > MATE - 100 && val < INFINITY) val--;
else if (val < -MATE + 100 && val > -INFINITY) val++;

I think this works fine with transposition tables or any pruning methods. This way the search function always returns MATE - distance_to_mate for any position the leads to a mate instead of MATE + distance_to_leaf_node which is what your code seems to do.

[Eduardo Waghabi]

Thanks for the feedback.

Sven, the ?+1? is pretty obvious once you stop and think (what is even more frightening if you consider how many times I?ve thought about it). After that, the scores have been consistent, and it hasn?t missed any more mate-in-ones, so now I?m thinking it wasn?t missing in the first place, I was just being misled by the wrong score.

Ilari, I?ll take a look at your code and see if I can use something, but my code is currently also returning MATE ? distance to mate, as I intended to (which is an amazing coincidence!).

[Ilari Pihlajisto]

Okay, it seems I don't really understand your code then or we are just doing things very differently.

This correctly stores the mate scores in the hash table for the first mate found, but during the search if I?m at ply 10, and I find it?s a mate in one (score == 9997), I?ll store 10007 in the ttable.

Why don't you just store 9997 also in the hash table? I don't see how the depth (10 plys in this case) is relevant here, just the distance to mate (1 ply). I mean of course you have to also store depth, but why add it to the score?

[Eduardo Waghabi]

I don?t actually want to store such strange value on the ttable, I was just referring to the collateral bug I had before I coded the last part of my original post. I see now that was probably where you assumed I wanted to store MATE + distance.

I have just tried to use your very simple solution (decrementing/incrementing the value at each node if it?s a mate score), but in spite of making much sense do me, it didn?t work. My engine showed wrong scores and didn?t take the shortest path to mate. I could have done something wrong, so later I?ll give it another try.

[Sven Schüle]

Thanks for the feedback.

Sven, the “+1” is pretty obvious once you stop and think (what is even more frightening if you consider how many times I’ve thought about it). After that, the scores have been consistent, and it hasn’t missed any more mate-in-ones, so now I’m thinking it wasn’t missing in the first place, I was just being misled by the wrong score.

Ilari, I’ll take a look at your code and see if I can use something, but my code is currently also returning MATE – distance to mate, as I intended to (which is an amazing coincidence!).

Hi Eduardo,

what does your search function return at ply 1 when it detects that the moving side is mate? I would expect it returns -(MATE-1).
Being mate at ply d should return -(MATE-d).

When, at ply d, your search finds that the moving side can mate in one ply, it should return +(MATE-(d+1)).
Finding mate in N at ply d should return +(MATE-(d+N)).

The TT values in these four examples would be -MATE, -MATE, +(MATE-1), +(MATE-N), provided someone would also store the first two (mate) positions in TT.

Now why are you "off by one"? I'm sorry, but it is not obvious to me.

Sven
(Sorry for some edits in the last few minutes)

[Anonymous]

If you encounter a mate score, convert it to the "worst" possible mate score and store it as a bound.

For example, if you find an "exact mate in 6", turn it into "at least mate in 1000" when you store it.

This is easy to understand, won't cause bugs, and will still allow cutoffs in most cases.

The only gotcha is that if you have an "at most mate in 6" score come in, meaning a fail low on a positive mate score, which is a weird thing to see, the best thing to do is refuse to store this element, since it is impossible to use this technique to convert the score into something sane. The same is true of a fail high on a negative mate.

See Gerbil for apparently bug-free mate hash store code.

bruce

[Josu? Forte]

Hi Eduardo,

I will try to help you.
What Bruce has explainned in his message is implemented in the piece of code below. It works fine in my engine Matheus.
Boa sorte!

Um abra?o,
Josu?

Code: Select all

/*
+---------------------------------------------------------------------+
|                                                                     |
|   Search() - Executes the search.                                   |
|   On entry :                                                        |
|   moving_color is next to move.                                     |
|   current_move[ply - 1] contains last performed move.               |
|   alpha, beta contains the alpha - beta window.                     |
|   depth_remaining contains the depth of search left.                |
|                                                                     |
|   On exit :                                                         |
|   pv[] contains the principal variation.                            |
|   search returns the evaluation for moving_color.                   |
|                                                                     |
+---------------------------------------------------------------------+
*/

int Search (int alpha, int beta, int depth_remaining)
{
   int *move;
   int score;
   int pvs = 0;
   int fail_low_score = -MATE_VALUE;
   HASH_ENTRY *hash_entry =
      &hashtable[moving_color][(unsigned int)hashkey & hashtable_size_mask];

   if (++node_counter > node_counter_limit) ScanInput();
   depth_remaining--;

/* Verify if this position is in the hashtable. ("always" element) */

   if (hash_entry->always.hashkey == hashkey) {
      if (hash_entry->always.depth_remaining >= (char)depth_remaining) {
         int hash_score = (int)hash_entry->always.score;

/*
Mate scores have to be adjusted because here "hash_score" represents
mate in N plies from this position. We must retrieve "hash_score"
as mate in N plies from the root.
*/
         if (abs(hash_score) >= MATE_VALUE - MAX_DEPTH) {
            if (hash_score > 0) hash_score -= ply;
            else hash_score += ply;
         }
         if (hash_entry->always.flag.bound & LOWER_BOUND) {
            if (hash_score >= beta)
               return(hash_score);
         }
         else if (hash_entry->always.flag.bound & UPPER_BOUND) {
            if (hash_score <= alpha)
               return(hash_score);
         }
      }
   }

/* Verify if this position is in the hashtable. ("depth" element) */

   if (hash_entry->depth.hashkey == hashkey) {
      if (hash_entry->depth.depth_remaining >= (char)depth_remaining) {
         int hash_score = (int)hash_entry->depth.score;
/*
Mate scores have to be adjusted because here "hash_score" represents
mate in N plies from this position. We must retrieve "hash_score"
as mate in N plies from the root.
*/
         if (abs(hash_score) >= MATE_VALUE - MAX_DEPTH) {
            if (hash_score > 0) hash_score -= ply;
            else hash_score += ply;
         }
         if (hash_entry->depth.flag.bound & LOWER_BOUND) {
            if (hash_score >= beta)
               return(hash_score);
         }
         else if (hash_entry->depth.flag.bound & UPPER_BOUND) {
            if (hash_score <= alpha)
               return(hash_score);
         }
      }
   }

   next_move_pointer[ply + 1] = GenerateLegalMoves(next_move_pointer[ply]);
   legal_moves[ply] = next_move_pointer[ply + 1] - next_move_pointer[ply];

/* Search starts here.*/

   for (move = next_move_pointer[ply]; move < next_move_pointer[ply + 1]; move++) {
      MakeMove(move);
      current_move[ply] = *move;

      moving_color = not_moving_color;
      not_moving_color ^= 1;
      ply++;

      if (depth_remaining > 0) {
         if (pvs) {
            score = -Search(-alpha - 1, -alpha, depth_remaining);
            if ((score > alpha) && (score < beta))
               score = -Search(-beta, -alpha, depth_remaining);
         }
         else score = -Search(-beta, -alpha, depth_remaining);
      }
      else
         score = -QuiescentSearch(-beta, -alpha);

      ply--;
      not_moving_color = moving_color;
      moving_color ^= 1;

      UnMakeMove(move);
      if (stop_search) return(score);

      if (score >= beta) { /* Fail High.*/
         int fail_high_score = score;

         if (abs(score) >= (MATE_VALUE - MAX_DEPTH)) { /* Mate score */
/*
Mate scores have to be adjusted because here "score" represents
mate in N moves from this position. We must retrieve "score" as
mate in N moves from the root.
*/
            if (score > 0) score += ply;
            else score -= ply;
         }

/* Record search result in hashtable. ("always" element) */

         hash_entry->always.flag.bound = LOWER_BOUND;
         hash_entry->always.move = *move;
         hash_entry->always.hashkey = hashkey;
         hash_entry->always.score = score;
         hash_entry->always.depth_remaining = (char)depth_remaining;

/* Record search result in hashtable. ("depth" element) */

         if ((age != hash_entry->depth.flag.age) ||
            (hash_entry->depth.depth_remaining < (char)depth_remaining)) {
            if (age != hash_entry->depth.flag.age) {
               hashtable_write++;
               hash_entry->depth.flag.age = (unsigned char)age;
            }
            hash_entry->depth.move = *move;
            hash_entry->depth.hashkey = hashkey;
            hash_entry->depth.depth_remaining = (char)depth_remaining;
            hash_entry->depth.score = score;
            hash_entry->depth.flag.bound = LOWER_BOUND;
         }
         return(fail_high_score);
      }

      if (score > alpha) {
            alpha = score;
            pv[ply][ply] = *move;
            if (depth_remaining) UpDatePV();
            else pv_length[ply] = 1;
            pvs = 1;
      }
      if (score > fail_low_score)
         fail_low_score = score;
   }
/* Search ends here.*/

   if (legal_moves[ply] == 0) { /* Verify if it is Mate or Stalemate.*/
      pv[ply][ply] = 0;
      pv_length[ply] = 0;
      if (IsAttacked(KING_SQUARE(moving_color), not_moving_color))
         return(ply - MATE_VALUE);
      else /* Stale Mate */
         return(0);
   }

   score = alpha;
   if (pvs) {
      
/* This is an EXACT_SCORE, so update killer moves.

      UpdateKillerMove((MOVE *)&pv[ply][ply]);

/* Record search result in hashtable. ("always" element) */

      if (abs(alpha) >= (MATE_VALUE - MAX_DEPTH)) {
/*
Mate scores have to be adjusted because here "score" represents
mate in N moves from this position. We must retrieve "score" as
mate in N moves from the root.
*/
         if (alpha > 0) score = alpha + ply;
         else score = alpha - ply;

/* If EXACT_SCORE on +mate, change it to LOWER_BOUND.*/

         if (alpha > 0) {
            hash_entry->always.move = pv[ply][ply];
            hash_entry->always.flag.bound = LOWER_BOUND;
         }

/* If EXACT_SCORE on -mate, change it to UPPER_BOUND.*/

         else {
            hash_entry->always.move = 0;
            hash_entry->always.flag.bound = UPPER_BOUND;
         }
      }
      else {
          hash_entry->always.flag.bound = EXACT_SCORE;
         hash_entry->always.move = pv[ply][ply];
      }
      hash_entry->always.hashkey = hashkey;
      hash_entry->always.score = score;
      hash_entry->always.depth_remaining = (char)depth_remaining;

/* Record search result in hashtable. ("depth" element) */

      if ((age != hash_entry->depth.flag.age) ||
         (hash_entry->depth.depth_remaining < (char)depth_remaining)) {
         if (age != hash_entry->depth.flag.age) {
            hashtable_write++;
            hash_entry->depth.flag.age = (unsigned char)age;
         }
         if (abs(alpha) >= (MATE_VALUE - MAX_DEPTH)) {

/* EXACT_BOUND on +mate. Change it to LOWER_BOUND.*/

            if (alpha > 0) {
               hash_entry->depth.move = pv[ply][ply];
               hash_entry->depth.flag.bound = LOWER_BOUND;
            }

/* EXACT_BOUND on -mate. Change it to UPPER_BOUND.*/

            else {
               hash_entry->depth.move = 0;
               hash_entry->depth.flag.bound = UPPER_BOUND;
            }
         }
         else {
            hash_entry->depth.move = pv[ply][ply];
            hash_entry->depth.flag.bound = EXACT_SCORE;
         }
         hash_entry->depth.hashkey = hashkey;
         hash_entry->depth.score = score;
         hash_entry->depth.depth_remaining = (char)depth_remaining;
      }
      return(alpha);
   }
   else { /* Fail Low.*/
      if (abs(fail_low_score) >= (MATE_VALUE - MAX_DEPTH)) { /* Mate score */
/*
Mate scores have to be adjusted because here "score" represents
mate in N moves from this position. We must retrieve "score" as
mate in N moves from the root.
*/
         if (fail_low_score > 0) score = fail_low_score + ply;
         else score = fail_low_score - ply;
      }

/* Record search result in hashtable. ("always" element) */

      hash_entry->always.hashkey = hashkey;
      hash_entry->always.move = 0;
      hash_entry->always.flag.bound = UPPER_BOUND;
      hash_entry->always.score = score;
      hash_entry->always.depth_remaining = (char)depth_remaining;

/* Record search result in hashtable. ("depth" element) */

      if ((age != hash_entry->depth.flag.age) ||
         (hash_entry->depth.depth_remaining < (char)depth_remaining)) {
         if (age != hash_entry->depth.flag.age) {
            hashtable_write++;
            hash_entry->depth.flag.age = (unsigned char)age;
         }
         hash_entry->depth.hashkey = hashkey;
         hash_entry->depth.move = 0;
         hash_entry->depth.flag.bound = UPPER_BOUND;
         hash_entry->depth.score = score;
         hash_entry->depth.depth_remaining = (char)depth_remaining;
      }
      return(fail_low_score);
   }
}


[Chan Rasjid]

Bruce Moreland wrote:-

If you encounter a mate score, convert it to the "worst" possible mate score and store it as a bound.

For example, if you find an "exact mate in 6", turn it into "at least mate in 1000" when you store it.

This is easy to understand, won't cause bugs, and will still allow cutoffs in most cases.

The only gotcha is that if you have an "at most mate in 6" score come in, meaning a fail low on a positive mate score, which is a weird thing to see, the best thing to do is refuse to store this element, since it is impossible to use this technique to convert the score into something sane. The same is true of a fail high on a negative mate.

See Gerbil for apparently bug-free mate hash store code.

bruce

Hello everyone, Eduardo,

I am surprise to read there may be alternatives (or concern) in storing mate-scores in hash.

When I started, I figured the only logical method and later read others
made the same mistakes and just followed the same one method as I use.

The only difference is in my normal search, it returns whenever the score>=P_MATE and hashed as exact(9999)/lower.I have a search_better_mate_root() that is called if score_root>=P_MATE. So mate search never ever(seem to) fail,it goes like... 9991, 9993, 9997, checkmate. If there are problems, it miss detecting them.

Edwardo, your original post is rather lengthy.
Should I have your type of bugs (or dissatisfaction).

Thanks
Rasjid

Code: Select all

#define    INFI             10000
#define    MAX_PLY           63
//last min edit
#define    P_MATE          9937
#define    M_MATE         -9937



void storeHash(int type, int depth, int val, long m)
{
   
....

   if (val>M_MATE && val<P_MATE);
   else if (val<=M_MATE){
      val -= ply;//adjusted value to store
      assert(val>=-INFI && !(val&1));//parity
   }else{
      val += ply;
      assert(val<=INFI-1 && val&1);//parity
   }
..
}
 

int hashValue(){
   int i;
   //retrieve score from hash
   i = (int)((I64)phT->buf2>>50);//14 bits,msb==sign, sign extended ok
   assert(i>HASH_SCORE_MIN && i<HASH_SCORE_MAX);
   
   if (i>M_MATE && i<P_MATE)
   return i;
   if (i<=M_MATE){
      assert(i>=-INFI && !(i&1));
      return i+ply;//undo ply adjustment
   }
   
   assert(i<=INFI-1 && i&1);
   return i-ply;   
}


[Chan Rasjid]

Eduardo's original post has:-

This correctly stores the mate scores in the hash table for the first mate found, but during the search if I?m at ply 10, and I find it?s a mate in one (score == 9997), I?ll store 10007 in the ttable.

Eduardo,

I can't understand this. If at ply 10 and it is mate in 1, you would have:-

val = -search(....);
undo();

where val = -(-10000 + (10+3)) = 9987;
ie, 3 ply above returns -10000+ply.

Usual adjusted hashing score seem to be:-
val+ply == 9987+10 == 9997.

Thanks
Rasjid

[Chan Rasjid]

I just forget one more thing that may be relevant or wrong!;

for hashing adjusted plus-mate the depth is always MAX_DEPTH;
same for exact/upper minus-mate.

for lower minus-mate - just the depth???

Thanks Rasjid

[Eduardo Waghabi]

Chan, I might have expressed myself rather poorly in the first post. About the ?10007? score, I was just explaining a bug before I coded the whole solution. I?ve answered Ilari?s similar question some posts above.

Hi Eduardo,

what does your search function return at ply 1 when it detects that the moving side is mate? I would expect it returns -(MATE-1).
Being mate at ply d should return -(MATE-d).

Sven, I?m not sure anymore of what it used to return at the time I wrote the original post, but right now it returns ?(MATE + 1 - ply) whenever the side is in check and has no legal moves.

So in a position like 6k1/5ppp/8/8/b7/8/5PPP/2R3K1 w - - 0 1
Analysis give me the following line:
depth=4 +99.97 1. Rc8+ Be8 2. Rxe8#

Is this score wrong? Am I ?off by one??

One thing I don?t get from Bruce?s post (and also from his excellent website) is this ?at least mate in 1000? thing. If I store both exact mates in 6 and 7 as ?at least mate in 1000?, how will the engine choose the fastest option?

Thanks Josu? and Chan for the snippets. I?ll take a look at them as soon as I can.

[Sven Schüle]

what does your search function return at ply 1 when it detects that the moving side is mate? I would expect it returns -(MATE-1).
Being mate at ply d should return -(MATE-d).

Sven, I’m not sure anymore of what it used to return at the time I wrote the original post, but right now it returns –(MATE + 1 - ply) whenever the side is in check and has no legal moves.

So in a position like 6k1/5ppp/8/8/b7/8/5PPP/2R3K1 w - - 0 1
Analysis give me the following line:
depth=4 +99.97 1. Rc8+ Be8 2. Rxe8#

Is this score wrong? Am I “off by one”?

Hi Eduardo,

this score looks o.k. but then you might also decide to change the value (and meaning) of your MATE constant into 10000 which is more reasonable, at least for me. You are using MATE + 1 anyway before subtracting ply, so why not simply -(MATE - ply)?

I had thought you were "off by one" only because it appeared to me that you got a score of 9997 (your MATE - 2) for a "mate in one" = mate in one ply. But let's forget the past!

Btw, meanwhile I have fixed my mate scoring problems in Surprise 4.2.4 (at least I hope so). The main problem was that I did not flag TT mate scores as "exact" although they were. I found that there are cases where even a beta cutoff can return an exact value. Consider searching at ply 7 with some alpha-beta window far away from mate. The subtree finds a mate in one ply (MATE - 8). This is the maximum possible value here, so it is exact although MATE - 8 >= beta. There is no better value for the moving side than mating in one ply.

The same applies for the alpha direction, same example: finding a mate in two plies at ply 7, i.e. -(MATE - 9), is an exact value (for full search of course, and only if not being in check). The opponent cannot do better at that ply, and the moving side will be mated instantly regardless which move is selected.

Implementing this handling of minimum/maximum possible values (I also set it to zero if the corresponding side has only the king left) had been present in Surprise for a long time but was incomplete, especially it did not have any influence on stored TT information. Therefore, when returning to a TT position flagged as "alpha value" with a different window, it was possible that the search returned the new alpha value instead of the already stored "exact" value (as shown above), this was repeated several times (perhaps once per iteration), and a real mate score of, say, -9995 migrated into some artificial "-9875" or the like.

Phew, I hunted this bug for more than half a year, now it seems to be gone ...

Thanks to you, Eduardo, and to all contributors of this thread. Looks like we both solved our problem by writing and reading about it here, great!

Sven

[Anonymous]

I did not read all of the thread carefully. Hope my response is still ok, even when it might miss some context.

Btw, meanwhile I have fixed my mate scoring problems in Surprise 4.2.4 (at least I hope so). The main problem was that I did not flag TT mate scores as "exact" although they were. I found that there are cases where even a beta cutoff can return an exact value. Consider searching at ply 7 with some alpha-beta window far away from mate. The subtree finds a mate in one ply (MATE - 8). This is the maximum possible value here, so it is exact although MATE - 8 >= beta. There is no better value for the moving side than mating in one ply.

This looks wrong to me. You should just adjust any mate value with the current ply from root, not only exact values. (Bob had suggested in the past to only adjust exact mate values, IMO, this is clearly wrong).

An example, where just storing any mate value as exact will go wrong.

Assume you search with [-Infinity, -Mate in 5]; you get a fail high with -Mate in 6 (counting from the root, you may get this after some blunder move of the opponent in much better position, that allows some easy baseline mate some plies down from the root). When you store an exact value here, and revisit the position (with a totally different window), you grab that mate score from the HT and cutoff with a totally bogus score from the HT. If you had kept the score as a lower bound in the HT, everything would be fine.

Sure, failing high with a positive mate score can be seen as an (almost) exact score, dito for failing low with a negative mate score. But no need or advantage, to change the bound here either.

When fetching a mate score from the HT, some tricks can be done. When the score is out of the window and has the correct bound, (lower bound for positive mate scores and upper bound for negative mate scores), you can cutoff independent of the stored draft. You can do the same with exact mate scores. But you should not throw away the bound information when storing.

Regards,
Dieter

PS. I see, you are from Berlin. Since a while, I am in Berlin, too. I meet quite regularily Stefan Knappe, author of Matador, in the evening for a beer. Often we also talk about computer chess. Perhaps you want to join now and then?

[Sven Schüle]

Btw, meanwhile I have fixed my mate scoring problems in Surprise 4.2.4 (at least I hope so). The main problem was that I did not flag TT mate scores as "exact" although they were. I found that there are cases where even a beta cutoff can return an exact value. Consider searching at ply 7 with some alpha-beta window far away from mate. The subtree finds a mate in one ply (MATE - 8). This is the maximum possible value here, so it is exact although MATE - 8 >= beta. There is no better value for the moving side than mating in one ply.

This looks wrong to me. You should just adjust any mate value with the current ply from root, not only exact values. (Bob had suggested in the past to only adjust exact mate values, IMO, this is clearly wrong).

Hi Dieter,

correct of course, but my "MATE - 8" was meant to be the tree score, not the adjusted TT score. Sorry for not pointing this out.

An example, where just storing any mate value as exact will go wrong.

I don't do this in general, only in the case I described above (min or max possible score detected). So your example is not in contradiction to my implementation, that's fine!

When fetching a mate score from the HT, some tricks can be done. When the score is out of the window and has the correct bound, (lower bound for positive mate scores and upper bound for negative mate scores), you can cutoff independent of the stored draft. You can do the same with exact mate scores. But you should not throw away the bound information when storing.

I'll check whether I already do this (probably not yet because checking for the draft is one of the first steps in my code IIRC).

PS. I see, you are from Berlin. Since a while, I am in Berlin, too. I meet quite regularily Stefan Knappe, author of Matador, in the evening for a beer. Often we also talk about computer chess. Perhaps you want to join now and then?

Nice to hear this, I'll contact you via PN! Perhaps I can allocate some time for drinking a beer ...

Sven