Determining playoff clinching scenarios in the NHL using constraint programming

使用约束编程确定NHL季后赛锁定情景 | 人工智能

使用约束编程确定NHL季后赛锁定情景

当国家冰球联盟（NHL）常规赛季进入每年春天的最后阶段时，冰球迷们最关心的问题就是：我的球队是否已经锁定季后赛资格？这个问题的答案往往令人意外地难以判断。由于有32支球队、复杂的积分排名规则以及数百场剩余比赛，判断一支球队是否在数学上已确定获得季后赛席位是一项严峻的组合优化挑战。

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

背景：锁定季后赛资格的含义

当一支球队无论剩余比赛结果如何都确定能进入季后赛时，即可认为该球队已锁定季后赛资格（简称“锁定”）。随着赛季推进（通常从3月开始），NHL会根据当天比赛结果发布各支球队可能锁定季后赛的每日情景。这些情景通常以如下形式呈现：

如果以下任一情况成立，明尼苏达狂野队将锁定季后赛资格：他们对阵阿纳海姆鸭队至少获得1分，圣路易斯蓝调队以任何方式输给犹他冰球俱乐部，或者卡尔加里火焰队以任何方式输给拉斯维加斯金骑士队。

随着联盟积分排名规则日益复杂，手动生成此类情景变得越来越耗时且容易出错。我们的工作提供了一种自动化且数学严谨的替代方案，能够高效支持日常使用。

NHL季后赛结构

NHL的32支球队分为东西两个联盟，每个联盟再分为两个分区。16支球队获得季后赛资格：每个联盟中，每个分区积分排名前三的球队直接晋级，另外两个“外卡”球队则占据剩余席位。

每场比赛必须产生胜者。如果常规时间结束后比分持平，比赛将进入加时赛，必要时还会进行点球大战。因此从单支球队视角来看，每场比赛有六种可能结果：常规时间胜利（RW）、加时赛胜利（OTW）、点球大战胜利（SOW）、点球大战失利（SOL）、加时赛失利（OTL）和常规时间失利（RL）。胜利获得2分，加时/点球失利获得1分，常规时间失利获得0分。

当球队积分相同时，NHL会依次应用以下七项排名规则：

• 积分百分比（即比赛场次较少）
• 常规时间胜利次数
• 常规时间胜利加加时赛胜利次数
• 总胜利次数
• 直接交锋积分
• 进球差（包含点球决胜进球）
• 总进球数（包含点球决胜进球）

这些复杂的排名规则是确定季后赛锁定情景计算难度的主要原因。

我们将此问题表述为一个可行性问题：能否为所有剩余比赛找到结果，使得所讨论的球队无法进入季后赛？如果不存在这样的场景，则说明该球队已经锁定季后赛资格。该模型使用Google OR-Tools中的CP-SAT求解器进行求解，并充分考虑了NHL平局规则的全部复杂性。

n日前瞻分析：在掌握0日求解器后，我们进一步提出问题：接下来n天的比赛结果中，哪些情况会导致特定球队锁定季后赛资格？

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

例如，在图1中，0日求解器推断出一支球队在下一场比赛中通过加时赛胜利（OTW）即可锁定季后赛资格，标记为“X”。该球队在该场比赛取得更强结果（如常规时间胜利RW）或接下来n天内任何其他相关比赛的任何结果时，同样会锁定资格。绿色阴影表示无需显式评估即可证明锁定资格的节点。

图1：n日前瞻的树搜索，绿色节点表示无需显式评估即可证明锁定资格的节点

结果

我们使用NHL公开API的数据，在四个NHL常规赛季（2021–22至2024–25）上验证了我们的方法生成的锁定场景。系统生成的所有场景与NHL公布的场景完全一致。

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

确定1日锁定场景的中位数运行时间在分钟级别，相比人工方法有显著加速（见图2）。这种效率源于剪枝：通过合理的预处理策略、节点排序启发式方法和推理算法，大部分搜索树无需探索。在图3中，我们展示了大多数实例的剪枝效率接近100%。

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

实际价值

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

• 对于NHL和媒体：可自动生成、可证明正确的每日锁定场景，无需人工操作，显著节省时间。
• 对于球迷：季后赛临近时提供更丰富的互动体验，明确说明球队锁定季后赛所需的具体条件。
• 对于体育分析：可扩展至其他里程碑（如分区冠军、淘汰、特定种子）的严谨框架，并可能适用于其他联赛。

这项工作是AWS为各行业客户提供的一系列数学优化解决方案的一部分。从路线规划和调度到体育分析，这些技术能快速提供明确答案，而人工方法则需要大量时间、精力和专业知识。

结论

确定NHL季后赛锁定场景是一个计算上困难的问题。联盟复杂的资格结构和平局规则构成了一个难以手动解决的组合挑战。我们的方法结合约束编程和自定义树搜索，高效且正确地解决了这一问题，并通过四个真实NHL赛季的数据验证。

该框架具有可扩展性：未来的工作可以将这种方法扩展到NHL（国家冰球联盟）中的其他锁定和淘汰场景，或适应具有不同结构和规则的其他体育联盟。

如果您面临复杂的组合优化问题，并希望了解优化技术如何应用于您的使用场景，请联系您的账户经理，开始与AWS生成式AI创新中心合作探索。

关于作者

'"`