A Constraint Programming Approach for $n$-Day Lookahead Playoff Clinching

技術概要：NHL における n 日間先読みによるプレーオフ進出確定の制約プログラミングアプローチ

問題定義
本論文は、ナショナル・ホッケー・リーグ（NHL）における「プレーオフ進出確定」シナリオの決定という計算上の課題に取り組む。チームが「確定」したとは、残りの試合の結果に関わらずポストシーズン出場が保証されることを指す。シーズン現在の状態（0 日間先読み）に基づいてチームが確定したかどうかを判断することは既知の NP 完全な組み合わせ問題であるが、著者らはこれを「n 日間先読み」へと拡張する。これは、今後 n 日間の試合結果の特定の組み合わせを特定し、それがチームのプレーオフ出場を保証するかどうかを明らかにするものである。

この問題は、NHL の複雑な出場資格構造（2 つのカンファレンス、各カンファレンスに 2 つのディビジョン、各ディビジョン上位 3 位が直接出場、各カンファレンスに 2 つのワイルドカード）と、ポイント率からゴール差、得点までに至る 7 つの階層的なタイブレーカーの広範なリストによって複雑化している。将来の試合を考慮すると、可能な試合結果の種類（6 種類：レギュレーション勝利、オーバータイム勝利、シュートアウト勝利、シュートアウト敗退、オーバータイム敗退、レギュレーション敗退）の数に応じて探索空間が指数関数的に増大するため、複雑性は著しく高まる。

手法
著者らは、制約プログラミング（CP）とカスタム木探索アルゴリズムを組み合わせた 2 段階のアプローチを提案する。

1. 0 日間先読みサブルーチン（CP モデル）：
   このアプローチの中核は、特定のチーム（k）が数学的に排除されるかどうかを決定するように設計された CP ベースのモデルである。このモデルは、チーム k が出場を逃すような、残りの全試合の結果割り当てという「反例」を検索する。そのような割り当てが存在しない場合、そのチームは確定したとみなされる。

   • 勝利割り当てモデル： この初期段階では、試合結果（勝利/敗退）を割り当ててポイント数と勝利数を決定する。チーム k に対して「最悪のケース」（残りの全試合をレギュレーションで敗退する）という仮定を組み込み、確定の難易度を最大化する。これは、順位を表すバイナリ変数を使用し、タイブレーカー（1）から（4）までを直接処理する。
   • タイグループ評価と遅延制約： タイブレーカー（4）まで残るタイが発生する場合、モデルは順位を仮定する「推測」変数（$u_{ij}$）を使用する。ソルバーの推測が実際の直接対決ポイント（タイブレーカー 5）と矛盾する場合、その特定の順位推測を除外する「ノーグッド」制約が生成され、ソルバーに代替解の探索を強制する。
   • ゴール割り当てモデル： 潜在的な排除シナリオがタイブレーカー（5）まで残るタイを含む場合、二次的な CP モデルがトリガーされる。このモデルは、特定のゴールスコアを試合に割り当て、そのタイがゴール差（タイブレーカー 6）または得点（タイブレーカー 7）によって打破可能かどうかを検証する。このモデルは、計算オーバーヘッドを避けるため、必要な場合のみ構築される。

2. n 日間先読みアルゴリズム（木探索）：
   今後 n 日間の確定シナリオを決定するため、著者らはノードが特定の試合結果を表す木探索を採用する。

   • プレソルブフェーズ： 探索前に、アルゴリズムはチームが「不可能なほど楽観的」な最善のシナリオで確定できるか、あるいは「不可能なほど悲観的」な最悪のシナリオで排除されるかをチェックする。答えが決定的であれば、探索はスキップされる。
   • 木トラバースと枝刈り： アルゴリズムは、試合、ノード、推論アルゴリズムに対する高度な順序付けヒューリスティックを用いた、キューベースの探索（主に深さ優先）を使用する。
   • 枝刈り戦略： 探索は 0 日間 CP サブルーチンを用いて大幅に枝刈りされる。ノードがチーム k が確定した状態を表す場合、すべての子ノード（さらに先の結果）が枝刈りされる。チームが排除された場合、そのノードとその子ノードが枝刈りされる。
   • サイドウェイ枝刈り： 主要な効率向上は「サイドウェイ枝刈り」から得られる。試合結果をチーム k への影響度で順序付け可能（例：レギュレーション勝利はオーバータイム勝利よりも厳密に優位）であり、特定の結果が確定に至る場合、探索木内の右側にあるすべての「より強い」結果も、同じ結果に至るため枝刈りされる。

主な貢献

• 新規の 0 日間アプローチ： 本論文は、現代の NHL 構造（2019-20 年以降のルール）に合わせて更新された CP モデルを導入し、分解戦略（勝利割り当て対ゴール割り当て）と遅延制約生成を活用して、複雑なタイブレーカーを効率的に処理する。
• 新規の n 日間アルゴリズム： 具体的な n 日間先読みシナリオを決定するカスタム木探索アルゴリズムを提示する。このアプローチは、プリプロセッシング、枝刈り戦略、ノード順序付けヒューリスティックを組み合わせて、将来の試合結果の組み合わせ爆発を管理する。
• 検証とベンチマーク： 手法は、4 シーズン（2021-22 から 2024-25）にわたる $n \in \{0, 1\}$ に対する公式の NHL シナリオに対して検証され、完全な一致を示した。著者らは、実行時間、枝刈りの有効性、シナリオの複雑性について報告している。

結果

• 精度： アルゴリズムは、テストされたシーズンにおいて NHL が発表したすべての公式の 0 日間および 1 日間の確定シナリオを正常に再現した。
• パフォーマンス：
  • 0 日間： 解決時間は一般的に低く、プレーオフ争いが熾烈になるシーズンの半ばでピークに達する。
  • 1 日間： アルゴリズムは高い枝刈り効率（しばしば 1.0 に近い）を示し、可能な全試合結果の組み合わせの非常に小さな割合しか探索しない。ただし、解決時間は大きく変動する可能性がある。最も複雑なシナリオ（2023 年 3 月のボストン・ブルーインズ）は 25,000 秒以上を要し、27 個のリテラルを含んでいた。
  • n > 1： 2024-25 シーズンにおいて $n=2$ および $n=3$ に対してアルゴリズムがテストされた。多くのケースで計算上可能であるが、必要な時間は関連する試合の数とともに指数関数的に増大する。$n=3$ のシナリオは、30 分タイムアウト内で解けた場合でも、65 個までのリテラルを含む複雑な出力となり、ステークホルダーにとって解釈が困難であった。
• モデルの使用： ゴール割り当てモデルと遅延制約は、特定のタイブレークシナリオでのみ稀に呼び出されるが、呼び出された際には正確性のために決定的に重要である。

意義
本論文は、その主な貢献として、NHL の複雑なタイブレーク規則により誤りやすくなってきた手動による確定シナリオの決定に対する、自動化され、数学的に厳密で、計算的に効率的な代替手段を提供することを主張している。これらの手法により、ファン、マーケティング担当者、チームなどのステークホルダーは、チームが近未来に確定する条件を正確に理解できるようになる。著者らは、このアプローチは NHL に特化しているが、基礎となる CP と木探索の技術は、他のスポーツ、異なる出場資格指標（ディビジョンタイトル、プレジデントズ・トロフィーなど）、または他のシード固有の確定シナリオに適応するのに十分汎用性があると指摘している。この研究は、特に先読みウィンドウ（$n$）が増大するにつれて、計算の複雑さと結果のシナリオの解釈可能性との間のトレードオフを浮き彫りにしている。