Problem with Transposition Table and Repitition-Draw

[OliverBr]

I found the following "bug" in my program:

From a the starting position 4R3/2p2p2/3q1pk1/1pN2bp1/1Q1P3p/2P2P2/2r3PP/6K1 w - - 0 32

my programm calculates correctly (?) the same Hashkey for the position after the two following move sequences.

A) e8-g8 g6-h5 g8-h8 h5-g6 d4-d5 d6xd5
B) d4-d5 d6xd5 e8-g8 g6-h5 g8-h8 h5-g6

But, they are not exactly the same, because the next move h8-g8 yields 0 (repition-draw) just for B), not to talk about some 50move rule..

One solution would be to "destroy" the hashkey with a capture-move "d6xd5" (=include the fifty-move value in the key) but this would be too much, because all other moves than h8-g8 yield exactly the same score for A) and B).

How is this problem solved in other chess programms?

[Edsel Apostol]

Hi Oliver,

In my program, I call the three fold repetition and fifty move rule procedure before the call to the transposition table. This way, correct draw score will be returned instead of the score from the transposition table if in case the position is a draw.

[OliverBr]

Hi Oliver,

In my program, I call the three fold repetition and fifty move rule procedure before the call to the transposition table. This way, correct draw score will be returned instead of the score from the transposition table if in case the position is a draw.

Of course, I do it as well... but this doesn't solve my problem. The Drawscore (0) could be "transported" to parent nodes. There you have no information whether it was a drawscore or not.
It could be saved in the transposition table. If the transposition table does NOT contain the 50 move counter, this 0-score can be pulled out of the TT on a complete different node even there is no 0-score at all.
Here it doesn't help at all that you call the repitition check before the TT.

So if I want to do it in a clean way, the TT-Key must contain the exact fifty-move counter, but this -one the other hand- means a lot of correct transpositions will be lost, because most scores are equal independent of the fifty-move counter.

How is this solved in other engines?

[hgm]

This is an unsolved problem. Using the complete game state (including 50-move counter, and path from root) as TT key would be completely counterproductive, as it enormously reduces hit rate.

In Joker I try to keep the information in the hash tabel 'uncontaminated' by path-dependence, by making sure that scores influenced by rep-draws (or 50-move if Joker would have used that) are not stored, and the nodes of which the scores are affected by such nodes by propagation are also not stored, unless the repetition can be forced. So all positions are stored with scores that they would have if this was the first time they occurred (with still 50 moves to go), and only the positions occurring in the game history were the ones that occurred before. (So not the ones on the path from the root to the position in question.)

But even that does not solve all problems. In particular, positions get stored in the TT when they are encountered for the first time, with non-draw scores. But if the game then gets in a repetitive stage, they become in reality drawns positions. Now you could correct this by removing new game positions from the TT, to make sure they are re-evaluated on a new visit with the knowledge that they occurred before, but this re-evaluation would also have to be propagated through the tree, for which I have not found a suitable algorithm yet. So a position that never occurred before in the game, can suddenly become a draw because the side wanting the draw can do a move from there which reaches a position that was just revisited at game level. Only removing the latter postion from the TT won't protect you from missing that, as long as the search is prevented from reaching the drawn position by a TT cutoff on the position leading to it. Clearing the TT between moves would solve it, but is again counterproductive.

So as all known cures are worse than the disease, all existing engines try to live with this problem as good as they can. To make life more bearable it helps if you don't allow TT cutoffs in the PV, and count a first recurrence already as a draw.

[OliverBr]

I was afraid this hasn't been solved yet... And things go even worse:

With the starting position:

8/k7/3R2p1/p1p1p2p/q6P/6r1/6r1/7K w - - 0 8

A) d6-d7 a7-a6 d7-a7 a6-b6 a7-b7 b6-a6 b7-b6 a6-a7
B) d6-a6 a7-b7 a6-b6 b7-a8 b6-a6 a8-b8 a6-b6 b8-a7

Both bring the exact the same position *including* fifty move score. Exact the same? No, not really.

The next move b6-a6

after B) returns correctly DRAW (0) because a repetition occurs.
after A) brings a complete new position. No DRAW SCORE.

[hgm]

Yes, it is a very nasty problem. The repetition draws even more so than the 50-move rule, as it is not really harmful (and argually even better) to ignore the latter anyway.

But so far simply ignoring the path-dependence problem seems by far the best solution so far.