Mate scores in TT (a new?... approach)

[MOBMAT]

I'm not sure if if "found" this solution somewhere, or came up with it on my own, so please, if anyone has seen this done before, mention them to give them credit.

Like so many before me, I struggled with trying to figure out how to store/retrieve mate scores in the TT. There are so many solutions out there and trying to understand and test them is a royal pain.

Here is the solution I use which requires NO "fixing" of values in/out of the TT.

My implementation of the game tree uses the copy/make method.

I have a Position class has all the data needed to represent the state of a position. This includes the bitboards, a serialized board, side to move, etc. To that list of data I've added an additional counter that I've named "Mate". At the root node, I initialize this variable to a value that represents a Mate in zero. I happen to use 31000. This value is a lot larger than any Eval value I would ever use, even when taking into account a mate in 100 search.

As the search goes down the tree, the Position is cloned prior to each move. when the position is copied, the "Mate" value in the cloned position is decremented by one. So, 31000 at the root, then 30999 at ply 1, 30998 at ply two, etc.

At the bottom of the code for each node (A/B search code), I check for checkmate/stalemate. If checkmate is found, I return the negative of the current "Mate" value (no additional +/- Ply needed).

at some point, the Mate value might become the score that needs to go into the TT. Well, the usual way to store the mate value is to check if the score exceeds the worse case mate, such as mate in 100 (or whatever your search limit is), and the score is modified by adding/subtracting the current Ply number (depending on a wining/losing condition). Well, "Mate" already has that calculation built in, so when storing it in the TT, nothing needs to be done.

The same goes for retrieving the mate score from the TT. The stored "Mate" value requires no modification and represents the "mate/mated in" score from the stored position.

So far, I haven't found a problem with this solution.

I hope this makes sense, since my senses are running on fumes (haha) as it is well past 1am here. I just wanted to add my own 2 cents! Ok, enough.

Enjoy

[hgm]

It seems to me that you are just incrementally tracking the value of MATE - ply. (Which is more expensive that calculating MATE - ply 'on the fly' when you need it, as you would not need it very often: nodes where you are checkmated are very rare in the tree.)

I don't see how this could work without adapting the score that you store in the TT. If you find a checkmate position 3 ply deep in the tree, you would assign it score 31000-3 = 30997. That would be the score you want in the root, so that is OK. But if that would go into the TT unmodified, and you would get a hit on it later 5 ply deep in the tree, the (sub-optimal) move in the tree that leads to mate in 5 now would also get score 30997 in the root, which is wrong. Also, when you keep the TT for the next search, a full move later, you would still find it with a mate-in-3 score, while in fact it is now mate in 1.

This should not work at all.

[MOBMAT]

H.G.,
I didn't think about the ramifications of finding the same position at different depths.
Thanks for clearing that up.

[hgm]

Well, this is the only reason why people covert distance mate-to-root into the distance mate-to-position (by subtracting 'ply') when storing it in the TT. So that the can correctly convert it back to mate-to-root when they hit it in at a differen level of the tree.

[Ras]

Another option is not to care about the mate distance and just put it into the TT. For PV nodes, I don't return TT values, but use them for move sorting only, which also escapes the "truncated PV" issue. The additional effort is neglectable because there are relatively few PV nodes.

The worst thing that might happen is that a non-PV branch could offer a quicker or longer mate, depending on whether the engine is winning or losing, and that doesn't change the outcome.

During normal game, when no side has a forced mate, positions that indicate mate for either side will fall prey to alpha-beta-pruning anyway, no matter what the mate depth is.