lucasart wrote:lucasart wrote:[d]6Bk/PPPPPp1P/8/7R/7K/8/ppppppQ1/6B1 w - - 0 1
(...) I need to test it and find out why my program didn't find this mate with SEE pruning removed.
with or without SEE pruning it should find it, so long as checking moves are not subject to SEE pruning (like Qg7+ and later Bxf7+).
I found the bug in my program. I was not generating promotions!
So Jan Brouwer was right. This position really *is* a qsearch explosion.
I'll experiment with forcefully limiting the depth of the qsearch.
I decided to fix this qsearch explosion problem by introducing a depth limit. Basically when the depth is QS_LIMIT, we don't call qsearch() recursively, and return eval + SEE instead.
This will make the implementation of the hash table a bit trickier. The depth that I'll have to enter in the hash entries will have to be
Code: Select all
depth == 0 ? 0 : (depth <= QS_LIMIT : -2 : -1)
Something to remember for when I implement a hash table.
Here's my qsearch() so far:
Code: Select all
#define QS_LIMIT -6
int qsearch(Board& B, int alpha, int beta, int depth, int ply)
{
assert(depth <= 0);
assert(alpha < beta);
node_count++;
bool in_check = B.is_check();
int best_score = -INF, static_eval = -INF;
// stand pat
if (!in_check) {
best_score = static_eval = eval(B);
alpha = std::max(alpha, best_score);
if (alpha >= beta)
return alpha;
}
MoveSort MS(&B, depth < 0 ? MoveSort::CAPTURES : MoveSort::CAPTURES_CHECKS);
move_t *m;
int cnt = 0;
while ( alpha < beta && (m = MS.next()) ) {
cnt++;
int check = move_is_check(B, *m);
if (!in_check && check != DISCO_CHECK && see(B, *m) < 0)
continue;
int score;
if (depth <= QS_LIMIT && !in_check)
score = static_eval + see(B,*m); // prevent qsearch explosion
else {
B.play(*m);
score = -qsearch(B, -beta, -alpha, depth-1, ply+1);
B.undo();
}
best_score = std::max(best_score, score);
alpha = std::max(alpha, score);
}
if (B.is_check() && !cnt)
return ply-MATE;
return best_score;
}
This means that the qsearch() cannot find the mate anymore, as black will always manage to get the qsearch() deeper than QS_LIMIT and get a pseudo-standpat on -[eval(White)+see(white move)].
Overall the gain should easily compensate the pain. A single position like that in the game and the consequences can be disastrous, if the engine doesn't even finish a depth 1...
Sample run (I don't have hash tables yet)
Code: Select all
depth=0 score=2955 nodes=2996
depth=1 score=2955 nodes=8099
depth=2 score=31997 nodes=101867
depth=3 score=31997 nodes=418299
depth=4 score=31997 nodes=2040988
depth=5 score=31997 nodes=6859752
The mate is found at depth 2, not 1, because I don't extend checks in the search. And even when I implement that, I will not extend checks with a SEE < 0 (unless discovered checks where the SEE is irrelevant in most cases).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
