Hashtable and 50 move rule draws

[Stan Arts]

Nemeton's hashtable does a good job of hiding 50 move rule draws because of transpositions. Often it will spot it at the root only 2-4 moves prior. In practise this probably doesn't cost any Elo but it's very ugly behaviour.

I've tried several things to combat this.
Don't take the hash cutoff if the depth of the entry comes close to or crosses the 50 move rule.
Don't cutoff if the fifty move rule counter of the current node approaches a certain margin. (Say for example 70, 30 ply away from the draw.) And variations.
What this does is cause the program to stall as the 50 move rule approaches. Searching 2 ply less deep every move but effectively still being blind to it as it comes up one ply short of seeing the draw at the root.
Note: Nemeton stores 3 rep and 50 move rule draw scored nodes with 0 depth in the hashtable which can never be used for a cutoff later.

I can think of some drastic measures like not cutting off on exact scores or reduce the depth of entries from previous searches. In both cases the cure seems worse than the disease. (Though the latter I did in my previous engine Neurosis as it did not have aging bits. And even there the difference in spotting the draw is typically only one or two moves faster.)
I'm thinking of scaling hashtable cutoff scores to 0 when approaching the 50 move rule draw but this I think has it's own drawbacks.

How do you handle this?

[hgm]

In general it is a good thing if engines do not see the 50-move draw coming, as it would only make them do silly (and often losing) sacrifices when they do. Engines should be designed to make progress without '50-move blackmail'.

You could try to taper the evaluation towards zero after 25 reversible plies. It should be difficult for the hash table to hide this for 25 moves, and at some point the position after captures or Pawn pushes might start to look more attractive than just meddling on with the current material and Pawn structure.

I might do this in my Xiangqi engine, which is generally stupid (because I know little about Xiangqi). Lately I saw that draw a game where it was very much ahead, because it could totally paralize the opponent except for a single Pawn. It could have easily gained that Pawn, but then the opponent would be able to escape from his cramped position, which would gain him more in mobility and centralization than the Pawn was worth. But as it was the opponent could just kept moving its Pawn back and forth. The Pawn was very valuable in this position for avoiding zugzwang, and of course the evaluation would not recognize that.

If the already existing material advantage of Rook vs Horse would have started being scaled down, it would have been driven to capture the Pawn just to undo that scaling, no matter how low it evaluated the intrinsic value of the Pawn. (The Pawn had already reached tha last rank, and thus wasn;t worh much.)

[Stan Arts]

Thanks. That's a good point, that it might be better to not be too aware.
Indeed sacrifices to barely equal positions can quickly lead to losing positions.

After some thought and a new try though it seems the fifty move counter + depth of entry < 100 was probably just a tad too close to a hundred. That leads to problems with extentions and transpositions in transpositions.. So just setting that to 90 now seems to do the trick. It essentially disables all transpositions near the draw and now finds the draws easily 6-8 moves in advance which I can live with. It doesn't perform very well depth wise when there is no way to break the draw but at that point that also doesn't matter.

However the evaluation scaling does seem interesting and something to experiment with as I haven't before. One would imagine it would give more of an urge to look for progress though I don't yet know what the hashtable sideeffects will be.
What about your delayed loss bonus? Do you use that in KingSlayer or any of your variant engines currently?

[petero2]

Nemeton's hashtable does a good job of hiding 50 move rule draws because of transpositions. Often it will spot it at the root only 2-4 moves prior. In practise this probably doesn't cost any Elo but it's very ugly behaviour.

How do you handle this?

In texel I include the half-move clock in the hash key if the half-move clock is >= 80. That way I can still get transposition cutoffs but I don't get "grafting" hits that would fool the 50-move draw rule.

I also have special rules to deal with how I scale down my evaluation score when the half-move clock is large and to deal with my non-standard tablebase probing code. The function that computes the hash signature looks like this:

Code: Select all

inline U64
Position::historyHash() const {
    U64 ret = hashKey; // Incremental zobrist hash
    if &#40;nPieces&#40;) <= TBProbeData&#58;&#58;maxPieces&#41; &#123;
        ret ^= moveCntKeys&#91;std&#58;&#58;min&#40;halfMoveClock, 100&#41;&#93;;
    &#125; else if &#40;halfMoveClock >= 40&#41; &#123;
        if &#40;halfMoveClock < 80&#41;
            ret ^= moveCntKeys&#91;halfMoveClock / 10&#93;;
        else
            ret ^= moveCntKeys&#91;std&#58;&#58;min&#40;halfMoveClock, 100&#41;&#93;;
    &#125;
    return ret;
&#125;

The moveCntKeys array contains pseudo-random 64-bit values.

[Stan Arts]

Thanks. Storing the halfmove counter in the entry is very clever. Because you only store it at >=80 I suppose you only need 5 bits, 4 if you could sacrifice some accuracy.

Do you get any negative hashtable effects from the evaluation scaling or does the counter come into play there too?

[syzygy]

Thanks. Storing the halfmove counter in the entry is very clever. Because you only store it at >=80 I suppose you only need 5 bits, 4 if you could sacrifice some accuracy.

He does not store in the entry, but he hashes it into the hash key.