minmax.c

#define CHECKMATE_EVALUATION -9001
#define STALEMATE_EVALUATION 0

static int AISearch(int depth, GameState *state, int alpha, int beta)
{
    if (depth == 0)
    {
        return AIEvaluate(state);
    }
    uint16_t moves[1024];
    int numMoves = getAllLegalMoves(moves, state);
    if (numMoves <= 0)
    {
        if (playerInCheck(state))
        {
            return CHECKMATE_EVALUATION;
        }
        else
        {
            return STALEMATE_EVALUATION;
        }
    }
    for (int i = 0; i < numMoves; i++)
    {
        GameState copyState = *state;
        movePiece(moves[i], &copyState);
        int score = AISearch(depth - 1, &copyState, -beta, -alpha);
        score = -score;
        if (score >= beta)
        {
            return beta;
        }
        if (score > alpha)
        {
            alpha = score;
        }
    }
    return alpha;
}

// Working but probably not optimal
uint16_t getComputerMove(void)
{
    uint16_t bestMoves[1024];
    uint32_t numBestMoves = 0;
    uint16_t moves[1024];
    int numMoves = getAllLegalMoves(moves, &gameState);
    int bestScore = CHECKMATE_EVALUATION;
    for (int i = 0 ; i < numMoves; i++)
    {
        GameState copyState = gameState;
        movePiece(moves[i], &copyState);
        int score = AISearch(3, &copyState, CHECKMATE_EVALUATION, -CHECKMATE_EVALUATION);
        score = -score;
        if (score > bestScore)
        {
            bestScore = score;
            bestMoves[0] = moves[i];
            numBestMoves = 1;
        }
        else if (score == bestScore)
        {
            bestMoves[numBestMoves] = moves[i];
            numBestMoves++;
        }
    }

    // Pick a move at random if multiple moves are tied for best evaluation.
    // Helps stop AI from repeating moves.
    if (numBestMoves == 0)
    {
        debugLog("getComputerMove: Did not find a move (this should never happen)");
    }
    return bestMoves[pcgRangedRandom(numBestMoves)];
}

// Not working
uint16_t getComputerMove(void)
{
    uint16_t bestMoves[1024];
    uint32_t numBestMoves = 0;
    uint16_t moves[1024];
    int numMoves = getAllLegalMoves(moves, &gameState);
    int alpha = CHECKMATE_EVALUATION;
    int beta = -CHECKMATE_EVALUATION;
    for (int i = 0 ; i < numMoves; i++)
    {
        GameState copyState = gameState;
        movePiece(moves[i], &copyState);
        int score = AISearch(3, &copyState, -beta, -alpha);
        score = -score;
        if (score > alpha)
        {
            alpha = score;
            bestMoves[0] = moves[i];
            numBestMoves = 1;
        }
        else if (score == alpha)
        {
            bestMoves[numBestMoves] = moves[i];
            numBestMoves++;
        }
    }

    // Pick a move at random if multiple moves are tied for best evaluation.
    // Helps stop AI from repeating moves.
    if (numBestMoves == 0)
    {
        debugLog("getComputerMove: Did not find a move (this should never happen)");
    }
    return bestMoves[pcgRangedRandom(numBestMoves)];
}