본문으로 건너뛰기
AWS ML Blog

제약 프로그래밍으로 NHL 플레이오프 확정 시나리오 자동 산출

CP-SAT 기반 0-day solver와 n-day 트리 탐색을 결합해 NHL 플레이오프 확정 조건을 자동으로 결정하고 네 시즌 검증에서 NHL 발표와 일치시켰다.

이 요약은 AI가 원문을 분석해 생성했습니다. 정확한 내용은 원문 기준으로 확인하세요.

TL;DR

AWS 연구진은 NHL의 복잡한 타이브레이커 규칙을 완전하게 모델링한 제약 프로그래밍(CP) 0-day solver와 그 위에 얹은 n-day 전방 탐색 트리를 결합해 플레이오프 확정 시나리오를 자동으로 산출하는 시스템을 구현했다. 각 트리 노드에서 0-day 만족성 판정을 호출하고 전처리·가지치기·노드 정렬로 탐색을 대폭 줄여 대부분의 사례에서 분 단위 중앙값으로 결과를 산출했다. 네 시즌(2021–22~2024–25)에 대해 NHL 발표와 완전 일치하는 검증 결과를 얻었고, 높은 가지치기 효율로 실무 적용이 가능하다는 점이 핵심 성과다.

섹션별 상세

문제 맥락은 시즌 말미에 특정 팀이 남은 경기 결과와 복잡한 타이브레이커 규칙을 고려해 플레이오프 진출을 수리적으로 보장받는지 판정하는 것이며, 이 문제는 가능한 경기 결과의 조합 수가 폭발적으로 늘어나 단순 수작업으로는 실수나 시간이 큰 비용으로 이어진다. 해결 방식은 남은 경기들을 변수로 하는 제약 만족성 문제로 정식화한 뒤, 해당 팀이 탈락하는 가능한 결과 조합이 존재하는지를 찾는 것으로 귀결시킨다. 이 접근법은 완전성을 유지하는 방식으로 수학적 확정 여부를 판별하므로 수동 발표와 정합성을 비교해 검증 가능하다.
기술적 핵심은 두 계층으로 구성된다. 첫째 0-day solver는 현재 순위를 입력으로 받아서 그 팀이 이미 확정되었는지 여부를 CP(Constraint Programming) 모델의 만족성 문제로 풀며, 이 단계에서 NHL의 일곱 단계 타이브레이커 규칙을 모두 모델링해 실제 리그 규칙과 동등한 판정을 보장한다. 둘째 n-day lookahead는 다음 n일 동안의 각 경기 결과를 트리로 확장해 각 노드에서 0-day solver를 호출해 누적된 결과로 확정 여부를 판정하고, 전처리·가지치기·노드 정렬 등으로 탐색 폭을 줄여 현실적 시간 안에 일별 시나리오를 산출한다.
n-day lookahead 트리 다이어그램으로 한 경기의 특정 결과(SOW)에서 확정이 도출되고, 더 강한 결과(OTW, RW)나 다른 경기 결과로도 확정이 귀결되는 구조를 녹색으로 표시하고 있다.
Diagram이 도표는 각 층이 하루 내 개별 경기를 나타내고 각 자식 노드가 그 경기의 가능한 결과를 표현하는 트리 구조를 시각화한다. 트리의 일부 노드가 0-day solver의 추론으로 바로 확정됨을 녹색 음영으로 표시해 전처리·추론 기반 가지치기가 탐색 폭을 어떻게 줄이는지 메커니즘을 보여준다. 이 그림은 n-day lookahead가 노드에서 0-day 판정을 호출해 누적 결과를 귀결시키는 구현 방식을 직관적으로 확인하게 한다.
근거
  • 0-day 모델은 현재 순위에서 해당 팀이 탈락하는 가능한 경기 결과 조합의 존재 여부를 CP-SAT로 푸는 만족성 문제로 정식화한다. — 본문 '0-day solver' 설명 문단 및 CP-SAT 언급.
  • n-day lookahead는 각 경기 결과를 노드로 하는 트리를 확장하고 각 노드에서 0-day solver를 호출해 누적 결과로 확정 판정을 수행한다. — 본문 'n-day lookahead' 설명과 Figure 1의 트리 다이어그램.
실험적 결과는 네 시즌(2021–22부터 2024–25) 전체에 대해 NHL이 공개한 시나리오와 완전 일치하는 산출을 얻었다는 점이 주된 증거이며, 1일 전방 탐색의 중앙값 수행 시간은 분 단위로 나타나 실무적 적용이 가능하다는 근거를 제공한다. 또한 적절한 전처리와 추론 규칙으로 대부분의 트리 노드가 가지치기로 제거되어 전체 탐색을 실행할 필요가 없다는 점이 Figure 2와 Figure 3의 박스플롯으로 나타난다. 이 검증은 시스템의 정확성과 운영 적합성 둘 다를 뒷받침한다.
네 시즌(2021–22~2024–25) 날짜별 해결 시간의 박스플롯으로, 로그 스케일에서 중앙값이 분 단위에 놓여 있음을 보여준다.
Chart박스플롯은 각 시즌별로 일별 실행 시간 분포를 로그 스케일로 제시해 중앙값과 퍼짐을 동시에 보여준다. 중앙값이 분 단위에 위치해 일간 자동 계산이 실무적으로 가능함을 뒷받침하고, 상위 이상치가 존재하나 대부분의 인스턴스는 짧은 시간에 해결된다는 점을 시각적 근거로 제공한다. 이 데이터는 전처리와 가지치기 덕분에 평균적인 계산 비용이 실용적 수준임을 증명한다.
가지치기 효율을 0~1로 표시한 박스플롯으로 대부분 인스턴스에서 효율이 거의 1에 가깝게 분포함을 보여준다.
Chart이 플롯은 각 시즌별로 전체 탐색에서 전처리와 추론 규칙이 제거한 노드 비율을 보여주며, 박스 중앙과 상자 위치가 1에 근접해 많은 경우에 탐색이 거의 필요 없음을 시사한다. 높은 가지치기 효율은 n-day lookahead가 실제로 탐색해야 할 상태공간을 극단적으로 줄여 0-day 판정만으로 귀결되는 경우가 다수임을 증명하는 자료로 해석된다. 따라서 실시간 일별 업데이트를 구현할 때 연산 자원을 크게 절약할 수 있다는 실용적 근거가 된다.
근거
  • 시스템이 생성한 모든 확정 시나리오가 NHL이 공개한 시나리오와 네 시즌(2021–22~2024–25)에 걸쳐 정확히 일치했다. — 본문 결과 문단과 Figure 2, Figure 3; 데이터 출처로 NHL의 public API를 사용했다고 명시됨.
  • 적절한 전처리, 가지치기, 노드 정렬 히ュー리스틱으로 탐색해야 하는 노드 수가 크게 줄어들며, 대부분 인스턴스에서 가지치기 효율이 거의 100%에 근접했다. — Figure 3의 박스플롯과 본문 'pruning' 관련 기술적 설명.
실용적 중요성은 세 분야로 확장된다. NHL 및 미디어 관점에서는 매일 자동으로 수리적으로 증명된 확정 조건을 생성해 수작업 소요를 크게 줄일 수 있고, 팬 관점에서는 '어떤 결과가 나오면 확정되는가'를 명확한 조건으로 제공해 경기 관전의 몰입을 높일 수 있다. 스포츠 애널리틱스 관점에서는 동일한 프레임워크를 우승·시드·탈락 판정 등 다른 이정표로 확장하거나 규칙이 다른 리그로 적응시키는 것이 가능해지므로 최적화 기반 응용 범위가 넓어진다.

용어 해설

플레이오프 확정 시나리오(Clinching scenario)
— 남은 경기 결과와 리그의 타이브레이커 규칙을 모두 고려해 특정 팀이 어떤 조합의 결과에서 반드시 플레이오프에 진출하는지를 판정하는 문제로, 가능한 경기 결과의 조합을 만족·불가능성 여부로 모델링해 수리적으로 귀결을 결정하는 방식이다.
n일 전방 탐색(n-day lookahead)
— 다음 n일 동안 발생하는 경기 각각의 가능한 결과를 계층적 트리로 구성하고, 각 노드에서 현재까지 누적된 결과를 0-day 모델에 질의해 그 노드가 확정(clinch)인지 아닌지를 판단하는 탐색 기법으로, 전방 탐색과 CP 기반 판정을 결합해 효율을 개선한다.
NHL 타이브레이커 연쇄 규칙(NHL tie-breakers)
— 승점 동률 시 우선순위를 매기는 일곱 단계 규칙(경기수 대비 포인트 비율, 규정승, 규정승+연장승, 총승수, 상대전적 포인트, 골득실, 득점)을 말하며, 이 규칙들을 완전하게 모델링해야만 수학적 확정 판정이 가능해진다.
전처리·가지치기 전략(Preprocessing and pruning)
— 남은 경기와 현재 순위를 전처리해 불필요한 노드를 일찍 제거하고, 노드 우선순위를 정해 중요한 분기를 먼저 실행하며, 추론 규칙으로 추가 귀결을 도출해 트리 확장을 대폭 줄이는 일련의 기법군으로 탐색 시간을 단축시키는 핵심 요소이다.
시합 결과의 6분류(NHL game outcomes)
— 각 경기의 팀 관점에서 규정승(RW), 연장승(OTW), 슛아웃승(SOW), 슛아웃패(SOL), 연장패(OTL), 규정패(RL) 여섯 가지 결과를 사용해 승점 산정(승 2점, 연장·슛아웃 패 1점, 규정패 0점)을 그대로 모델화한 것이 계산의 기초가 된다.

기술

  • CP-SAT
  • Google OR-Tools
  • constraint programming
  • custom tree search
  • NHL public API
  • AWS Generative AI Innovation Center

활용 사례

  • 리그 주관 기관과 미디어는 경기 종료 후 일별로 수리적으로 증명된 확정 조건을 자동으로 산출해 공개할 수 있으며, 이는 수작업 발표에 비해 소요 시간을 크게 줄이고 오류 가능성을 낮춘다. 자동화된 시나리오 산출은 경기 해설과 데이터 서비스의 정확성을 높이는 데 직접적으로 기여한다.
  • 팬을 위한 인터랙티브 도구로 확장하면 사용자가 관심 팀을 선택해 '어떤 결과 조합에서 확정되는가'를 즉시 확인할 수 있으며, 각 조건을 명확한 게임 단위의 결과로 환원해 보여주면 경기 관전의 맥락 이해가 깊어진다. 이런 도구는 미디어 콘텐츠와 소셜 캠페인에도 활용 가능하다.
  • 스포츠 애널리틱스 분야에서는 동일한 프레임워크를 우승·디비전 타이틀·시드 등 다른 이정표 판정으로 확장하거나, 규칙이 다른 리그로 모델을 이식해 경쟁 구조·규칙 변화가 시즌 결과에 미치는 영향을 분석하는 데 활용할 수 있다. 또한 비스포츠 도메인의 스케줄링·제약 문제에도 같은 최적화 파이프라인을 적용할 수 있다.

언급된 리소스

API DocsNHL public API
문서scientific paper
문서AWS Generative AI Innovation Center blog post
AI 분석 전체 내용 보기

AI 요약 · 북마크 · 개인 피드 설정 — 무료

출처 · 인용 안내

원문 발행 2026. 08. 08.수집 2026. 08. 08.출처 타입 RSS

인용 시 "요약 출처: AI Trends (aitrends.kr)"를 표기하고, 사실 확인은 원문 보기 기준으로 진행해 주세요. 자세한 기준은 운영 정책을 참고해 주세요.