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

Resumen Técnico: Un Enfoque de Programación por Restricciones para el Aseguramiento de Playoffs con Perspectiva de n Días en la NHL

Definición del Problema
El artículo aborda el desafío computacional de determinar escenarios de "aseguramiento de playoffs" (playoff clinching) en la Liga Nacional de Hockey (NHL). Se dice que un equipo ha "asegurado" su plaza si garantiza un puesto en la postemporada independientemente de los resultados de cualquier partido restante. Si bien determinar si un equipo ha asegurado su plaza basándose en el estado actual de la temporada (perspectiva de 0 días) es un conocido problema combinatorio NP-Completo, los autores lo extienden a una "perspectiva de n días". Esto implica identificar las combinaciones específicas de resultados de partidos en los próximos $n$ días que garantizan la clasificación de un equipo a los playoffs.

El problema se complica por la estructura compleja de clasificación de la NHL (dos conferencias, dos divisiones por conferencia, clasificadores de los tres primeros lugares de cada división y dos comodines por conferencia) y una extensa lista jerárquica de siete desempates (que van desde el porcentaje de puntos hasta la diferencia de goles y los goles anotados). La complejidad aumenta significativamente al considerar partidos futuros, ya que el espacio de búsqueda crece exponencialmente con el número de resultados posibles de partidos (seis tipos: victoria en tiempo reglamentario, victoria en tiempo extra, victoria en tanda de penales, derrota en tanda de penales, derrota en tiempo extra, derrota en tiempo reglamentario).

Metodología
Los autores proponen un enfoque de dos etapas que combina Programación por Restricciones (CP) y un algoritmo de búsqueda en árbol personalizado.

1. Subrutina de Perspectiva de 0 Días (Modelo CP):
   El núcleo del enfoque es un modelo basado en CP diseñado para determinar si un equipo específico ($k$) puede ser matemáticamente eliminado. El modelo busca un "contraejemplo": una asignación de resultados a todos los partidos restantes donde el equipo $k$ falla en clasificarse. Si no existe tal asignación, el equipo ha asegurado su plaza.

   • Modelo de Asignación de Victorias: Esta fase inicial asigna resultados de partidos (victorias/derrotas) para determinar puntos y conteos de victorias. Incorpora supuestos de "peor caso" para el equipo $k$ (perder todos los partidos restantes en tiempo reglamentario) para maximizar la dificultad de asegurar la plaza. Utiliza variables binarias para representar clasificaciones y maneja los desempates (1) a (4) directamente.
   • Evaluación de Grupos de Empate y Restricciones Perezosas: Para empates que persisten más allá del desempate (4), el modelo utiliza variables de "suposición" ($u_{ij}$) para hipotetizar clasificaciones. Si la suposición del solucionador entra en conflicto con los puntos reales de enfrentamiento directo (desempate 5), se genera una restricción "no-good" para excluir esa suposición de clasificación específica, forzando al solucionador a explorar soluciones alternativas.
   • Modelo de Asignación de Goles: Si un escenario de eliminación potencial involucra empates que persisten más allá del desempate (5), se activa un modelo CP secundario. Este modelo asigna puntuaciones de goles específicas a los partidos para verificar si el empate puede resolverse mediante la diferencia de goles (desempate 6) o los goles anotados (desempate 7). Este modelo solo se construye cuando es necesario para evitar sobrecarga computacional.

2. Algoritmo de Perspectiva de n Días (Búsqueda en Árbol):
   Para determinar escenarios de aseguramiento en los próximos $n$ días, los autores emplean una búsqueda en árbol donde los nodos representan resultados específicos de partidos.

   • Fase de Presolución: Antes de buscar, el algoritmo verifica si el equipo puede asegurar su plaza en un escenario de "caso mejor imposible" o si está eliminado en un escenario de "peor caso imposible". Si la respuesta es definitiva, se omite la búsqueda.
   • Recorrido del Árbol y Poda: El algoritmo utiliza una búsqueda basada en colas (principalmente en profundidad) con heurísticas de ordenamiento sofisticadas para partidos, nodos y algoritmos de inferencia.
   • Estrategias de Poda: La búsqueda se poda intensamente utilizando la subrutina CP de 0 días. Si un nodo representa un estado donde el equipo $k$ ha asegurado su plaza, todos los nodos hijos (resultados adicionales) se podan. Si el equipo está eliminado, el nodo y sus hijos se podan.
   • Poda Lateral: Una ganancia clave de eficiencia proviene de la "poda lateral". Si los resultados de los partidos pueden ordenarse por su impacto en el equipo $k$ (por ejemplo, una Victoria en Tiempo Reglamentario es estrictamente mejor que una Victoria en Tiempo Extra), y un resultado específico conduce a un aseguramiento, todos los resultados "más fuertes" a la derecha en el árbol de búsqueda también se podan, ya que conducirían al mismo resultado.

Contribuciones Clave

• Enfoque Novel de 0 Días: El artículo introduce un modelo CP actualizado para la estructura moderna de la NHL (reglas posteriores a 2019-20), utilizando una estrategia de descomposición (asignación de victorias frente a asignación de goles) y generación de restricciones perezosas para manejar los complejos desempates de manera eficiente.
• Algoritmo Novel de n Días: Presenta un algoritmo de búsqueda en árbol personalizado que determina escenarios concretos de perspectiva de n días. Este enfoque combina preprocesamiento, estrategias de poda y heurísticas de ordenamiento de nodos para gestionar la explosión combinatoria de resultados futuros de partidos.
• Validación y Pruebas de Referencia: Los métodos se validan frente a escenarios oficiales de la NHL para $n \in \{0, 1\}$ a lo largo de cuatro temporadas (2021-22 a 2024-25), mostrando coincidencias exactas. Los autores informan sobre el tiempo de ejecución, la eficacia de la poda y la complejidad de los escenarios.

Resultados

• Precisión: El algoritmo reprodujo con éxito todos los escenarios oficiales de aseguramiento de 0 días y 1 día publicados por la NHL para las temporadas probadas.
• Rendimiento:
  • 0 Días: Los tiempos de resolución son generalmente bajos, alcanzando un pico a mitad de temporada cuando las carreras por los playoffs están reñidas.
  • 1 Día: El algoritmo demuestra una alta eficiencia de poda (a menudo cercana a 1.0), lo que significa que explora una fracción muy pequeña del total de combinaciones posibles de resultados de partidos. Sin embargo, los tiempos de resolución pueden variar significativamente; el escenario más complejo (Boston Bruins, marzo de 2023) requirió más de 25.000 segundos e involucró 27 literales.
  • n > 1: El algoritmo se probó para $n=2$ y $n=3$ en la temporada 2024-25. Aunque es computacionalmente factible para muchos casos, el tiempo requerido escala exponencialmente con el número de partidos relevantes. Los escenarios con $n=3$ a menudo resultaron en salidas complejas (hasta 65 literales) que fueron difíciles de interpretar para las partes interesadas, incluso cuando eran resolubles dentro de un tiempo de espera de 30 minutos.
• Uso del Modelo: El modelo de asignación de goles y las restricciones perezosas se invocan raramente (solo en escenarios específicos de desempate), pero son críticos para la corrección cuando se invocan.

Significado
El artículo afirma que su contribución principal es proporcionar una alternativa automatizada, matemáticamente rigurosa y computacionalmente eficiente a la determinación manual de escenarios de aseguramiento, la cual se ha vuelto cada vez más propensa a errores debido a las complejas reglas de desempate de la NHL. Los métodos permiten a las partes interesadas (aficionados, comercializadores, equipos) comprender con precisión bajo qué condiciones un equipo asegurará su plaza en el futuro cercano. Los autores señalan que, aunque el enfoque está adaptado a la NHL, las técnicas subyacentes de CP y búsqueda en árbol son lo suficientemente generales para adaptarse a otros deportes, diferentes métricas de clasificación (por ejemplo, títulos de división, Trofeo Presidente) u otros escenarios de aseguramiento específicos de semillas. El trabajo destaca la compensación entre la complejidad computacional y la interpretabilidad de los escenarios resultantes, particularmente a medida que aumenta la ventana de perspectiva ($n$).