Каждый год в конце регулярного сезона НХЛ болельщики задаются вопросом: гарантировала ли их команда выход в плей-офф? Ответ часто неочевиден из-за сложных правил тай-брейков и множества оставшихся матчей. Инженеры AWS Generative ИИ Innovation Center разработали автоматизированную систему, которая решает эту задачу с помощью constraint programming (CP) и кастомного поиска по дереву. Результаты, опубликованные в научной статье, показывают, что система точно воспроизводит официальные сценарии НХЛ.
Чтобы понять суть задачи, нужно разобраться в правилах. В НХЛ 32 команды, разделенные на две конференции и четыре дивизиона. В плей-офф выходят 16 команд: по три лучших из каждого дивизиона и по две wild-card команды из каждой конференции. Каждая игра имеет шесть возможных исходов с точки зрения команды: победа в основное время (RW), победа в овертайме (OTW), победа по буллитам (SOW), поражение по буллитам (SOL), поражение в овертайме (OTL) и поражение в основное время (RL). За победу дается 2 очка, за поражение в овертайме или по буллитам — 1 очко, за поражение в основное время — 0. При равенстве очков применяется каскад из семи тай-брейков, начиная с процента набранных очков и заканчивая забитыми голами. Именно эти сложные правила делают задачу вычислительно трудной.
Разработанная система состоит из двух компонентов. Первый — 0-day solver, который отвечает на вопрос, гарантировала ли команда выход в плей-офф при текущем положении. Он формулирует задачу как проблему выполнимости: можно ли найти такие исходы всех оставшихся матчей, при которых команда не попадает в плей-офф? Если такого сценария не существует, команда квалифицировалась. Для решения используется CP-SAT солвер из Google OR-Tools, который учитывает все правила тай-брейков. Второй компонент — n-day lookahead solver, который определяет, какие исходы игр ближайших n дней приведут к квалификации. Он использует кастомный поиск по дереву, где каждый уровень соответствует игре, а каждый узел — конкретному исходу. На каждом узле вызывается 0-day solver, чтобы проверить, достаточны ли накопленные результаты. Для ускорения применяются предварительная обработка, стратегии отсечения и эвристики упорядочивания узлов.
Система включает 0-day solver и n-day lookahead solver, которые учитывают все правила тай-брейков лиги.
Система была проверена на данных четырех сезонов НХЛ (2021–22 по 2024–25), взятых из публичного API лиги. Все сгенерированные сценарии полностью совпали с официально опубликованными НХЛ. Медианное время расчета 1-дневных сценариев составило порядка минут, что значительно быстрее ручных методов, которые становятся все более трудоемкими и подверженными ошибкам по мере усложнения правил. Этот подход демонстрирует, как методы ИИ и оптимизации могут применяться в спортивной аналитике для решения задач, которые ранее требовали значительных ручных усилий.