Mate handling with transposition tables

[Odjaahla]

I've recently implemented a transposition table into my chess program, and when playing opening and middle-game positions it seems to work fine; the evaluation and best move at each ply are identical to the ones found without the transposition table activated.

However, there is a problem in endgame positions where a mate is found beyond the search limit. I've been testing a K+R vs. K ending, which is supposed to be mate in 21 ply according to other programs. At a search depth of 16 ply my program announces mate in <some bogus number>, and first makes a couple of sensible moves forcing the opposing king towards the edge of the board as one would hope and expect. Annoyingly it then starts wandering around, still announcing mate, but making no progress and even sometimes allowing its rook to be captured.

I have been over the program umpteen times trying to fix this. I have modified the mate scores inserted into the transposition table to reflect the distance to the mate from the current node, and the scores returned when a fetched table entry allows for a fast fail-low or fail-high cutoff are also translated.

I realize that since my code seems to work nicely in all cases except the ones with deep mates and heavy amounts of transpositions, I could ignore the problem (especially if I implement end games databases), and probably get away with it in a vast majority of games. But there's this unpleasant anxiety that there's a nasty bug lurking somewhere that could affect other situations as well.

I imagine there are a few out there who's had these kinds of problems so I wonder if there's a top five list of transposition table programming mistakes one usually makes. Any thoughts that would help me eradicate this bug would be extremely appreciated.

//Rikard

[hgm]

That you can see checkmates beyond the horizon with TT is normal. It especially occurs in games like KPK and KRK, where the path to mate with optimal defense is long, and where stupid defence can greatly accelerate it. Initially stupid defence will then visit quickly won positions (against best defence), before being able to draw the conclusion that the initial defence was stupid. And then later searched better defending branches, for which the mate is beyond the horizon, will be able to reach these mate-in-N positions stored in the TT, and conclude they have a forced path to checkmate. This is usually not the optimum path, though, so the mating distance they report is usually too large.

Now a lot depends on how your search operates: does it stop at the first mate it finds, or do you search on until you are sure you have the fastest mate. (Which you can know only if the mate is within the horizon, and the horizon is not closer than you think because of prunings.) A program that does not always go for the shortest mate might in many cases postpone the mate forever. Especially 'trans-horizon' mates are very volatile; on the next search you might no longer see them, because the required TT entries happen to be overwritten, and your move ordering will be different. (It then searches the non-stupid defence first, now it knows that it exists!) So it might find a different (later) trans-horizon mate on every subsequent search, and never get closer to an optimal mate, chasing distant mirages forever.

There is no excuse for giving away a Rook, however. Unless, of course, you made it aware of the 50-move rule. Then at some point it might score every move as leading to a 50-move draw, and giving away the Rook is then just as good a move as any other, since it also leads to a draw (and perhaps even a positive score if you don't always score KK as 0.).

[Gerd Isenberg]

I guess Rikard's problem is stroring/retrieving path dependent mate-scores inside the hash-table, which values are also dependent from distance to root. Making the mate score inside the hash independent from distance to root, should solve it. Some do explict adjustment while storing/probing, some increment/decrement mate-scores while backing them up to the root.

[sje]

... some increment/decrement mate-scores while backing them up to the root.

Along with a sign inversion, this is what Symbolic does. Problem solved.

[hgm]

Problem solved.

Well, not really. It is an ad-hoc fix to a general problem, which repairs only the case of checkmate.

The recommended procedure is to give a minimal bonus to all scores below current eval (and of course pre-adapt the search window accordingly, if it has bounds below the current eval). Then it will also prevent similar problems in cases where the only move within the horizon bringing the win closer is not a checkmate. E.g. in KQKP, where the progress indicator is the approach of the winning King.

[Uri Blass]

Problem solved.

Well, not really. It is an ad-hoc fix to a general problem, which repairs only the case of checkmate.

The recommended procedure is to give a minimal bonus to all scores below current eval (and of course pre-adapt the search window accordingly, if it has bounds below the current eval). Then it will also prevent similar problems in cases where the only move within the horizon bringing the win closer is not a checkmate. E.g. in KQKP, where the progress indicator is the approach of the winning King.

I do not understand what you recommend exactly but I do not like changing the evaluation to solve these problems.

This problem is a search problem and not an evaluation problem.
I think that it may be better simply to use hash for pruning only in the last plies and in the first plies to use hash only for order of moves.

An alternative solution may be not to use hash for pruning but only for order of moves in case that the fifty move counter is higher than 80(or different number dependent on search depth) or a position repeated twice and there was no capture or pawn moves after the repetition.

Note that both cases almost never happen during games so the demage from not using hash for pruning is very small if you do it.

It is clear that Joker 1.1.07 did not use one of these idea otherwise it could avoid repetition draw against Neurosis 2.3 in round 14 of the 4th CCRL Amateur Championship Division 5.

Uri

[hgm]

The problem is a search problem. Search uses minimax, and minimax is a fundamentally flawed algorithm for deciding on a move, as it does assign the same score for moves that lead to the same end leaf (in best play). Even if the two paths leading to it have unequal length.

If you want to use the score to pick a move, the length of the path should be incorporated in the score. You can make the weight of it as small as you want, so that it becomes a decisive factor only for otherwise exactly equal scores. But it has to have non-zero weight, or you get problems like described here.

In fact, in the presence of end leaves with not 100% reliable score (i.e. every non-mate position!), there is a lot to be said from weighting the path length more heavily: A short path to a good node has the side branches searched more deeply than the final nodes in a long path, and so you are unlikely to have unpleasant surprises. It might on the average be better to go vor a slightly worse node with a high probability to get there, than to a slightly better node where it is very uncertain if you will be able to reach it.

Mate in N deserves a better evaluation than mate in N+1. Conversion in 1 deserves a better evaluation than conversion in N+1. The whole idea of tablebases is built on this.

The rep-draw problem has nothing to do with this. (I have not looked at any of the games from 4t Division 5 yet.) This is simply a matter of not using hash cutoffs in PV nodes. I still have to implement that in Joker.

[hgm]

It is clear that Joker 1.1.07 did not use one of these idea otherwise it could avoid repetition draw against Neurosis 2.3 in round 14 of the 4th CCRL Amateur Championship Division 5.

OK, I looked at the Neurosis-Joker game, and there is indeed something fishy there. From the zero score of the move 77. ..., Rh6 it is clear that Joker was aware that this move allows the opponent to draw. The previous time it played that move it still had score +2.81. It also did search a lot longer than on the previous occasion (4:01 vs 1:12, reaching 14 ply in stead of 13). It seems unconceivable, though, that none of the other moves could have provided a positive score.

I guess that there is a time-management problem here. Apparently Joker ran into a timeout before a good alternative had been searched, and so played the best move from the previous iteration. At this (13-ply) iteration Rh6 was still satisfied from the hash, as the move itself did not draw, but only the reply did. (Repetitions are checked before hash probing.) So only at 14 ply Joker becomes aware that Rh6 is no good, and the alternatives are first thought with a completely different window (making most of the hashed information useless) at 14 ply. This took so long that it did not finish the search of even a single acceptable one.

This clearly highlights some errors. Although Joker only scores the third occurrence as a draw, it should suppress hash cutoffs, and in fact hash probing, even in a second repeat. (I looked at the code, and it seems to do that only for the repeat of a tree positions, not of a game position.) Because, depending on who started the repeating, a move from a 2nd occurrence might lead to a 3rd occurrence, in which case the opponent can draw. Currently such draws are screened by the hash pruning, and even if you would only use the hash move it might not be the move that draws, and you would spend a lot of time on a deep search of it (a PV move!) before stumbling on an alternative that draws in one move.

With this modification it would be obvious from iteration 1 on that the hash move in the root is no good, and the search for an alternative would start at low depth, producing something long before any timeout could occur.

In the second place the ID procedure should be more 'defensive': if the best score suddenly drops dramatically, it should not look for an alternative move at the depth where this occured, but switch back to a lower depth to first quickly gather some information about the other moves. This might be a good idea for IID as well.

Another idea that might be useful in protection against rep-draws: In a situation where the engine ahead has difficulty making progress, it is likely that it will plan to move to positions that have not occurred in the game before, but from which the opponent can draw in a single move to a three-fold repeat. Such positions could still be hashed from a time were the opponent's move was not a rep-draw. This would then also be discovered rather late. This could be prevented by adding to your repeat table all those positions with the side that is behind to move, that could be parents from positions from the game history.