32개 팀과 7단계 타이브레이커가 만드는 조합 최적화 난제

NHL 리그는 32개 팀을 동부와 서부의 2개 컨퍼런스로 나누고, 각 컨퍼런스를 다시 2개 디비전으로 분리하여 운영한다. 플레이오프 진출권은 총 16개 팀에게 부여되며, 각 컨퍼런스의 디비전별 상위 3개 팀이 직접 진출하고 나머지 2개 자리는 컨퍼런스 내 성적순으로 와일드카드를 통해 결정한다. 모든 경기는 반드시 승패가 결정되는 구조이며, 정규 시간 이후 연장전과 슛아웃을 통해 최종 승자를 가린다. 이에 따라 한 팀이 얻을 수 있는 결과는 정규 승리(RW), 연장 승리(OTW), 슛아웃 승리(SOW), 슛아웃 패배(SOL), 연장 패배(OTL), 정규 패배(RL)의 6가지 시나리오로 구분된다.

승점 체계는 승리 시 2점, 연장 및 슛아웃 패배 시 1점, 정규 패배 시 0점을 부여하는 방식을 따른다. 팀 간 승점이 동일할 경우 NHL은 총 7단계의 계층적 타이브레이커(Tie-breaker) 규칙을 순차적으로 적용하여 최종 순위를 결정한다. 수백 개의 잔여 경기 결과가 만들어내는 경우의 수에 이 7단계 규칙이 결합하면, 특정 팀의 진출 확정 여부를 판별하는 작업은 기하급수적인 조합의 수를 처리해야 하는 조합 최적화 문제로 변한다. 이러한 구조적 복잡성으로 인해 분석가가 수동으로 진출 확정 여부를 계산하는 과정은 막대한 시간이 소요되며 오류 발생 가능성이 매우 높다.

AWS Generative AI Innovation Center는 이러한 수동 계산의 한계를 해결하기 위해 제약 프로그래밍(CP)과 커스텀 트리 탐색을 결합한 자동화 시스템을 구축했다. 이 시스템은 남은 모든 경기의 결과 조합 속에서 대상 팀이 탈락하는 시나리오가 단 하나도 존재하지 않음을 수학적으로 증명하여 진출 확정(Clinched) 여부를 판별한다. 기존의 수동 방식이 단순한 추측이나 부분적 계산에 의존했다면, 이번 자동화 구현은 리그의 모든 제약 조건을 모델링하여 분 단위의 빠른 연산으로 수학적 확정성을 도출하는 체계를 완성했다.

0-day 솔버: CP-SAT를 이용한 진출 확정 가능성 판별

AWS는 현재 시점의 순위표를 기준으로 즉각적인 진출 확정 여부를 판단하기 위해 Google OR-Tools의 CP-SAT 솔버를 활용한 0-day 솔버를 설계했다. 0-day 솔버는 특정 팀의 진출 여부를 '타당성 문제(Feasibility Problem)'로 정의하여 해결한다. 즉, 남은 모든 경기의 결과 조합을 탐색하여 해당 팀이 플레이오프 진출권 밖으로 밀려나는 시나리오가 단 하나라도 존재하는지를 확인한다. 만약 솔버가 어떤 조합을 통해서도 탈락 시나리오를 찾아내지 못한다면, 해당 팀은 남은 경기 결과와 상관없이 진출이 확정된 상태로 판정된다.

CP-SAT 솔버는 변수 간의 복잡한 제약 조건을 수학적으로 정의하고 이를 빠르게 해결하는 제약 만족 솔버다. AWS는 NHL의 7단계 타이브레이커 규칙 전체를 CP-SAT 모델 내의 제약 조건으로 구현하여, 단순 승점 합계를 넘어 실제 리그 규정에 부합하는 엄격한 판별을 수행하도록 만들었다. 이는 승점, 상대 전적, 득점 기록 등이 얽힌 고차원적인 제약 조건을 효율적으로 처리하기 위한 설계다. 솔버는 6가지 경기 결과(RW, OTW, SOW, SOL, OTL, RL)의 모든 조합을 변수로 처리하여 대상 팀의 순위가 역전될 가능성을 전수 조사한다.

이 장치는 매일 업데이트되는 순위표를 입력값으로 받아 현재 상태에서 논리적으로 탈락이 불가능한지를 검증하는 필터 역할을 수행한다. 수조 개의 가능한 경기 결과 조합이 존재함에도 불구하고, 제약 프로그래밍 방식을 통해 탐색 공간을 효율적으로 압축하여 오차 없는 결과를 도출한다. 결과적으로 0-day 솔버는 미래를 예측하는 것이 아니라, 현재의 데이터가 주는 논리적 결론을 수학적으로 확정 짓는 기초 토대가 된다.

n-day 룩어헤드: 커스텀 트리 탐색 기반의 조건 산출

AWS는 향후 n일간의 경기 결과에 따른 진출 조건을 산출하기 위해 0-day 솔버 상단에 커스텀 트리 탐색(Custom Tree Search) 구조의 n-day 룩어헤드 솔버를 배치했다. 트리 탐색의 각 층(Layer)은 다음 n일 동안 예정된 개별 경기를 의미하며, 각 노드(Node)는 해당 경기가 가질 수 있는 구체적인 결과값을 나타낸다. 시스템은 최상위 노드에서 시작해 하위 노드로 내려가며 가능한 모든 시나리오를 가지 형태로 탐색하며, 특정 팀이 진출하기 위해 필요한 최소한의 경기 결과 조합을 추적한다.

트리 탐색의 각 노드에 도달할 때마다 시스템은 0-day 솔버를 호출하여 현재까지 누적된 경기 결과들이 진출 확정을 만들기에 충분한 조건인지 판정한다. 조합 폭발 문제를 해결하기 위해 전처리 전략과 가지치기(Pruning) 기법을 도입했다. 가지치기가 적용되면 특정 경로의 상위 노드에서 이미 조건이 충족되었거나 불가능함이 판명된 경우, 그 하위의 모든 노드 탐색을 즉시 중단하여 연산 자원 낭비를 막는다. 또한 노드 순서 휴리스틱을 적용해 해를 빠르게 찾을 수 있는 경로를 우선적으로 방문하도록 설계했다.

특히 경기 결과의 '강도' 차이를 이용한 논리적 최적화를 통해 탐색 효율을 높였다. 예를 들어, 슛아웃 승리(SOW)라는 상대적으로 약한 조건에서 진출이 확정된다면, 이보다 더 강한 결과인 연장 승리(OTW)나 정규 승리(RW)가 도출된 시나리오는 별도의 솔버 호출 없이 자동으로 확정 처리한다. 이러한 결과 간의 포함 관계를 활용한 추론은 트리 탐색의 깊이와 넓이를 획기적으로 제어하며, 복잡한 조건 산출 과정을 가속화하는 핵심 기제로 작동한다.

분 단위의 연산 속도와 100%에 가까운 가지치기 효율

AWS는 NHL 공개 API에서 추출한 2021-22 시즌부터 2024-25 시즌까지 총 4개 시즌의 실데이터를 사용하여 시스템의 성능을 검증했다. 검증 결과, 자동화 시스템이 도출한 모든 진출 확정 시나리오는 NHL 공식 발표 내용과 100% 일치하는 정확도를 기록했다. 1일 기준 확정 시나리오를 산출하는 데 소요되는 중앙값 실행 시간은 분 단위로 측정되었으며, 이는 사람이 직접 계산하던 수동 방식 대비 연산 속도를 획기적으로 단축한 결과다.

연산 효율의 핵심은 대부분의 사례에서 100%에 근접하게 나타난 가지치기 효율에 있다. 전처리 전략, 노드 순서 휴리스틱, 추론 알고리즘을 유기적으로 결합하여 전체 탐색 공간의 대부분을 조사하지 않고도 최적의 해를 찾아냈다. 가지치기 효율이 100%에 가깝다는 것은 불필요한 경로 탐색을 거의 완벽하게 차단하여 컴퓨팅 자원 낭비를 최소화했음을 의미한다. 이는 복잡한 제약 조건이 얽힌 실제 스포츠 데이터에서도 모델이 일관된 성능을 유지할 수 있음을 입증한다.

이러한 결과는 수동 계산에서 발생하던 휴먼 에러를 완전히 배제하고, 수학적 검증을 거친 자동화 프로세스가 실제 운영 환경에서 기존 방식을 완전히 대체할 수 있음을 보여준다. 4개 시즌의 장기 데이터를 통해 모델의 범용적 신뢰성을 확보했으며, 매일 반복되는 데이터 처리 업무에 즉시 투입 가능한 수준의 효율성을 증명했다. 결과적으로 시스템은 복잡한 리그 규칙 속에서도 정답을 강제하는 수학적 모델링의 실효성을 입증했다.

스포츠 분석을 넘어선 조합 최적화의 실무 적용 범위

AWS는 이번 NHL 사례에 적용된 수학적 최적화 기법을 라우팅(경로 최적화), 스케줄링, 스포츠 분석 등 다양한 조합 최적화 문제에 적용하고 있다. 조합 최적화 문제는 변수가 증가함에 따라 경우의 수가 기하급수적으로 늘어나므로, 사람이 수동으로 처리할 경우 막대한 시간과 전문 지식이 필요하다. 수학적 최적화 기법은 이러한 수작업 과정을 자동화하여 논리적 결함이 없는 확정적인 정답을 빠르게 도출하며, 분석의 신뢰도를 높이는 결과를 낸다.

본 시스템의 프레임워크는 확장성이 뛰어나 NHL 내의 다른 탈락 조건이나 진출 시나리오 정의에 그대로 활용될 수 있다. 또한 규칙 체계가 다른 타 스포츠 리그의 제약 조건을 입력값으로 설정하면 동일한 구조로 적용이 가능하다. 이는 AWS Generative AI Innovation Center가 산업별 고객에게 제공하는 수학적 최적화 솔루션의 핵심 방향성으로, 복잡한 제약 조건 하에서 비즈니스 결정 속도를 높이는 구조를 설계하는 데 목적이 있다.

수동으로 처리하기 힘든 복잡한 제약 조건 기반의 조합 최적화 문제는 제약 프로그래밍(CP)과 트리 탐색을 결합한 자동화 구조를 통해 정확도와 속도를 동시에 확보하는 것이 실무적인 해결책이다. 복잡한 조합론적 난제를 가진 기업은 제약 조건을 수학적으로 모델링하고 CP-SAT와 같은 솔버를 통해 해를 찾는 방식을 도입함으로써, 인적 오류를 제거하고 데이터 기반의 확정적인 의사결정 체계를 구축할 수 있다.