alpha-beta/quiesc. bug; score returned alternates between pos/neg for even/odd depths

[am5083]

I've been working on implementing/optimizing my engine's search function for the past couple days but I hit a major roadblock yesterday and decided to rewrite from first principles as I have a much better understanding of the concepts now than I did when I started.

However, when after implementing quiescent search, I now get scores that alternate between pos/neg for odd/even depths. I have not done anything special with my implementation and even when checking against the pseudocode on wikipedia and the chess programming wiki, I can't seem to understand what is causing this to happen.

I'm using a very barebones evaluation to test search, so I don't suspect that's at fault

Code: Select all

    int wMaterial = (P_VAL * count_bits(board->pieceBB[n_wPawn])) +
                          (N_VAL * count_bits(board->pieceBB[n_wKnight])) +
                          (B_VAL * count_bits(board->pieceBB[n_wBishop])) +
                          (R_VAL * count_bits(board->pieceBB[n_wRook])) +
                          (Q_VAL * count_bits(board->pieceBB[n_wQueen])) +
                          (K_VAL * count_bits(board->pieceBB[n_wKing]));

    int bMaterial = (P_VAL * count_bits(board->pieceBB[n_bPawn])) +
                          (N_VAL * count_bits(board->pieceBB[n_bKnight])) +
                          (B_VAL * count_bits(board->pieceBB[n_bBishop])) +
                          (R_VAL * count_bits(board->pieceBB[n_bRook])) +
                          (Q_VAL * count_bits(board->pieceBB[n_bQueen])) +
                          (K_VAL * count_bits(board->pieceBB[n_bKing]));

    if (count_bits(board->pieceBB[n_wBishop] >= 2)) wMaterial += 50; else wMaterial -= 50;
    if (count_bits(board->pieceBB[n_bBishop] >= 2)) bMaterial += 50; else bMaterial -= 50;

    const int material = wMaterial - bMaterial;

    return color * (material + (nMoves / 2));

and this is what I have for quiescent/aB search

Code: Select all

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;
}

I added the color args to try to debug the issue, but previously I was just grabbing color from board state.

This is my principal search function

Code: Select all

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 quiescent search, and I think that I'm implementing it incorrectly; however, I don't understand what exactly im doing wrong. Any help is appreciated

[Ras]

int standPat = eval(board, nMoves, color);

Unless you have some colour code in your eval, there should probably be some black/white discernation here. Because your white eval score is positive, black is negative, but both are trying to maximise here. Means, you could try something like this:

Code: Select all

int standPat;
if (color > 0) /*or however you code "white to move"*/
    standPat = eval(board, nMoves, color);
else
    standPat = -eval(board, nMoves, color);

[am5083]

Yeah, that was it. I can't believe I didn't think to do that, lol.

[am5083]

I'm having another, unrelated, problem that has to do with magic bit boards overflowing the stack. I'm using the plain implementation, but it seems that switching to the fancy implementation would solve this problem. The only issue is that I don't get how the attack table is populated, are bishop and rook moves next to each other? Do you fill bishop first *then* rook?

I don't know if it's appropriate to ask in the same thread, but I dont think the question deserves a thread