一种约束规划方法用于$n$日前瞻季后赛锁定

# 一种用于 NHL 中 n 天前瞻季后赛出线判定的约束规划方法
来源：https://arxiv.org/html/2605.13142 \\hideLIPIcs

Amazon Advanced Solutions Lab，西雅图，华盛顿州，98170，美国  
gilir@amazon\.com  
https://orcid\.org/0009-0007-6866-9949  

Amazon Advanced Solutions Lab，西雅图，华盛顿州，98170，美国  
kybooth@amazon\.com  
https://orcid\.org/0000-0001-6929-8042  

Amazon Advanced Solutions Lab，西雅图，华盛顿州，98170，美国  
j\.kylebrubaker@gmail\.com  
https://orcid\.org/0000-0002-6439-5270  

Amazon Advanced Solutions Lab，西雅图，华盛顿州，98170，美国  
randrist@amazon\.ch  
https://orcid\.org/0000-0003-1126-6931  

\CopyrightGili Rosenberg, Kyle E\. C\. Booth, J\. Kyle Brubaker, 和 Ruben S\. Andrist

\ccsdesc\[500\]计算理论 约束与逻辑编程  
\ccsdesc\[300\]数学基础 组合优化  

###### 致谢。作者感谢 Helmut Katzgraber 和 Nino DiPasquale 的支持，以及 Greg Inglis、Neil Pierson、Ben Resnick 和 Katie Yates 富有成效的讨论。

\SeriesVolume379  
\ArticleNo13

Kyle E\. C\. Booth  
J\. Kyle Brubaker  
111贡献时隶属于 Amazon。  
Ruben S\. Andrist

###### 摘要

在职业体育中，一支球队如果无论剩余比赛结果如何都能保证获得季后赛席位，则称该球队已出线。随着赛季的进行，体育迷和其他利益相关者希望确切知道他们的球队在何时、何种条件下能够出线。本文研究国家冰球联盟（NHL）中的季后赛出线判定问题，由于复杂的平局规则，生成出线场景在计算上具有挑战性。我们提出一种算法，用于确定在接下来 n 天的比赛结果组合下，球队将在何种情况下出线（即“n 天前瞻出线”）。我们的方法采用自定义树搜索，结合多种预处理技术、剪枝策略和节点排序启发式，高效地探索可能的结果空间。树搜索利用基于约束规划（CP）的子程序进行推理，判断球队在常规赛某个时间点是否已经出线（即“0 天前瞻出线”）。该 CP 子程序旨在寻找一个反例，使被评估的球队被淘汰，同时考虑资格规则和 NHL 广泛的平局规则。我们使用基于 2021-22 至 2024-25 赛季公开 NHL 数据的数百个场景验证了算法的有效性。所介绍的方法可以轻松扩展到其他感兴趣的指标，包括季后赛淘汰的数学证明、夺得总统奖杯，以及确保（或失去）排名表中任何其他种子席位。

###### 关键词：约束规划、运筹学、树搜索、体育、冰球

## 1 引言

国家冰球联盟（NHL）是一个职业冰球联盟，有 32 支球队来自美国和加拿大的主要城市。NHL 常规赛中，这些球队相互竞争，争夺有限数量的季后赛席位，席位根据球队常规赛表现授予。随着赛季的进行，NHL 球迷、营销人员和其他利益相关者希望确切知道他们的球队在何时、在何种条件下能够“出线”。一支球队如果无论剩余比赛结果如何都能保证进入季后赛，则称该球队已出线。在常规赛的关键阶段（通常从三月份开始），NHL 开始每天发布受当晚比赛影响的球队的季后赛出线场景（即使用 1 天前瞻）。随着联盟平局规则变得越来越复杂，手动确定出线场景变得越来越耗时且容易出错。我们的工作提供了一种自动化且数学上严格的替代方案，能够以足够快的速度确定出线场景，供日常使用。

多年来，NHL 经历了联盟结构（球队、分区等）、平局规则、资格条件、比赛场次等方面的多次变化。本研究基于自 2019-20 赛季以来联盟规则的最新变化（季后赛资格和平局规则）的状态（并且对未来的变化保持灵活）。NHL 常规赛通常从十月持续到四月，每支球队进行 82 场比赛。联盟分为两个联合会（东部和西部），每个联合会再分为两个分区（东部：大西洋和都市，西部：中央和太平洋）。这种结构在季后赛资格中起着关键作用。常规赛结束时，16 支球队获得季后赛资格（每个联合会 8 支）。在每个联合会中，每个分区的前三名球队获得资格，另外还有两支外卡球队。这种资格结构引入了复杂的场景，球队不仅要在本分区内竞争，还要在整个联合会内争夺外卡席位。

每场 NHL 比赛必须产生一个胜者。如果比赛在常规时间后打平，则进入加时赛，如果仍然打平，则进行点球大战。因此，从一支球队的角度来看，NHL 比赛有六种可能的结果——常规时间赢（RW）、加时赢（OTW）、点球赢（SOW）、点球输（SOL）、加时输（OTL）和常规时间输（RL）。任何方式的胜利获得 2 分，加时或点球失利获得 1 分，常规时间失利获得 0 分。在 NHL 中，球队首先按积分排名。当球队积分相同时，应用一系列平局规则 [nhl\_tiebreakers]，见表 1 (https://arxiv.org/html/2605.13142#S1.T1)。

表 1：NHL 平局规则。每个规则按升序应用，直到打破平局。胜率是获得积分与最大可能积分之比。净胜球是进球数减去失球数。

要判断一支球队是否已根据其当前赛季表现数学上确保季后赛席位（即“0 天前瞻”），必须考虑所有剩余比赛的所有可能结果。这使得它成为一个具有挑战性的组合问题。事实上，已知这个问题以及其他资格问题的变体是 NP-完全问题 [bernholt1999football, gusfield2002structure, kern2004computational]。通常，确定未来 n 天内比赛的结果（场景）是很有趣的，这些结果将使球队能够证明出线（即“n 天前瞻”）。这些场景可以被体育营销人员用来提高球迷参与度，并且通常会使季后赛临近时关注球队变得更加激动人心。我们在表 2 中提供了一个简单的 0 天和 1 天前瞻季后赛出线场景示例 (https://arxiv.org/html/2605.13142#S1.T2)。

表 2：2024 年 4 月 15 日结束时东部联合会积分榜。*0 天前瞻：* 纽约岛人（NYI）在都市分区获得前三名，从而出线。对于 NYI 的最坏情况，他们将输掉剩余比赛，最终获得 92 分，这超过了除两支球队外所有其他都市球队的最大可能积分。*1 天前瞻：* 如果 WSH 以任何方式赢得最后一场比赛（2 分），他们将获得最后一个（外卡）季后赛席位，超越 DET（唯一的大西洋分区竞争者），而 DET 即使在其最佳情况下也无法超越，因为目前少四个常规比赛取胜 [平局规则 (2)]。*注意：为了简洁，省略了最后六支球队的排名。* *列：当前积分（PTS）、最大可能积分（MAX）、比赛场次（GP）、常规比赛取胜（RW）、加时取胜（OTW）、点球取胜（SOW）、净胜球（DIFF）、进球数（GF）、剩余比赛（GR）和分区（DIV）。*

确定一支球队在接下来 n 天内的比赛出线场景需要考虑这段时间内相关比赛中结果的组合。自然，n 天前瞻问题在实际中算法和计算上更具挑战性。在本文中，我们介绍了一种算法，通过使用自定义树搜索结合基于约束规划（CP）的剪枝方法、预处理技术和节点排序启发式，有效地解决这一挑战。本文介绍的方法也为分析其他成就（包括分区冠军或特定季后赛种子）的出线场景奠定了基础。

本文的贡献如下：

- • 我们引入了一种新颖的“0 天前瞻”方法，利用 CP 和分解，判断球队在某个常规赛积分榜状态下是否已出线。在先前工作的基础上，该方法考虑了自 2019-20 赛季以来使用的广泛的平局规则。
- • 我们引入了一种新颖的“n 天前瞻”算法，用于确定给定目标球队的具体季后赛出线场景，涉及接下来 n 天内将进行的比赛。该方法涉及自定义树搜索，并通过预处理技术、剪枝策略和节点排序启发式进行增强。
- • 我们对 2021-22 至 2024-25 四个 NHL 赛季的方法进行了广泛的基准测试，并针对 NHL 先前发布的场景（对于 n ∈ {0,1}）验证了我们“n 天前瞻”方法的准确性，结果完全匹配。我们报告了算法运行时间、剪枝效率和出线场景复杂度。

我们首先在第 2 节 (https://arxiv.org/html/2605.13142#S2) 中回顾相关文献。在第 3 节 (https://arxiv.org/html/2605.13142#S3) 中，我们引入一个使用约束规划（CP）的“0 天前瞻”子程序，根据当前联盟状态判断球队是否已出线。在第 4 节 (https://arxiv.org/html/2605.13142#S4) 中，我们引入一个使用树搜索的“n 天前瞻”算法，确定在接下来 n 天内哪些比赛结果组合下球队将出线（如有），并在第 5 节 (https://arxiv.org/html/2605.13142#S5) 中展示结果。最后，我们在第 6 节 (https://arxiv.org/html/2605.13142#S6) 中给出结论。

## 2 相关文献

季后赛出线判定问题在许多体育项目中都很常见，并引起了学术界的广泛关注。已有多种体育项目被研究，包括棒球 [schwartz1966possible, robinson1991baseball, wayne2001new, adler2002baseball, kim2024improving]、足球 [ribeiro2005application, lucena2008multi, raack2014standings]、赛车 [donne2012studying, raack2014standings]、（美式）橄榄球 [whittle2014nfl]、篮球 [ito2018calculation, hused2019enhancing, hused2021improving] 以及本工作中的冰球 [russell2008mathematically, russell2009determining, russell2009lessons, russell2010computational, russell2012hybrid]。由于所考虑的体育项目各不相同，这些工作分别解决了问题的不同变体。在给定体育项目中，每个联盟通常需要特别考虑，因为联盟结构、平局规则、积分系统、比赛结果类型和资格标准各不相同。即使考虑同一个联盟，这些因素也可能随着时间而改变，正如 NHL 中多次发生的那样。需要回答的具体问题也有所不同：球队是否已经出线、确保出线所需的积分或胜利数（也称为“魔术数字”或“出线数字”），或者是否已确保某个特定排名。

与我们工作最相关的先前工作是 Russell 和 van Beek 发表的一系列关于 2005-06 和 2006-07 赛季 NHL 出线问题的论文 [russell2008mathematically, russell2009determining, russell2009lessons, russell2010computational, russell2012hybrid]。尽管自那时以来联盟发生了很大变化（30 支球队 vs. 现在的 32 支，6 个分区 vs. 现在的 4 个，联合会前八名资格 vs. 现在的前三名加外卡，3 条平局规则 vs. 现在的 7 条），但这些相关的工作构成了我们方法的基础。在参考文献 [russell2008mathematically] 中，他们提出了一个用于季后赛出线的“0 天前瞻”CP 模型。与我们的 0 天方法（见第 3 节 (https://arxiv.org/html/2605.13142#S3)）不同，该方法迭代求解一系列 CP 模型并在必要时添加无好约束，而他们利用定制的传播算法和支配规则。在后续工作中 [russell2009lessons, russell2009determining]，他们提出了一个优化模型，确定球队必须获得的最低积分才能出线，以及球队可以获得但仍无法获得季后赛资格的最高积分。最后，在参考文献 [russell2012hybrid] 中，他们扩展了早期的工作，提出了一种基于 CP、枚举、网络流和分解的方法，用于计算所需积分（或接近出线）。我们的工作在多个关键方面与这些先前工作有所不同。首先，我们的方法针对现代联盟结构和显著不同的平局规则（见表 1 (https://arxiv.org/html/2605.13142#S1.T1)）进行了定制，并引入了一个新颖的进球分配模型来满足这一要求。其次，遵循 NHL 自身发布的季后赛出线“前瞻”场景，我们的工作在早期工作的基础上，确定了更详细的未来结果：在接下来 n 天内发生的比赛的具体结果，这些结果将导致特定球队出线（如有）。最后，我们的方法在现代求解器中实现，不依赖于参考文献 [russell2008mathematically] 中至关重要的特殊用途约束传播算法。相反，我们利用相对简单的无好约束生成，并认识到某些平局条件极少被触发。

## 3 0 天前瞻方法

0 天前瞻方法判断所考虑的球队在常规赛某个积分榜状态下是否已出线。它使用基于参考文献 [russell2008mathematically] 的 CP 模型，但方法已进行大幅更新，以适应联盟结构、资格要求和平局规则的显著变化。该方法询问：“球队 k 能否被淘汰？”（从现在起，我们将被测试的球队称为球队 k），并寻找一个剩余比赛的结果分配，导致其被淘汰。如果找到这样一个分配，则该球队尚未出线。相反，如果没有找到，则该球队已出线。这种表述的一个优点是，在大多数场景中，通过提出一个反例，可以快速证明被测试的球队并未出线。此外，约束满足问题比相关的优化问题（例如，“找出球队 k 可能的最差排名”）更方便。对于季后赛出线，检查球队 k 的最坏情况就足够了。如果在最坏情况下没有淘汰场景，那么在任何更好的场景中也不会有。例如，我们利用这一假设，假设所有与球队 k 比赛的球队都在常规时间获胜，从而获得两分，而球队 k 得零分。完整的 0 天前瞻方法如图 1 (https://arxiv.org/html/2605.13142#S3.F1) 所示，包括三个主要模块：i）胜利分配模型，ii）平局组评估，和 iii）目标