AWS用约束规划自动计算NHL季后赛锁定条件，经验证四个赛季

每年春季，当北美职业冰球联盟（NHL）常规赛进入最后冲刺阶段时，一个问题占据了冰球迷的头脑：我的球队锁定季后赛席位了吗？答案往往出人意料地难以判断。32 支球队、复杂的平局打破规则、数百场剩余比赛，判断一支球队是否在数学上已确保季后赛席位是一个严肃的组合学挑战。

在本文中，我们描述了 AWS 生成式 AI 创新中心如何创建了一个自动化系统来确定 NHL 季后赛锁定场景。我们的方法使用约束编程（CP）和自定义树搜索来生成这些场景，并将结果与 NHL 官方发布的进行了验证。更多细节请参阅我们的科学论文。

背景：锁定季后赛意味着什么

当一支球队"锁定"季后赛（简称"锁定"）时，意味着无论剩余比赛结果如何，该球队都必定进入季后赛。随着赛季推进，通常从 3 月开始，NHL 会每日发布可能锁定的球队的锁定场景。这些场景以如下陈述的形式呈现：

明尼苏达狂野队将在以下任一条件成立时锁定季后赛：在对阵安纳海姆鸭队的比赛中获得至少一分，圣路易斯蓝调队以任何方式负于犹他冰球俱乐部，或卡尔加里火焰队以任何方式负于维加斯金骑士队。

随着联盟的平局打破规则变得越来越复杂，手动生成这些场景变得日益耗时且容易出错。我们的工作贡献了一个自动化、数学上严格且适用于日常使用的替代方案。

NHL 季后赛结构

NHL 的 32 支球队分为两个赛区（东部和西部），每个赛区又分为两个分区。16 支球队获得季后赛资格：每个赛区中，每个分区的前三名直接晋级，两个额外的"外卡"球队填补剩余名额。

每场比赛必须产生胜者。如果比赛在常规时间后打平，则进入加时赛，必要时再进入点球大战。因此，从特定球队的视角来看，比赛有六种可能的结果：常规时间胜利（RW）、加时胜利（OTW）、点球大战胜利（SOW）、点球大战失败（SOL）、加时失败（OTL）和常规时间失败（RL）。胜利积 2 分，加时/点球大战失败积 1 分，常规时间失败积 0 分。

当球队积分相同时，NHL 采用七层平局打破规则的级联：

积分百分比（即已赛场次更少）。

常规时间胜利数加加时胜利数。

净胜球数，包括点球决胜的进球。

进球数，包括点球决胜的进球。

这些复杂的平局打破规则是确定季后赛锁定场景计算上具有挑战性的主要原因。

我们的解决方案

我们的解决方案有两个关键组成部分：0 天求解器和 n 天前瞻求解器。

0 天求解器

我们方法的基础是一个约束编程（CP）模型，回答以下问题： given the current standings, has a team already clinched the playoffs?（给定当前排名，一支球队是否已经锁定季后赛？）

我们将此表述为一个可行性问题：我们能否为所有剩余比赛找到结果，使目标球队无缘季后赛？如果这样的场景不存在，则该球队已锁定。这个模型使用 Google OR-Tools 的 CP-SAT 求解器求解，并考虑了 NHL 平局打破规则的完整复杂性。

n 天前瞻

有了 0 天求解器后，我们进一步问：未来 n 天比赛的哪些结果会导致给定球队锁定？

我们使用自定义树搜索来回答这个问题，其中每一层代表未来 n 天内进行的一场比赛，每个节点代表该比赛的特定结果（见图 1）。树搜索在每个节点调用 0 天求解器，以确定累积的结果是否足以锁定。通过预处理、剪枝策略和节点排序启发式方法保持搜索的可解性。

例如，在图 1 中，0 天求解器推导出某支球队在下一场比赛中通过点球大战胜利（SOW）即可锁定季后赛，用"X"标记。该球队在该场比赛的任何更强结果（OTW 或 RW）下也会锁定，同时对于未来 n 天内任何其他相关比赛的任何结果也会锁定。绿色阴影表示无需显式求值即可证明锁定的节点。

图 1：n 天前瞻的树搜索，其中绿色节点是无需显式求值即可证明锁定的节点

验证结果

我们使用 NHL 公共 API 的数据，对四个 NHL 常规赛赛季（2021-22 至 2024-25）验证了我们方法产生的锁定场景。我们的系统生成的所有场景与 NHL 发布的场景完全匹配。

图 2：四个 NHL 赛季每日求解耗时

确定 1 天锁定场景的中位运行时间在分钟级别，与手动方法相比有显著加速（见图 2）。这种效率来自剪枝：通过正确的预处理策略、节点排序启发式方法和推理算法，大部分搜索树不需要被遍历。在图 3 中，我们展示了大多数实例的剪枝效率接近 100%。

图 3：四个 NHL 赛季的剪枝效率

实际应用

这些方法有直接的实际应用：

对于 NHL 和媒体：自动化、可证明正确的锁定场景，可每日生成而无需人工 effort，带来显著的时间节省。

对于球迷：随着季后赛临近，提供更丰富的参与体验，场景能准确解释他们的球队需要什么条件才能锁定季后赛。

对于体育分析：一个严格的框架，可扩展到其他里程碑（分区冠军、出局、特定排名），并可能适应其他联盟。

总结

这项工作是 AWS 向各行业客户交付的更广泛的数学优化解决方案的一部分。从路线规划和调度到体育分析，这些技术能够快速提供明确答案，而手动方法需要 significant time, effort, and specialized expertise（大量时间、精力和专业 expertise）。

确定 NHL 季后赛锁定场景是一个计算上困难的问题。联盟的分层资格结构和平局打破规则创造了一个难以手动解决的组合学挑战。我们的方法将约束编程与自定义树搜索相结合，以高效且正确的方式解决了这一问题，并在四个赛季的真实 NHL 数据上进行了验证。

该框架具有可扩展性：未来的工作可以将其扩展到 NHL 内的其他锁定和出局场景，或将其适应于具有不同结构和规则的其他体育联盟。

如果您有复杂的组合学问题，并希望了解优化技术如何应用于您的用例，请联系您的客户经理，开始与 AWS 生成式 AI 创新中心一起探索。