AWS、制約プログラミングを活用してNHLのプレーオフ進出確定条件を自動算出するシステムを発表
要点
-
AWSのGenerative AI Innovation Centerは、北米プロアイスホッケーリーグ（NHL）のプレーオフ進出確定シナリオを自動算出するシステムを構築した。
-
制約プログラミング（CP）と独自の木探索を組み合わせ、Google OR-ToolsのCP-SATソルバーを用いて複雑な組み合わせ問題を解決している。
-
32チームが争うリーグの残り試合と7段階に及ぶタイブレーク規定を網羅し、算出結果はNHLの公式発表データと照合して検証された。
-
システムの中核となる「0-dayソルバー」は、対象チームが予選落ちする試合結果パターンが存在するかを判定する充足可能性問題として定式化されている。
-
本取り組みの詳細なアプローチは学術論文としてまとめられ、arXiv上で公開されている。
-
米Amazon Web Services（AWS）のGenerative AI Innovation Centerは、北米プロアイスホッケーリーグ（NHL）におけるプレーオフ進出確定シナリオ（クリンチ条件）を自動算出する仕組みを開発したと発表した。制約プログラミングと独自の木探索技術を組み合わせることで、複雑な順位決定ルールに対応した厳密な数学的アプローチを実現したという。研究の成果は論文としてarXivで公開されている。
複雑化するNHLのプレーオフ進出条件の背景
NHLのレギュラーシーズン終盤となる毎年3月頃から、ファンの間では応援するチームがプレーオフ進出を決めたかどうかが大きな関心事となる。リーグ側もこれに合わせて、その日の試合結果によって進出が決まるシナリオを連日発表している。
しかし、この進出確定（クリンチ）の判定は計算上極めて難度が高い課題となっている。NHLは全32チームで構成され、東と西の2つのカンファレンス、さらにそれぞれ2つのディビジョンに分かれている。プレーオフに進出できるのは合計16チームで、各ディビジョンの上位3チーム（計12チーム）と、各カンファレンスで残る上位2チームの「ワイルドカード」（計4チーム）が進出枠を獲得する。
各試合は必ず勝敗が決まる仕組みになっており、試合結果はチーム視点で以下の6通りに分類される。
- レギュレーション勝ち（RW）
- 延長戦勝ち（OTW）
- シュートアウト勝ち（SOW）
- シュートアウト負け（SOL）
- 延長戦負け（OTL）
- レギュレーション負け（RL）
獲得ポイントは、勝利した場合は結果の種類によらず2ポイント、延長戦やシュートアウトでの敗戦は1ポイント、規定時間内（レギュレーション）での敗戦は0ポイントとなる。
さらに、シーズン終了時に勝ち点で並んだ場合の順位決定ルール（タイブレーク）として、以下の7段階に及ぶ条件が順番に適用される。
- 勝率（消化試合数の少なさ）
- レギュレーションでの勝利数
- レギュレーションおよび延長戦での勝利数の合計
- 総勝利数
- 直接対決での獲得ポイント
- シュートアウト決定弾を含む得失点差
- シュートアウト決定弾を含む総得点
シーズン終盤には数百の未消化試合が残されている場合もあり、これら無数の試合結果の組み合わせと7段階のタイブレーク条件を人手で計算して進出確定条件を導き出す作業は、多大な時間を要しミスも起こりやすい状態になっていた。
制約プログラミングによるアプローチ
AWSの研究チームは、この課題を解決するために「0-dayソルバー」と「n-day先読みソルバー」という2つの主要コンポーネントからなる自動化システムを構築した。
システムの土台となる0-dayソルバーは、「現在の順位表において、対象のチームがすでにプレーオフ進出を確定させているか」を判定する役割を担う。これを実現するため、問題を充足可能性問題（Feasibility Problem、与えられた制約をすべて満たす解が存在するかを判定する問題）として定式化している。
具体的には、「残りの全試合において、対象チームがプレーオフ進出を逃すような試合結果の組み合わせが存在するか」を探索する。もしそのようなシナリオが1つも存在しないと証明されれば、そのチームは残りの試合がどのような結果になろうとも進出が確定（クリンチ）したと判断できる。
この制約充足モデルの求解には、Googleが提供するオープンソースの最適化スイート「Google OR-Tools」に含まれるCP-SATソルバーが使用されている。このソルバーにより、NHLの複雑なタイブレーク規定を余すところなく組み込んだ厳密な計算を高速に実行できるとしている。
公式データとの照合による検証
研究チームは、本システムによって導き出された進出確定シナリオをNHLが公式に発表した記録と照合し、その正確性を検証したと説明している。数学的に厳密なモデルを構築したことで、日々の運用に耐えうる処理効率と正確性を両立させた。
なお、本手法の数理モデルやアルゴリズムの詳細については、研究チームが執筆した学術論文（arXiv: 2605.13142）にまとめられている。