Page 1 of 6
repetition draw bug
Posted: Wed Aug 17, 2011 8:12 pm
by 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(mated_in(MAX_PLY), beta))
&& ((tte->type == ScoreLbound && tt_score >= beta)
||(tte->type == ScoreUbound && tt_score < beta));
}
}
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
Re: repetition draw bug
Posted: Wed Aug 17, 2011 11:36 pm
by Desperado
lucasart wrote:
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(mated_in(MAX_PLY), beta))
&& ((tte->type == ScoreLbound && tt_score >= beta)
||(tte->type == ScoreUbound && tt_score < beta));
}
}
"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(mated_in(MAX_PLY), beta)) /*return closed*/
&&((tte->type == ScoreLbound && tt_score >= beta)
|| (tte->type == ScoreUbound && tt_score < beta));
}
}
i did not look at the rest so far...
Michael
Re: repetition draw bug
Posted: Thu Aug 18, 2011 12:22 am
by lucasart
Desperado wrote:lucasart wrote:
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(mated_in(MAX_PLY), beta))
&& ((tte->type == ScoreLbound && tt_score >= beta)
||(tte->type == ScoreUbound && tt_score < beta));
}
}
"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(mated_in(MAX_PLY), beta)) /*return closed*/
&&((tte->type == ScoreLbound && tt_score >= beta)
|| (tte->type == ScoreUbound && tt_score < beta));
}
}
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;
Re: repetition draw bug
Posted: Thu Aug 18, 2011 12:34 am
by Desperado
lucasart wrote:Desperado wrote:lucasart wrote:
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(mated_in(MAX_PLY), beta))
&& ((tte->type == ScoreLbound && tt_score >= beta)
||(tte->type == ScoreUbound && tt_score < beta));
}
}
"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(mated_in(MAX_PLY), beta)) /*return closed*/
&&((tte->type == ScoreLbound && tt_score >= beta)
|| (tte->type == ScoreUbound && tt_score < beta));
}
}
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...
Re: repetition draw bug
Posted: Thu Aug 18, 2011 12:39 am
by mar
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(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(mated_in(MAX_PLY), beta))
&& ((tte->type == ScoreLbound && tt_score >= beta)
||(tte->type == ScoreUbound && tt_score < beta));
}
}
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
Re: repetition draw bug
Posted: Thu Aug 18, 2011 12:48 am
by Desperado
But before i leave, what happens if you simply disable your trans-code ?
Re: repetition draw bug
Posted: Thu Aug 18, 2011 4:42 am
by bob
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(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(mated_in(MAX_PLY), beta))
&& ((tte->type == ScoreLbound && tt_score >= beta)
||(tte->type == ScoreUbound && tt_score < beta));
}
}
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...
An easy test for repetition draw detection
Posted: Thu Aug 18, 2011 5:17 am
by 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)
Re: repetition draw bug
Posted: Thu Aug 18, 2011 7:12 pm
by lucasart
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!
Re: repetition draw bug
Posted: Thu Aug 18, 2011 7:14 pm
by lucasart
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