Transposition tables and mate scores

[jwes]

I was thinking about handling of mate scores in the TT, and it seems that there are several things that should be handled differently (besides correcting the score for the depth).
1. Mate scores should cause cutoffs even if the depth is not sufficient, e.g. a position that has a lower bound of mate in 7 ply stored with a depth of 5 ply should cause a cutoff if the value is >= beta even if the search depth is greater than 5.
2. Mates that have been searched deeply enough should be treated like egtb mates and never searched more deeply, e.g. a position that has a lower bound of mate in 7 ply searched with a depth of 7 ply should be stored as an exact value and marked so it will not be searched again.
3. TT entries with a mate score from the current search should not be replaced in the TT with non-mate scores if there is a choice.

[hgm]

(3) is absolutely fatal, even when applied only to checkmated-in-0 scores. I accidentally had this in my first uMax that supported TT, where I bumped the depth of a checkmated position to 99 to terminate IID in that node, and that depth got stored in the TT. The whole TT became quickly poisoned with mate scores.

Note that a (deep) forced mate in a side branch doesn't mean you get mated in the root. So the side branch monopolizes the TT.

[jwes]

(3) is absolutely fatal, even when applied only to checkmated-in-0 scores. I accidentally had this in my first uMax that supported TT, where I bumped the depth of a checkmated position to 99 to terminate IID in that node, and that depth got stored in the TT. The whole TT became quickly poisoned with mate scores.

Note that a (deep) forced mate in a side branch doesn't mean you get mated in the root. So the side branch monopolizes the TT.

That is why I put in the qualifiers "current search" and "if there is a choice".
I was thinking of a hash scheme like crafty's, where entries have an age. When replacing a hash entry in a bucket, if all the entries in that bucket have the current age, don't replace an entry with a mate score unless all the entries have a mate score. I don't know how this would work in the general case, but in the specific case of KBNk we were discussing in another thread, you want the TT to be "poisoned" with mate scores. Another idea is, when a mate score is retrieved from the hash table, set the depth to the current search depth if that is greater than the stored depth. This might keep the more useful mate scores in the TT while allowing other mate scores to be overwritten.

[hgm]

A bad move close to the root that would get you mated after many moves can easily monopolize the entire TT even within the current search, at long TC. I found it is quite dangerous to fudge the stored depth if it is also used for replacement decisions. The recent discussion on how to store nul-move cutoffs also points in this direction. Ideally, the quantity used to decide about replacement should represent the amount of search effort needed to regenerate the entry. Keeping an entry that was cheap to generate just because it can satisfy high-depth probes seems a losing deal. Deep probes are not frequent, and having the entry wait for them, occupying a TT slot, is not good use of the slot. You could have gotten more hits on more expensive entries if it had been used (perhaps repeatedly) to store entries that were more expensive to generate and valid to lower depth.

The other scheme you propose (fudging the score on probing) does not have that problem, and works much better.

[wgarvin]

A bad move close to the root that would get you mated after many moves can easily monopolize the entire TT even within the current search, at long TC. I found it is quite dangerous to fudge the stored depth if it is also used for replacement decisions. The recent discussion on how to store nul-move cutoffs also points in this direction. Ideally, the quantity used to decide about replacement should represent the amount of search effort needed to regenerate the entry. Keeping an entry that was cheap to generate just because it can satisfy high-depth probes seems a losing deal. Deep probes are not frequent, and having the entry wait for them, occupying a TT slot, is not good use of the slot. You could have gotten more hits on more expensive entries if it had been used (perhaps repeatedly) to store entries that were more expensive to generate and valid to lower depth.

The other scheme you propose (fudging the score on probing) does not have that problem, and works much better.

If you have 12 or more available bits in your TT entry, how about storing a fixed-point rounded estimate of the node count of the subtree in there, and using it for replacement decisions (instead of depth)?

[hgm]

If you have 12 or more available bits in your TT entry, how about storing a fixed-point rounded estimate of the node count of the subtree in there, and using it for replacement decisions (instead of depth)?

The problem is that such an estimate is not easy to come by. Actually counting nodes in the sub-tree might give highly distorted numbers, because of hash hits. You could be doing a very deep search, which you happened to have searched before as a transposition (the first move of which was later refuted by another reply), and get an immediate TT cutof after one node.

[jwes]

If you have 12 or more available bits in your TT entry, how about storing a fixed-point rounded estimate of the node count of the subtree in there, and using it for replacement decisions (instead of depth)?

The problem is that such an estimate is not easy to come by. Actually counting nodes in the sub-tree might give highly distorted numbers, because of hash hits. You could be doing a very deep search, which you happened to have searched before as a transposition (the first move of which was later refuted by another reply), and get an immediate TT cutof after one node.

You would have to add the node count from the tt entry that gave the cutoff to your node count. This may or may not help in the general case but in the case of mate scores could hurt more than help as these scores may well have low node counts.

[wgarvin]

Suppose you have a "fake nodes count" for the purpose of computing these subtree costs (and just not use it for reporting NPS etc.) This counter would just be used to compute estimated replacement costs for a node, and a fixed-point approximation of this would be stored in the TT entry. Its just like a normal node counter, except that we can add whatever we want to it on a hash hit, to represent the "cost to recompute" that node.

If you have 12 or more available bits in your TT entry, how about storing a fixed-point rounded estimate of the node count of the subtree in there, and using it for replacement decisions (instead of depth)?

The problem is that such an estimate is not easy to come by. Actually counting nodes in the sub-tree might give highly distorted numbers, because of hash hits. You could be doing a very deep search, which you happened to have searched before as a transposition (the first move of which was later refuted by another reply), and get an immediate TT cutof after one node.

You would have to add the node count from the tt entry that gave the cutoff to your node count. This may or may not help in the general case but in the case of mate scores could hurt more than help as these scores may well have low node counts.

Adding in the stored cost from the TT entry is a bit fishy because it attributes a "cost" to recompute the node which you didn't actually pay to compute it in the first place. It kind of assumes that NONE of the hash hits in child nodes would occur if you did a future re-computation of the parent node.

On the other hand, not adding them in is a bit fishy too because it is kind of like assuming that ALL of the hash hits in child nodes would occur if you did a future re-computation of the parent node.

A more reasonable cost estimate is probably somewhere between these two values. With the caveat that hash hits closer to the root of the subtree will save you more work than ones near the leaves.

Maybe it would be reasonable, on a hash hit, to add half of the stored node count from that entry to the fake nodes count for the subtree? Or some fixed percentage that is related to your current average branching factor and/or your current hash table hit rate?