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

기술 요약: NHL 에서 n 일 전향 플레이오프 확정 시나리오를 위한 제약 프로그래밍 접근법

문제 정의
본 논문은 내셔널 하키 리그 (NHL) 에서 "플레이오프 확정 (playoff clinching)" 시나리오를 결정하는 계산적 과제를 다룹니다. 팀이 남은 경기 결과와 무관하게 포스트시즌 진출이 보장될 때, 해당 팀이 "확정 (clinched)"되었다고 합니다. 시즌 현재 상태 (0 일 전향) 를 기반으로 팀이 확정되었는지 여부를 판단하는 것은 알려진 NP-완전 조합 문제이지만, 저자들은 이를 "n 일 전향"으로 확장합니다. 이는 향후 n 일 동안의 경기 결과 특정 조합이 팀의 플레이오프 진출을 보장하는지 식별하는 것을 포함합니다.

문제는 NHL 의 복잡한 진출 구조 (두 개의 컨퍼런스, 컨퍼런스당 두 개의 디비전, 상위 3 개 디비전 진출팀, 컨퍼런스당 두 개의 와일드카드) 와 점수 비율부터 골 득실차 및 득점까지 이어지는 7 단계의 계층적 동점 처리 규칙으로 인해 복잡해집니다. 미래 경기를 고려할 때 복잡성은 크게 증가하는데, 가능한 경기 결과 유형 (정규 시간 승리, 연장 승리, 승부차기 승리, 승부차기 패배, 연장 패배, 정규 시간 패배) 의 6 가지 유형으로 인해 가능한 경기 결과의 수가 기하급수적으로 증가하기 때문입니다.

방법론
저자들은 제약 프로그래밍 (CP) 과 맞춤형 트리 검색 알고리즘을 결합한 2 단계 접근법을 제안합니다.

1. 0 일 전향 서브루틴 (CP 모델):
   이 접근법의 핵심은 특정 팀 ($k$) 이 수학적으로 탈락했는지 여부를 결정하도록 설계된 CP 기반 모델입니다. 이 모델은 팀 $k$ 가 진출에 실패하는 모든 잔여 경기 결과의 할당을 의미하는 "반례"를 검색합니다. 그러한 할당이 존재하지 않으면, 해당 팀은 확정된 것입니다.

   • 승리 할당 모델: 이 초기 단계는 경기 결과 (승/패) 를 할당하여 승점과 승리 횟수를 결정합니다. 팀 $k$ 에 대해 "최악의 경우" 가정 (남은 모든 경기를 정규 시간 패배) 을 적용하여 확정 난이도를 극대화합니다. 이 모델은 순위 표현을 위해 이진 변수를 사용하며 동점 처리 규칙 (1) 부터 (4) 까지를 직접 처리합니다.
   • 동점 그룹 평가 및 지연 제약: 동점 처리 규칙 (4) 까지 이어지는 동점이 발생할 경우, 모델은 순위 가설을 세우기 위해 "추측" 변수 ($u_{ij}$) 를 사용합니다. 솔버의 추측이 실제 맞대결 승점 (동점 처리 규칙 5) 과 충돌할 경우, 해당 특정 순위 추측을 배제하는 "노-굿 (no-good)" 제약이 생성되어 솔버가 대안 솔루션을 탐색하도록 강제합니다.
   • 골 할당 모델: 잠재적 탈락 시나리오가 동점 처리 규칙 (5) 까지 이어지는 동점을 포함하는 경우, 2 차 CP 모델이 트리거됩니다. 이 모델은 경기별 특정 골 점수를 할당하여 동점이 골 득실차 (동점 처리 규칙 6) 나 득점 (동점 처리 규칙 7) 으로 깨질 수 있는지 검증합니다. 이 모델은 계산 오버헤드를 피하기 위해 필요한 경우에만 구성됩니다.

2. n 일 전향 알고리즘 (트리 검색):
   향후 n 일 동안의 확정 시나리오를 결정하기 위해 저자들은 노드가 특정 경기 결과를 나타내는 트리 검색을 사용합니다.

   • 전처리 (Presolve) 단계: 검색 전에 알고리즘은 팀이 "불가능할 정도로 낙관적인" 최선 시나리오에서 확정될 수 있는지, 아니면 "불가능할 정도로 비관적인" 최악 시나리오에서 탈락되었는지 확인합니다. 답이 명확한 경우 검색을 건너뜁니다.
   • 트리 탐색 및 가지치기: 알고리즘은 경기, 노드 및 추론 알고리즘에 대한 정교한 순서 휴리스틱을 사용하는 큐 기반 검색 (주로 깊이 우선) 을 사용합니다.
   • 가지치기 전략: 검색은 0 일 CP 서브루틴을 사용하여 강력하게 가지치기됩니다. 노드가 팀 $k$ 가 확정된 상태를 나타내면 모든 자식 노드 (추가 결과) 가 가지치기됩니다. 팀이 탈락한 경우 해당 노드와 자식 노드가 가지치기됩니다.
   • 측면 가지치기 (Sideways Pruning): 주요 효율성 향상은 "측면 가지치기"에서 나옵니다. 경기 결과를 팀 $k$ 에 미치는 영향 (예: 정규 시간 승리는 연장 승리보다 엄격히 우위) 으로 순서화할 수 있고, 특정 결과가 확정으로 이어진다면 검색 트리에서 오른쪽에 있는 모든 "더 강력한" 결과도 동일한 결과로 이어지므로 가지치기됩니다.

주요 기여

• 새로운 0 일 접근법: 본 논문은 현대 NHL 구조 (2019-20 시즌 이후 규칙) 에 맞춰 업데이트된 CP 모델을 소개하며, 복잡한 동점 처리 규칙을 효율적으로 처리하기 위해 분해 전략 (승리 할당 대 골 할당) 과 지연 제약 생성을 활용합니다.
• 새로운 n 일 알고리즘: 구체적인 n 일 전향 시나리오를 결정하는 맞춤형 트리 검색 알고리즘을 제시합니다. 이 접근법은 전처리, 가지치기 전략, 노드 순서 휴리스틱을 결합하여 미래 경기 결과의 조합 폭발을 관리합니다.
• 검증 및 벤치마킹: 이 방법들은 4 개 시즌 (2021-22~2024-25) 에 걸쳐 $n \in \{0, 1\}$에 대한 공식 NHL 시나리오와 비교 검증되었으며, 정확한 일치를 보였습니다. 저자들은 실행 시간, 가지치기 효율성, 시나리오 복잡성에 대해 보고합니다.

결과

• 정확도: 알고리즘은 테스트된 시즌 동안 NHL 이 발표한 모든 공식 0 일 및 1 일 확정 시나리오를 성공적으로 재현했습니다.
• 성능:
  • 0 일: 해결 시간은 일반적으로 낮으며, 플레이오프 경쟁이 치열한 시즌 중반에 정점을 이룹니다.
  • 1 일: 알고리즘은 높은 가지치기 효율성 (종종 1.0 에 근접) 을 보여주며, 이는 총 가능한 경기 결과 조합의 매우 작은 부분만 탐색함을 의미합니다. 그러나 해결 시간은 크게 변동할 수 있습니다. 가장 복잡한 시나리오 (2023 년 3 월 보스턴 브루인스) 는 25,000 초 이상 소요되었으며 27 개의 리터럴을 포함했습니다.
  • n > 1: 알고리즘은 2024-25 시즌에 대해 $n=2$ 및 $n=3$으로 테스트되었습니다. 많은 경우에 계산적으로 가능하지만, 소요 시간은 관련 경기 수에 따라 기하급수적으로 증가합니다. $n=3$인 시나리오는 30 분 타임아웃 내에서 해결 가능하더라도 이해하기 어려운 복잡한 결과 (최대 65 개의 리터럴) 를 초래하는 경우가 많았습니다.
• 모델 사용: 골 할당 모델과 지연 제약은 드물게 호출되지만 (동점 처리 시나리오에서만), 호출될 경우 정확성에 필수적입니다.

의의
본 논문은 NHL 의 복잡한 동점 처리 규칙으로 인해 오류가 점점 더 빈번해지고 있는 수동적 확정 시나리오 결정에 대한 자동화되고 수학적으로 엄밀하며 계산적으로 효율적인 대안을 제공한다는 것이 주요 기여라고 주장합니다. 이 방법들은 팬, 마케팅 담당자, 팀 등 이해관계자들이 팀이 가까운 미래에 어떤 조건 하에서 확정을 이루는지 정확히 이해할 수 있게 합니다. 저자들은 이 접근법이 NHL 에 맞춰져 있지만, 근본적인 CP 및 트리 검색 기법은 다른 스포츠, 다른 진출 지표 (예: 디비전 타이틀, 프레지던트 트로피), 또는 다른 시드별 확정 시나리오에 적응하기에 충분히 일반적이라고 지적합니다. 이 연구는 계산 복잡성과 결과 시나리오의 해석 가능성 사이의 트레이드오프, 특히 전향 창 ($n$) 이 증가함에 따라 이를 강조합니다.