Texel recipe to fix TT draws scores

[mcostalba]

Browsing Texel (http://www.talkchess.com/forum/viewtopi ... 3d8ac4dfc9) sources I found this nicety:

Code: Select all

    uint64_t historyHash() const {
        uint64_t ret = hashKey;
        if (halfMoveClock >= 80)
            ret ^= moveCntKeys[std::min(halfMoveClock, 100)];
        return ret;
    }

For what I have understood the hash key saved / probed in TT until 80 half moves is the usual one, after that it is xored with zobrist keys that depends on the half move number.

This is the first time I saw this trick that I guess is used to avoid a draw by repeptition score to be stored in TT associated with a position.

I would like to ask from where it comes this idea and what are tests result of this idea (I guess we need long TC to test it).

Thanks
Marco

[Daniel Shawul]

Well someone here was trying to add the "game phase" into to the zobrist key which I told him is wrong. This (fifty move count) however makes sense. It is the only fundamental parameter that I i do not hash but is needed to completely describe the position.

Code: Select all

 rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1 

The last one ,full move number, should not be included otherwise we would have no tt hits at all. Which is probably the reason why most do not hash the half move clock as well. So ignoring the fifty move count in the first 80 half moves is good in this regard. So maybe he found treating the last 10 moves (in the end game) differently pays off. I never tested it.

[petero2]

Browsing Texel (http://www.talkchess.com/forum/viewtopi ... 3d8ac4dfc9) sources I found this nicety:

Code: Select all

    uint64_t historyHash() const {
        uint64_t ret = hashKey;
        if (halfMoveClock >= 80)
            ret ^= moveCntKeys[std::min(halfMoveClock, 100)];
        return ret;
    }

For what I have understood the hash key saved / probed in TT until 80 half moves is the usual one, after that it is xored with zobrist keys that depends on the half move number.

This is the first time I saw this trick that I guess is used to avoid a draw by repeptition score to be stored in TT associated with a position.

I would like to ask from where it comes this idea and what are tests result of this idea (I guess we need long TC to test it).

This is used to avoid missing draws by the fifty move rule due to hash grafting. I added it after I added hash tables to my program and some of my draw by 50 move rule tests started to fail. See lines 99-155 here: http://code.google.com/p/cuckoochess/so ... hTest.java

This was when my program was less than 2 months old, so I had not started to attempt to measure its strength yet, and I have never measured this afterwards either. I just coded something I thought was reasonable and that fixed the broken test cases. I don't know if this idea has been used before I used it.

I tested in current texel to remove that code again, and the test cases did not break. A lot has changed since I added this code and it could easily change whether or not you get a problematic hash graft during search. I guess it still helps in some positions though, but the effect on playing strength is likely too small to be measurable in a reasonable amount of time.

[rvida]

I would like to ask from where it comes this idea and what are tests result of this idea (I guess we need long TC to test it).

Thanks
Marco

Ivanhoe has something similar but with higher granularity. The code is surrounded by #ifdef and IIRC it is disabled by default. The code itself is a bit ugly.

basically, it does

key = usual_key ^ ZobristRev[pos->rule50 >> 3];

Setup of the ZobristRev array is controlled by an UCI option which specifies after how many n*8 halfmoves should the key change.

Personally, I don't recommend messing with hash keys, it effectively disables parts of the TT and wrecks the move ordering.

IMO it is better to modify the cut-off mechanism instead:

When the half-move counter is higher than some N
- don't cutoff on fail-lows at all
- on fail-high with an irreversible tt move cut-off as usual
- else continue searching and reuse the stored tt-move

This way at least the move ordering isn't destroyed.

[lucasart]

Browsing Texel (http://www.talkchess.com/forum/viewtopi ... 3d8ac4dfc9) sources I found this nicety:

Code: Select all

    uint64_t historyHash() const {
        uint64_t ret = hashKey;
        if (halfMoveClock >= 80)
            ret ^= moveCntKeys[std::min(halfMoveClock, 100)];
        return ret;
    }

For what I have understood the hash key saved / probed in TT until 80 half moves is the usual one, after that it is xored with zobrist keys that depends on the half move number.

This is the first time I saw this trick that I guess is used to avoid a draw by repeptition score to be stored in TT associated with a position.

I would like to ask from where it comes this idea and what are tests result of this idea (I guess we need long TC to test it).

Thanks
Marco

The idea of hashing the 50 move counter is quite logical, and not really new. I remember seeing it in GNU Chess 5.07, a long time ago. Using a min count of 80 half moves certainly makes sense, as it reduces the overhead.

However, I'm a bit skeptical about this idea:
* if you don't use a min depth condition that is high enough, clearly the pain outweighs the gain
* if you do use a min half move condition >= 80, then it means you'll see 50 move draws 20 plies before. But that is already 80 plies from the last pawn/capture move. So it seems to me that it's already too late, and you're already engaged into a 50 move draw whether you like it or not. The engine will show a 0 score before others, but will it be able to play the right move 80 plies before to avoid it is the real question ? Assuming your search depth doesn't often exceed 80, the answer is no in most cases.

Anyway, I'd be glad to be proven wrong, if someone has some testing results.

[bob]

Browsing Texel (http://www.talkchess.com/forum/viewtopi ... 3d8ac4dfc9) sources I found this nicety:

Code: Select all

    uint64_t historyHash() const {
        uint64_t ret = hashKey;
        if (halfMoveClock >= 80)
            ret ^= moveCntKeys[std::min(halfMoveClock, 100)];
        return ret;
    }

For what I have understood the hash key saved / probed in TT until 80 half moves is the usual one, after that it is xored with zobrist keys that depends on the half move number.

This is the first time I saw this trick that I guess is used to avoid a draw by repeptition score to be stored in TT associated with a position.

I would like to ask from where it comes this idea and what are tests result of this idea (I guess we need long TC to test it).

Thanks
Marco

It doesn't fix anything, it just hides the symptoms a bit. One will always get hash hits that have wrong scores due to draws. I invalidate the hash scores when I start to approach the 50 move limit, but that is also not a complete fix either...

[petero2]

Browsing Texel (http://www.talkchess.com/forum/viewtopi ... 3d8ac4dfc9) sources I found this nicety:

Code: Select all

    uint64_t historyHash() const {
        uint64_t ret = hashKey;
        if (halfMoveClock >= 80)
            ret ^= moveCntKeys[std::min(halfMoveClock, 100)];
        return ret;
    }

For what I have understood the hash key saved / probed in TT until 80 half moves is the usual one, after that it is xored with zobrist keys that depends on the half move number.

This is the first time I saw this trick that I guess is used to avoid a draw by repeptition score to be stored in TT associated with a position.

I would like to ask from where it comes this idea and what are tests result of this idea (I guess we need long TC to test it).

Thanks
Marco

It doesn't fix anything, it just hides the symptoms a bit. One will always get hash hits that have wrong scores due to draws. I invalidate the hash scores when I start to approach the 50 move limit, but that is also not a complete fix either...

If fixes the problem during the last 20 plies before the 50-move rule that hash grafts can cause the 50-move rule to be applied incorrectly. It doesn't in general fix draw by repetition problems though. It may "accidentally" fix some draw by repetition problems as a side effect of giving fewer hash hits.

By the way, crafty 23.4 was not able to solve this position when I tried: [d]8/7k/1R6/R7/8/7P/8/1K6 w - - 98 200
Crafty plays Ra7+ which lets black play Kg8 and claim a draw by the 50-move rule:

Code: Select all

...
Crafty v23.4 (1 cpus)

White(1): setboard 8/7k/1R6/R7/8/7P/8/1K6 w - - 98 200
White(1): go
              time surplus   0.00  time limit 30.00 (+0.00) (3:00)
              depth   time  score   variation (1)
                4->   0.00  Mat02   1. Ra7+ Kg8 2. Rb8#
              time=0.00  mat=11  n=3282  fh=100%  nps=1.0M
              extensions=184 qchecks=385 reduced=132 pruned=1K
              predicted=0  evals=15  50move=0  EGTBprobes=0  hits=0
              SMP->  splits=0  aborts=0  data=0/256  elap=0.00

mate in 2 moves.

White(1): Ra7+
              time used:   0.00
Black(1): Kg8 [pondering]
              time surplus  30.00  time limit 30.50 (+0.00) (3:03)
              depth   time  score   variation (3)
                4->   0.00   Mate   2. Rb8#
              time=0.00  mat=11  n=2119  fh=100%  nps=1.0M
              extensions=130 qchecks=171 reduced=88 pruned=1K
              predicted=0  evals=1  50move=1  EGTBprobes=0  hits=0
              SMP->  splits=0  aborts=0  data=0/256  elap=0.00
Black(1): 

Stockfish gets it right though:

Code: Select all

Stockfish 2.2.2 64bit by Tord Romstad, Marco Costalba and Joona Kiiski
uci
id name Stockfish 2.2.2 64bit
id author Tord Romstad, Marco Costalba and Joona Kiiski
...
uciok
position fen 8/7k/1R6/R7/8/7P/8/1K6 w - - 98 200
go depth 5
info depth 1 seldepth 2 score cp 9054 nodes 53 nps 1606 time 33 multipv 1 pv b1c2
info depth 2 seldepth 4 score cp 9044 nodes 283 nps 8323 time 34 multipv 1 pv h3h4 h7g8 b1a2
info depth 3 seldepth 6 score mate 3 nodes 699 nps 20558 time 34 multipv 1 pv h3h4 h7g8 a5a7 g8h8 b6b8
info depth 4 seldepth 6 score mate 3 nodes 829 nps 24382 time 34 multipv 1 pv h3h4 h7g8 a5a7 g8h8 b6b8
info depth 5 seldepth 6 score mate 3 nodes 962 nps 27485 time 35 multipv 1 pv h3h4 h7g8 a5a7 g8h8 b6b8
bestmove h3h4 ponder h7g8

[bob]

Browsing Texel (http://www.talkchess.com/forum/viewtopi ... 3d8ac4dfc9) sources I found this nicety:

Code: Select all

    uint64_t historyHash() const {
        uint64_t ret = hashKey;
        if (halfMoveClock >= 80)
            ret ^= moveCntKeys[std::min(halfMoveClock, 100)];
        return ret;
    }

For what I have understood the hash key saved / probed in TT until 80 half moves is the usual one, after that it is xored with zobrist keys that depends on the half move number.

This is the first time I saw this trick that I guess is used to avoid a draw by repeptition score to be stored in TT associated with a position.

I would like to ask from where it comes this idea and what are tests result of this idea (I guess we need long TC to test it).

Thanks
Marco

It doesn't fix anything, it just hides the symptoms a bit. One will always get hash hits that have wrong scores due to draws. I invalidate the hash scores when I start to approach the 50 move limit, but that is also not a complete fix either...

If fixes the problem during the last 20 plies before the 50-move rule that hash grafts can cause the 50-move rule to be applied incorrectly. It doesn't in general fix draw by repetition problems though. It may "accidentally" fix some draw by repetition problems as a side effect of giving fewer hash hits.

By the way, crafty 23.4 was not able to solve this position when I tried: [d]8/7k/1R6/R7/8/7P/8/1K6 w - - 98 200
Crafty plays Ra7+ which lets black play Kg8 and claim a draw by the 50-move rule:

Code: Select all

...
Crafty v23.4 (1 cpus)

White(1): setboard 8/7k/1R6/R7/8/7P/8/1K6 w - - 98 200
White(1): go
              time surplus   0.00  time limit 30.00 (+0.00) (3:00)
              depth   time  score   variation (1)
                4->   0.00  Mat02   1. Ra7+ Kg8 2. Rb8#
              time=0.00  mat=11  n=3282  fh=100%  nps=1.0M
              extensions=184 qchecks=385 reduced=132 pruned=1K
              predicted=0  evals=15  50move=0  EGTBprobes=0  hits=0
              SMP->  splits=0  aborts=0  data=0/256  elap=0.00

mate in 2 moves.

White(1): Ra7+
              time used:   0.00
Black(1): Kg8 [pondering]
              time surplus  30.00  time limit 30.50 (+0.00) (3:03)
              depth   time  score   variation (3)
                4->   0.00   Mate   2. Rb8#
              time=0.00  mat=11  n=2119  fh=100%  nps=1.0M
              extensions=130 qchecks=171 reduced=88 pruned=1K
              predicted=0  evals=1  50move=1  EGTBprobes=0  hits=0
              SMP->  splits=0  aborts=0  data=0/256  elap=0.00
Black(1): 

Stockfish gets it right though:

Code: Select all

Stockfish 2.2.2 64bit by Tord Romstad, Marco Costalba and Joona Kiiski
uci
id name Stockfish 2.2.2 64bit
id author Tord Romstad, Marco Costalba and Joona Kiiski
...
uciok
position fen 8/7k/1R6/R7/8/7P/8/1K6 w - - 98 200
go depth 5
info depth 1 seldepth 2 score cp 9054 nodes 53 nps 1606 time 33 multipv 1 pv b1c2
info depth 2 seldepth 4 score cp 9044 nodes 283 nps 8323 time 34 multipv 1 pv h3h4 h7g8 b1a2
info depth 3 seldepth 6 score mate 3 nodes 699 nps 20558 time 34 multipv 1 pv h3h4 h7g8 a5a7 g8h8 b6b8
info depth 4 seldepth 6 score mate 3 nodes 829 nps 24382 time 34 multipv 1 pv h3h4 h7g8 a5a7 g8h8 b6b8
info depth 5 seldepth 6 score mate 3 nodes 962 nps 27485 time 35 multipv 1 pv h3h4 h7g8 a5a7 g8h8 b6b8
bestmove h3h4 ponder h7g8

The last 20 plies is not the ONLY place where this is a problem... By the point you get to that "hack" you might already be committed to a drawing line that you thought was winning, with no way to back out.

It doesn't get that correct because it has never parsed the half-move counter and doesn't realize the 50-move rule is about to kick in. You can look at this line:

predicted=0 evals=1 50move=1 EGTBprobes=0 hits=0

Which shows the 50 move counter after the move was played. "1"...

[syzygy]

If fixes the problem during the last 20 plies before the 50-move rule that hash grafts can cause the 50-move rule to be applied incorrectly. It doesn't in general fix draw by repetition problems though. It may "accidentally" fix some draw by repetition problems as a side effect of giving fewer hash hits.

The last 20 plies is not the ONLY place where this is a problem... By the point you get to that "hack" you might already be committed to a drawing line that you thought was winning, with no way to back out.

Did Peter say anything else?