棋类 AI 程序：Minimax 与 Alpha-Beta 剪枝搜索

python def minimax(node, depth, maximizing_player): if depth == 0 或 node 是终局: return 评估函数(node)

if maximizing_player:  # AI 的回合
    max_eval = -无穷大
    for 每个子节点 child:
        eval = minimax(child, depth - 1, False)
        max_eval = max(max_eval, eval)
    return max_eval
else:                 # 对手的回合
    min_eval = +无穷大
    for 每个子节点 child:
        eval = minimax(child, depth - 1, True)
        min_eval = min(min_eval, eval)
    return min_eval

实际应用时，你需要在根节点调用 `minimax(root, depth, True)` 并记录下得到最高分的那个子节点作为实际要走的一步。

#### 2.3 复杂度与局限

Minimax 会检查所有可能的分支。假设每个局面平均有 `b` 个合法走法（分枝因子），搜索深度为 `d`，时间复杂度就是 O(bᵈ)。对于围棋（b≈250）或国际象棋（b≈35），即使是浅层搜索，节点数也会爆炸，因此必须引入剪枝优化。

### 3. Alpha-Beta 剪枝：剪掉无关的子树

Alpha-Beta 剪枝是 Minimax 的一种优化，它能在不改变结果的前提下，大幅度减少需要评估的节点数量。其核心思想是：**当某个节点无论后续结果如何，都不会影响上层决策时，就停止对该节点的搜索。**

#### 3.1 核心概念：α 与 β

在搜索过程中我们维护两个边界值：

- **α**：当前最大化玩家所能保证的最低分值（下界）。AI 至少能得到这个值。
- **β**：当前最小化玩家所能保证的最高分值（上界）。对手最多能将分数限制在这个值。

初始时，α = -∞，β = +∞。搜索过程中，最大化层会尝试提高 α，最小化层会尝试降低 β。一旦出现 **α ≥ β**，就发生了剪枝。

#### 3.2 剪枝发生的两种情形

- **在最小化层**：如果某个子节点的评价值 ≤ α，那么当前节点最多只能得到该值，而父节点（最大化层）已经有了一个 α 的保证，它不会选择这个更差的结果，因此剩余兄弟节点可以全部剪掉。
- **在最大化层**：如果某个子节点的评价值 ≥ β，那么当前节点至少能得到该值，但父节点（最小化层）已经有一个 β 的上界，它不会允许如此高的分数，因此剩余兄弟节点也可以剪掉。

#### 3.3 算法伪代码

```python
def alphabeta(node, depth, alpha, beta, maximizing_player):
    if depth == 0 或 node 是终局:
        return 评估函数(node)

    if maximizing_player:
        max_eval = -无穷大
        for 每个子节点 child:
            eval = alphabeta(child, depth - 1, alpha, beta, False)
            max_eval = max(max_eval, eval)
            alpha = max(alpha, eval)
            if beta <= alpha:
                break  # β 剪枝
        return max_eval
    else:
        min_eval = +无穷大
        for 每个子节点 child:
            eval = alphabeta(child, depth - 1, alpha, beta, True)
            min_eval = min(min_eval, eval)
            beta = min(beta, eval)
            if beta <= alpha:
                break  # α 剪枝
        return min_eval

根节点调用时传入 alphabeta(root, depth, -∞, +∞, True)。

3.4 效率提升与走法排序

在最理想的情况下（每次都能先检查“最佳”走法），Alpha-Beta 剪枝可以将需要检查的节点数从 O(bᵈ) 降低到约 O(b^(d/2))。这意味着同样的时间内，搜索深度可以接近翻倍。

为了接近理想情况，工程师通常会采用启发式走法排序：

• 优先搜索历史统计中得分高的走法（历史启发）。
• 优先搜索吃子、将军等激烈走法。
• 利用迭代加深中上一轮浅层搜索的结果来排序。
• 在叶子节点尝试“静态搜索”以解决被吃子的地平线效应。

4. 实战要点：评估函数与实现细节

4.1 设计合理的评估函数

评估函数直接决定 AI 的棋力。对于简单棋类（如井字棋），可直接根据输赢赋值（赢+10，输-10，平0）。对于复杂棋类（如国际象棋），常用材料分值、位置表、机动性等加权和。例如：

总分 = 子力价值差 + 位置加成 + 机动性分值 + 王安全系数