C语言：在Minimax递归算法中保存游戏有效路径

问题说明 #

开发双人代币抽取游戏，玩家A先手，有5种抽取选项：左代币、右代币、左侧连续两个代币、左右各一个代币、右侧连续两个代币。规则限定：若某回合抽取2个代币，下一回合必须抽取2个代币。现有基于Minimax算法的代码可计算出最优得分，但无法记录达成该得分的有效操作路径，此前尝试用数组存储路径但逻辑混乱。

解决方案 #

核心思路是改造Minimax递归函数，让其同时返回最优得分与对应的操作路径，利用已定义的SCORE结构体承载这两类信息。每次递归选择最优分支时，将当前操作加入路径，并拼接后续分支的路径，确保仅保留最优路径。

修改后的完整代码 #

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#include <string.h>

#define MAX_SIZE 100

// 定义操作类型，标记不同抽取动作
typedef enum {
    MOVE_LEFT,          // 抽左代币
    MOVE_RIGHT,         // 抽右代币
    MOVE_LEFT_TWO,      // 抽左侧连续两个
    MOVE_RIGHT_TWO,     // 抽右侧连续两个
    MOVE_LEFT_RIGHT     // 抽左右各一个
} MoveType;

typedef struct {
    int score;
    MoveType moves[MAX_SIZE];
    int moveCount;      // 路径中操作的数量
} SCORE;

void getTokens(int* tokens, size_t* size) {
    int token;
    printf("Zetony:\n");
    while(scanf("%d", &token) == 1) {
        tokens[(*size)++] = token;
        if (*size > MAX_SIZE) {
            *size = 0;
            break;
        }
    }
}

// 复制路径：将src的路径复制到dst中
void copyMoves(SCORE* dst, const SCORE* src) {
    dst->moveCount = src->moveCount;
    memcpy(dst->moves, src->moves, src->moveCount * sizeof(MoveType));
}

// 在路径开头添加一个操作
void prependMove(SCORE* score, MoveType move) {
    memmove(&score->moves[1], score->moves, score->moveCount * sizeof(MoveType));
    score->moves[0] = move;
    score->moveCount++;
}

// 获取五个SCORE中的最优解（最大化玩家）
SCORE maxOfFiveScores(const SCORE* a, const SCORE* b, const SCORE* c, const SCORE* d, const SCORE* e) {
    const SCORE* choices[] = {b, c, d, e};
    SCORE max = *a;
    for (int i = 0; i < 4; i++) {
        if (choices[i]->score > max.score) {
            max = *choices[i];
        }
    }
    return max;
}

// 获取五个SCORE中的最优解（最小化玩家）
SCORE minOfFiveScores(const SCORE* a, const SCORE* b, const SCORE* c, const SCORE* d, const SCORE* e) {
    const SCORE* choices[] = {b, c, d, e};
    SCORE min = *a;
    for (int i = 0; i < 4; i++) {
        if (choices[i]->score < min.score) {
            min = *choices[i];
        }
    }
    return min;
}

// 获取两个SCORE中的最大值（最大化玩家）
SCORE maxScore(const SCORE* a, const SCORE* b) {
    return (a->score > b->score) ? *a : *b;
}

// 获取两个SCORE中的最小值（最小化玩家）
SCORE minScore(const SCORE* a, const SCORE* b) {
    return (a->score < b->score) ? *a : *b;
}

SCORE minimaxRec(int* tokens, int start, int end, int scoreA, bool maximize, bool twoA, bool twoB) {
    SCORE result;
    // 边界条件：无代币可抽，初始化空路径
    if (start > end) {
        result.score = scoreA;
        result.moveCount = 0;
        return result;
    }

    if (maximize) {
        if (twoA && (end - start >= 1)) {
            // 五种操作分支
            SCORE moveLeft = minimaxRec(tokens, start + 1, end, scoreA + tokens[start], !maximize, twoA, twoB);
            prependMove(&moveLeft, MOVE_LEFT);

            SCORE moveRight = minimaxRec(tokens, start, end - 1, scoreA + tokens[end], !maximize, twoA, twoB);
            prependMove(&moveRight, MOVE_RIGHT);

            SCORE moveLeftTwo = minimaxRec(tokens, start + 2, end, scoreA + tokens[start] + tokens[start+1], !maximize, !twoA, twoB);
            prependMove(&moveLeftTwo, MOVE_LEFT_TWO);

            SCORE moveRightTwo = minimaxRec(tokens, start, end - 2, scoreA + tokens[end] + tokens[end-1], !maximize, !twoA, twoB);
            prependMove(&moveRightTwo, MOVE_RIGHT_TWO);

            SCORE moveLeftRight = minimaxRec(tokens, start + 1, end - 1, scoreA + tokens[start] + tokens[end], !maximize, !twoA, twoB);
            prependMove(&moveLeftRight, MOVE_LEFT_RIGHT);

            result = maxOfFiveScores(&moveLeft, &moveRight, &moveLeftTwo, &moveRightTwo, &moveLeftRight);
        } else {
            // 仅能抽单个代币的分支
            SCORE moveLeft = minimaxRec(tokens, start + 1, end, scoreA + tokens[start], !maximize, !twoA, twoB);
            prependMove(&moveLeft, MOVE_LEFT);

            SCORE moveRight = minimaxRec(tokens, start, end - 1, scoreA + tokens[end], !maximize, !twoA, twoB);
            prependMove(&moveRight, MOVE_RIGHT);

            result = maxScore(&moveLeft, &moveRight);
        }
    } else {
        if (twoB && (end - start >= 1)) {
            // 五种操作分支（玩家B操作不影响scoreA，仅改变代币范围）
            SCORE moveLeft = minimaxRec(tokens, start + 1, end, scoreA, !maximize, twoA, twoB);
            prependMove(&moveLeft, MOVE_LEFT);

            SCORE moveRight = minimaxRec(tokens, start, end - 1, scoreA, !maximize, twoA, twoB);
            prependMove(&moveRight, MOVE_RIGHT);

            SCORE moveLeftTwo = minimaxRec(tokens, start + 2, end, scoreA, !maximize, twoA, !twoB);
            prependMove(&moveLeftTwo, MOVE_LEFT_TWO);

            SCORE moveRightTwo = minimaxRec(tokens, start, end - 2, scoreA, !maximize, twoA, !twoB);
            prependMove(&moveRightTwo, MOVE_RIGHT_TWO);

            SCORE moveLeftRight = minimaxRec(tokens, start + 1, end - 1, scoreA, !maximize, twoA, !twoB);
            prependMove(&moveLeftRight, MOVE_LEFT_RIGHT);

            result = minOfFiveScores(&moveLeft, &moveRight, &moveLeftTwo, &moveRightTwo, &moveLeftRight);
        } else {
            // 仅能抽单个代币的分支
            SCORE moveLeft = minimaxRec(tokens, start + 1, end, scoreA, !maximize, twoA, twoB);
            prependMove(&moveLeft, MOVE_LEFT);

            SCORE moveRight = minimaxRec(tokens, start, end - 1, scoreA, !maximize, twoA, twoB);
            prependMove(&moveRight, MOVE_RIGHT);

            result = minScore(&moveLeft, &moveRight);
        }
    }
    return result;
}

SCORE minimax(int* tokens, size_t size) {
    int start = 0, end = size - 1;
    bool maximize = true, twoA = true, twoB = true;
    return minimaxRec(tokens, start, end, 0, maximize, twoA, twoB);
}

// 将操作类型转为可读字符串
const char* moveTypeToString(MoveType type) {
    switch(type) {
        case MOVE_LEFT: return "抽左代币";
        case MOVE_RIGHT: return "抽右代币";
        case MOVE_LEFT_TWO: return "抽左侧连续两个代币";
        case MOVE_RIGHT_TWO: return "抽右侧连续两个代币";
        case MOVE_LEFT_RIGHT: return "抽左右各一个代币";
        default: return "未知操作";
    }
}

int main() {
    int tokens[MAX_SIZE];
    size_t size = 0;
    SCORE result;

    getTokens(tokens, &size);
    if (!size) {
        printf("Nespravny vstup.\n");
        return 0;
    }

    result = minimax(tokens, size);
    printf("\n最优得分: %d\n", result.score);
    printf("操作路径:\n");
    for (int i = 0; i < result.moveCount; i++) {
        printf("第%d步: %s\n", i+1, moveTypeToString(result.moves[i]));
    }

    return 0;
}

关键修改说明 #

1. 新增操作类型枚举：用MoveType明确标记5种抽取操作，避免模糊的位置数字记录，提升路径可读性。
2. 递归函数返回值改造：将minimaxRec返回值从int改为SCORE结构体，同时承载得分和操作路径。
3. 路径操作工具函数：实现copyMoves和prependMove，简化路径复制与拼接逻辑，确保路径顺序与操作顺序一致。
4. 最优分支选择：针对最大化/最小化玩家场景，比较分支的SCORE结构体，选择得分最优的分支并保留其路径。
5. 路径输出：新增moveTypeToString函数将操作转为可读字符串，在主函数中遍历输出完整操作路径。

注意事项 #

• 递归中每次选择最优分支后，将当前操作插入路径前端，保证路径顺序从第一步到最后一步。
• 严格遵循游戏规则：抽2个代币后，通过!twoA/!twoB传递下一回合必须抽2个代币的状态。
• 路径存储受MAX_SIZE限制，避免数组越界。

内容的提问来源于stack exchange，提问作者Marek Pospíšil