search or transposition table bug?

mar · Post by **mar** » Tue Nov 30, 2010 2:27 pm

Hi all, I have a strange problem with my chess engine. I'm pretty sure I've a bug somewhere, either in the search or in the transposition table code. I've no clue so I wanted to ask if someone ever ran into a similar problem. I've a position (b3r1k1/2P4p/p2K2p1/8/p2N4/R3Pp2/8/8 w - - 0 52). When I let my engine analyze it, it chooses to play Kd7 until at depth 14 it realises it's a losing move. The strange thing is that when I reduce TT size to 1 meg (default=4 megs) it sees that Kd7 is losing at depth 12 (and chooses Rc3). So there's obviously something very wrong. However I went through the search/tt code a few times and didn't find anything... I'm pretty sure my movegen is ok as well as hash updates (move/undo move) (lots of asserts in debug version). My evalfn is symmetric. Same behavior if I turn nullmove/lmr off. Same if I clamp search result to oldalpha, beta. Any ideas? Many thanks.
PS the 1-meg version scored 65% against a 128-meg TT version in 40 test games (1 game in 1 minute) so that's quite a difference...

Sven · Post by **Sven** » Tue Nov 30, 2010 3:08 pm

Can you show the PV of your engine in the default version when it thinks that Kd7 wins prior to depth 14? Maybe this includes some hint.

If the PV is very short due to TT access then you may choose to extend the PV from TT, at least for debugging.

Using less memory for TT means that your table gets filled more quickly, so you are overwriting old entries more frequently. If this leads to better play then I could imagine that you are storing some wrong information in certain cases but you kick it out earlier so your search suffers less from it. I don't know whether this is realistic, though, it is just an idea.

Maybe you want to cross-check again the way how you store and retrieve your TT entries.

Sven

mar · Post by **mar** » Tue Nov 30, 2010 3:34 pm

Thanks for reply

the PV prior to depth 14 is
d6d7 g8f7 d4f3 a8f3 a3a4 e8e7 d7d8 e7e8 d8d7, score cp 0
(no change since depth 9)
depth 14:
d6d7 e8f8 c7c8q f8c8 d4f3 c8c5 f3d4 c5c4 d7e6 a8b7 e6e5 c4c5 e5d6 c5a5 a3c3, score cp -255

1-meg version:
depth 9-11
d6d7 g8f7 d4f3 a8f3 a3a4 e8e7 d7d8 e7e8 d8d7, score cp 0
depth 12:
d6d7 e8f8 a3a4 f3f2 a4a1 a8g2 d4e6 g2h3 a1f1 h3f1 e6f8 f1b5 d7e7, score cp -240

I don't know if this reveals something (except score 0 due to repetition; I consider 1-fold repetition as a draw).
I get the same PVs as the 1-meg version (for depth 9-11) even if I disable TT stores (=> no TT).

OliverUwira · Post by **OliverUwira** » Tue Nov 30, 2010 5:22 pm

mar wrote:Thanks for reply

the PV prior to depth 14 is
d6d7 g8f7 d4f3 a8f3 a3a4 e8e7 d7d8 e7e8 d8d7, score cp 0
(no change since depth 9)
depth 14:
d6d7 e8f8 c7c8q f8c8 d4f3 c8c5 f3d4 c5c4 d7e6 a8b7 e6e5 c4c5 e5d6 c5a5 a3c3, score cp -255

1-meg version:
depth 9-11
d6d7 g8f7 d4f3 a8f3 a3a4 e8e7 d7d8 e7e8 d8d7, score cp 0
depth 12:
d6d7 e8f8 a3a4 f3f2 a4a1 a8g2 d4e6 g2h3 a1f1 h3f1 e6f8 f1b5 d7e7, score cp -240

I don't know if this reveals something (except score 0 due to repetition; I consider 1-fold repetition as a draw).
I get the same PVs as the 1-meg version (for depth 9-11) even if I disable TT stores (=> no TT).

Do you store the draw score into the TT before returning? A scenario could be that when you are at iteration depth 11, the repetition gets stored at depth 9 in the tree with 2 ply yet to go. If your engine now reaches the position at iteration depth 12, it could hit that hash entry at depth 11 in the tree and have an exact TT hit that could cause it to miss the winning line due to an early return.

At iteration depth 14, that would no longer be an issue, because the draft of the hash entry is not deep enough anymore.

EDIT: With the smaller TT or the TT turned off, that repetition entry could have been overwritten before doing any harm, or not be there, respectively.

mar · Post by **mar** » Tue Nov 30, 2010 5:45 pm

OliverUwira wrote:
mar wrote:Thanks for reply

the PV prior to depth 14 is
d6d7 g8f7 d4f3 a8f3 a3a4 e8e7 d7d8 e7e8 d8d7, score cp 0
(no change since depth 9)
depth 14:
d6d7 e8f8 c7c8q f8c8 d4f3 c8c5 f3d4 c5c4 d7e6 a8b7 e6e5 c4c5 e5d6 c5a5 a3c3, score cp -255

1-meg version:
depth 9-11
d6d7 g8f7 d4f3 a8f3 a3a4 e8e7 d7d8 e7e8 d8d7, score cp 0
depth 12:
d6d7 e8f8 a3a4 f3f2 a4a1 a8g2 d4e6 g2h3 a1f1 h3f1 e6f8 f1b5 d7e7, score cp -240

I don't know if this reveals something (except score 0 due to repetition; I consider 1-fold repetition as a draw).
I get the same PVs as the 1-meg version (for depth 9-11) even if I disable TT stores (=> no TT).
Do you store the draw score into the TT before returning? A scenario could be that when you are at iteration depth 11, the repetition gets stored at depth 9 in the tree with 2 ply yet to go. If your engine now reaches the position at iteration depth 12, it could hit that hash entry at depth 11 in the tree and have an exact TT hit that could cause it to miss the winning line due to an early return.

At iteration depth 14, that would no longer be an issue, because the draft of the hash entry is not deep enough anymore.

EDIT: With the smaller TT or the TT turned off, that repetition entry could have been overwritten before doing any harm, or not be there, respectively.

No I do the draw test before I even probe the TT. When I detect a draw I simply return 0. But of course it eventually gets stored in the parent node anyway. I wonder if other engines use some magic to handle draws by repetition (esp. when using TTs)?

The strange thing is that even if I disable TT cutoffs in PV nodes it still behaves unexpectedly.

Maybe disabling rep detection during search and only force 0 scores at the root? But that seems like a hack to me... I sure want to prune subtrees if I run into a repetition

EDIT: maybe I'm wrong but are you suggesting to use a special value for draw by repetition which I shouldn't use for TT cutoffs or that I shouldn't store anything into the TT when I get draw by repetition (not even in parent nodes)?

OliverUwira · Post by **OliverUwira** » Tue Nov 30, 2010 7:00 pm

mar wrote: No I do the draw test before I even probe the TT. When I detect a draw I simply return 0. But of course it eventually gets stored in the parent node anyway. I wonder if other engines use some magic to handle draws by repetition (esp. when using TTs)?

The strange thing is that even if I disable TT cutoffs in PV nodes it still behaves unexpectedly.

Maybe disabling rep detection during search and only force 0 scores at the root? But that seems like a hack to me... I sure want to prune subtrees if I run into a repetition

EDIT: maybe I'm wrong but are you suggesting to use a special value for draw by repetition which I shouldn't use for TT cutoffs or that I shouldn't store anything into the TT when I get draw by repetition (not even in parent nodes)?

I do the same as you. I don't store the position where the repetition is detected and I also judge a twofold repetition as a draw.

Code: Select all

if&#40;engine->mode.nodes_restriction && &#40;engine->mode.nodes_restriction == ptree->info.nodes&#41;)
	AbortSearch&#40;engine, ply&#41;;
	
if&#40;&#40;ptree->info.nodes & 0x000ffff&#41; == 0&#41;
	CheckAbortSearch&#40;engine, ply&#41;;

InitGenerator&#40;pstate, ptree->PathNode&#91;ply-1&#93;.MoveGenState.end, &&#40;engine->pos&#41;);

if&#40;IsDrawByRule&#40;pstate->pos&#41;)
	return 0;	

if&#40;dist == 0&#41; 
	return QuiescenceSearch&#40;alpha, beta, ply, engine, 0&#41;;

ttres = TTableQuery&#40;engine, &alpha, beta, ply, dist&#41;;

My engine produces this:

Code: Select all

FEN&#58; b3r1k1/2P4p/p2K2p1/8/p2N4/R3Pp2/8/8 w - - 0 52 

Kurt 0.9.3 x64&#58;
   1	00&#58;00	          40	1	-2,18	Ra3xa4
   2	00&#58;00	         388	1	-0,37	Kd6d7 Ba8c6+
   3	00&#58;00	         494	1	-0,37	Kd6d7 Ba8c6+ Kd7xc6
   4	00&#58;00	       1.937	1	+0,05	Kd6d7 Kg8f7 c7c8Q Re8xc8
   5	00&#58;00	       2.714	1	+0,05	Kd6d7 Kg8f7 c7c8Q Re8xc8 Kd7xc8
   6	00&#58;00	       4.337	1	-0,11	Kd6d7 Kg8f7 c7c8Q Re8xc8 Kd7xc8 f3f2
   7	00&#58;00	       7.608	1	-0,23	Kd6d7 Kg8f7 c7c8Q Re8xc8 Kd7xc8 f3f2 Ra3a1
   8	00&#58;00	      17.321	1.154.733	-0,63	Kd6d7 Kg8f7 c7c8Q Re8xc8 Kd7xc8 f3f2 Ra3a1 Ba8e4
   9	00&#58;00	      52.688	849.806	-1,83	Kd6d7 Kg8f7 e3e4 Ba8xe4 c7c8Q Re8xc8 Kd7xc8
  10	00&#58;00	      89.321	960.441	-2,01	Kd6d7 Kg8f7 e3e4 Ba8xe4 c7c8Q Re8xc8 Kd7xc8 f3f2 Ra3a1 h7h5
  11	00&#58;00	     234.412	941.414	-2,20	Kd6d7 Kg8f7 Nd4e6 Re8e7+ Kd7d8 Re7xe6 c7c8Q Re6e8+ Kd8d7 Re8xc8 Kd7xc8
  12	00&#58;00	     352.088	941.412	-1,58	Kd6d7 Kg8f7 Nd4xf3 Ba8xf3 Ra3xa4 Re8e4 c7c8Q Re4xa4 Qc8e8+ Kf7g7 Qe8e7+ Kg7h6
  13	00&#58;01	   1.140.730	974.983	-2,53	Kd6d7 Re8f8 Ra3xa4 Ba8b7 Ra4a1 f3f2 Ra1f1 Bb7c8+ Kd7d6 Bc8h3 Nd4e6 Bh3xf1 Ne6xf8
  14	00&#58;01	   1.501.807	982.858	-2,65	Kd6d7 Re8f8 Ra3xa4 Ba8b7 Ra4a1 f3f2 Ra1f1 Bb7c8+ Kd7d6 Bc8h3 Nd4e6 Bh3xf1 Ne6xf8 Bf1c4

Since your PV contains the draw from depth 9 onwards, the drawscore must have entered the TT as an EXACT entry, which could then result in the same effect.

This is something which can't comfortably be prevented. Repetition and 50-move draws in the TT can be tricky, but since the worst that can happen is that the better line is discovered later, most programmers seem to put up with that inconvenience. After all, it is quite rare for such a draw to enter the root PV.

What I'm wondering about is how the draw became the mainline for your engine in the first place. I've checked with Rybka 3 and Stockfish 1.8 and they also have a plus score for Kd7 during the first plies.

bob · Post by **bob** » Tue Nov 30, 2010 7:29 pm

mar wrote:Hi all, I have a strange problem with my chess engine. I'm pretty sure I've a bug somewhere, either in the search or in the transposition table code. I've no clue so I wanted to ask if someone ever ran into a similar problem. I've a position (b3r1k1/2P4p/p2K2p1/8/p2N4/R3Pp2/8/8 w - - 0 52). When I let my engine analyze it, it chooses to play Kd7 until at depth 14 it realises it's a losing move. The strange thing is that when I reduce TT size to 1 meg (default=4 megs) it sees that Kd7 is losing at depth 12 (and chooses Rc3). So there's obviously something very wrong. However I went through the search/tt code a few times and didn't find anything... I'm pretty sure my movegen is ok as well as hash updates (move/undo move) (lots of asserts in debug version). My evalfn is symmetric. Same behavior if I turn nullmove/lmr off. Same if I clamp search result to oldalpha, beta. Any ideas? Many thanks.
PS the 1-meg version scored 65% against a 128-meg TT version in 40 test games (1 game in 1 minute) so that's quite a difference...

That is not unusual. Fine #70 will almost certainly exhibit this behaviour and your program will find the correct move/score at different depths depending on hash size.

mar · Post by **mar** » Wed Dec 01, 2010 11:04 am

OliverUwira wrote:
mar wrote: No I do the draw test before I even probe the TT. When I detect a draw I simply return 0. But of course it eventually gets stored in the parent node anyway. I wonder if other engines use some magic to handle draws by repetition (esp. when using TTs)?

The strange thing is that even if I disable TT cutoffs in PV nodes it still behaves unexpectedly.

Maybe disabling rep detection during search and only force 0 scores at the root? But that seems like a hack to me... I sure want to prune subtrees if I run into a repetition

EDIT: maybe I'm wrong but are you suggesting to use a special value for draw by repetition which I shouldn't use for TT cutoffs or that I shouldn't store anything into the TT when I get draw by repetition (not even in parent nodes)?
I do the same as you. I don't store the position where the repetition is detected and I also judge a twofold repetition as a draw.
Code: Select all
if&#40;engine->mode.nodes_restriction && &#40;engine->mode.nodes_restriction == ptree->info.nodes&#41;)
	AbortSearch&#40;engine, ply&#41;;
	
if&#40;&#40;ptree->info.nodes & 0x000ffff&#41; == 0&#41;
	CheckAbortSearch&#40;engine, ply&#41;;

InitGenerator&#40;pstate, ptree->PathNode&#91;ply-1&#93;.MoveGenState.end, &&#40;engine->pos&#41;);

if&#40;IsDrawByRule&#40;pstate->pos&#41;)
	return 0;	

if&#40;dist == 0&#41; 
	return QuiescenceSearch&#40;alpha, beta, ply, engine, 0&#41;;

ttres = TTableQuery&#40;engine, &alpha, beta, ply, dist&#41;;
My engine produces this:
Code: Select all
FEN&#58; b3r1k1/2P4p/p2K2p1/8/p2N4/R3Pp2/8/8 w - - 0 52 

Kurt 0.9.3 x64&#58;
   1	00&#58;00	          40	1	-2,18	Ra3xa4
   2	00&#58;00	         388	1	-0,37	Kd6d7 Ba8c6+
   3	00&#58;00	         494	1	-0,37	Kd6d7 Ba8c6+ Kd7xc6
   4	00&#58;00	       1.937	1	+0,05	Kd6d7 Kg8f7 c7c8Q Re8xc8
   5	00&#58;00	       2.714	1	+0,05	Kd6d7 Kg8f7 c7c8Q Re8xc8 Kd7xc8
   6	00&#58;00	       4.337	1	-0,11	Kd6d7 Kg8f7 c7c8Q Re8xc8 Kd7xc8 f3f2
   7	00&#58;00	       7.608	1	-0,23	Kd6d7 Kg8f7 c7c8Q Re8xc8 Kd7xc8 f3f2 Ra3a1
   8	00&#58;00	      17.321	1.154.733	-0,63	Kd6d7 Kg8f7 c7c8Q Re8xc8 Kd7xc8 f3f2 Ra3a1 Ba8e4
   9	00&#58;00	      52.688	849.806	-1,83	Kd6d7 Kg8f7 e3e4 Ba8xe4 c7c8Q Re8xc8 Kd7xc8
  10	00&#58;00	      89.321	960.441	-2,01	Kd6d7 Kg8f7 e3e4 Ba8xe4 c7c8Q Re8xc8 Kd7xc8 f3f2 Ra3a1 h7h5
  11	00&#58;00	     234.412	941.414	-2,20	Kd6d7 Kg8f7 Nd4e6 Re8e7+ Kd7d8 Re7xe6 c7c8Q Re6e8+ Kd8d7 Re8xc8 Kd7xc8
  12	00&#58;00	     352.088	941.412	-1,58	Kd6d7 Kg8f7 Nd4xf3 Ba8xf3 Ra3xa4 Re8e4 c7c8Q Re4xa4 Qc8e8+ Kf7g7 Qe8e7+ Kg7h6
  13	00&#58;01	   1.140.730	974.983	-2,53	Kd6d7 Re8f8 Ra3xa4 Ba8b7 Ra4a1 f3f2 Ra1f1 Bb7c8+ Kd7d6 Bc8h3 Nd4e6 Bh3xf1 Ne6xf8
  14	00&#58;01	   1.501.807	982.858	-2,65	Kd6d7 Re8f8 Ra3xa4 Ba8b7 Ra4a1 f3f2 Ra1f1 Bb7c8+ Kd7d6 Bc8h3 Nd4e6 Bh3xf1 Ne6xf8 Bf1c4
Since your PV contains the draw from depth 9 onwards, the drawscore must have entered the TT as an EXACT entry, which could then result in the same effect.

This is something which can't comfortably be prevented. Repetition and 50-move draws in the TT can be tricky, but since the worst that can happen is that the better line is discovered later, most programmers seem to put up with that inconvenience. After all, it is quite rare for such a draw to enter the root PV.

What I'm wondering about is how the draw became the mainline for your engine in the first place. I've checked with Rybka 3 and Stockfish 1.8 and they also have a plus score for Kd7 during the first plies.

Hmm your engine sees that Kd7 is losing since ply 9. Even if my engine would see it at ply 12 it's still too late. My evalfn is probably to blame, who knows... It drives the search and most pruning so it's still far from perfect... but even then the search should see it... why should I need 3 or even 5 more plies? ... I'm sure I've a bug somewhere...

btw. insane nps

I get only 33% and the search takes much longer (14x) to reach more time to reach 14 plies

mar · Post by **mar** » Wed Dec 01, 2010 11:12 am

bob wrote:
mar wrote:Hi all, I have a strange problem with my chess engine. I'm pretty sure I've a bug somewhere, either in the search or in the transposition table code. I've no clue so I wanted to ask if someone ever ran into a similar problem. I've a position (b3r1k1/2P4p/p2K2p1/8/p2N4/R3Pp2/8/8 w - - 0 52). When I let my engine analyze it, it chooses to play Kd7 until at depth 14 it realises it's a losing move. The strange thing is that when I reduce TT size to 1 meg (default=4 megs) it sees that Kd7 is losing at depth 12 (and chooses Rc3). So there's obviously something very wrong. However I went through the search/tt code a few times and didn't find anything... I'm pretty sure my movegen is ok as well as hash updates (move/undo move) (lots of asserts in debug version). My evalfn is symmetric. Same behavior if I turn nullmove/lmr off. Same if I clamp search result to oldalpha, beta. Any ideas? Many thanks.
PS the 1-meg version scored 65% against a 128-meg TT version in 40 test games (1 game in 1 minute) so that's quite a difference...
That is not unusual. Fine #70 will almost certainly exhibit this behaviour and your program will find the correct move/score at different depths depending on hash size.

Ok but that doesn't explain why a 1-meg TT version is 100 elo stronger. So I suppose I have a serious bug somewhere. Thanks for reply anyway.

Dann Corbit · Post by **Dann Corbit** » Wed Dec 01, 2010 11:26 am

There is a simple way to find out if you have a TT bug.
1. Write a second hash calculator that computes the entire hash from scratch.
Then when you incrementally update your Zobrist hash in debug mode, also update the full hash.
Compare both hash values. If they do not agree, then you have a hash calculation bug.

2. Make a hash table that holds the Epd position as one of its elements if it is compiled in debug mode. When you have a hash hit, then check the Epd position you are analyzing with the stored Epd position. If the hash matches and the EPD values don't match, and it happens frequently, there is a problem. This is better than storing the whole 64 bit hash instead, but that is also a good idea.

So if you have a hash formation bug or a hash storage bug or a hash retrieval bug this will catch it. You probably have most of the code already written (e.g. just call the routine you will call when someone gives you an EPD or FEN string to create the hash against the whole position).

Most hash computation bugs I have seen are from:
1. e.p. problem
2. null move problem
3. castle rights problem
Other problems happen too, but are more rare.

If you have a fancy pants hash that chains long lists of equal hash values or otherwise stores multiple values for a single hash number, you might try simplifying to a single value lookup to see if that fixes it. Sometimes the alternative lookups in the hash table get muddled.

search or transposition table bug?

search or transposition table bug?

Re: search or transposition table bug?

Re: search or transposition table bug?

Re: search or transposition table bug?

Re: search or transposition table bug?

Re: search or transposition table bug?

Re: search or transposition table bug?

Re: search or transposition table bug?

Re: search or transposition table bug?

Re: search or transposition table bug?