repetition draw bug

[lucasart]

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

[Desperado]

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;

"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(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;) /*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

[lucasart]

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;

"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(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;) /*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;

[Desperado]

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;

"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(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;) /*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...

[mar]

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

Perhaps you should look at board_is_draw instead of TT. I would drop ++rep == 3 and change i += 4 to i += 2

[Desperado]

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

[bob]

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

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...

[sje]

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

[] rgstat 1000000
Summary:
  Checkmate 153,299 (0.153299)
  FiftyMoves 200,293 (0.200293)
  Insufficient 560,294 (0.560294)
  Repetition 25,340 (0.02534)
  Stalemate 60,774 (0.060774)
Count: 1,000,000   Elapsed: 204.051  (4900.75 Hz / 0.000204051 s)

[lucasart]

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!

[lucasart]

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