I've been working on implementing/improving my engine's search function the past few days, but yesterday I decided my current search implementation was a mess and that it would be much better to rewrite it from scratch, which is what I'm currently doing.
The issue is, my alpha beta function is returning negative/positive evaluations for the same position for even/odd depths. To try and debug, I wrote a barebones search using the chess programming wiki as reference, but the issue still persists. I don't see where the issue is/could be.
Here is my current implementation:
static int quiesce(Board *board, int alpha, int beta, int color) {
moveList mList = { 0 };
moveList tacticalMoves = { 0 };
int nMoves = genLegalMoves(board, &mList);
int nTactical = genLegalTactical(board, &tacticalMoves);
int standPat = eval(board, nMoves, color);
if (standPat >= beta)
return beta;
if (standPat > alpha)
alpha = standPat;
for (int i = 0; i < nMoves; i++) {
if (nTactical == 0) break;
make(board, mList.moves[i].move);
int score = -quiesce(board, -beta, -alpha, -color);
unmake(board, mList.moves[i].move);
if (score >= beta) return beta;
if (score > alpha) alpha = score;
}
return alpha;
}
int alphaBeta(Board *board, int alpha, int beta, int depthLeft, int color) {
if (depthLeft == 0) return quiesce(board, alpha, beta, color);
moveList mList = {0};
genLegalMoves(board, &mList);
for (int i = 0; i < mList.nMoves; i++) {
make(board, mList.moves[i].move);
int score = -alphaBeta(board, -beta, -alpha, depthLeft - 1, -color);
unmake(board, mList.moves[i].move);
if (score >= beta) return beta;
if (score > alpha) alpha = score;
}
return alpha;
}
void search(Board *board, int depth) {
moveList mList = { 0 };
genLegalMoves(board, &mList);
int best;
int max = -500000;
for (int i = 0; i < mList.nMoves; i++) {
int color = (board->turn == WHITE) ? 1 : -1;
make(board, mList.moves[i].move);
int score = -alphaBeta(board, -500000, 500000, depth - 1, -color);
unmake(board, mList.moves[i].move);
if (score > max) {
max = score;
best = mList.moves[i].move;
}
}
printf("score: %d, best move: ", max);
print_move(best);
printf("\n");
}
I suspect the issue is the quiescence function, as I don't quite understand how it's supposed to be implemented, but I don't see any glaring differences from the chess programming wiki's pseudocode that would cause this behavior.