Minimax算法实现异常求助：最优代币收集游戏优化

我正在完成一项作业，需要开发一款由电脑自动模拟对战的逻辑游戏，目标是收集总价值最高的代币。程序输入格式如下（输入以'END'结束，后续计划移除该标识）：

N:1,2 
W:3,5
E:9,1,1,1
S:1,7
END

字母代表方向（东E、西W、北N、南S），方向后的数字为对应代币的价值，玩家仅能从各方向的末端取代币，最终收集代币总价值高的玩家获胜。

我希望游戏以最优策略自动运行，因此选用Minimax算法，但完全不清楚如何正确实现。目前我的代码虽能运行，但无法达到最优效果：例如上述输入的最优结果应为A/B:15/16，而实际运行结果为A/B:14/17。

附上我的C语言代码，恳请帮忙修正算法实现，或提供优化建议。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#define MAX_TOKENS 100

struct Game
{
    //lists with the values ​​of the tokens on the individual arms of the cross
    int *north;
    int *west;
    int *east;
    int *south;
    //lengths of token value lists
    int north_size;
    int west_size;
    int east_size;
    int south_size;
    //scores of players A and B
    int score_a;
    int score_b;
};
void remove_token(struct Game *game, int player, char direction)
{
    //variable for the token taken
    int token;

    //according to the direction, remove the token and add its value to the player's score
    switch (direction)
    {
    case 'N':
        //remove the token from the N arm
        token = game->north[game->north_size - 1];
        //reduce the length of the token value list by 1
        game->north_size--;
        //add the chip value to the player's score
        if (player == 0)
            game->score_a += token;
        else
            game->score_b += token;
        break;
    case 'W':
        //remove the token from the W arm
        token = game->west[game->west_size - 1];
        //reduce the length of the token value list by 1
        game->west_size--;
        //add the chip value to the player's score
        if (player == 0)
            game->score_a += token;
        else
            game->score_b += token;
        break;
    case 'E':
        //remove the token from the E arm
        token = game->east[game->east_size - 1];
        //reduce the length of the token value list by 1
        game->east_size--;
        //add the chip value to the player's score
        if (player == 0)
            game->score_a += token;
        else
            game->score_b += token;
        break;
    case 'S':
        //remove the token from the S arm
        token = game->south[game->south_size - 1];
        //reduce the length of the token value list by 1
        game->south_size--;
        //add the chip value to the player's score
        if (player == 0)
            game->score_a += token;
        else
            game->score_b += token;
        break;
    default:
        //throw an error if the player entered an invalid direction
        printf("Neplatný směr pro odebrání žetonu!\n");
    }
}
char minimax(struct Game *game, int depth, int player, int alpha, int beta)
{
    //if all arms are empty or we have reached the maximum depth, return the best direction
    if (game->north_size == 0 && game->west_size == 0 && game->east_size == 0 && game->south_size == 0 || depth == 0)
        return 'X';

    //the best move value for player A
    int best_score_a = INT_MIN;
    //the best move value for player B
    int best_score_b = INT_MAX;
    //direction for best move
    char best_direction;

    //go through all arms to find the best move
    if (game->north_size > 0)
    {
        //copy the game state
        struct Game game_copy = *game;
        //remove the token from the N arm
        remove_token(&game_copy, player, 'N');
        //find out the best move for your opponent
        int score = minimax(&game_copy, depth - 1, player == 0 ? 1 : 0, alpha, beta);
        //update the best move for player A
        if (player == 0 && score > best_score_a)
        {
            best_score_a = score;
            best_direction = 'N';
        }
        //update the best move for player B
        if (player == 1 && score < best_score_b)
        {
            best_score_b = score;
            best_direction = 'N';
        }
        //update alpha and beta
        if (player == 0)
            alpha = fmax(alpha, score);
        else
            beta = fmin(beta, score);
        //if beta is less than alpha, we end traversing the tree
        if (beta <= alpha)
            return best_direction;
    }
      if (game->west_size > 0)
    {
        //copy the game state
        struct Game game_copy = *game;
        //remove the token from the W arm
        remove_token(&game_copy, player, 'W');
        //find out the best move for your opponent
        int score = minimax(&game_copy, depth - 1, player == 0 ? 1 : 0, alpha, beta);
        //update the best move for player A
                if (player == 0 && score > best_score_a)
        {
            best_score_a = score;
            best_direction = 'W';
        }
        //update the best move for player B
        if (player == 1 && score < best_score_b)
        {
            best_score_b = score;
            best_direction = 'W';
        }
        //update alpha and beta
        if (player == 0)
            alpha = fmax(alpha, score);
        else
            beta = fmin(beta, score);
        //if beta is less than alpha, we end traversing the tree
        if (beta <= alpha)
            return best_direction;
    }
    if (game->east_size > 0)
    {
        //copy the game state
        struct Game game_copy = *game;
        //remove the token from the E arm
        remove_token(&game_copy, player, 'E');
        //find out the best move for your opponent
        int score = minimax(&game_copy, depth - 1, player == 0 ? 1 : 0, alpha, beta);
        //update the best move for player A
        if (player == 0 && score > best_score_a)
        {
            best_score_a = score;
            best_direction = 'E';
        }
        //update the best move for player B
        if (player == 1 && score < best_score_b)
        {
            best_score_b = score;
            best_direction = 'E';
        }
        //update alpha and beta
        if (player == 0)
            alpha = fmax(alpha, score);
        else
            beta = fmin(beta, score);
        //if beta is less than alpha, we end traversing the tree
        if (beta <= alpha)
            return best_direction;
    }
    if (game->south_size > 0)
    {
        //copy the game state
        struct Game game_copy = *game;
        //remove the token from the S arm
        remove_token(&game_copy, player, 'S');
        //find out the best move for your opponent
        int score = minimax(&game_copy, depth - 1, player == 0 ? 1 : 0, alpha, beta);
        //update the best move for player A
        if (player == 0 && score > best_score_a)
        {
            best_score_a = score;
            best_direction = 'S';
        }
        //update as soon as possible
                if (player == 1 && score < best_score_b)
        {
            best_score_b = score;
            best_direction = 'S';
        }
        //update alpha and beta
        if (player == 0)
            alpha = fmax(alpha, score);
        else
            beta = fmin(beta, score);
        //if beta is less than alpha, we end traversing the tree
        if (beta <= alpha)
            return best_direction;
    }

    //return the best move
    return player == 0 ? best_direction : best_direction;
}
void read_tokens(int *north, int *west, int *east, int *south, int *north_size, int *west_size, int *east_size, int *south_size)
{
    //buffer for reading in input
    char buffer[MAX_TOKENS];

    //read in the input line by line
    while (fgets(buffer, MAX_TOKENS, stdin) != NULL)
    {
        //remove the newline character from the end of the line
        buffer[strcspn(buffer, "\n")] = 0;
        //check for the "END" string to end the input
        if (strcmp(buffer, "END") == 0)
            break;
        //split the line at the colon character
        char *direction = strtok(buffer, ":");
        char *tokens = strtok(NULL, ":");

        //split the tokens at each comma
        char *token = strtok(tokens, ",");

        //determine the direction and store the tokens in the appropriate array
        if (strcmp(direction, "N") == 0)
        {
            while (token != NULL)
            {
                north[*north_size] = atoi(token);
                (*north_size)++;
                token = strtok(NULL, ",");
            }
        }
        else if (strcmp(direction, "W") == 0)
        {
            while (token != NULL)
            {
                west[*west_size] = atoi(token);
                (*west_size)++;
                token = strtok(NULL, ",");
            }
        }
        else if (strcmp(direction, "E") == 0)
        {
            while (token != NULL)
            {
                east[*east_size] = atoi(token);
                (*east_size)++;
                token = strtok(NULL, ",");
            }
        }
        else if (strcmp(direction, "S") == 0)
        {
            while (token != NULL)
            {
                south[*south_size] = atoi(token);
                (*south_size)++;
                token = strtok(NULL, ",");
            }
        }
        else
        {
            //invalid direction = error
            printf("Nespravny vstup.\n");
        }
    }
}

void print_progress(struct Game *game, int player, char direction)
{
    char letter_player = ' ';
    if (player == 0)
    {
        letter_player = 'A';
    }
    else
        letter_player = 'B';
    //printing of individual steps
    switch (direction)
    {
    case 'N':
        printf("%c: %c[%d] (%d)\n", letter_player, direction, game->north_size, game->north[game->north_size - 1]);
        break;
    case 'W':
        printf("%c: %c[%d] (%d)\n", letter_player, direction, game->west_size, game->west[game->west_size - 1]);
        break;
    case 'E':
        printf("%c: %c[%d] (%d)\n", letter_player, direction, game->east_size, game->east[game->east_size - 1]);
        break;
    case 'S':
        printf("%c: %c[%d] (%d)\n", letter_player, direction, game->south_size, game->south[game->south_size - 1]);
        break;
    default:
        break;
    }
}

void play(struct Game *game, int depth)
{
    //variable for current player (A or B)
    int player = 0;

    //until all chips are taken, alternate players taking chips
    while (game->north_size > 0 || game->west_size > 0 || game->east_size > 0 || game->south_size > 0)
    {
        //player A
        if (player == 0)
        {
            //function on the selection of a token
            char direction = minimax(game, depth, 0, INT_MIN, INT_MAX);
            print_progress(game, player, direction);
            //remove the token from the game
            remove_token(game, player, direction);
        }
        //player B
        else
        {
            //function on the selection of a token
            char direction = minimax(game, depth, 1, INT_MIN, INT_MAX);
            print_progress(game, player, direction);
            //remove the token from the game
            remove_token(game, player, direction);
        }

        //switch players
        player = (player + 1) % 2;
    }
}
int main(void)
{
    //field for token values
    int north[MAX_TOKENS], west[MAX_TOKENS], east[MAX_TOKENS], south[MAX_TOKENS];
    //sizes of token value fields
    int north_size = 0, west_size = 0, east_size = 0, south_size = 0;
    printf("Input:\n");
    //fetch token values ​​from input
    read_tokens(north, west, east, south, &north_size, &west_size, &east_size, &south_size);

    //creating a game
    struct Game game;
    game.north = north;
    game.west = west;
    game.east = east;
    game.south = south;
    game.north_size = north_size;
    game.west_size = west_size;
    game.east_size = east_size;
    game.south_size = south_size;
    game.score_a = 0;
    game.score_b = 0;
    //set the maximum depth of the minimax search tree
    int depth = 1;
    //start the game using the play() function
    play(&game, depth);

    //evaluation of the result of the game

    printf("Celkem A/B: %d/%d\n", game.score_a, game.score_b);

    return 0;
}

你的Minimax实现存在几个关键逻辑错误，导致无法计算出最优策略：

1. 函数返回值逻辑完全错误 #

当前minimax函数返回方向字符，但递归调用时却将该字符当作整数得分使用，这完全违背Minimax的核心逻辑——Minimax应返回当前状态下的最优得分差值（比如玩家A得分减去玩家B得分），而非直接返回方向。

修正方案： #

重构minimax函数，让它返回当前状态的最优得分值，通过指针参数输出最优方向。修改后的函数签名：

int minimax(struct Game *game, int player, int alpha, int beta, char *best_direction)

2. 终止状态评估错误 #

当游戏结束（所有代币取完）时，应返回当前玩家的得分优势：对于玩家A，返回game->score_a - game->score_b；对于玩家B，同样基于该差值选择最小化结果（因为B的目标是让A的优势最小）。而非返回无意义的'X'字符。

3. 搜索深度设置错误 #

你当前设置depth = 1，仅搜索一步，完全浪费了Minimax的深度搜索能力。对于示例输入，总共有10个代币，需将深度设置为总代币数，或直接移除深度限制（游戏状态空间不大，无需剪枝深度）。

4. 最优方向选择逻辑错误 #

当前代码将递归返回的方向字符当作得分比较，完全逻辑混乱。正确逻辑：

• 玩家A（最大化玩家）：遍历所有可能移动，计算每个移动后的得分差值，选择差值最大的方向。
• 玩家B（最小化玩家）：遍历所有可能移动，计算每个移动后的得分差值，选择差值最小的方向。

以下是修正后的minimax核心实现：

int minimax(struct Game *game, int player, int alpha, int beta, char *best_direction) {
    // 终止条件：所有代币被取完
    if (game->north_size == 0 && game->west_size == 0 && game->east_size == 0 && game->south_size == 0) {
        return game->score_a - game->score_b; // 返回A与B的得分差
    }

    int best_val;
    char dir = 'X';

    if (player == 0) { // 玩家A：最大化得分差
        best_val = INT_MIN;
        // 尝试北方向
        if (game->north_size > 0) {
            struct Game copy = *game;
            remove_token(&copy, 0, 'N');