Matchmaking 로직: 비슷한 전력의 유저를 묶는 방 생성과 매칭 알고리즘

매칭의 목표는 공정성과 대기 시간의 균형이다

매칭 시스템은 단순히 대기 중인 유저를 순서대로 묶는 기능이 아니다. 실력 차이가 적은 경기를 만들수록 공정성은 좋아지지만 조건이 엄격하면 대기 시간이 길어진다. 반대로 빠르게 방을 만들면 실력 차이와 네트워크 품질 문제가 커질 수 있다.

실무에서는 보통 다음 요소를 함께 고려한다.

• MMR 또는 레이팅 차이
• 대기 시간
• 파티 인원과 역할 조합
• 지역 및 지연 시간
• 차단 관계, 재대전 방지 같은 사회적 조건

이 글에서는 가장 기본적인 1대1 또는 고정 인원 팀 게임을 기준으로 MMR 중심의 방 생성 알고리즘을 단계적으로 설계한다.

기본 데이터 모델

매칭 큐에 들어가는 항목은 유저 ID만으로 부족하다. 매칭 판단과 방 생성에 필요한 정보를 함께 보관해야 한다.

public sealed record QueueEntry(
    string TicketId,
    string PlayerId,
    int Mmr,
    DateTime QueuedAt,
    string Region,
    int PartySize = 1
);

TicketId는 매칭 요청 하나를 식별하는 값이다. 같은 유저가 재접속하거나 취소 요청을 보낼 수 있으므로 유저 ID와 별도로 관리하는 편이 안전하다.

MMR은 승패 기록을 바탕으로 계산한 실력 추정치다. 단순한 Elo처럼 하나의 숫자만 쓸 수도 있고 평균 실력과 불확실성을 분리한 Glicko 계열 방식을 사용할 수도 있다. 매칭 단계에서는 우선 정수형 MMR 하나만 있다고 가정해도 충분하다.

두 유저의 기본 전력 차이는 다음처럼 계산한다.

$$\Delta_{mmr} = |mmr_a - mmr_b|$$

이 값이 작을수록 일반적으로 더 균형 잡힌 대전이 된다.

대기 시간이 길수록 허용 범위를 넓힌다

처음부터 MMR 차이 300인 유저까지 허용하면 매칭은 빠르지만 품질이 쉽게 나빠진다. 그래서 처음에는 좁은 범위만 탐색하고 기다린 시간이 길어질수록 탐색 범위를 조금씩 넓히는 방식이 널리 쓰인다.

예를 들어 기본 허용 차이를 50, 10초마다 확장 폭을 25, 최대 허용 차이를 300으로 두면 다음과 같다.

$$range(t) = \min(50 + 25 \times \lfloor t / 10 \rfloor, 300)$$

여기서 $t$는 초 단위 대기 시간이다. 0초에는 MMR 차이 50 이내만 허용하고 40초가 지나면 150 이내까지 탐색한다.

public static int GetAllowedMmrGap(TimeSpan waitTime)
{
    const int baseGap = 50;
    const int expansionPerStep = 25;
    const int stepSeconds = 10;
    const int maxGap = 300;

    var steps = (int)(waitTime.TotalSeconds / stepSeconds);
    return Math.Min(baseGap + steps * expansionPerStep, maxGap);
}

중요한 점은 후보의 범위만 확인해서는 안 된다는 것이다. 이미 오래 기다린 후보는 더 넓은 범위를 허용할 수 있지만 새로 들어온 요청은 여전히 좁은 기준을 가질 수 있다. 따라서 두 유저 모두가 상대를 허용하는지 검사하는 편이 일관적이다.

public static bool CanMatch(QueueEntry a, QueueEntry b, DateTime now)
{
    if (a.Region != b.Region)
    {
        return false;
    }

    var gap = Math.Abs(a.Mmr - b.Mmr);
    var aRange = GetAllowedMmrGap(now - a.QueuedAt);
    var bRange = GetAllowedMmrGap(now - b.QueuedAt);

    return gap <= aRange && gap <= bRange;
}

매칭 처리 흐름

매칭 서버는 보통 일정 주기마다 큐를 훑거나 새 요청이 들어올 때 주변 후보를 즉시 탐색한다. 단순 구현에서는 일정 주기 방식이 이해하기 쉽고 운영하기도 편하다.

flowchart TD
    A[매칭 요청 등록] --> B[지역·게임 모드별 큐에 저장]
    B --> C[가장 오래 대기한 요청 선택]
    C --> D[MMR 범위 안의 후보 검색]
    D --> E{양쪽 조건을 모두 충족하는가?}
    E -- 아니오 --> F[다음 후보 탐색]
    F --> D
    E -- 예 --> G[후보 예약]
    G --> H[방 생성]
    H --> I[참가자 확정 후 게임 서버 할당]

가장 오래 기다린 요청을 우선 처리하면 대기 시간의 상한을 낮추는 데 도움이 된다. 후보가 여러 명이면 단순히 첫 후보를 고르기보다 MMR 차이, 예상 핑, 파티 조건을 점수로 합산해 가장 좋은 조합을 선택한다.

public static int GetCandidateScore(QueueEntry source, QueueEntry candidate)
{
    var mmrGap = Math.Abs(source.Mmr - candidate.Mmr);
    var waitBonus = (int)(DateTime.UtcNow - candidate.QueuedAt).TotalSeconds;

    // 점수가 낮을수록 좋은 후보다.
    return mmrGap * 10 - Math.Min(waitBonus, 120);
}

이 점수는 예시일 뿐이다. MMR 차이를 강하게 우선할지 오래 기다린 유저를 더 우대할지는 게임 장르와 목표 대기 시간에 맞춰 조정해야 한다.

2대2 이상에서는 팀 평균만 비교하면 부족하다

팀 게임에서 모든 유저를 모은 뒤 팀 평균 MMR만 비슷하게 맞추면 특정 팀에 고레벨 유저가 몰리는 문제가 생길 수 있다. 평균이 같아도 체감 난이도는 크게 달라진다.

예를 들어 2대2에서 후보의 MMR이 1600, 1400, 1550, 1450이라면 다음 배치가 자연스럽다.

• A팀: 1600 + 1400
• B팀: 1550 + 1450

팀 평균 차이는 다음으로 계산할 수 있다.

$$teamGap = \left|\frac{\sum MMR_A}{|A|} - \frac{\sum MMR_B}{|B|}\right|$$

작은 인원 게임은 가능한 팀 분할을 전부 계산해 최적안을 찾을 수 있다. 다만 5대5 이상에서 모든 조합을 완전 탐색하면 비용이 급격히 커진다. 이 경우 높은 MMR과 낮은 MMR을 번갈아 배치하는 탐욕적 방식으로 초기 해를 만들고 몇 번의 자리 교환으로 팀 차이를 줄이는 방식이 현실적이다.

public static (List<QueueEntry> TeamA, List<QueueEntry> TeamB) BuildTwoTeams(
    IReadOnlyList<QueueEntry> players)
{
    var sorted = players.OrderByDescending(player => player.Mmr).ToList();
    var teamA = new List<QueueEntry>();
    var teamB = new List<QueueEntry>();
    var sumA = 0;
    var sumB = 0;

    foreach (var player in sorted)
    {
        if (sumA <= sumB)
        {
            teamA.Add(player);
            sumA += player.Mmr;
        }
        else
        {
            teamB.Add(player);
            sumB += player.Mmr;
        }
    }

    return (teamA, teamB);
}

역할 기반 게임이라면 MMR만으로는 부족하다. 탱커, 딜러, 서포터처럼 필수 역할이 있다면 큐 항목에 희망 역할과 허용 역할을 넣고 역할 조합이 성립하는 후보군만 팀 밸런싱 대상으로 삼아야 한다.

방 생성은 원자적으로 처리한다

매칭 후보를 찾은 뒤에는 같은 유저가 다른 매칭 작업에 동시에 선택되지 않도록 보호해야 한다. 여러 매칭 워커가 같은 큐를 처리하면 이 문제가 특히 자주 발생한다.

안전한 순서는 다음과 같다.

1. 후보 티켓을 짧은 만료 시간으로 예약한다.
2. 모든 티켓 예약이 성공했는지 확인한다.
3. 방 ID를 만들고 참가자 목록을 기록한다.
4. 게임 서버 또는 릴레이 서버를 할당한다.
5. 예약을 확정 상태로 전환하고 클라이언트에 결과를 전달한다.

Redis를 큐 저장소로 쓴다면 정렬 집합으로 MMR 또는 입장 시간을 인덱싱할 수 있다. 다만 여러 티켓의 상태 변경은 단일 명령만으로 해결되지 않는 경우가 많다. Lua 스크립트나 트랜잭션, 데이터베이스의 조건부 업데이트를 이용해 대기 중 -> 예약됨 전환을 원자적으로 보장해야 한다.

방 생성에 실패했을 때 예약을 그대로 두면 유저가 큐에서 사라진 것처럼 보일 수 있다. 예약에는 반드시 TTL을 두고 서버 할당 실패 시 즉시 대기 상태로 되돌리는 보상 처리를 준비한다.

매칭 품질을 측정하는 지표

알고리즘은 구현 후에도 계속 조정해야 한다. 다음 지표를 수집하면 문제를 빠르게 발견할 수 있다.

• 평균 및 분위수별 대기 시간
• 실제 매칭된 MMR 차이
• 매칭 취소율과 수락 실패율
• 지역별 핑 분포
• 매치 종료 후 승률 편차
• 재대전 비율

승률이 항상 50%에 가까워야 하는 것은 아니다. 파티, 역할, 신규 유저의 높은 MMR 불확실성 때문에 개별 매치에는 편차가 생긴다. 대신 구간별로 큰 편향이 반복되는지 확인해야 한다. 예를 들어 특정 MMR 구간에서 한쪽 팀 승률이 지속적으로 60% 이상이라면 팀 구성 규칙이나 MMR 갱신 규칙을 점검할 신호다.

구현을 시작할 때의 권장 순서

처음부터 복잡한 예측 모델을 도입하기보다 다음 순서로 확장하는 편이 안정적이다.

1. 모드와 지역별 FIFO 큐를 만든다.
2. 양쪽의 대기 시간 기반 MMR 범위를 적용한다.
3. 티켓 예약과 방 생성을 원자적으로 처리한다.
4. 팀 평균 차이와 역할 조합을 추가한다.
5. 대기 시간과 경기 결과 데이터를 바탕으로 범위 확장 규칙을 조정한다.

좋은 매칭은 가장 정교한 수식보다 명확한 우선순위와 실패해도 유저를 잃지 않는 상태 관리에서 시작한다. 먼저 관측 가능한 단순한 규칙을 만들고 실제 대기 시간과 경기 품질 데이터를 근거로 점진적으로 개선하는 것이 가장 안전하다.