My program has a hashing bug that I could not resolve after weeks of attempts. If anyone had come across a similar situation in the development of their engine, I would like to know the solution.
With TT hashing enabled, my program plays normally from the start position and does not do strange moves. But when given KQK or KRK positions, it fails to mate and will concede a repetition/fifty-moves draw.
But with TT disabled, it does successfully mate with KQK or KRK. With KRK, it will take some moves to force the lone king into the corner. When it detects mate, matesearch() will be called starting at root. The root search iterates through even depth 2/4/6/8.. to seek the best mate. It will take almost zero second for it to find the next better mate move: mate in 5/4/3/2/1 - checkmate.
My matesearch() code is here:
EDIT: at root, the 1st call to search_mate() has :- best = alpha = positve mate score with a bestmove.
Code: Select all
/* Mate Search
* =======
* Mate search starts with a +mate score X which may not be the best mate.
* Root search iterates through even depth 2, 4, 6, 8, ...If any improvement in the mate score is found,
* then it is the best mate and search returns.
* After depth N where INFI - N + 1 == X, then it means there is no better mate than X
* and search also returns.
*/
int search_mate(const int depth, int alpha, int beta, const int side, const int xside,
const int ply, check_t check_s, int followPV) {
const int alpha0 = alpha;
const int incheck = check_s.type;
int i, x, nummove, sorted_front;
int movepc, ep, movedone;
int best, xeval;
move_t *move, bestmove, ttmove = 0;
move_t list[256];
/* even depth == engine side */
assert(depth > 0);
assert(ply & 1 ? beta <= M_MATE : alpha >= P_MATE);
assert(!is_sq_attacked(king[xside], side));
pv[ply][0] = 0;
maxply = MAX(maxply, ply);
if (ply > MAX_PLY) {
assert(0);
sendlog("matesearch maxply reached %d, depth %d\n", ply, depth);
return mat[side] - mat[xside] - 2;
}
++fnodes;
++nodes;
/* may run out of time */
if (nodes & timeoutNodeMask || notimeout || !searchInfo->bestmove || searchinfi)
;
else {
timeout();
}
best = -INFI;
bestmove = 0;
movedone = 0;
xeval = -INFI;
#if !ENABLE_HASH
ttdata->type = 0;
ttdata->move = 0;
#else
probehash(ply);
++numprobe;
if (ttdata->type && ttdata->depth >= depth) {
++probehit;
switch (ttdata->type) {
case EX:
assert(ttdata->score ^ -INFI);
ttmove = ttdata->move;/* return if not rpt3; a temp bad hack */
break;
case LB:
if (ttdata->score >= beta) {
assert(ttdata->score ^ INFI);
return ttdata->score;
}
assert(ttdata->score != -INFI);
break;
case UB:
assert(pv[ply][0] == 0);
if (ttdata->score <= alpha) {
assert(ttdata->score ^ INFI);
return ttdata->score;
}
break;
default:
assert(0);
}
}
if (ttdata->type) {
xeval = ttdata->eval;
}
#endif
move = gen_all(list, side, &check_s);
nummove = move - list;
if (!nummove) {
goto MATE;
}
sorted_front = 0;
if (followPV && pv[0][ply]) {
swapMoveFront(list, pv[0][ply]);
sorted_front = 1;
} else {
followPV = 0;
if (ttdata->type && ttdata->move) {
swapMoveFront(list, ttdata->move);
sorted_front = 1;
}
}
assert(*move == 0);
assert(list[nummove] == 0);
assert(depth > 0);
for (move = list; *move; ++move) {
assert(* (list + nummove - 1));
assert(* (list + nummove) == 0);
if (!sorted_front) {
if (!incheck) {
if (movedone < 32) {
bubbleBestMoveHistory(move, list + nummove, history[side]);
}
} else {
swapBestMove(move);
}
}
sorted_front = 0;
if (is_move_valid(*move, side, incheck))
;
else {
followPV = 0;
continue;
}
movepc = MOVE_PC(*move);
ep = currstack->epRights && TO(*move) == currstack->ep && movepc == Pawn;
currstack->move = *move;
makemove(*move, side);
if (currstack->fifty < 100) {
for (i = 4; i <= currstack->fifty; i += 2) {
if (currstack->hash ^ (currstack - i)->hash)
;
else {
/* repetition */
x = 0;
pv[ply + 1][0] = 0;
goto SET_BEST;
}
}
} else {
x = 0;
pv[ply + 1][0] = 0;
goto SET_BEST;
}
if (ttmove){
/* !!! TEMP; return TT exact hit */
unmake(*move, side);
pv[ply][0] = ttmove;
pv[ply][1] = 0;
return ttdata->score;
}
//validate ep;
if (ep && is_sq_attacked_brq(king[side], xside)) {
unmake(*move, side);
continue;
}
assert(!is_sq_attacked(king[side], xside));
if (depth == 1) {
assert(ply & 1);
/* seeks mate only. returns if not mate. */
x = mat[side] - mat[xside] + 2;
assert(x >= beta);
unmake(*move, side);
storehash(x, depth, LB, *move, xeval);
return x;
}
getSideIncheck(&check_s, xside);
if (check_s.type) {
SET_CHECKBIT(*move); /* may hashed with TT move */
}
assert(!(ply & 1) ? alpha >= P_MATE : 1);
if (depth == 2 && !check_s.type) {
/* seek only mate. */
x = mat[side] - mat[xside] + 2;
pv[ply + 1][0] = 0;
assert(x <= alpha);
goto SET_BEST;
}
#if 0
if (!(ply & 1) && INFI - (ply + 1) == alpha + 2 && !check_s.type) {
x = mat[side] - mat[xside] + 2;
pv[ply + 1][0] = 0;
goto SET_BEST;
}
#endif
x = -search_mate(depth - 1, -beta, -alpha, xside, side, ply + 1, check_s, followPV);
assert(x ^ INFI);
SET_BEST:
unmake(*move, side);
++movedone;
followPV = 0;
assert(x >= -INFI && x <= INFI);
if (x > best) {
best = x;
bestmove = *move;
if (best > alpha) {
if (best >= beta) {
assert(best ^ -INFI);
++history[side][movepc][TO(bestmove)];
break;
}
alpha = best;
pv[ply][0] = *move;
pv_t *dst = pv[ply] + 1;
pv_t *src = pv[ply + 1];
while ((*(dst++) = *(src++)));
assert(debugPV(pv[ply], side, ply));
assert(depth & 1 ? beta <= M_MATE : alpha >= P_MATE);
/* may have lesser mate from TT hit ??? */
if (!(ply & 1) && best == INFI - (ply + 1)) {
storehash(best + ply, MAX_DEPTH, EX, bestmove, -INFI);
return best;
}
}
}
}/* end for loop*/
if (best ^ -INFI) {
assert(bestmove);
assert(is_move_generated(list, bestmove));
if (best > M_MATE && best < P_MATE) {
if (best ^ 0) {
storehash(best, depth, best <= alpha0 ? UB : (best >= beta ? LB : EX), bestmove, xeval);
}
} else if (best <= M_MATE) {
/* even ply has -mate, odd ply +mate */
storehash(best - ply, MAX_DEPTH, best <= alpha0 ? UB : (best < beta ? EX : LB), bestmove, -INFI);
} else {
storehash(best + ply, MAX_DEPTH, best <= alpha0 ? UB : (best < beta ? EX : LB), bestmove, -INFI);
}
assert(best ^ INFI);
return best;
} else {
MATE:
assert(!bestmove);
if (incheck) {
storehash(-INFI, MAX_DEPTH, EX, 0, -INFI);
return -INFI + ply;
}
assert(depth >= 1);
/* stalemate*/
storehash(1, MAX_DEPTH, EX, 0, -INFI);
return 1;
}
}
Rasjid.
And I try to avoid touching any of that today for fear of "fixing it again"...