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

Resumo Técnico: Uma Abordagem de Programação por Restrições para o Aferimento de Classificação para os Playoffs com Previsão de n Dias na NHL

Definição do Problema
O artigo aborda o desafio computacional de determinar cenários de "classificação para os playoffs" (playoff clinching) na National Hockey League (NHL). Diz-se que uma equipe "classificou-se" se estiver garantida uma vaga na pós-temporada, independentemente dos resultados de quaisquer jogos remanescentes. Embora determinar se uma equipe se classificou com base no estado atual da temporada (previsão de 0 dias) seja um problema combinatório conhecido como NP-Completo, os autores estendem isso para "previsão de n dias". Isso envolve identificar as combinações específicas de resultados de jogos nos próximos $n$ dias que garantem a qualificação de uma equipe para os playoffs.

O problema é complicado pela complexa estrutura de qualificação da NHL (duas conferências, duas divisões por conferência, três classificados por divisão e dois wild cards por conferência) e por uma extensa lista hierárquica de sete critérios de desempate (variando de porcentagem de pontos a diferença de gols e gols marcados). A complexidade aumenta significativamente ao considerar jogos futuros, pois o espaço de busca cresce exponencialmente com o número de resultados possíveis de jogos (seis tipos: vitória na regulamentação, vitória na prorrogação, vitória no shoot-out, derrota no shoot-out, derrota na prorrogação, derrota na regulamentação).

Metodologia
Os autores propõem uma abordagem em duas etapas, combinando Programação por Restrições (CP) e um algoritmo de busca em árvore personalizado.

1. Sub-rotina de Previsão de 0 Dias (Modelo CP):
   O núcleo da abordagem é um modelo baseado em CP projetado para determinar se uma equipe específica ($k$) pode ser matematicamente eliminada. O modelo busca um "contra-exemplo" — uma atribuição de resultados a todos os jogos remanescentes onde a equipe $k$ falha em se classificar. Se tal atribuição não existir, a equipe se classificou.

   • Modelo de Atribuição de Vitórias: Esta fase inicial atribui resultados de jogos (vitórias/derrotas) para determinar pontos e contagens de vitórias. Incorpora suposições de "pior caso" para a equipe $k$ (perder todos os jogos remanescentes na regulamentação) para maximizar a dificuldade da classificação. Utiliza variáveis binárias para representar classificações e lida diretamente com os critérios de desempate (1) através de (4).
   • Avaliação de Grupos de Empate e Restrições Preguiçosas (Lazy Constraints): Para empates que persistem após o critério de desempate (4), o modelo utiliza variáveis de "palpite" ($u_{ij}$) para hipotetizar classificações. Se o palpite do solver conflitar com os pontos reais no confronto direto (critério de desempate 5), uma restrição "no-good" é gerada para excluir essa hipótese específica de classificação, forçando o solver a explorar soluções alternativas.
   • Modelo de Atribuição de Gols: Se um cenário potencial de eliminação envolver empates que persistem após o critério de desempate (5), um modelo secundário de CP é acionado. Este modelo atribui placares específicos de gols aos jogos para verificar se o empate pode ser quebrado pela diferença de gols (critério de desempate 6) ou por gols marcados (critério de desempate 7). Este modelo é construído apenas quando necessário para evitar sobrecarga computacional.

2. Algoritmo de Previsão de n Dias (Busca em Árvore):
   Para determinar cenários de classificação nos próximos $n$ dias, os autores empregam uma busca em árvore onde os nós representam resultados específicos de jogos.

   • Fase de Presolução: Antes de buscar, o algoritmo verifica se a equipe pode se classificar em um cenário de "melhor caso" impossivelmente otimista ou se está eliminada em um cenário de "pior caso" impossivelmente pessimista. Se a resposta for definitiva, a busca é omitida.
   • Travessia da Árvore e Poda: O algoritmo utiliza uma busca baseada em fila (principalmente em profundidade) com heurísticas sofisticadas de ordenação para jogos, nós e algoritmos de inferência.
   • Estratégias de Poda: A busca é fortemente podada usando a sub-rotina CP de 0 dias. Se um nó representar um estado onde a equipe $k$ se classificou, todos os nós filhos (resultados adicionais) são podados. Se a equipe estiver eliminada, o nó e seus filhos são podados.
   • Poda Lateral: Um ganho chave de eficiência vem da "poda lateral". Se os resultados dos jogos puderem ser ordenados por seu impacto na equipe $k$ (por exemplo, uma Vitória na Regulamentação é estritamente melhor que uma Vitória na Prorrogação), e um resultado específico levar a uma classificação, todos os resultados "mais fortes" à direita na árvore de busca também são podados, pois levariam ao mesmo resultado.

Principais Contribuições

• Abordagem Inovadora de 0 Dias: O artigo introduz um modelo CP atualizado para a estrutura moderna da NHL (regras pós-2019-20), utilizando uma estratégia de decomposição (atribuição de vitórias vs. atribuição de gols) e geração de restrições preguiçosas para lidar com critérios de desempate complexos de forma eficiente.
• Algoritmo Inovador de n Dias: Apresenta um algoritmo de busca em árvore personalizado que determina cenários concretos de previsão de $n$ dias. Esta abordagem combina pré-processamento, estratégias de poda e heurísticas de ordenação de nós para gerenciar a explosão combinatória de resultados futuros de jogos.
• Validação e Benchmarking: Os métodos são validados contra cenários oficiais da NHL para $n \in \{0, 1\}$ em quatro temporadas (2021-22 a 2024-25), mostrando correspondências exatas. Os autores relatam sobre tempo de execução, eficácia da poda e complexidade dos cenários.

Resultados

• Precisão: O algoritmo reproduziu com sucesso todos os cenários oficiais de classificação de 0 e 1 dia publicados pela NHL para as temporadas testadas.
• Desempenho:
  • 0 Dias: Os tempos de resolução são geralmente baixos, atingindo o pico no meio da temporada quando as corridas pelos playoffs estão acirradas.
  • 1 Dia: O algoritmo demonstra alta eficiência de poda (frequentemente próxima de 1,0), o que significa que explora uma fração muito pequena das combinações totais possíveis de resultados de jogos. No entanto, os tempos de resolução podem variar significativamente; o cenário mais complexo (Boston Bruins, março de 2023) exigiu mais de 25.000 segundos e envolveu 27 literais.
  • n > 1: O algoritmo foi testado para $n=2$ e $n=3$ na temporada 2024-25. Embora computacionalmente viável para muitos casos, o tempo necessário escala exponencialmente com o número de jogos relevantes. Cenários com $n=3$ frequentemente resultaram em saídas complexas (até 65 literais) que foram difíceis de interpretar para as partes interessadas, mesmo quando solucionáveis dentro de um limite de tempo de 30 minutos.
• Uso do Modelo: O modelo de atribuição de gols e as restrições preguiçosas são invocados raramente (apenas em cenários específicos de desempate), mas são críticos para a correção quando invocados.

Significado
O artigo afirma que sua principal contribuição é fornecer uma alternativa automatizada, matematicamente rigorosa e computacionalmente eficiente à determinação manual de cenários de classificação, que se tornou cada vez mais propensa a erros devido às complexas regras de desempate da NHL. Os métodos permitem que as partes interessadas (torcedores, profissionais de marketing, equipes) compreendam precisamente sob quais condições uma equipe se classificará no futuro próximo. Os autores observam que, embora a abordagem seja adaptada à NHL, as técnicas subjacentes de CP e busca em árvore são suficientemente gerais para serem adaptadas a outros esportes, diferentes métricas de qualificação (por exemplo, títulos de divisão, Troféu Presidencial) ou outros cenários de classificação específicos de sementes. O trabalho destaca o compromisso entre complexidade computacional e a interpretabilidade dos cenários resultantes, particularmente à medida que a janela de previsão ($n$) aumenta.