We're having some problems with a chess program we're developing. The program right now uses negascout (fail-soft) with PV move ordering, iterative deepening and an always-replace transposition table. It also uses SEE-ordered quiescence search (fail-hard).
The problem occurs when both quiescence search and transposition tables are activated. In this case the program produces moves/scores that seem "off". The test position at the moment is this one:
FEN: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
The program plays the same move (Bxa6) but has a worse score with both activated (-226) than with transposition tables off (732) or both off (1034), and plays worse moves after this one. We're wondering if we've made an implementation mistake.
I have taken the time to produce a clean pseudo-code version of our program below. I would be delighted if anyone could explain what we might be doing wrong, or what some good steps to debug the program is, or test positions to debug, and so on, so we can proceed. Thanks!
Code: Select all
int maxd;
tt_replace(u64 zobrist, int score, int scoretype, int depth);
void start(Position pos, int d) {
for (maxd=1; maxd<d; maxd++)
negascout_best(pos, 0);
}
int negascout_best(Position pos, int d) {
if (fifty_move_rule(pos)) return 0;
if (repetition_rule(pos)) return 0;
if (tt_contains_entry(pos.zobrist)) {
entry = tt_get_entry(pos.zobrist);
if (entry.depth >= maxd-d && is_exact_score(entry)) {
return entry.score;
}
}
if (d == maxd) {
score = quiescence(pos, 0, -INF_SCORE, INF_SCORE);
tt_replace(pos.zobrist, score, EXACT_SCORE, 0);
return score;
}
b = INF_SCORE; maxscore = -INF_SCORE;
children = get_children_pv(pos); // ordered using the pv
for (all children) {
if (child_is_pv(child))
score = -negascout_best(child, d+1);
else
score = -negascout(child, d+1, -b, -maxscore);
if (score > maxscore) { // score improved
if (b == INF_SCORE || d >= maxd-2) { // acc. to negascout paper score is always correct up to this depth
maxscore = score;
} else { // re-search
maxscore = -negascout(child, d+1, -INF_SCORE, -score);
}
savepv(child);
}
b = maxscore+1; // set null window
}
if (had_children) {
tt_replace(pos.zobrist, maxscore, EXACT_SCORE, maxd-d);
return maxscore;
} else {
if (checkmate(pos)) {
tt_replace(pos.zobrist, -CHECKMATE_SCORE, EXACT_SCORE, maxd-d);
return -CHECKMATE_SCORE;
} else { // stalemate
tt_replace(pos.zobrist, 0, EXACT_SCORE, maxd-d);
return 0;
}
}
}
int negascout(Position pos, int d, int alpha, int beta) {
if (fifty_move_rule(pos)) return 0;
if (repetition_rule(pos)) return 0;
if (tt_contains_entry(pos.zobrist)) {
entry = tt_get_entry(pos.zobrist);
if (entry.depth >= maxd-d) {
if (is_exact_score(entry))
return entry.score;
else if (is_lower_bound(entry) && entry.score >= beta)
return entry.score;
else if (is_upper_bound(entry) && entry.score <= alpha)
return entry.score;
}
}
if (d == maxd) {
score = quiescence(pos, 0, alpha, beta);
tt_replace(pos.zobrist, score, get_score_type(score, alpha, beta), 0);
return score;
}
b = beta; maxscore = -INF_SCORE; a = alpha;
children = get_children(pos);
for (all children) {
score = -negascout(child, d+1, -b, -a);
if (score > maxscore) { // score improved
if (b == beta || d >= maxd-2) { // acc. to negascout paper score is always correct up to this depth
maxscore = score;
} else { // re-search
maxscore = -negascout(child, d+1, -beta, -score);
}
savepv(child);
}
if (maxscore >= beta) {
tt_replace(pos.zobrist, maxscore, LOWER_BOUND)
return maxscore;
}
a = max(maxscore, alpha);
b = a+1; // set null window
}
if (had_children) {
tt_replace(pos.zobrist, maxscore, get_score_type(maxscore, alpha, beta), maxd-d);
return maxscore;
} else {
if (checkmate(pos)) {
tt_replace(pos.zobrist, -CHECKMATE_SCORE, get_score_type(-CHECKMATE_SCORE, alpha, beta), maxd-d);
return -CHECKMATE_SCORE;
} else { // stalemate
tt_replace(pos.zobrist, 0, get_score_type(0, alpha, beta), maxd-d);
return 0;
}
}
}
int quiescence(Position pos, int depth, int alpha, int beta) {
stand_pat = pos.to_move * evaluate(pos);
if (stand_pat >= beta) {
return beta;
}
if (stand_pat > alpha) {
alpha = stand_pat;
}
children = get_dramatic_moves(pos); // gets captures whose SEE value is larger than 0 (and ordered after them)
for (all children) {
score = -quiescence(child, depth+1, -beta, -alpha);
if (score >= beta) {
return beta;
}
if (score > alpha) {
alpha = score;
}
}
return alpha;
}
