优化带Alpha-Beta剪枝的Minimax算法以解决博弈树超时问题

问题背景 #

我正在用带Alpha-Beta剪枝的Minimax算法解决一个博弈编程问题，规则如下：

• 博弈以一棵有根树表示，每个节点有固定代价，非叶子节点必有子节点，游戏只能在叶子节点结束。
• 玩家A（最大化方）：可选择停留在当前节点，或前往任意子节点，目标是最大化最终获得的代价。
• 玩家B（最小化方）：必须选择子节点移动，无法停留，目标是最小化最终代价。
• 双方均采用最优策略行动。

目前已实现的代码能得到正确结果，但节点规模较大时会超时。尝试用缓存优化Minimax搜索结果，但仅在玩家A选择前进时有效，玩家A选择停留时仍需重新执行搜索。

初始实现代码 #

vector<int> edges[MAXN];
int minimax(int node, bool p1_turn, int alpha, int beta) {
    if(edges[node].empty()) return cost[node];

    if(p1_turn) {
        int best = minimax(node, false, alpha, beta);
        for(auto u: edges[node]) {
            int val = minimax(u, false, alpha, beta);
            best = max(val, best);
            alpha = max(alpha, best);

            if(beta <= alpha) {
                break;
            } 
        }
        return best;
    } else {
        int best = MAX_INF;
        for(auto u: edges[node]){
            int val = minimax(u, true, alpha, beta);
            best = min(best, val);
            beta = min(best, beta);

            if(beta <= alpha){
                break;
            }
        }
        return best;
    }
}

// 调用示例
minimax(1, true, MIN_INF, MAX_INF)

修改后的代码（贴合维基百科Alpha-Beta剪枝伪代码） #

if(edges[node].empty()) return cost[node];
if(p1_turn) {
    int best = minimax(node, false, alpha, beta);
    for(auto u: edges[node]) {
        best = max(best, minimax(u, false, alpha, beta));
        if(best > beta) {
            break;
        }
        alpha = max(alpha, best);        
    }
    return best;
} else {
    int best = MAX_INF;
    for(auto u: edges[node]){
        best = min(best, minimax(u, true, alpha, beta));
        if(best < alpha){
            break;
        }
        beta = min(best, beta);
    }
    return best;
}

内容的提问来源于stack exchange，提问作者user20888300