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

Résumé technique : Une approche par programmation en contraintes pour la qualification aux séries éliminatoires de la LNH avec anticipation de n jours

Définition du problème
L'article traite du défi computationnel consistant à déterminer les scénarios de « qualification aux séries éliminatoires » (playoff clinching) dans la Ligue nationale de hockey (LNH). Une équipe est dite avoir « assuré sa qualification » si elle garantit une place en séries éliminatoires, indépendamment des résultats de tous les matchs restants. Alors que la détermination du fait qu'une équipe a assuré sa qualification à partir de l'état actuel de la saison (anticipation de 0 jour) est un problème combinatoire connu comme NP-complet, les auteurs étendent cela à une « anticipation de n jours ». Cela implique d'identifier les combinaisons spécifiques de résultats de matchs sur les n prochains jours qui garantissent la qualification d'une équipe pour les séries éliminatoires.

Le problème est compliqué par la structure complexe de qualification de la LNH (deux conférences, deux divisions par conférence, les trois premiers qualifiés par division, et deux wild cards par conférence) et une liste hiérarchique étendue de sept critères de départage (allant du pourcentage de points à l'écart de buts et aux buts marqués). La complexité augmente considérablement lorsqu'on considère les matchs futurs, car l'espace de recherche croît de manière exponentielle avec le nombre de résultats de matchs possibles (six types : victoire en temps réglementaire, victoire en prolongation, victoire aux tirs de fusillade, défaite aux tirs de fusillade, défaite en prolongation, défaite en temps réglementaire).

Méthodologie
Les auteurs proposent une approche en deux étapes combinant la programmation en contraintes (CP) et un algorithme de recherche arborescente personnalisé.

1. Sous-routine d'anticipation de 0 jour (Modèle CP) :
   Le cœur de l'approche est un modèle basé sur la CP conçu pour déterminer si une équipe spécifique ($k$) peut être mathématiquement éliminée. Le modèle recherche un « contre-exemple » — une affectation des résultats à tous les matchs restants où l'équipe $k$ échoue à se qualifier. Si une telle affectation n'existe pas, l'équipe a assuré sa qualification.

   • Modèle d'affectation des victoires : Cette phase initiale attribue les résultats des matchs (victoires/défaites) pour déterminer les points et les nombres de victoires. Elle intègre des hypothèses de « pire cas » pour l'équipe $k$ (perdre tous ses matchs restants en temps réglementaire) afin de maximiser la difficulté d'assurer la qualification. Elle utilise des variables binaires pour représenter les classements et gère directement les critères de départage (1) à (4).
   • Évaluation des groupes d'égalité et contraintes paresseuses : Pour les égalités persistant au-delà du critère de départage (4), le modèle utilise des variables « hypothèses » ($u_{ij}$) pour postuler des classements. Si l'hypothèse du solveur entre en conflit avec les points directs (critère de départage 5), une contrainte « no-good » est générée pour exclure cette hypothèse de classement spécifique, forçant le solveur à explorer des solutions alternatives.
   • Modèle d'affectation des buts : Si un scénario d'élimination potentiel implique des égalités persistant au-delà du critère de départage (5), un modèle CP secondaire est déclenché. Ce modèle attribue des scores de buts spécifiques aux matchs pour vérifier si l'égalité peut être rompue par l'écart de buts (critère de départage 6) ou par les buts marqués (critère de départage 7). Ce modèle n'est construit que lorsque nécessaire pour éviter une surcharge computationnelle.

2. Algorithme d'anticipation de n jours (Recherche arborescente) :
   Pour déterminer les scénarios de qualification sur les n prochains jours, les auteurs emploient une recherche arborescente où les nœuds représentent des résultats de matchs spécifiques.

   • Phase de pré-résolution : Avant la recherche, l'algorithme vérifie si l'équipe peut assurer sa qualification dans un scénario de « meilleur cas » impossiblement optimiste ou si elle est éliminée dans un scénario de « pire cas » impossiblement pessimiste. Si la réponse est définitive, la recherche est ignorée.
   • Parcours de l'arbre et élagage : L'algorithme utilise une recherche basée sur une file d'attente (principalement en profondeur d'abord) avec des heuristiques de classement sophistiquées pour les matchs, les nœuds et les algorithmes d'inférence.
   • Stratégies d'élagage : La recherche est fortement élaguée en utilisant la sous-routine CP d'anticipation de 0 jour. Si un nœud représente un état où l'équipe $k$ a assuré sa qualification, tous les nœuds enfants (résultats ultérieurs) sont élagués. Si l'équipe est éliminée, le nœud et ses enfants sont élagués.
   • Élagage latéral : Un gain d'efficacité clé provient de l'« élagage latéral ». Si les résultats de matchs peuvent être ordonnés par leur impact sur l'équipe $k$ (par exemple, une victoire en temps réglementaire est strictement meilleure qu'une victoire en prolongation), et qu'un résultat spécifique mène à une qualification, tous les résultats « plus forts » à droite dans l'arbre de recherche sont également élagués car ils conduiraient au même résultat.

Contributions clés

• Nouvelle approche d'anticipation de 0 jour : L'article introduit un modèle CP mis à jour pour la structure moderne de la LNH (règles post-2019-20), utilisant une stratégie de décomposition (affectation des victoires vs affectation des buts) et une génération de contraintes paresseuses pour gérer efficacement les critères de départage complexes.
• Nouvel algorithme d'anticipation de n jours : Il présente un algorithme de recherche arborescente personnalisé qui détermine des scénarios concrets d'anticipation de n jours. Cette approche combine prétraitement, stratégies d'élagage et heuristiques de classement des nœuds pour gérer l'explosion combinatoire des résultats de matchs futurs.
• Validation et benchmarking : Les méthodes sont validées par rapport aux scénarios officiels de la LNH pour $n \in \{0, 1\}$ sur quatre saisons (2021-22 à 2024-25), montrant des correspondances exactes. Les auteurs rendent compte du temps d'exécution, de l'efficacité de l'élagage et de la complexité des scénarios.

Résultats

• Précision : L'algorithme a reproduit avec succès tous les scénarios de qualification officiels d'anticipation de 0 jour et de 1 jour publiés par la LNH pour les saisons testées.
• Performance :
  • Anticipation de 0 jour : Les temps de résolution sont généralement faibles, culminant au milieu de la saison lorsque les courses aux séries éliminatoires sont serrées.
  • Anticipation de 1 jour : L'algorithme démontre une efficacité d'élagage élevée (souvent proche de 1,0), ce qui signifie qu'il explore une très petite fraction des combinaisons totales de résultats de matchs possibles. Cependant, les temps de résolution peuvent varier considérablement ; le scénario le plus complexe (Boston Bruins, mars 2023) a nécessité plus de 25 000 secondes et impliquait 27 littéraux.
  • $n > 1$ : L'algorithme a été testé pour $n=2$ et $n=3$ sur la saison 2024-25. Bien que computationnellement réalisable pour de nombreux cas, le temps requis augmente de manière exponentielle avec le nombre de matchs pertinents. Les scénarios avec $n=3$ ont souvent donné lieu à des sorties complexes (jusqu'à 65 littéraux) difficiles à interpréter pour les parties prenantes, même lorsqu'ils étaient résolubles dans un délai de 30 minutes.
• Utilisation du modèle : Le modèle d'affectation des buts et les contraintes paresseuses sont invoqués rarement (uniquement dans des scénarios spécifiques de départage) mais sont critiques pour la correction lorsqu'ils sont invoqués.

Importance
L'article affirme que sa contribution principale est de fournir une alternative automatisée, mathématiquement rigoureuse et computationnellement efficace à la détermination manuelle des scénarios de qualification, qui est devenue de plus en plus sujette aux erreurs en raison des règles complexes de départage de la LNH. Les méthodes permettent aux parties prenantes (fans, marketeurs, équipes) de comprendre précisément dans quelles conditions une équipe assurera sa qualification dans un avenir proche. Les auteurs notent que, bien que l'approche soit adaptée à la LNH, les techniques sous-jacentes de CP et de recherche arborescente sont suffisamment générales pour être adaptées à d'autres sports, à différentes métriques de qualification (par exemple, titres de division, Trophée des présidents) ou à d'autres scénarios de qualification spécifiques à une position. Le travail met en évidence le compromis entre la complexité computationnelle et l'interprétabilité des scénarios résultants, en particulier à mesure que la fenêtre d'anticipation ($n$) augmente.