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

Sintesi Tecnica: Un Approccio di Programmazione a Vincoli per la Determinazione della Qualificazione ai Playoff con Previsione di n Giorni nella NHL

Definizione del Problema
Il documento affronta la sfida computazionale di determinare gli scenari di "qualificazione ai playoff" nella National Hockey League (NHL). Si dice che una squadra abbia "assicurato la qualificazione" se le è garantito un posto nei playoff indipendentemente dagli esiti di tutte le partite rimanenti. Sebbene determinare se una squadra abbia assicurato la qualificazione basandosi sullo stato attuale della stagione (previsione a 0 giorni) sia un noto problema combinatorio NP-completo, gli autori estendono questo concetto alla "previsione di n giorni". Ciò comporta l'identificazione delle combinazioni specifiche di esiti delle partite nei successivi $n$ giorni che garantiscono la qualificazione ai playoff di una squadra.

Il problema è complicato dalla complessa struttura di qualificazione della NHL (due conferenze, due divisioni per conferenza, i primi tre classificati di ogni divisione qualificati, e due wild card per conferenza) e da un'estesa, gerarchica lista di sette criteri di spareggio (che vanno dalla percentuale di punti alla differenza reti e ai gol segnati). La complessità aumenta significativamente quando si considerano le partite future, poiché lo spazio di ricerca cresce esponenzialmente con il numero di possibili esiti delle partite (sei tipi: vittoria nei tempi regolamentari, vittoria ai tempi supplementari, vittoria ai tiri di rigore, sconfitta ai tiri di rigore, sconfitta ai tempi supplementari, sconfitta nei tempi regolamentari).

Metodologia
Gli autori propongono un approccio in due fasi che combina la Programmazione a Vincoli (CP) e un algoritmo di ricerca ad albero personalizzato.

1. Sottoprogramma di Previsione a 0 Giorni (Modello CP):
   Il nucleo dell'approccio è un modello basato su CP progettato per determinare se una specifica squadra ($k$) può essere matematicamente eliminata. Il modello cerca un "controesempio"—un assegnazione di esiti a tutte le partite rimanenti in cui la squadra $k$ non riesce a qualificarsi. Se tale assegnazione non esiste, la squadra ha assicurato la qualificazione.

   • Modello di Assegnazione delle Vittorie: Questa fase iniziale assegna gli esiti delle partite (vittorie/sconfitte) per determinare i punti e il numero di vittorie. Incorpora assunzioni di "caso peggiore" per la squadra $k$ (perdita di tutte le partite rimanenti nei tempi regolamentari) per massimizzare la difficoltà della qualificazione. Utilizza variabili binarie per rappresentare le classifiche e gestisce direttamente i criteri di spareggio (1) attraverso (4).
   • Valutazione dei Gruppi di Pari Punteggio e Vincoli Lazy: Per i pareggi che persistono oltre il criterio di spareggio (4), il modello utilizza variabili "di ipotesi" ($u_{ij}$) per ipotizzare le classifiche. Se l'ipotesi del risolutore entra in conflitto con i punti reali testa a testa (criterio di spareggio 5), viene generato un vincolo "no-good" per escludere quella specifica ipotesi di classifica, costringendo il risolutore a esplorare soluzioni alternative.
   • Modello di Assegnazione dei Gol: Se uno scenario di potenziale eliminazione coinvolge pareggi che persistono oltre il criterio di spareggio (5), viene attivato un modello CP secondario. Questo modello assegna punteggi specifici di gol alle partite per verificare se il pareggio può essere risolto dalla differenza reti (criterio di spareggio 6) o dai gol segnati (criterio di spareggio 7). Questo modello viene costruito solo quando necessario per evitare sovraccarichi computazionali.

2. Algoritmo di Previsione di n Giorni (Ricerca ad Albero):
   Per determinare gli scenari di qualificazione nei prossimi $n$ giorni, gli autori impiegano una ricerca ad albero in cui i nodi rappresentano esiti specifici delle partite.

   • Fase di Presoluzione: Prima di iniziare la ricerca, l'algoritmo verifica se la squadra può assicurarsi la qualificazione in uno scenario di "caso migliore" impossibilmente ottimistico o se è eliminata in uno scenario di "caso peggiore" impossibilmente pessimistico. Se la risposta è definitiva, la ricerca viene saltata.
   • Attraversamento dell'Albero e Potatura: L'algoritmo utilizza una ricerca basata su code (principalmente in profondità) con euristiche di ordinamento sofisticate per le partite, i nodi e gli algoritmi di inferenza.
   • Strategie di Potatura: La ricerca è pesantemente potata utilizzando il sottoprogramma CP a 0 giorni. Se un nodo rappresenta uno stato in cui la squadra $k$ ha assicurato la qualificazione, tutti i nodi figli (ulteriori esiti) vengono potati. Se la squadra è eliminata, il nodo e i suoi figli vengono potati.
   • Potatura Laterale: Un guadagno chiave di efficienza deriva dalla "potatura laterale". Se gli esiti delle partite possono essere ordinati in base al loro impatto sulla squadra $k$ (ad esempio, una vittoria nei tempi regolamentari è strettamente migliore di una vittoria ai tempi supplementari), e un esito specifico porta alla qualificazione, tutti gli esiti "più forti" a destra nell'albero di ricerca vengono anch'essi potati poiché porterebbero allo stesso risultato.

Contributi Chiave

• Approccio Innovativo a 0 Giorni: Il documento introduce un modello CP aggiornato per la struttura moderna della NHL (regole post-2019-20), utilizzando una strategia di decomposizione (assegnazione delle vittorie vs assegnazione dei gol) e la generazione di vincoli lazy per gestire in modo efficiente complessi criteri di spareggio.
• Algoritmo Innovativo di Previsione di n Giorni: Presenta un algoritmo di ricerca ad albero personalizzato che determina scenari concreti di previsione di n giorni. Questo approccio combina pre-elaborazione, strategie di potatura ed euristiche di ordinamento dei nodi per gestire l'esplosione combinatoria degli esiti delle partite future.
• Validazione e Benchmarking: I metodi sono stati validati contro scenari ufficiali della NHL per $n \in \{0, 1\}$ su quattro stagioni (dal 2021-22 al 2024-25), mostrando corrispondenze esatte. Gli autori riportano tempi di esecuzione, efficacia della potatura e complessità degli scenari.

Risultati

• Accuratezza: L'algoritmo ha riprodotto con successo tutti gli scenari ufficiali di qualificazione a 0 e 1 giorno pubblicati dalla NHL per le stagioni testate.
• Prestazioni:
  • 0 Giorni: I tempi di risoluzione sono generalmente bassi, con picchi a metà stagione quando le gare per i playoff sono serrate.
  • 1 Giorno: L'algoritmo dimostra un'elevata efficienza di potatura (spesso vicina a 1,0), il che significa che esplora una frazione molto piccola delle combinazioni totali di esiti delle partite possibili. Tuttavia, i tempi di risoluzione possono variare significativamente; lo scenario più complesso (Boston Bruins, marzo 2023) ha richiesto oltre 25.000 secondi e ha coinvolto 27 letterali.
  • n > 1: L'algoritmo è stato testato per $n=2$ e $n=3$ sulla stagione 2024-25. Sebbene computazionalmente fattibile per molti casi, il tempo richiesto scala esponenzialmente con il numero di partite rilevanti. Gli scenari con $n=3$ hanno spesso prodotto output complessi (fino a 65 letterali) difficili da interpretare per gli stakeholder, anche quando risolvibili entro un timeout di 30 minuti.
• Utilizzo del Modello: Il modello di assegnazione dei gol e i vincoli lazy vengono invocati raramente (solo in specifici scenari di spareggio) ma sono critici per la correttezza quando invocati.

Significato
Il documento afferma che il suo contributo principale è fornire un'alternativa automatizzata, matematicamente rigorosa e computazionalmente efficiente alla determinazione manuale degli scenari di qualificazione, diventata sempre più soggetta a errori a causa delle complesse regole di spareggio della NHL. I metodi permettono agli stakeholder (tifosi, marketer, squadre) di comprendere precisamente in quali condizioni una squadra assicurerà la qualificazione nel prossimo futuro. Gli autori notano che, sebbene l'approccio sia adattato alla NHL, le tecniche sottostanti di CP e ricerca ad albero sono abbastanza generali da poter essere adattate ad altri sport, diverse metriche di qualificazione (ad esempio, titoli di divisione, Trofeo del Presidente) o altri scenari di qualificazione specifici per il seeding. Il lavoro evidenzia il compromesso tra complessità computazionale e interpretabilità degli scenari risultanti, in particolare all'aumentare della finestra di previsione ($n$).