象棋AI算法

发表于 更新于

一、最小-最大搜索（Minimax Search）

核心思想：最小与最大是相对的，且只针对一方（AI）。

原理：
AI走一步后，假设对手会走对AI最差的一步；AI需选择使自身收益最大的走法。

示例（搜索深度4）： 

1
AI走第1步 → 对手走第2步（最差） → AI走第3步（最佳） → 对手走第4步（最差）

→ 深度0时调用 Evaluate() 返回局面评价

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int Max(int depth) {
    int best = -INFINITY;
    if (depth <= 0) {
        return Evaluate();
    }
    GenerateLegalMoves();       //产生所有合理走法
    while (MovesLeft()) {
        MakeNextMove();          //走这一步时
        val = Min(depth - 1);    //接受一个相对最小值
        UnmakeMove();
        if (val > best) {
            best = val;
        }
    }
    return best;                //返回一个相对最大的评价（AI 认为的最佳着法）
}

int Min(int depth) {
    int best = INFINITY;        // 注意这里不同于"最大"算法
    if (depth <= 0) {
        return Evaluate();
    }
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        val = Max(depth - 1);    //接受一个相对最大值
        UnmakeMove();
        if (val < best) {       // 注意这里不同于"最大"算法
            best = val;
        }
    }
    return best;                //返回一个相对最小的评价（对方，人认为的最差走法）
}

调用方式：val = MinMax(5); → 返回向前看5步的当前局面评价。

二、负值最大函数（Negamax Search）

优化点：将 Min/Max 合并为单函数，通过取负号处理双方角色切换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int NegaMax(int depth) {
    int best = -INFINITY;
    if (depth <= 0) {
        return Evaluate();
    }
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        val = -NegaMax(depth - 1);  // 注意这里有个负号
        UnmakeMove();
        if (val > best) {           //始终最优值
            best = val;
        }
    }
    return best;
}

优势：省去求 min 函数的步骤，减少代码量，始终求对当前节点的最佳走法。

三、Alpha-Beta搜索

问题：Minimax 需检查整个博弈树，分枝因子大导致效率低。

解决方案：通过维护上下界 alpha 和 beta，剪枝无效分支。

3.1 核心概念

概念 说明
Alpha 当前节点的最优上界（MAX节点的最大值）
Beta 对手节点的最优下界（MIN节点的最小值）
Alpha剪枝 MIN节点：当 alpha >= beta 时终止扩展
Beta剪枝 MAX节点：当 alpha >= beta 时终止扩展

3.2 口袋示例

场景：死敌面前有多个口袋，你挑口袋，他挑物品。

目标：挑出在诸多最糟糕物品中最好的物品所在的口袋。

排序后剪枝示意：

  • 节点2最小值200，节点3中150<200
  • 节点1下第一个子节点170 < 200，第二个子节点更小 → 剪裁
  • 节点4类似，第一个子节点50，后面的无需再比较

3.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int AlphaBeta(int depth, int alpha, int beta) {
    if (depth == 0) {
        return Evaluate();
    }
    GenerateLegalMoves();
    while (MovesLeft()) {
        MakeNextMove();
        val = -AlphaBeta(depth - 1, -beta, -alpha);  // Alpha和Beta互换并取负
        UnmakeMove();
        if (val >= beta) {
            return beta;      // Beta剪枝
        }
        if (val > alpha) {
            alpha = val;      // 更新alpha
        }
    }
    return alpha;
}

3.4 性能关键

依赖搜索顺序：若先搜最差分支，无法触发剪枝，退化为 Minimax。

优化建议：生成全部着法后，排序很重要。

参考文献

待补充

  • 评估函数设计（子力价值、位置优势、残局特征）
  • 迭代加深（Iterative Deepening）优化
  • 实际象棋博弈树规模估算