🤖 AI

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

Dit artikel presenteert een hybride algoritme dat een aangepaste boomzoektocht combineert met een subroutine op basis van constraint programming om op efficiënte wijze de specifieke combinaties van toekomstige wedstrijduitkomsten te bepalen die nodig zijn opdat een team in de National Hockey League een plek in de play-offs kan binnenslepen binnen een vooruitblikvenster van $n$ dagen, rekening houdend met complexe regels voor het oplossen van gelijkstand.

Oorspronkelijke auteurs: Gili Rosenberg, Kyle E. C. Booth, J. Kyle Brubaker, Ruben S. Andrist

Gepubliceerd 2026-05-14

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Gili Rosenberg, Kyle E. C. Booth, J. Kyle Brubaker, Ruben S. Andrist

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een lang, zwaar seizoen van een ijshockeyliga bekijkt. Naarmate het seizoen ten einde loopt, zijn fans wanhopig op zoek naar het antwoord: "Heeft mijn team officieel een plek in het grote play-offtoernooi veiliggesteld, of zweven ze nog in de onzekerheid?"

In de National Hockey League (NHL) is dit uitvinden niet zomaar een kwestie van punten optellen. Het is een enorm, ingewikkeld puzzelstuk met 32 teams, een strikte reeks regels voor het oplossen van gelijkstand (zoals het vergelijken van doelpuntenverschil of onderlinge resultaten) en een duizelingwekkende reeks mogelijke toekomstige uitslagen.

Dit artikel introduceert een slim computerprogramma dat ontworpen is om die puzzel direct op te lossen. Hieronder wordt uitgelegd hoe de auteurs dit hebben opgebroken, met behulp van eenvoudige analogieën:

1. De "0-Daagse" Vooruitblik: De Momentopname

Allereerst bouwden de auteurs een tool om de volgende vraag te beantwoorden: "Op dit moment, kijkend naar de huidige stand, heeft een team zich geplaatst?"

Denk hierbij aan een beveiliger die een gastenlijst controleert. De computer vraagt: "Is er enige manier waarop het team nog van de lijst kan worden gehaald?"

Om het antwoord te vinden, probeert de computer een "slechtste-mogelijke-nachtmerrie"-scenario te construeren. Het stelt zich voor dat het team elke resterende wedstrijd verliest terwijl hun rivalen alles winnen.
Als de computer zelfs maar één scenario kan vinden waarin het team wordt uitgeschakeld, dan hebben ze zich nog niet geplaatst.
Als de computer elk mogelijk nachtmerrie-scenario heeft geprobeerd en het team toch niet kan uitschakelen, dan zijn ze veilig. Ze hebben zich geplaatst.

Het Moeilijke Deel (De Gelijkstandsregels):
Soms eindigen teams met exact hetzelfde aantal punten en hetzelfde aantal overwinningen. De NHL heeft een lange lijst met regels om deze gelijkstanden te doorbreken (zoals wie meer doelpunten scoorde).

De Analogie: Stel je voor dat de computer een rechter is. Normaal gesproken kan hij de winnaar bepalen door naar de score te kijken. Maar als de scores gelijk zijn, moet hij kijken naar de "gelijkstandsregels".
De auteurs bedachten een slimme truc waarbij de computer een "gissing" doet over wie de gelijkstand zou winnen. Als die gissing verkeerd blijkt te zijn op basis van de feitelijke regels, zegt de computer: "Oeps, verkeerde gissing!" en probeert een ander pad. Dit gebeurt zeer zelden, maar wanneer het wel gebeurt, zorgt het ervoor dat het antwoord 100% wiskundig correct is.

2. De "n-Daagse" Vooruitblik: De Kristallen Bol

De echte magie van dit artikel zit in de "n-dagse vooruitblik". Dit beantwoordt: "Welke specifieke uitslagen in de komende dagen garanderen dat mijn team zich plaatst voor de play-offs?"

Stel je voor dat je een spel speelt van "Kies je eigen avontuur", maar in plaats van een boek is het een gigantische boom van mogelijkheden.

De Boom: Elke wedstrijd die op het punt staat te gebeuren, is een tak op de boom. Omdat een ijshockeywedstrijd op zes verschillende manieren kan eindigen (een reguliere overwinning, een overwinning in overtime, een overwinning in de shoot-out, enz.), splitst de boom zich in zes richtingen voor elke wedstrijd.
Het Probleem: Als er 10 wedstrijden over zijn, heeft de boom miljoenen takken. Het controleren van elk individueel stukje zou eeuwig duren.
De Oplossing (Uitdunnen): De auteurs bouwden een "slimme tuinman" voor deze boom. Terwijl de computer een tak afloopt, controleert hij of het pad zinvol is.
- Voorbeeld: Als de computer een pad ziet waarbij het team een cruciale wedstrijd verliest, realiseert hij zich misschien: "Wacht, als ze deze verliezen, kunnen ze zich niet meer plaatsen, wat er ook verder gebeurt." Dus dunt hij (snijdt af) die hele tak en alle takken die daaruit groeien, uit.
- Hij kijkt ook zijwaarts. Als een team zich plaatst met een "Shoot-out Overwinning", weet de computer dat ze zich ook zullen plaatsen met een "Reguliere Overwinning" (wat nog beter is). Dus hoeft hij het pad "Reguliere Overwinning" niet apart te controleren; hij markeert gewoon de hele rechterkant van de boom als "Geplaatst".

3. Hoe Ze Het Testten

Het team testte hun "slimme tuinman" op vier recente NHL-seizoenen (2021–2025).

Ze controleerden of de antwoorden van hun computer overeenkwamen met de officiële scenario's die door de NHL werden gepubliceerd. Het kwam perfect overeen.
Ze ontdekten dat de computer op de meeste dagen ongelooflijk snel was, waarbij 99% van de onnodige mogelijkheden werd weggehaald.
Ze testten zelfs het kijken 2 en 3 dagen vooruit. Hoewel de wiskunde veel moeilijker wordt (zoals proberen een Rubik's kubus op te lossen terwijl je jongleert), kon het systeem toch de antwoorden vinden voor de meeste scenario's binnen een redelijke tijd.

Samenvatting

Kortom, de auteurs bouwden een wiskundige kristallen bol.

Het gebruikt een Constraint Programming-engine (een soort logische solver) om te controleren of een team op dit moment veilig is.
Het gebruikt een Boomzoektocht (een methode om mogelijkheden te verkennen) om in de toekomst te kijken.
Het gebruikt Uitdunnen (het afsnijden van doodlopende wegen) om onmogelijke of irrelevante scenario's te negeren.

Het resultaat is een tool die een fan precies kan vertellen wat er de komende dagen moet gebeuren om zich te plaatsen voor de play-offs, waarbij alle complexe gelijkstandsregels automatisch en direct worden verwerkt.

Technische Samenvatting: Een Constraint Programming-benadering voor n-dagen vooruitkijkende playoff-kwalificatie in de NHL

Probleemdefinitie
Het artikel behandelt de computationele uitdaging van het bepalen van scenario's voor "playoff-kwalificatie" (het zeker stellen van een plek) in de National Hockey League (NHL). Een team wordt geacht te hebben "gekwalificeerd" als ze gegarandeerd een plek in de postseason hebben, ongeacht de uitkomsten van resterende wedstrijden. Hoewel het bepalen of een team zich heeft gekwalificeerd op basis van de huidige staat van het seizoen (0-dagen vooruitkijken) een bekend NP-compleet combinatorisch probleem is, breiden de auteurs dit uit tot "n-dagen vooruitkijken". Dit houdt in het identificeren van specifieke combinaties van wedstrijduitkomsten over de komende $n$ dagen die de playoff-kwalificatie van een team garanderen.

Het probleem wordt bemoeilijkt door de complexe kwalificatiestructuur van de NHL (twee conferenties, twee divisies per conferentie, drie divisiekwalificanten per divisie, en twee wildcards per conferentie) en een uitgebreide, hiërarchische lijst van zeven tie-breakers (variërend van puntenpercentage tot doelsaldo en aantal gescoorde doelpunten). De complexiteit neemt aanzienlijk toe bij het beschouwen van toekomstige wedstrijden, aangezien de zoekruimte exponentieel groeit met het aantal mogelijke wedstrijduitkomsten (zes types: reguliere winst, winst na overtime, winst na shoot-out, verlies na shoot-out, verlies na overtime, regulier verlies).

Methodologie
De auteurs stellen een tweestapsbenadering voor die Constraint Programming (CP) combineert met een aangepast boomzoekalgoritme.

0-dagen vooruitkijkende Subroutine (CP-model):
De kern van de benadering is een op CP gebaseerd model dat is ontworpen om te bepalen of een specifiek team ( $k$ ) wiskundig kan worden uitgesloten. Het model zoekt naar een "tegenvoorbeeld"—een toewijzing van uitkomsten aan alle resterende wedstrijden waarbij team $k$ niet kwalificeert. Als een dergelijke toewijzing niet bestaat, heeft het team zich gekwalificeerd.
- Winsttoewijzingsmodel: Deze initiële fase wijst wedstrijduitkomsten (winsten/verliezen) toe om punten en winsttellingen te bepalen. Het omvat "slechtst-mogelijke" aannames voor team $k$ (alle resterende wedstrijden verliezen in reguliere tijd) om de moeilijkheidsgraad van kwalificatie te maximaliseren. Het gebruikt binaire variabelen om rangschikkingen weer te geven en behandelt tie-breakers (1) tot en met (4) direct.
- Tie-groep Evaluatie & Lazy Constraints: Voor ties die aanhouden tot en met tie-breaker (4), gebruikt het model "gok"-variabelen ( $u_{ij}$ ) om rangschikkingen te hypothetiseren. Als de gok van de solver in strijd is met de feitelijke head-to-head punten (tie-breaker 5), wordt een "no-good"-constraint gegenereerd om die specifieke rangschikking gok uit te sluiten, waardoor de solver gedwongen wordt om alternatieve oplossingen te verkennen.
- Doeltoewijzingsmodel: Als een potentieel uitsluitingsscenario ties omvat die aanhouden tot en met tie-breaker (5), wordt een secundair CP-model geactiveerd. Dit model wijst specifieke doelpunten toe aan wedstrijden om te verifiëren of de tie kan worden verbroken door doelsaldo (tie-breaker 6) of aantal gescoorde doelpunten (tie-breaker 7). Dit model wordt alleen geconstrueerd wanneer nodig om computationele overhead te vermijden.
n-dagen vooruitkijkend Algoritme (Boomzoek):
Om kwalificatiescenario's over de komende $n$ dagen te bepalen, maken de auteurs gebruik van een boomzoek waarbij knopen specifieke wedstrijduitkomsten vertegenwoordigen.
- Presolve-fase: Voordat er gezocht wordt, controleert het algoritme of het team kan kwalificeren in een "onmogelijk optimistisch" best-case scenario of of ze worden uitgesloten in een "onmogelijk pessimistisch" worst-case scenario. Als het antwoord definitief is, wordt de zoektocht overgeslagen.
- Boom traversie & Pruning: Het algoritme gebruikt een op een wachtrij gebaseerde zoektocht (voornamelijk diepte-eerst) met verfijnde ordeningsheuristieken voor wedstrijden, knopen en inferentie-algoritmen.
- Pruning-strategieën: De zoektocht wordt zwaar geprepareerd met behulp van de 0-dagen CP-subroutine. Als een knoop een staat vertegenwoordigt waarin team $k$ zich heeft gekwalificeerd, worden alle kindknopen (verdere uitkomsten) geprepareerd. Als het team wordt uitgesloten, worden de knoop en zijn kinderen geprepareerd.
- Sideways Pruning: Een belangrijke winst in efficiëntie komt voort uit "sideways pruning". Als wedstrijduitkomsten kunnen worden gerangschikt op basis van hun impact op team $k$ (bijvoorbeeld: een reguliere winst is strikt beter dan een winst na overtime), en een specifieke uitkomst leidt tot kwalificatie, dan worden alle "sterkere" uitkomsten rechts in de zoekboom eveneens geprepareerd, aangezien deze tot hetzelfde resultaat zouden leiden.

Belangrijkste Bijdragen

Nieuwe 0-dagen Benadering: Het artikel introduceert een CP-model dat is bijgewerkt voor de moderne NHL-structuur (regels na 2019-20), waarbij gebruik wordt gemaakt van een decompositiestrategie (winsttoewijzing versus doeltoewijzing) en lazy constraint-generatie om complexe tie-breakers efficiënt te hanteren.
Nieuwe n-dagen Algoritme: Het presenteert een aangepast boomzoekalgoritme dat concrete n-dagen vooruitkijkende scenario's bepaalt. Deze benadering combineert preprocessing, pruning-strategieën en knoop-ordeningsheuristieken om de combinatorische explosie van toekomstige wedstrijduitkomsten te beheersen.
Validatie en Benchmarking: De methoden worden gevalideerd tegen officiële NHL-scenario's voor $n \in \{0, 1\}$ over vier seizoenen (2021-22 tot en met 2024-25), waarbij exacte overeenkomsten worden aangetoond. De auteurs rapporteren over runtime, pruning-efficiëntie en scenario-complexiteit.

Resultaten

Nauwkeurigheid: Het algoritme slaagde erin alle officiële 0-dagen en 1-dagen kwalificatiescenario's die door de NHL zijn gepubliceerd voor de geteste seizoenen, succesvol te reproduceren.
Prestaties:
- 0-dagen: Oplostijden zijn over het algemeen laag, met pieken halverwege het seizoen wanneer de strijd om de playoffs krap is.
- 1-dagen: Het algoritme toont een hoge pruning-efficiëntie (vaak dicht bij 1,0), wat betekent dat het een zeer klein fractie van de totale mogelijke combinaties van wedstrijduitkomsten verkent. Oplostijden kunnen echter aanzienlijk variëren; het meest complexe scenario (Boston Bruins, maart 2023) vereiste meer dan 25.000 seconden en omvatte 27 literalen.
- n > 1: Het algoritme werd getest voor $n=2$ en $n=3$ op het seizoen 2024-25. Hoewel computationeel haalbaar voor veel gevallen, schaalt de benodigde tijd exponentieel met het aantal relevante wedstrijden. Scenario's met $n=3$ resulteerden vaak in complexe outputs (tot 65 literalen) die moeilijk te interpreteren waren voor belanghebbenden, zelfs wanneer ze binnen een time-out van 30 minuten oplosbaar waren.
Modelgebruik: Het doeltoewijzingsmodel en lazy constraints worden zelden opgeroepen (alleen in specifieke tie-breaking scenario's), maar zijn cruciaal voor correctheid wanneer ze wel worden opgeroepen.

Betekenis
Het artikel beweert dat de primaire bijdrage het bieden is van een geautomatiseerd, wiskundig rigoureus en computationeel efficiënt alternatief voor de handmatige bepaling van kwalificatiescenario's, wat steeds vatbaarder is geworden voor fouten door de complexe tie-breaking regels van de NHL. De methoden stellen belanghebbenden (fans, marketeers, teams) in staat om precies te begrijpen onder welke voorwaarden een team zich in de nabije toekomst zal kwalificeren. De auteurs merken op dat hoewel de benadering is toegespitst op de NHL, de onderliggende CP- en boomzoektechnieken algemeen genoeg zijn om te worden aangepast voor andere sporten, verschillende kwalificatiemetingen (bijvoorbeeld divisietitels, President's Trophy), of andere seed-specifieke kwalificatiescenario's. Het werk benadrukt de afweging tussen computationele complexiteit en de interpreteerbaarheid van de resulterende scenario's, met name naarmate het vooruitkijkende venster ( $n$ ) toeneemt.

1. De "0-Daagse" Vooruitblik: De Momentopname

2. De "n-Daagse" Vooruitblik: De Kristallen Bol

3. Hoe Ze Het Testten

Samenvatting

Meer zoals dit