基于混合整数规划的宝可梦队伍优化：约束求解与实战参数

在游戏 AI 优化领域，宝可梦队伍构建是一个典型的组合优化问题。面对 1025 种宝可梦、18 种属性类型、复杂的克制关系，传统的手工组队方法往往难以找到全局最优解。本文将深入解析如何将这一复杂问题转化为混合整数规划（Mixed-Integer Programming, MIP）问题，并提供完整的工程化解决方案。

问题建模：从游戏规则到数学公式

核心决策变量

宝可梦队伍优化的本质是一个选择问题：从 N 个候选宝可梦中选出最多 6 个，组成最优队伍。数学上，我们可以定义二元决策变量：

[ x_n \in {0, 1}, \quad n = 1, 2, \ldots, N ]

其中 (x_n = 1) 表示选择第 n 个宝可梦，(x_n = 0) 表示不选择。

目标函数：最大化基础属性总值

每个宝可梦有一个基础属性总值（Base Stat Total, BST），这是衡量其综合强度的关键指标。目标函数为：

[ \max \sum_{n=1}^{N} b_n x_n ]

其中 (b_n) 是第 n 个宝可梦的基础属性总值。

基础约束条件

1. 队伍大小约束：队伍必须包含 1 到 6 个宝可梦 [ 1 \leq \sum_{n=1}^{N} x_n \leq 6 ]

2. 唯一性约束：每个宝可梦最多被选择一次 [ x_n \in {0, 1} ]

复杂约束处理：属性抵抗的数学表达

属性克制矩阵

定义属性克制矩阵 (T_{An})，表示属性 A 对宝可梦 n 的伤害倍数：

• (T_{An} = 2.0)：双倍克制
• (T_{An} = 1.0)：正常伤害
• (T_{An} = 0.5)：抵抗（半伤）
• (T_{An} = 0.25)：双倍抵抗
• (T_{An} = 0)：免疫

抵抗约束的挑战

我们希望队伍对每个属性 A 至少有一个抵抗该属性的宝可梦。数学表达为：

[ \min_{n} (x_n T_{An}) \leq 0.5 ]

但 (\min) 函数是非线性的，无法直接用于线性规划。这里需要巧妙的线性化技巧。

辅助变量技巧

引入两组辅助二元变量：

• (y_{An} \in {0, 1})：表示宝可梦 n 是否被选为属性 A 的抵抗者
• (z_{An} \in {0, 1})：表示宝可梦 n 同时被选中且被选为属性 A 的抵抗者

约束系统如下：

1. 大 M 法处理抵抗条件： [ x_n T_{An} + M \times (y_{An} - 1) \leq 0.5, \quad M \gg 1 ] 当 (y_{An} = 1) 时，约束变为 (x_n T_{An} \leq 0.5)，即该宝可梦抵抗属性 A。

2. 逻辑与约束（确保 (z_{An} = x_n \land y_{An})）： [ \begin {aligned} z_{An} &\leq x_n \ z_{An} &\leq y_{An} \ z_{An} &\geq x_n + y_{An} - 1 \end {aligned} ]

3. 每个属性至少一个抵抗者： [ \sum_{n=1}^{N} z_{An} \geq 1, \quad \forall A ]

工程实现：PuLP 库实战代码

环境配置与数据准备

import pulp
import pandas as pd

# 加载宝可梦数据集（Kaggle格式）
pokemon_df = pd.read_csv('pokemon.csv')
# 包含字段：name, type1, type2, hp, attack, defense, sp_attack, sp_defense, speed, base_total
# 以及18个属性的抵抗系数矩阵

问题定义与变量创建

def optimize_pokemon_team(pokemon_data, resistance_matrix, team_size=6):
    """优化宝可梦队伍的核心函数"""
    
    N = len(pokemon_data)  # 宝可梦数量
    A = 18  # 属性类型数量
    
    # 创建优化问题
    prob = pulp.LpProblem("Pokemon_Team_Optimization", pulp.LpMaximize)
    
    # 主决策变量：是否选择宝可梦
    x = pulp.LpVariable.dicts("x", range(N), cat="Binary")
    
    # 辅助变量
    y = pulp.LpVariable.dicts("y", 
                             [(a, n) for a in range(A) for n in range(N)], 
                             cat="Binary")
    z = pulp.LpVariable.dicts("z",
                             [(a, n) for a in range(A) for n in range(N)],
                             cat="Binary")
    
    # 目标函数：最大化基础属性总值
    prob += pulp.lpSum(pokemon_data.iloc[n]['base_total'] * x[n] 
                      for n in range(N)), "Maximize_Base_Total"
    
    # 队伍大小约束
    prob += pulp.lpSum(x[n] for n in range(N)) == team_size, "Team_Size"
    
    # 大M参数（足够大的常数）
    M = 1000
    
    # 属性抵抗约束
    for a in range(A):
        # 每个属性至少有一个抵抗者
        prob += pulp.lpSum(z[(a, n)] for n in range(N)) >= 1, f"Resistance_Type_{a}"
        
        for n in range(N):
            # 逻辑与约束
            prob += z[(a, n)] <= x[n], f"Z_Constraint_1_{a}_{n}"
            prob += z[(a, n)] <= y[(a, n)], f"Z_Constraint_2_{a}_{n}"
            prob += z[(a, n)] >= x[n] + y[(a, n)] - 1, f"Z_Constraint_3_{a}_{n}"
            
            # 抵抗条件约束
            resistance_value = resistance_matrix[a][n]
            prob += (x[n] * resistance_value + 
                    M * (y[(a, n)] - 1) <= 0.5), f"Resistance_Condition_{a}_{n}"
    
    # 求解
    solver = pulp.PULP_CBC_CMD(msg=False)
    status = prob.solve(solver)
    
    if status == pulp.LpStatusOptimal:
        selected_indices = [n for n in range(N) if pulp.value(x[n]) == 1]
        return selected_indices, pulp.value(prob.objective)
    else:
        return None, None

关键参数配置表

结果分析与实战洞察

基础模型结果

运行基础模型（最大化 BST + 全属性抵抗）会得到一个明显的结论：队伍由传说宝可梦和准传说宝可梦主导。例如：

1. 超梦（Mewtwo） - 基础属性总值 680
2. 烈空坐（Rayquaza） - 基础属性总值 680
3. 盖欧卡（Kyogre） - 基础属性总值 670
4. 固拉多（Groudon） - 基础属性总值 670
5. 代欧奇希斯（Deoxys） - 基础属性总值 600
6. 拉帝欧斯（Latios） - 基础属性总值 600

这个结果虽然数学上最优，但实际对战中有两个问题：

1. 传说宝可梦在对战规则中通常被禁止
2. 忽略了技能覆盖、速度线、特性等实战因素

实用约束扩展

为了得到更实用的队伍，可以添加以下约束：

# 禁止传说宝可梦
legendary_indices = get_legendary_indices(pokemon_data)
for idx in legendary_indices:
    prob += x[idx] == 0, f"Ban_Legendary_{idx}"

# 禁止准传说宝可梦（可选）
pseudo_legendary_indices = get_pseudo_legendary_indices(pokemon_data)
for idx in pseudo_legendary_indices:
    prob += x[idx] == 0, f"Ban_Pseudo_Legendary_{idx}"

# 属性覆盖约束：确保队伍能克制所有属性
# 需要额外的攻击克制矩阵和类似抵抗约束的处理

# 速度线约束：确保有高速先手宝可梦
fast_pokemon_indices = get_fast_pokemon_indices(pokemon_data, speed_threshold=100)
prob += pulp.lpSum(x[idx] for idx in fast_pokemon_indices) >= 1, "At_Least_One_Fast"

实战优化队伍示例

应用禁止传说和准传说宝可梦约束后，得到的实用队伍可能包含：

1. 暴鲤龙（Gyarados） - 水 / 飞行，基础属性总值 540

   • 抵抗：火、地面、钢、水
   • 实战价值：威吓特性降低对手攻击

2. 巨沼怪（Swampert） - 水 / 地面，基础属性总值 535

   • 抵抗：电属性（重要！）
   • 实战价值：抗电且能学习地震

3. 沙奈朵（Gardevoir） - 超能力 / 妖精，基础属性总值 518

   • 抵抗：龙、格斗、超能力
   • 实战价值：妖精属性对抗龙系

4. 请假王（Slaking） - 一般，基础属性总值 670

   • 抵抗：幽灵
   • 注意：懒惰特性限制其实战价值

5. 波士可多拉（Aggron） - 钢 / 岩石，基础属性总值 530

   • 抵抗：妖精、飞行、冰、一般、毒
   • 实战价值：高物理防御

6. 路卡利欧（Lucario） - 格斗 / 钢，基础属性总值 525

   • 抵抗：虫、恶、草、岩石
   • 实战价值：双刀输出手

模型局限性与改进方向

当前模型的主要局限

1. 技能覆盖缺失：模型只考虑属性抵抗，未考虑技能学习池和实际输出能力
2. 速度种族值忽略：先手权在对战中至关重要
3. 特性未纳入：如威吓、降雨、日照等特性极大影响实战
4. 道具系统缺失：道具如剩饭、专爱围巾等改变对战动态
5. 努力值分配：个体宝可梦的能力值定制

扩展建模建议

1. 多目标优化：平衡基础属性、速度、技能覆盖等多个目标

   # 加权多目标
   prob += (alpha * pulp.lpSum(base_stats[n] * x[n]) +
            beta * pulp.lpSum(speed_stats[n] * x[n]) +
            gamma * coverage_score)
   

2. 分层优化：先优化属性覆盖，再在满足覆盖的队伍中优化其他指标

3. 集成机器学习：使用历史对战数据训练评估函数，替代简单的基础属性加总

4. 实时调整：根据对手队伍动态调整己方队伍选择（VGC 规则）

工程化部署建议

性能优化参数

对于生产环境部署，建议以下优化：

1. 预处理过滤：先排除明显不合适的宝可梦（如 BST 过低）
2. 启发式初始解：提供好的初始解加速求解
3. 并行求解：对不同的约束组合并行求解
4. 缓存机制：缓存常见查询结果

监控指标

部署后需要监控的关键指标：

API 设计示例

from fastapi import FastAPI
from pydantic import BaseModel

app = FastAPI()

class TeamRequest(BaseModel):
    banned_types: list[str] = []
    required_coverage: list[str] = []
    min_speed: int = 0
    exclude_legendary: bool = True
    team_size: int = 6

@app.post("/optimize-team")
async def optimize_team(request: TeamRequest):
    """优化宝可梦队伍的API端点"""
    # 根据请求参数构建约束
    # 调用优化引擎
    # 返回优化结果
    return {
        "team": selected_pokemon_names,
        "total_bst": total_bst,
        "coverage_score": coverage_score,
        "solve_time": solve_time
    }

总结与展望

宝可梦队伍优化问题展示了组合优化在游戏 AI 中的强大应用。通过混合整数规划，我们能够系统化地解决这一复杂问题，得到数学上最优或接近最优的队伍配置。

关键收获：

1. 复杂游戏问题可以通过数学建模转化为可求解的优化问题
2. 辅助变量技巧是处理非线性约束的关键
3. 实用约束（如禁止传说宝可梦）对得到可用结果至关重要
4. 工程化部署需要考虑性能、监控和 API 设计

未来方向：

1. 集成更复杂的对战模拟器作为评估函数
2. 开发交互式工具，允许玩家调整偏好并实时看到优化结果
3. 扩展到双打对战、轮盘对战等更复杂的规则
4. 结合强化学习进行端到端的队伍优化

无论是游戏开发者还是优化算法工程师，这个案例都提供了宝贵的实践经验：将实际问题抽象为数学模型，选择合适的求解工具，并通过工程化实现创造实际价值。

资料来源：

1. Nicolas Chagnet. "Pokémon team optimization" (2025-12-26). https://nchagnet.pages.dev/blog/pokemon-team-optimization/
2. Hacker News 讨论：Pokémon Team Optimization (2026-01-01). https://news.ycombinator.com/item?id=46401763
3. PuLP 文档：https://coin-or.github.io/pulp/
4. Kaggle 宝可梦数据集：https://www.kaggle.com/datasets/rounakbanik/pokemon

相关工具：

• PuLP：Python 线性规划库
• OR-Tools：Google 优化工具包
• CBC：开源混合整数规划求解器
• Pandas：数据处理库

ai-systems