feat: LoL Temporal 포지션 선호도 기반 5:5 팀 매칭 알고리즘 구현

[Sunja-An]

개요

기존 구현(#82)은 라인별 2명 고정 배정 방식이었으나,
Notion 기획서 기반으로 포지션 선호도를 반영한 완전 탐색 3단계 필터링 알고리즘으로 교체한다.

기획 핵심 (Notion 참조)

• 핵심 목표: 10명 내 양 팀 승리 확률 50:50에 가깝게 맞추는 실력 균형
• 보조 목표: 플레이어 포지션 선호도 존중

포지션 보정 (Model A)

포지션 선호 순위	MMR 반영 비율
1순위	100%
2순위	93.75%
3순위	87.5%
4순위	81.25%
5순위	75%

보정 공식: adjustedMMR = baseMMR × (17 - preferenceRank) (×16 스케일)

알고리즘: 3단계 필터링

10명에서 나올 수 있는 모든 팀 조합 C(10,5) = 252가지 × 포지션 배정 5! × 5! = 14,400가지 = 약 360만 경우 완전 탐색

1. [1단계] 팀 전체 밸런스: |팀A 보정MMR 합 - 팀B 보정MMR 합| 최소
2. [2단계] 라인별 맞대결: 각 포지션별 보정MMR 차이 합 최소
3. [3단계] 포지션 만족도: 10명의 포지션 선호 순위 합 최소

API 변경

Request: POST /api/contests/lol/temporal

Before (기존)

{
  "members": {
    "TOP": [{"username": "A", "tag": "KR1", "rank": "GOLD I"}, ...],
    ...
  }
}

After (신규)

{
  "members": [
    {
      "username": "Player1",
      "tag": "KR1",
      "rank": "GOLD II",
      "positions": ["TOP", "MID", "JG", "ADC", "SUP"]
    },
    ... (총 10명)
  ]
}

Response

{
  "team_a": [
    {"username": "Player1", "tag": "KR1", "rank": "GOLD II", "position": "TOP", "position_preference": 1},
    ...
  ],
  "team_b": [...]
}

작업 범위

• DTO: LolTemporalPlayerV2, LolTemporalContestRequestV2, LolTemporalAssignedPlayer, LolTemporalContestResponseV2
• 에러 코드 추가: ErrLolTemporalInvalidPlayerCount (CT048), ErrLolTemporalInvalidPositions (CT049)
• 알고리즘: balanceLolTeamsV2 (조합 생성, 순열 생성, 3단계 필터링)
• 서비스: BalanceLolTemporalContestV2 메서드
• 컨트롤러: 기존 엔드포인트 신규 메서드로 교체
• 단위 테스트

참고

• Notion: https://www.notion.so/33615b730745807f8090fd9c746d8efb
• 관련 이슈: feat: LoL Temporal Contest — 임시 5v5 팀 밸런싱 API 구현 #82

[Sunja-An]

[Feature] 5:5 커스텀 매치메이킹 시스템 개선 (전적 페널티 기반 Top-K 샘플링 알고리즘)

📌 배경 및 목적 (Background & Objective)

발로란트와 같은 5:5 베이스 게임의 내전 매치메이킹/커스텀 토너먼트를 위한 팀 밸런싱 시스템을 구현합니다.
10명의 유저가 제시한 '포지션 지망 순위(1~5순위 및 기피 포지션)'와 '유저의 랭크 점수'를 기반으로 최상의 밸런스를 맞추면서도, 매 판 동일한 유저들끼리만 팀이 되는 것을 방지하기 위해 전적 페널티 기반의 랜덤 셔플링을 적용해야 합니다.

📝 핵심 요구사항 (Core Requirements)

1. 10명의 플레이어를 5명씩 두 팀(Team A, Team B)으로 나눕니다. (총 126가지 조합)
2. **헝가리안 알고리즘(Hungarian Algorithm)**을 사용하여 각 팀 내에서 밸류 합이 최대가 되는 포지션 배치를 찾습니다.
3. 기피 포지션(Avoid Position) 선택 시 알고리즘이 해당 배치를 피하도록 **거대한 음수 페널티(-999,999)**를 부여합니다.
4. 직전 게임에서 같은 팀이었던 유저가 다시 같은 팀이 되는 것을 방지하기 위해 History Penalty를 적용합니다.
5. 무조건 1등 조합을 고정 픽하는 대신, Top-K 샘플링을 통해 상위 N개의 조합 중 하나를 무작위로 채택하여 매치업의 다양성을 확보합니다.

⚙️ 알고리즘 상세 파이프라인 (Algorithm Specification)

Step 1: 경우의 수 생성 및 가치 행렬(Value Matrix) 구성

• 10명을 5:5로 나누는 126개의 조합 리스트를 생성합니다.
• 각 팀마다 5x5 Value Matrix를 생성합니다.
  • Row: 5명의 플레이어
  • Column: 5개의 포지션
  • Value 계산식: 플레이어 랭크 점수 * 지망 순위 가중치 (예: 1지망 1.0, 5지망 0.75)
  • 기피 포지션 처리: 유저가 기피로 설정한 포지션의 Value는 -999,999로 강제 할당합니다.

Step 2: 팀 최대 밸류 도출 (Hungarian Algorithm)

• 각 조합의 Team A, Team B 매트릭스에 대해 최대 가중치 이분 매칭(Max-Weight Bipartite Matching)을 수행합니다.
• 수행 결과로 A팀 최적 포지션 배치 및 합산 밸류(ScoreA), B팀 최적 포지션 배치 및 합산 밸류(ScoreB)를 도출합니다.

Step 3: Base Score 산출 및 조합 필터링

• 126개의 조합에 대해 **Total Score (ScoreA + ScoreB)**를 구합니다.
• 기피 포지션이 억지로 배정된 경우(Score가 거대한 음수인 경우), 희생자 수가 가장 적은(Total Score가 가장 높은) 최상위 티어의 그룹만 남기고 나머지는 Drop합니다.
• 살아남은 조합들에 한해, 페널티 점수를 걷어낸 **순수 실력 밸런스 차이(|Pure ScoreA - Pure ScoreB|)**를 Base Balance Score로 정의합니다. (값이 작을수록 밸런스가 좋음)

Step 4: History Penalty 적용

• 시스템(또는 DB)에서 직전 매치의 팀 구성 데이터를 조회합니다.
• 현재 평가 중인 조합에서, **직전 매치에 같은 팀이었던 유저 쌍(Pair)**이 다시 같은 팀으로 묶여 있다면 Pair당 Penalty Weight (예: +100점)를 Base Balance Score에 가산합니다.
  • Adjusted Score = Base Balance Score + (History Penalty Count * Weight)

Step 5: Top-K Sampling & 최종 선정

• 126개의 조합을 Adjusted Score 오름차순(가장 공정+페널티 적음)으로 정렬합니다.
• 상위 K개 (예: Top 5)의 조합을 추출하여 후보군으로 만듭니다.
• 후보군 리스트에서 무작위(Random)로 1개의 조합을 최종 매치로 확정하여 반환합니다.

🚨 엣지 케이스 및 제약 사항 (Edge Cases)

• 모두가 특정 포지션을 기피하는 경우: 126개 전체가 -999,999 페널티를 받게 됩니다. Step 3의 로직에 따라 매칭을 취소하지 않고, 가장 적은 인원만 억지로 배정받는 선에서 게임을 정상적으로 성사시켜야 합니다.

✅ 구현 To-Do (Action Items for AI)

• 플레이어, 포지션 선호도, 매치 히스토리 처리를 위한 Struct/Class/Interface 데이터 모델 정의
• 10명을 5:5로 나누는 조합(Combination) 제너레이터 구현
• Hungarian Algorithm 구현 또는 검증된 라이브러리 연동 (Max-Matching 변환 포함)
• 기피 포지션 페널티(-999,999)가 적용된 5x5 Value Matrix 생성 로직 작성
• Total Score 필터링 및 Adjusted Score (Balance + History Penalty) 산출 로직 구현
• 최종 Top-K 샘플링 및 Random Pick 함수 작성 및 단위 테스트(Unit Test) 코드 작성