repetition draw bug

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
lucasart
Posts: 2994
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

repetition draw bug

Post by lucasart » Wed Aug 17, 2011 6:12 pm

My engine seems to accept a lot of repetition draws, when it clearly shouldn't. Obviously the problem comes from the transposition table. But I've looked at it again and again, and I can't figure out what I'm doing wrong.. Here's what I do

in the search

Code: Select all

	// TTable lookup
	U64 key = get_key(B);
	const TTEntry *tte = tt_find(key);
	move_t tt_move;
	if (tte) {
		si->best = tt_move = tte->depth > 0 ? tte->move : NoMove;
		current_eval = tte->eval;
		if (ply > 0 && can_return_tt(is_pv, tte, depth, beta, ply))
			return adjust_tt_score(tte->score, ply);
	}
in the qsearch

Code: Select all

	// TTable lookup
	U64 key = get_key(B);
	const TTEntry *tte = tt_find(key);
	move_t tt_move;
	int current_eval;
	if (tte) {
		si->best = tt_move = tte->move;
		current_eval = tte->eval;
		if (can_return_tt(is_pv, tte, depth, beta, ply))
			return adjust_tt_score(tte->score, ply);
	}
and the function can_return_tt

Code: Select all

static inline bool can_return_tt(bool is_pv, const TTEntry *tte, int depth, int beta, int ply)
{
	if (is_pv)
		return tte->depth >= depth && tte->type == ScoreExact;
	else {
		const int tt_score = adjust_tt_score(tte->score, ply);
		return (tte->depth >= depth
		        ||	tt_score >= max(mate_in(MAX_PLY), beta)
		        ||	tt_score < min&#40;mated_in&#40;MAX_PLY&#41;, beta&#41;)
		       &&	(&#40;tte->type == ScoreLbound && tt_score >= beta&#41;
		            ||&#40;tte->type == ScoreUbound && tt_score < beta&#41;);
	&#125;
&#125;
so I use the TT for pruning even at PV nodes, but not at the root (which should avoid most of the problems?)

Any suggestions are welcome!

PS: Of course I check for repetition draws (search and qsearch) *before* the TTable blocks shown above

User avatar
Desperado
Posts: 636
Joined: Mon Dec 15, 2008 10:45 am

Re: repetition draw bug

Post by Desperado » Wed Aug 17, 2011 9:36 pm

lucasart wrote:

Code: Select all

static inline bool can_return_tt&#40;bool is_pv, const TTEntry *tte, int depth, int beta, int ply&#41;
&#123;
	if &#40;is_pv&#41;
		return tte->depth >= depth && tte->type == ScoreExact;
	else &#123;
		const int tt_score = adjust_tt_score&#40;tte->score, ply&#41;;
		return &#40;tte->depth >= depth
		        || tt_score >= max&#40;mate_in&#40;MAX_PLY&#41;, beta&#41;
		        ||	tt_score < min&#40;mated_in&#40;MAX_PLY&#41;, beta&#41;)
		       &&	(&#40;tte->type == ScoreLbound && tt_score >= beta&#41;
		            ||&#40;tte->type == ScoreUbound && tt_score < beta&#41;);
	&#125;
&#125;
"can_return_tt should give a compiler error !?, doesnt it ?

now unmodified, but a little more structured...

Code: Select all

static inline bool can_return_tt&#40;bool is_pv, const TTEntry *tte, int depth, int beta, int ply&#41; 
&#123; 
 if &#40;is_pv&#41; return tte->depth >= depth && tte->type == ScoreExact; 
 else 
 &#123; 
  const int tt_score = adjust_tt_score&#40;tte->score, ply&#41;; 
 
  return&#40;   tte->depth >= depth 
         || tt_score   >= max&#40; mate_in&#40;MAX_PLY&#41;, beta&#41; 
         || tt_score    < min&#40;mated_in&#40;MAX_PLY&#41;, beta&#41;) /*return closed*/

         &&(&#40;tte->type == ScoreLbound && tt_score >= beta&#41; 
         || &#40;tte->type == ScoreUbound && tt_score  < beta&#41;); 
 &#125; 
&#125; 
i did not look at the rest so far...

Michael

User avatar
lucasart
Posts: 2994
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: repetition draw bug

Post by lucasart » Wed Aug 17, 2011 10:22 pm

Desperado wrote:
lucasart wrote:

Code: Select all

static inline bool can_return_tt&#40;bool is_pv, const TTEntry *tte, int depth, int beta, int ply&#41;
&#123;
	if &#40;is_pv&#41;
		return tte->depth >= depth && tte->type == ScoreExact;
	else &#123;
		const int tt_score = adjust_tt_score&#40;tte->score, ply&#41;;
		return &#40;tte->depth >= depth
		        || tt_score >= max&#40;mate_in&#40;MAX_PLY&#41;, beta&#41;
		        ||	tt_score < min&#40;mated_in&#40;MAX_PLY&#41;, beta&#41;)
		       &&	(&#40;tte->type == ScoreLbound && tt_score >= beta&#41;
		            ||&#40;tte->type == ScoreUbound && tt_score < beta&#41;);
	&#125;
&#125;
"can_return_tt should give a compiler error !?, doesnt it ?

now unmodified, but a little more structured...

Code: Select all

static inline bool can_return_tt&#40;bool is_pv, const TTEntry *tte, int depth, int beta, int ply&#41; 
&#123; 
 if &#40;is_pv&#41; return tte->depth >= depth && tte->type == ScoreExact; 
 else 
 &#123; 
  const int tt_score = adjust_tt_score&#40;tte->score, ply&#41;; 
 
  return&#40;   tte->depth >= depth 
         || tt_score   >= max&#40; mate_in&#40;MAX_PLY&#41;, beta&#41; 
         || tt_score    < min&#40;mated_in&#40;MAX_PLY&#41;, beta&#41;) /*return closed*/

         &&(&#40;tte->type == ScoreLbound && tt_score >= beta&#41; 
         || &#40;tte->type == ScoreUbound && tt_score  < beta&#41;); 
 &#125; 
&#125; 
i did not look at the rest so far...

Michael
you're missing the point. my code compiles and it's basically compiled as return A && B;

User avatar
Desperado
Posts: 636
Joined: Mon Dec 15, 2008 10:45 am

Re: repetition draw bug

Post by Desperado » Wed Aug 17, 2011 10:34 pm

lucasart wrote:
Desperado wrote:
lucasart wrote:

Code: Select all

static inline bool can_return_tt&#40;bool is_pv, const TTEntry *tte, int depth, int beta, int ply&#41;
&#123;
	if &#40;is_pv&#41;
		return tte->depth >= depth && tte->type == ScoreExact;
	else &#123;
		const int tt_score = adjust_tt_score&#40;tte->score, ply&#41;;
		return &#40;tte->depth >= depth
		        || tt_score >= max&#40;mate_in&#40;MAX_PLY&#41;, beta&#41;
		        ||	tt_score < min&#40;mated_in&#40;MAX_PLY&#41;, beta&#41;)
		       &&	(&#40;tte->type == ScoreLbound && tt_score >= beta&#41;
		            ||&#40;tte->type == ScoreUbound && tt_score < beta&#41;);
	&#125;
&#125;
"can_return_tt should give a compiler error !?, doesnt it ?

now unmodified, but a little more structured...

Code: Select all

static inline bool can_return_tt&#40;bool is_pv, const TTEntry *tte, int depth, int beta, int ply&#41; 
&#123; 
 if &#40;is_pv&#41; return tte->depth >= depth && tte->type == ScoreExact; 
 else 
 &#123; 
  const int tt_score = adjust_tt_score&#40;tte->score, ply&#41;; 
 
  return&#40;   tte->depth >= depth 
         || tt_score   >= max&#40; mate_in&#40;MAX_PLY&#41;, beta&#41; 
         || tt_score    < min&#40;mated_in&#40;MAX_PLY&#41;, beta&#41;) /*return closed*/

         &&(&#40;tte->type == ScoreLbound && tt_score >= beta&#41; 
         || &#40;tte->type == ScoreUbound && tt_score  < beta&#41;); 
 &#125; 
&#125; 
i did not look at the rest so far...

Michael
you're missing the point. my code compiles and it's basically compiled as return A && B;
Indeed, too late for me today... :oops:

mar
Posts: 1866
Joined: Fri Nov 26, 2010 1:00 pm
Full name: Martin Sedlak

Re: repetition draw bug

Post by mar » Wed Aug 17, 2011 10:39 pm

lucasart wrote:My engine seems to accept a lot of repetition draws, when it clearly shouldn't. Obviously the problem comes from the transposition table. But I've looked at it again and again, and I can't figure out what I'm doing wrong.. Here's what I do

in the search

Code: Select all

	// TTable lookup
	U64 key = get_key&#40;B&#41;;
	const TTEntry *tte = tt_find&#40;key&#41;;
	move_t tt_move;
	if &#40;tte&#41; &#123;
		si->best = tt_move = tte->depth > 0 ? tte->move &#58; NoMove;
		current_eval = tte->eval;
		if &#40;ply > 0 && can_return_tt&#40;is_pv, tte, depth, beta, ply&#41;)
			return adjust_tt_score&#40;tte->score, ply&#41;;
	&#125;
in the qsearch

Code: Select all

	// TTable lookup
	U64 key = get_key&#40;B&#41;;
	const TTEntry *tte = tt_find&#40;key&#41;;
	move_t tt_move;
	int current_eval;
	if &#40;tte&#41; &#123;
		si->best = tt_move = tte->move;
		current_eval = tte->eval;
		if &#40;can_return_tt&#40;is_pv, tte, depth, beta, ply&#41;)
			return adjust_tt_score&#40;tte->score, ply&#41;;
	&#125;
and the function can_return_tt

Code: Select all

static inline bool can_return_tt&#40;bool is_pv, const TTEntry *tte, int depth, int beta, int ply&#41;
&#123;
	if &#40;is_pv&#41;
		return tte->depth >= depth && tte->type == ScoreExact;
	else &#123;
		const int tt_score = adjust_tt_score&#40;tte->score, ply&#41;;
		return &#40;tte->depth >= depth
		        ||	tt_score >= max&#40;mate_in&#40;MAX_PLY&#41;, beta&#41;
		        ||	tt_score < min&#40;mated_in&#40;MAX_PLY&#41;, beta&#41;)
		       &&	(&#40;tte->type == ScoreLbound && tt_score >= beta&#41;
		            ||&#40;tte->type == ScoreUbound && tt_score < beta&#41;);
	&#125;
&#125;
so I use the TT for pruning even at PV nodes, but not at the root (which should avoid most of the problems?)

Any suggestions are welcome!

PS: Of course I check for repetition draws (search and qsearch) *before* the TTable blocks shown above
Perhaps you should look at board_is_draw instead of TT. I would drop ++rep == 3 and change i += 4 to i += 2

User avatar
Desperado
Posts: 636
Joined: Mon Dec 15, 2008 10:45 am

Re: repetition draw bug

Post by Desperado » Wed Aug 17, 2011 10:48 pm

But before i leave, what happens if you simply disable your trans-code ?

bob
Posts: 20357
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: repetition draw bug

Post by bob » Thu Aug 18, 2011 2:42 am

lucasart wrote:My engine seems to accept a lot of repetition draws, when it clearly shouldn't. Obviously the problem comes from the transposition table. But I've looked at it again and again, and I can't figure out what I'm doing wrong.. Here's what I do

in the search

Code: Select all

	// TTable lookup
	U64 key = get_key&#40;B&#41;;
	const TTEntry *tte = tt_find&#40;key&#41;;
	move_t tt_move;
	if &#40;tte&#41; &#123;
		si->best = tt_move = tte->depth > 0 ? tte->move &#58; NoMove;
		current_eval = tte->eval;
		if &#40;ply > 0 && can_return_tt&#40;is_pv, tte, depth, beta, ply&#41;)
			return adjust_tt_score&#40;tte->score, ply&#41;;
	&#125;
in the qsearch

Code: Select all

	// TTable lookup
	U64 key = get_key&#40;B&#41;;
	const TTEntry *tte = tt_find&#40;key&#41;;
	move_t tt_move;
	int current_eval;
	if &#40;tte&#41; &#123;
		si->best = tt_move = tte->move;
		current_eval = tte->eval;
		if &#40;can_return_tt&#40;is_pv, tte, depth, beta, ply&#41;)
			return adjust_tt_score&#40;tte->score, ply&#41;;
	&#125;
and the function can_return_tt

Code: Select all

static inline bool can_return_tt&#40;bool is_pv, const TTEntry *tte, int depth, int beta, int ply&#41;
&#123;
	if &#40;is_pv&#41;
		return tte->depth >= depth && tte->type == ScoreExact;
	else &#123;
		const int tt_score = adjust_tt_score&#40;tte->score, ply&#41;;
		return &#40;tte->depth >= depth
		        ||	tt_score >= max&#40;mate_in&#40;MAX_PLY&#41;, beta&#41;
		        ||	tt_score < min&#40;mated_in&#40;MAX_PLY&#41;, beta&#41;)
		       &&	(&#40;tte->type == ScoreLbound && tt_score >= beta&#41;
		            ||&#40;tte->type == ScoreUbound && tt_score < beta&#41;);
	&#125;
&#125;
so I use the TT for pruning even at PV nodes, but not at the root (which should avoid most of the problems?)

Any suggestions are welcome!

PS: Of course I check for repetition draws (search and qsearch) *before* the TTable blocks shown above
The critical question: when you stumble into such a draw, does your search output show a draw or not? I don't hash at the root as it makes no sense, which means I will always make a move and go to the next ply. There I will do the rep check before I do a hash probe, and if the move at the root draws, I will see it without having the hash table score cause me to overlook the draw.

So you first need to answer the above. If you don't see a rep score, then you must have a bug in that code (it is easy enough to do, I have screwed it up more times than I can count if you look at the comments in main.c and search for "repetition". If you do see a repetition score, then it seems that is apparently the best you can do. If you think something better is available, that is a different debugging issue.

There are some draw by rep issues with the trans/ref table. But such things should not cause this kind of bug with any significant frequency...

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

An easy test for repetition draw detection

Post by sje » Thu Aug 18, 2011 3:17 am

An easy test for repetition draw detection:

1) In your chess program, add a routine that will play a game with each move selected at random. This routine also reports back the reason (one of five possible) that the game ended.

2) Call the above routine a million times and summarize the results.

3) If the number of games that ended by repetition is about 2.6% of the total, then the repetition detection code is probably working.

Example:

Code: Select all

&#91;&#93; rgstat 1000000
Summary&#58;
  Checkmate 153,299 &#40;0.153299&#41;
  FiftyMoves 200,293 &#40;0.200293&#41;
  Insufficient 560,294 &#40;0.560294&#41;
  Repetition 25,340 &#40;0.02534&#41;
  Stalemate 60,774 &#40;0.060774&#41;
Count&#58; 1,000,000   Elapsed&#58; 204.051  &#40;4900.75 Hz / 0.000204051 s&#41;

User avatar
lucasart
Posts: 2994
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: repetition draw bug

Post by lucasart » Thu Aug 18, 2011 5:12 pm

mar wrote:Perhaps you should look at board_is_draw instead of TT. I would drop ++rep == 3 and change i += 4 to i += 2
good point. I'll have a look at that, and test my board_is_draw a bit more seriously.
thank you!

User avatar
lucasart
Posts: 2994
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: repetition draw bug

Post by lucasart » Thu Aug 18, 2011 5:14 pm

Desperado wrote:But before i leave, what happens if you simply disable your trans-code ?
unfortunately i haven't made my code flexible enough to do that. it's a nice feature to implement, for testing purposes. so i'll do that
thank you

Post Reply