Puzzle with mate scores in TT

[bob]

Ok, Evert/ Bob, I hear you. How about this, then? How likely are you to have problems if you don't look after mate scores (as outlined by Bob) in the TT?

Depends on how you deal with mate scores.
When the recursive call returns a mate-in-N score, I adjust it to mate-in-N+1 before returning it. That's also the value that is stored in the TT and I don't need to do anything special to it when it's returned after a hash probe.

Mate in N+1 makes no sense to me.

For Crafty, if it is a mate in N score, I change it to mate in N - + ply - 1, if it is a mated in N score, I change it to mate in N - (ply - 1)

which gives the correct score. In Crafty, MATE=32768, and in the search, if I discover I am mated at some ply, I return - (MATE - ply)

[Evert]

Mate in N+1 makes no sense to me.

For Crafty, if it is a mate in N score, I change it to mate in N - + ply - 1, if it is a mated in N score, I change it to mate in N - (ply - 1)

which gives the correct score. In Crafty, MATE=32768, and in the search, if I discover I am mated at some ply, I return - (MATE - ply)

I return -MATE if the current position is mate, which then gets backed up as "MATE-1" or "mate in 1 ply" one level up, "-MATE+2" or "mated in 2 ply" one level up from there, etc.
The reason for doing that is that I find that the easiest way to follow what is happening, probably in part because I thought of doing it that way independently years ago.

[bob]

Mate in N+1 makes no sense to me.

For Crafty, if it is a mate in N score, I change it to mate in N - + ply - 1, if it is a mated in N score, I change it to mate in N - (ply - 1)

which gives the correct score. In Crafty, MATE=32768, and in the search, if I discover I am mated at some ply, I return - (MATE - ply)

I return -MATE if the current position is mate, which then gets backed up as "MATE-1" or "mate in 1 ply" one level up, "-MATE+2" or "mated in 2 ply" one level up from there, etc.
The reason for doing that is that I find that the easiest way to follow what is happening, probably in part because I thought of doing it that way independently years ago.

That can be a bit problematic, because you end up storing different scores. And what about bounds? One can get mate scores as bounds. And then try to use them at a different "depth" due to transpositions. How do you keep that consistent??? Mate-in-N from current ply avoids that...

[Evert]

That can be a bit problematic, because you end up storing different scores. And what about bounds? One can get mate scores as bounds. And then try to use them at a different "depth" due to transpositions. How do you keep that consistent??? Mate-in-N from current ply avoids that...

Aren't we talking about the same thing, then?
If the current ply is mate-in-N, I return a score that says it's mate-in-N. It gets stored in the transposition table as "this position is mate-in-N", so when it's retrieved, it gets consistently reported as "mate-in-N".

[bob]

That can be a bit problematic, because you end up storing different scores. And what about bounds? One can get mate scores as bounds. And then try to use them at a different "depth" due to transpositions. How do you keep that consistent??? Mate-in-N from current ply avoids that...

Aren't we talking about the same thing, then?
If the current ply is mate-in-N, I return a score that says it's mate-in-N. It gets stored in the transposition table as "this position is mate-in-N", so when it's retrieved, it gets consistently reported as "mate-in-N".

Maybe you are correct. I might not have quite understood what you meant initially, but in thinking about it, the only problem I see is that you can have mate bounds near the root, and when you do alpha/beta comparisons near the tip the bounds are not compatible with the altered score.

Note that I do not adjust the score in the tree search, but only when I store or retrieve a score from the table. Backing up changing mate scores from ply to ply would still seem to be problematic to me from that perspective...

An example. At the root your bounds are (say) (Mate-in-6, mate in 4). The mate score (mate in 0) doesn't compare very well to those bounds... If you are at depth 10 and discover you are mated, back at ply 9 you have a score of mate in 5, which is within those bounds, normally. But in your case, you would have a score of mate, which is outside the window. How do you handle that???

[Evert]

Maybe you are correct. I might not have quite understood what you meant initially, but in thinking about it, the only problem I see is that you can have mate bounds near the root, and when you do alpha/beta comparisons near the tip the bounds are not compatible with the altered score.

Note that I do not adjust the score in the tree search, but only when I store or retrieve a score from the table. Backing up changing mate scores from ply to ply would still seem to be problematic to me from that perspective...

An example. At the root your bounds are (say) (Mate-in-6, mate in 4). The mate score (mate in 0) doesn't compare very well to those bounds... If you are at depth 10 and discover you are mated, back at ply 9 you have a score of mate in 5, which is within those bounds, normally. But in your case, you would have a score of mate, which is outside the window. How do you handle that???

That's a good point, and one that I handn't originally thought of. It's necessary to change the window bounds if they indicate a mate score, so bounds of (mate-in-6, mate-in-4) become (mated-in-3, mated-in-5) etc.
I'll have to check whether the way I handle that now is correct, because as I say it's not something I had originally thought of.

I use fail-soft alpha-beta, so I think a mate-score that is outside the window bounds will still be backed up to the root correctly, or at least there's a chance it will be backed up correctly even with incorrect window bounds, but I'll need to sit down with pen&paper to check my suspicion here.
I'll also make a note to double-check my code to make sure I handle this correctly. I know I don't have a problem with finding and delivering mates, but that doesn't mean there are no bugs there.

All in all, I won't disagree that this is not quite as simple as I made it out to be. Perhaps simply returning "mate-in-ply" when the mate is discovered and adjusting the score in the hash table is in fact the more elegant solution here.

[hgm]

This is the way I always do it in my engines.

Code: Select all

Search(alpha, beta)
{

    if(CAN_CAPTURE_KING) return +INF;

    if&#40;alpha < curEval&#41; alpha--;
    if&#40;beta <= curEval&#41; beta--;

    // Standard search
    ...

    return bestScore + &#40;alpha < curEval&#41;;
&#125;

The incrementing of negative return scores corrects the mating distance when backing up the score to the root, so that mate-in-N becomes mate-in-(N+1) two ply closer to the root. But the window bounds have to be corrected with the inverse function, or horrendous blunders get played. I never correct anything that is stored or read from the TT.

[zamar]

SF has this:

Code: Select all

    // At PV nodes, we don't use the TT for pruning, but only for move ordering.
    // This is to avoid problems in the following areas:
    //
    // * Repetition draw detection
    // * Fifty move rule detection
    // * Searching for a mate
    // * Printing of full PV line
    if (!PvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
    {
        TT.refresh(tte);
        ss->bestMove = ttMove; // Can be MOVE_NONE
        return value_from_tt(tte->value(), ply);
    }

We have changed this in latest development version. It's possible to probe TT in PV, but you have to be extremely careful to get it right.

[bob]

This is the way I always do it in my engines.

Code: Select all

Search(alpha, beta)
{

    if(CAN_CAPTURE_KING) return +INF;

    if&#40;alpha < curEval&#41; alpha--;
    if&#40;beta <= curEval&#41; beta--;

    // Standard search
    ...

    return bestScore + &#40;alpha < curEval&#41;;
&#125;

The incrementing of negative return scores corrects the mating distance when backing up the score to the root, so that mate-in-N becomes mate-in-(N+1) two ply closer to the root. But the window bounds have to be corrected with the inverse function, or horrendous blunders get played. I never correct anything that is stored or read from the TT.

I've always used what I consider the simplest method, having tried many different ideas over the years. In HashProbe() and HashStore() I correct the table score only, and I only correct if it is an EXACT score, not a bound. Essentially I correct the score on a store and store that, and I "un-correct" the score on a probe and use that for the value.

[silentshark]

and what about bruce moreland's approach to this issue? http://web.archive.org/web/200707070419 ... tehash.htm seems a reasonable way out, too