c - Negamax 算法没有给出恒定的行为

Question

我尝试使用带有 alpha-beta 修剪的 Negamax 在 C 中创建一个国际象棋引擎，但我无法让它工作。它在游戏的前几个动作中按预期工作，并开始在没有目标的情况下牺牲棋子。但是当它接近尾声时，它似乎再次按预期运行。我已经尝试调试了大约一个星期，但没有任何成功。任何帮助是极大的赞赏。以下是相关代码：

#define INFINITY INT_MAX

char isCheckMateOrStaleMate(uint64_t const *board, uint64_t const *prevBoard, char brkrwrkr00, char isWhiteYourColor) {
    ...
}

struct node {
    unsigned long len;
    uint64_t *pos;
    uint64_t *basepos;
    char brkrwrkr00;
    struct node *branches;
    char *move;
    char color;
};

int max(int a, int b) {
    return a > b ? a : b;
}

int evaluateNode(struct node n) {
    char cmate = isCheckMateOrStaleMate(n.pos, n.basepos, n.brkrwrkr00, !n.color);

    if (cmate)
        return (isCheckOnKing(n.pos, 1) ? -64000 : isCheckOnKing(n.pos, 0) ? 64000 : 0) * (!n.color - n.color);

    int posAdv = 0;

    char p;
    for (char i = 0; i < 64; i++) {
        p = accessBoardAt(n.pos, i);
        posAdv += p == PAWN_B ? -10 : p == PAWN_W ? 10 : p == KNIGHT_B ? -29 : p == KNIGHT_W ? 29 : p == BISHOP_B ? -30 : p == BISHOP_W ? 30 : p == ROOK_B ? -50 : p == ROOK_W ? 50 : p == QUEEN_B ? -90 : p == QUEEN_W ? 90 : 0;
    }

    return (!n.color - n.color) * posAdv;
}

unsigned long generateNodes(uint64_t const *board, uint64_t const *prevBoard, char brkrwrkr00, char isWhiteYourColor, struct node **ret, int depth) {
    if (!depth)
        return 0;

    char *valids = 0;
    unsigned long _len_ = validMoves(board, prevBoard, brkrwrkr00, isWhiteYourColor, &valids);
    
    if (!_len_)
        return 0;

    *ret = malloc(_len_ / 3 * sizeof **ret);

    for (unsigned long i = 0, j = 0; i < _len_; i += 3, j++) {
        (*ret)[j].color = isWhiteYourColor;
        (*ret)[j].pos = {board[0], board[1], board[2], board[3]};
        (*ret)[j].basepos = {board[0], board[1], board[2], board[3]};
        (*ret)[j].brkrwrkr00 = brkrwrkr00;
        (*ret)[j].move = {valids[i], valids[i + 1], valids[i + 2]};
        makeForcedMove((*ret)[j].pos, &((*ret)[j].brkrwrkr00), (*ret)[j].move);
        (*ret)[j].len = generateNodes((*ret)[j].pos, board, (*ret)[j].brkrwrkr00, !isWhiteYourColor, &((*ret)[j].branches), depth - 1);
    }

    free(valids);

    return _len_ / 3;
};

int negamaxscore(struct node n, int depth, char maximizer, int alpha, int beta) {
    if (!depth || !n.len)
        return evaluateNode(n);

    int eval = -INFINITY;

    for (unsigned long i = 0; i < n.len; i++) {
        eval = max(-negamaxscore(n.branches[i], depth - 1, !maximizer, -beta, -alpha), eval);
        alpha = max(eval, alpha);

        if (beta <= alpha)
            break;
    }

    return eval;
}

char *theBestMove(uint64_t const *board, uint64_t const *prevBoard, char brkrwrkr00, char isWhiteYourColor, int depth) {
    if (!depth)
        return NULL;

    struct node *branches;
    unsigned long len = generateNodes(board, prevBoard, brkrwrkr00, isWhiteYourColor, &branches, depth);

    if (!len)
        return NULL;

    char *bestmove = NULL;
    int curr;
    int eval = -INFINITY;
    int alpha = -INFINITY;
    int beta = INFINITY;

    for (unsigned long i = 0; i < len; i++) {
        curr = -negamaxscore(branches[i], depth - 1, !isWhiteYourColor, -beta, -alpha);

        if (curr >= eval) {
            eval = curr;
            bestmove = branches[i].move;
        }

        alpha = max(eval, alpha);

        if (beta <= alpha)
            break;
    }

    bestmove = memcpy(malloc(3), bestmove, 3);

    return bestmove;
}

char *theBestMove(uint64_t const *board, uint64_t const *prevBoard, char brkrwrkr00, char isWhiteYourColor, int depth) {
    if (!depth)
        return NULL;

    struct node *branches;
    unsigned long len = generateNodes(board, prevBoard, brkrwrkr00, isWhiteYourColor, &branches, depth);

    if (!len)
        return NULL;

    char *bestmove = NULL;
    int curr;
    int eval = -INFINITY;
    int alpha = -INFINITY;
    int beta = INFINITY;

    char seq[depth * 5];

    for (unsigned long i = 0; i < len; i++) {
        curr = -negamaxscore(branches[i], depth - 1, !isWhiteYourColor, -beta, -alpha);

        if (curr >= eval) {
            eval = curr;
            bestmove = branches[i].move;
        }

        alpha = max(eval, alpha);

        if (beta <= alpha)
            break;
    }

    bestmove = memcpy(malloc(3), bestmove, 3);

    return bestmove;
}