세션 게임의 매치메이킹 알고리즘

Elo, Glicko, TrueSkill, EOMM 그리고 EnMatch

Published in

취미로 논문 읽는 그룹

30 min readJun 16, 2024

헝가리 출생의 마케트 대학교 물리학 교수이자 체스 마스터 였던 엘로(Arpad Elo)님 께서는 체스 선수의 능력을 평가하고자 통계 기반의 Elo 알고리즘을 개발했습니다. 1960년에는 미국 체스 연맹(USCF)이, 1970년에는 세계 체스 연맹(FIDE)에서 Elo 모델을 채택합니다.

Elo 시스템은 각 선수들에게 능력치를 나타내는 점수를 부여합니다. 이 점수는 경기 결과에 따라 변화하는데요. 승리하면 증가하고 패배하면 감소합니다. 많은 온라인 게임에서 MMR이라는 이름으로 이 개념을 매치메이킹 단계에서 이용하고 있습니다.

오늘은 온라인 게임에서 유저들의 능력치를 평가하는 방법 중 유명한 Elo, Glicko, TrueSkill를 소개하고 EA에서 개발한 EOMM, 최근 AAAI’24 에서 발표된 EnMatch 논문 내용을 다룹니다.

INDEX

매치메이킹 시스템
매치메이킹 요구사항의 다양성
Elo
Glicko
TrueSkill™
EOMM
EnMatch
마무리

매치메이킹 시스템

매치메이킹은 게임을 시작하기 위해 대기중인 플레이어를 하나의 게임으로 배치하는 것을 말합니다. 이 때 진행되는 게임의 단위를 흔히 세션(Session)이라고 부릅니다. 일반적인 세션 기반 게임의 서버 구성은 백엔드 서버와 매치메이커 그리고 데디케이트 서버 Fleet으로 구분됩니다.

백엔드 서버가 회원, 인증, 상점, 플레이 정보, 소셜, 매칭 등 게임 플레이 이외에 필요한 기능을 수행합니다. 유저가 세션에 진입하기 위해 매칭을 돌리면 백엔드 서버가 플레이어들을 하나의 세션으로 할당하는데, 매치메이커가 플레이어를 어떤 세션에 할당할 것인지 결정합니다.

그림 그리기 귀찮았는데.. 구글 형님들 감사합니다. [출처 : OpenMatch]

매치메이킹 요구사항의 다양성

게임을 제작하는 팀 마다 매치메이커에 다양한목표를 설정하곤 합니다. 게임 디자이너들은 일차적으로 높은 품질의 게임 플레이 경험을 주고 싶어 합니다. 이를 위해 플레이어간의 레이턴시나 매칭에 걸리는 시간을 최소화 하면서도 게임의 내용을 재밌게 하기 위해 스킬 기반의 매칭(SBMM)을 이용하거나, 플랫폼 유저를 분리할 수 있습니다.

일부 회사들은 비즈니스 목적으로 매치메이킹 시스템을 이용하기도 합니다. GDC’2016에서 액티비전[1]은 한 발표에서 일반적으로는 게임 디자이너들은 게임이 가장 재밌는 방향 혹은 가장 공정한 방향으로 매치하길 원하지만 비즈니스 목표로 장기적인 monetary value를 높이는 방향을 설정할 수 있다고 설명합니다.

GDC’2016 | 스킬, 매치메이킹, 레이팅 시스템 디자인

여기서 말하는 비즈니스 팀의 목표인 Monetary value의 의미를 액티비전이 2015년 등록한 특허[2]에서 추측해볼 수 있습니다. 물론 이건 개인적인 뇌피셜이고 실제로 발표자 분께서 의도하신 건 아닐 수 있습니다.

어쨋든, 이름 마저 멀티플레이 게임에서 마이크로 결제를 이끄는 시스템이라는 이 특허는 결제를 유도하기 위해 어떻게 매치메이킹 로직을 이용할 수 있는지 수 많은 사례를 소개합니다. 특허문서에서 하나의 예시만 가져와 보자면, 유저가 새로운 무기를 결제하면 다음 게임은 일부러 그 무기가 가장 유용하게 사용되게끔 유도해서 결제한 것을 후회하지 않도록 연출합니다.

if the player purchased a particular weapon, the microtransaction engine may match the player in a gameplay session in which the particular weapon is highly effective, giving the player an impression that the particular weapon was a good purchase.

올해 초 콜 오브 듀티에서 공개한 매치메이킹 문서[3]에서는 플레이어가 지속적으로 패배할 경우, 진행중인 게임을 종료할 가능성이 높아져 플레이어 풀의 영향을 끼치는 구조가 나선 효과를 만든다고 설명했습니다.

플레이어의 능력을 통계 모델을 이용해서 객관적으로 평가하는 데서 출발한 스포츠의 스킬 레이팅 시스템은 온라인 게임에서 동일한 능력을 가진 플레이어를 세션에 모아 균형 잡힌 경기를 만드려고 하는 것을 스킬 기반 매치메이킹(SBMM) 이라고 합니다.

최근에는 게임을 스포츠가 아닌 서비스로 바라보는 시각이 생기면서 매칭을 공정한 게임의 규칙을 구축하는 것 뿐 아니라 다양한 용도로 사용하는 사례가 공유되고 있습니다. 대표적으로 UCLA와 EA가 공동으로 연구한 EOMM이 있으며 AAAI’24 에서도 중국의 대형 게임사 넷이즈에서도 발표한 EnMatch가 있습니다.

지금부터는 SBMM에서 쓸 수 있는 대표적인 스킬 평가 시스템인 ELO, TrueSkill, Glicko에 대해서 먼저 다루고, 그 다음에 EOMM과 EnMatch 논문을 소개합니다.

Elo Rating System

Elo[4]는 물리학자 교수이자 체스 마스터였던 엘로(Arpad Elo)가 만든 선수 평가 시스템입니다. Elo는 플레이어들의 능력 수준은 정규 분포를 따른다고 가정합니다.

많은 온라인 게임들이 채택하고 있고, 본인이 자주 참여하는 온라인 경쟁적 프로그래밍 대회인 AtCoder, LeetCode 에서도 Elo 기반의 점수 시스템을 사용하고 있습니다[5].

위키피디아에서 기재된 가장 기본적인 Elo Scheme은 다음과 같이 정의합니다. 경기 기록이 없는 선수들은 초기값을 부여해서 사용합니다.

E_{A,B}는 A가 B를 이길 확률을 의미합니다. 만약 두 선수의 점수 (R_B, R_A)가 서로 같다면 두 선수의 승률은 값은 1/2로 동일합니다. R_B > R_A인 상황에서는 승률이 < 50%로 낮아진다. 수식을 잘 보면 400 이라는 상수가 있는데, 이는 점수가 400점 정도 차이나면 승률이 90:10 정도 차이나도록 설정한 값입니다.

이 값은 마음대로 설정해도 되는데, 선수들의 점수 범위를 넓게 가져가고 싶으면 큰 값을 사용하면 되고 좁은 범위로 설정하고 싶다면 작은 값을 사용하면 됩니다. 이렇게 승률을 계산했다면 실제 경기 결과를 가지고 나의 점수에 반영합니다.

경기 결과인 Score는 게임에서 이긴 경우 1.0, 비긴 경우 0.5, 패배한 경우 0을 가집니다. K factor는 경기 결과가 점수의 증감에 얼마나 영향을 미치는지 나타내는 파라미터입니다. 만약 나의 예상 승률(Expected)이 낮은 상황에서 예상치 못한 승리를 거두면 점수가 큰 폭으로 증가합니다. 반대로 상대방은 예상 승률 대비해서 패배를 경험했기에 큰 폭으로 점수가 감소하게 됩니다.

순위 시스템 : ELO, TrueSkill 그리고 나만의 시스템

Elo는 간단하고 객관적인 점수 시스템이며 많은 연구에서 신뢰성이 높다고 평가 받았고 지금도 많은 온라인 게임에서 사용하는 점수 시스템이지만, 다음 같은 문제가 있습니다.

시간이 지나면 점수의 인플레이션이 발생한다.
점수가 너무 점진적으로 증가한다. 내가 굉장히 재능있는 플레이어라면 진짜 점수로 수렴하기 까지 많은 경기 회수가 필요하다.
팀 경기에서 적용한다면 내가 얼마나 활약했는지와 무관하게 오로지 경기 결과로만 평가된다.
시간에 따른 숙련도 감소를 표현하지 않는다. 1년 동안 게임을 접었다가 복귀했는데 게임의 변화된 시스템이나 경기 규칙과는 무관하게 나의 점수는 그대로 유지되어 있다.

Glicko

Glicko[6]는 1995년 Mark Glickman이 개발한 Elo 시스템의 발전된 버전인 평가(Rating) 시스템입니다. Elo에 영감을 받은 많은 평가 시스템들은 유저의 능력치가 정규 분포를 따른다고 가정하고 있습니다.

Ranking Systems: Elo, TrueSkill and Your Own

Elo 시스템에선 플레이어의 능력치를 나타내는 정규분포 N(μ, σ²)에서 평균이 점수가 되고요, 표준편차 σ는 고정된 값이라고 가정하고 있습니다. Glicko 시스템은 단순합니다. 이 표준편차 σ가 플레이어마다 다르다고 가정한겁니다.

The Glicko system therefore extends the Elo system by computing not only a rating, which can be thought of as a “best guess” of one’s playing strength, but also a “ratings deviation” (RD) or, in statistical terminology, a standard deviation, which measures the uncertainty in a rating

Glicko 시스템은 플레이어의 능력치를 나타내는 점수와 더불어 점수 편차(Ratings Deviation : RD)값을 같이 계산합니다. 이 값은점수에 대한 확실함을 가지는 정도를 표현합니다. 정규분포에서는 95%의 값들이 평균(μ)에서 ±2σ 에 존재합니다. Glicko 시스템도 플레이어의 점수가 1700점이고 RD가 200점이라면 플레이어 능력이 구간 [1500 ~ 1900]에 95%의 확신으로 존재한다고 생각합니다.

경기를 시작하기 전에 RD를 새로운 값으로 교체합니다. 유럽 프리미어 축구, 리그 오브 레전드 대회는 시즌제로 운영되고 선수마다 상이한 공백기가 존재합니다. RD는 이런 공식경기에서 모습을 비춘 기간에 따른 실력 변화를 가정하고 있고 공백기가 클수록 RD값이 더 커지는 성격을 가지고 있습니다. RD의 최소값 350은 기록이 없는 선수에게 할당되는 초기값입니다.

갑자기 수학식이 등장하니까 머리가 멍해지고, 가슴이 답답해지는게 느껴지는데요. 심호흡 한 번 하시고 용기를 가지고 눈을 크게 뜨고 잘 보면 사실 Glicko는 2개의 숫자만 다루는 간단한 시스템입니다. 여기서는 저 수학식이 어떻게 유도되었는지 설명하지 않겠습니다. 논문[6] 에서도 자세한 설명이 없었고 제가 수학적 배경이 부족해서 하나 하나가 어떤 의미를 가지는지 이해할 수는 없었습니다.

이 수식부터 출발하겠습니다. 경기 결과 이후에 기존에 가지고 있던 점수(r)과 점수편차(RD)는 각각 새로운 값인 r’과 RD’으로 갱신됩니다. 수식을 잘 보시면 (1) q는 ln10/400인 상수입니다. Glicko 시스템은 2명 이상이 참여하는 경기에 대해서 계산할 수 있습니다. 자신 이외의 상대방의 수를 의미하는 m이 존재합니다. 시그마 수식 안에 있는 g(RD)도 다른 변수 없이 바로 계산할 수 있는 값이죠

나와 상대방 점수를 가지고 계산하는 조건부 확률 기대 승률 E의 수식은 Elo에서 쓰던 것과 유사한데요 (r-r_j)에 g(RD)를 추가로 곱해준 모습입니다.

정리하자면 매 경기마다 우리가 갱신하고자 하는 값은 점수(r)과 점수편차(RD)이지만, 계산에 이용되는 q, g(RD), d², E(s|r,r_j,RD_j)는 눈을 크게 뜨고 잘보면 쉽게 계산할 수 있는 값들입니다. 이렇게 보면 구현이 엄청 복잡한 알고리즘은 아니죠? 눈에 보이는대로 계산하면 됩니다.

Elo에서는 내 점수가 50점이 오르면 상대방은 50점이 내려가는 반면, Glicko는 그렇게 동작하진 않습니다. Glicko의 점수는 양측 선수들의 r과 RD값에 의존하여 변동됩니다. Glicko는 현재 전세계 최대 게임 플랫폼 Steam을 가진 Valve에서 유통하는 게임인 카운터 스트라이크와 팀 포트리스[7], 그리고 Dota2[8] 등에 적용되어 있습니다.

TrueSkill™

TrueSkill™[9]은 마이크로소프트가 Xbox Network에서 매치메이킹에 이용하기 위해 만든 평가 시스템입니다. TrueSkill은 베이즈 통계학에 기반한 머신러닝 기법을 사용하고 있습니다. 2018년에 TrueSkill 2[10]가 추가로 발표되었는데 크게 달라진게 아니여서 근간이 되는 TrueSkill를 먼저 보시고, 나중에 TrueSkill 2를 보셔도 무방합니다.

Elo와 Glicko가 체스 경기를 염두해두고 설계되었다면, TrueSkill은 처음부터 온라인 게임을 위해서 설계된 평가 시스템입니다. 그래서 마이크로소프트는 본인들이 만들게 될 평가 시스템의 요구사항을 다음과 같이 정리했습니다.

팀 게임을 지원할 것 : 팀 사이즈에 상관없이 일반적으로 적용할 수 있는 알고리즘이어야 한다.
Skill Rating을 바꿀 수 있을 것, 과거에 얼마나 많은 게임을 했던 상관없이 Skill Rating 변경이 가능해야 한다.
현재 작동하고 있는 매치메이커와 호환성을 가질것 (Elo, Glicko 등을 사용하고 있었어도 TrueSkill로 큰 변경없이 전환이 가능해야 한다)
게임의 본질과 일치하는 인센티브를 만들어야 한다. 예를 들어, 힐을 많이 주는 사람한테 점수를 주는 시스템은 플레이어가 스스로 자해하고 힐을 하는 걸로 악용할 수 있다.
학습에 필요한 데이터는 최소화 해야 한다. 게임을 처음 런칭한 직후에 바로 매치메이킹이 동작해야 함
연산 코스트가 작을 것
게임의 시스템이 변경되어도 스킬 시스템 자체의 변경이 크지 않을 것

여기서 TrueSkill 2는 아래 6가지 사항을 추가로 최적화 했습니다.

플레이어의 잠재 스킬은 개별적인 통계 수치에 기반한다. e.g. 개인적인 KDA와 팀 성적 결과 (승리,패배)
게임을 하다가 탈주하면, 포기한 것으로 간주하고 게임에서 졌다고 가정하고 값을 갱신한다.
어떤 게임 모드에서 플레이어의 능력치는 다른 게임 모드의 능력과 관계 있다고 가정한다. e.g. 리그 오브 레전드에서 협곡과 칼바람
첫 게임의 결과에 대해 큰 편향치(bias)를 가진다.
스쿼드를 꾸리는 경우 평소보다 더 퍼포먼스가 높다고 가정한다. 배틀그라운드에서 솔플보다 스쿼드가 더 유리하니까 1000점을 가진 솔플러와 300점대로 구성된 4명의 스쿼드를 동등하게 평가할 수 있다.
시간에 따른 실려의 불확실성 증가를 반영했다.

논문에서는 TrueSkill을 구현하기 그래프 모델에서 베이즈 추론을 하는 프레임워크인 Infer.NET[12]을 사용했다고 했습니다. 깃허브에 방문하시고 코드를 구경하다보면 TrueSkill을 구현한 테스트 코드를 발견하실 수 있습니다. 혹시 적용할 계획이 있으시면 해당 코드를 참고하면 좋을 것 같습니다.

지금부터는 제 나름대로 이해한 TrueSkill의 원리에 대해 설명해보려고 합니다. 아무래도 통계 기반 지식이 부족해서 충분할 설명이 안될 것 같습니다. TrueSkill에 대한 자세한 내용은 Moserware 블로그[11]에서 더 쉽고 자세히 설명되어 있으니까요. 제 설명이 부족하시다면 해당 블로그 글을 참고해주시기 바랍니다. TrueSkill을 설명하기 전에 베이즈 통계학에 대한 이야기 부터 시작해야합니다.

우리가 교과과정에서 가장 먼저 만나는 통계는 빈도주의 통계학입니다. 동전을 던져서 앞면이 나올 확률은 50%입니다. 전체 집합의 개수와 앞면이 나올 빈도수를 세어보고 연역적 사고로 확률을 계산합니다. 동전을 5번 던져보고 결과가 HTHHT가 나온 것을 보고 앞면이 나올 확률은 3/5 이구나 하지 않죠

베이즈 통계학은 빈도주의와 달리 데이터에 따라 설정한 파라미터에 대한 신념을 평가합니다. 베이즈 정리는 가설(Hypothesis)과 새로운 정보 (Evidence)가 존재하면 새로운 정보에 대해 가설을 업데이트 하는 방법 P(H|E)를 표현합니다. 연역적 사고로 통계를 표현하는 빈도주의와 달리 베이지안 주의는 경험을 통해 확률을 갱신하는 귀납적인 접근 방법이라고 할 수 있습니다.

TrueSkill은 플레이어들의 능력치 s와 세션 내의 팀 할당 정보인 A를 가지고 있을 때 경기 결과(r)의 확률 분포를 P(r|s, A)로 정의합니다. 이 식 자체는 나의 현재 능력치를 가지고 경기 결과를 얻는 것이지만, 우리가 계산하고 싶은 건 경기 결과를 보고 능력치를 어떻게 갱신할 것인가이죠. 이는 베이즈 정리에 의해 다음과 같이 유도됩니다.

플레이어들의 능력치의 분포를 나타내는 사전 확률 분포 p(s)는 플레이어들의 능력치의 결합 확률 분포라고 가정하고 인수분해(Factorization) 합니다.

TrueSkill도 플레이어의 능력치를 정규분포로 표현하고 있습니다. 그리고 경기에서 보여준 실제 퍼포먼스는 고정된 분산값 β²와 플레이어의 개별 능력치 s_i를 평균으로 가진 정규분포를 따른다고 가정합니다.

그리고 게임의 팀 퍼포먼스는 개별 플레이어들이 보여주는 퍼포먼스의 총합입니다. 팀 퍼포먼스 까지는 이미 결정된 값입니다. 플레이어의 스킬을 나타내는 평균(μ)과 분산(σ)은 경기 시작 전에 이미 주어진 값이고, 퍼포먼스 pi 는 고정된 분산값을 가진 정규 분포일 입니다.

팀 퍼포먼스 까지 계산했는데요. 팀 퍼포먼스가 더 큰 팀 순서대로 게임에서 순위를 차지할 것으로 가정해서 확률 분포를 정의합니다.

위 조건부 확률은 단순히 팀 성적대로 순위가 매겨질 것이라고 가정한 값이고 실제로는 관찰된 순위로 팀 성적을 정렬한 다음에 성적을 맵핑하니다. 게임에서 보여준 두 팀의 성적차(d)를 계산하는데요. 이 성적차이의 절댓값이 미리 설정한 상수인 엡실론(ε : draw margin) 이내에 있으면 비등한 경기였다고 해석합니다.

TrueSkill : Factor Graph

Factor Graph[13]는 확률론에서 확률 분포 함수를 인수분해 해서 계산할 때 표현하는 그래프를 말합니다. 위에서 소개했던 사전 확률 p(s)와 가능도 함수 p(r|s)를 Factor Graph로 표현하면 다음과 같이 됩니다.

지금부터는 제가 이 분야를 제대로 아는게 아니라서
그냥 앵무새 처럼 문서에 나와있는 대로 읊었습니다.

어우 무섭게 생긴 그래프인데요. 눈을 크게 뜨고 잘보면 전부 위에서 했던 이야기 입니다. 이 이분 그래프(Bipartite Graph | 인접한 노드끼리 색상을 다르게 색칠할 수 있는 그래프)에서 원으로 생긴 그래프에 표현된 s, p, t, d에 대한 정의는 위에서 모두 소개했습니다.

게임이 모두 끝나면 경기 결과 d_i에 대한 주변 확률(Marginal Distribution)을 계산 해야 합니다. 논문에서는 Message Passing 알고리즘과 KL Divergence를 사용한다는 언급이 있었는데요. 배경 지식이 부족해서 자세히 이해하진 못했습니다.

그럼 이걸 어떻게 계산하느냐? 위 그림에서 각 그래프 생긴 모양대로 계산 방법을 친절하게 알려주고 있는데요. 기반이 되는 이론은 베이즈 통계학 기반의 머신러닝 학문에서 다루는 Belief Propagation을 토대로 2001년에 논문으로 발표된 Expectation Propagation을 사용합니다.

수식의 의미를 깊이 이해하려면 굉장히 먼 길을 돌아가야 할 것 처럼 보입니다. 😔 다행히도 우리는 마이크로소프트 형님들이 미리 만들어주신 Infer.NET을 사용하면 쉽게 계산할 수 있습니다.

Variable<double>[] skill = new Variable<double>[playerMeans.Length];
InferenceEngine engine = new InferenceEngine(new ExpectationPropagation());

for (int i = 0; i < marg.Length; i++)
{
    marg[i] = engine.Infer(skill[i]);
    Console.WriteLine("Skills[" + i + "]=" + marg[i]);
}

TrueSkill의 수학적 배경에 대한 내용은 The Math behind TrueSkill[14]에서 좀 더 자세히 다루고 있으니 참고바랍니다. 복잡한 수학적 배경을 다 빼고 간단하게만 다루면 이길 것으로 예상한 팀이 이기면 점수가 조금 반영되고, 예상 외로 질 것 같은 팀이 이기면 점수가 크게 반영됩니다. TrueSkill은 얼마나 크게 이겼는지는 따지지 않고 경기 결과만 성적에 반영합니다.

**팀 성적 차이(= t)**가 음수라는 말은 이길 것으로 생각되었던 팀이 졌다는 걸 의미합니다.

TrueSkill : Experiment

지금부터는 논문에서 TrueSkill을 평가하는데 이용한 3가지 지표를 소개하려고 합니다. 순서대로 (1) Match Quality, (2) Win Probability, (3) Convergence Properties 입니다. 실험에서 사용한 데이터는 Xbox의 대표 타이틀인 헤일로 시리즈의 베타 테스트에서 수집한 자료입니다.

(1) Match Quality
위에서 두 팀 t1, t2의 성적 차이를 d = t1-t2로 계산했고 |d| ≤ ε 이면 비등한 경기였다고 평가한다고 했습니다. 이 때 엡실론(ε) 값을 draw margin이라고 합니다. 이 draw margin은 경험적으로 타이트한 게임이 되는 확률 분포에서 가져와서 사용했다고 합니다. Halo 5 에서는 1/10³으로 설정했다고 합니다.

TrueSkill이 원하는 건 경기 결과가 공정하게, 다르게 말하면 비등 비등한 경기가 되도록 매칭하는 겁니다. 아래 그래프는 Elo와 TrueSkill간의 비등한 경기 비율을 보여줍니다. TrueSkill이 Free for All(8명 끼리 서로 대전하는 모드)와 Head To Head(1 vs 1) 모드에서 높은 매칭 퀄리티를 보여줍니다.

(2) Win Probability
다음 그래프는 승률 분포를 보여줍니다. 승률이 크게 나온다면 잘하는 사람이 상대적으로 실력이 부족한 사람과 많이 매칭되었다는 것을 나타냅니다. TrueSkill은 게임 수가 적어도 승률이 35% ~ 65% 사이에 나타나도록 공정한 게임을 매치했습니다.

(3) Convergence Properties
Elo는 점수가 너무 느리게 수렴한다는 단점을 가지고 있습니다. 다음 그래프는 TrueSkill은 적은 게임 수에도 빠르게 점수가 수렴한다는 장점을 가지고 있습니다. 실력이 챌린저급인 선수는 빠르게 점수를 올려줘야 실력차이에 따른 불쾌한 경험(양학)을 당하는 게임 수가 줄어들 겁니다.

TrueSkill : 마무리

TrueSkill 2는 게임 중간에 탈주한 사람이 있는지, 게임이 비록 패배했지만 나는 잘했는지(내 탓 아님 = K/D/A 성적을 반영)를 추가로 반영했는데요. Factor Graph에서 노드를 추가한 방식이기 때문에 Expectation Propagation을 이용하는 기본 원리는 동일합니다.

지금까지 대표적인 실력 평가 방법인 Elo, Glicko, TrueSkill을 다루었습니다. 이런 스킬 평가 시스템은 대전 게임을 스포츠라는 시각을 가지면서 공정한 혹은 비등한 게임이 되도록 매칭하는 것을 목표로 하고 있습니다.

이제부터는 게임을 스포츠가 아닌 서비스로 바라보는 시각에서 출발한 2개의 매치메이킹 알고리즘을 소개해드리려고 합니다. TrueSkill이 지면이 꽤 많았는데요. 지금부터는 빠르게 소개드리고 마무리 합니다.

EOMM

EOMM[15]은 2017년, EA와 UCLA가 공동으로 연구하로 발표한 매치메이킹 프레임워크입니다. EOMM은 게임을 스포츠가 아닌 서비스로 바라보면서 이탈율(churn rate)을 최소화 하는 것을 목표로 합니다.

그래서 EOMM이 활용하는 정보가 TrueSkill 같은 정교한 평가 시스템에만 국한되지는 않고, 게임 설치 날짜, 얼마나 잦은 주기로 플레이 하는지 등 데이터를 사용합니다. 어차피 로지스틱 회귀를 돌릴 거라서 게임 결과에 영향을 줄 것 같은 요소를 포함시키면 됩니다.

EOMM의 매치메이킹은 플레이어 풀에서 플레이어 간의 관계를 완전 그래프로 표현합니다. 그래프에서 정점은 플레이어 상태를 나타내며 플레이어 프로필 정보들을 가지고 있습니다. 그리고 간선으로 이어진 두 플레이어의 관계를 확률분포 P(c|s_i, s_j)로 표현하는데요. 이는 si 플레이어가 sj와 게임하고 난 후 게임을 이탈하는 비율을 말합니다.

정리하면 EOMM은 두 플레이어의 예상 이탈율을 최소화 하도록 매치메이킹을 해야 하는데요. 이 때 아직 발견되지 않은 이탈 확률 분포는 로지스틱 회귀를 돌려서 계산합니다. c(si,sj)는 플레이어 i가 이탈할 확률을, c(sj,si)는 플레이어 j의 이탈율이기 때문에 이 총합이 최대한 작아야 합니다.

EOMM: 이론적 배경

여기서 이탈율(churn)을 나타내는 함수 c는 로지스틱 회귀 모델로 구하는데요. 회귀 모델이 분류하고자 하는 값은 플레이어가 게임 이후에 (1) 다음 게임을 진행하는지 혹은 (2) 게임을 종료하고 8시간 동안 나타나는 않는지 입니다.

만약 모든 매칭의 이탈율에 대해서 c(승리) + c(패배) > 2 * c(비등함)의 결과를 보여준다면, 위에서 다루었듯 TrueSkil이 항상 비등한 경기를 추구하기 때문에 그냥 SBMM을 사용하면 될 겁니다.

그런데 만약 c(승리) + c(패배) < 2 * (비등함) 이라면 어떨까요? 매번 비등한 경기를 추구하는 SBMM이 플레이어가 게임에 몰입하는데 방해요소로 작용합니다. 물론 이런 가정이 공평한 게임이 좋은 게임이다라는 직관과는 모순되긴 해도 실제 게임에서는 이 현상이 충분히 발생할 수 있습니다.

EOMM : 예측 모델 및 그래프 매칭

로지스틱 회귀 모델은 고객이탈예측 모델을 개발하는데 많이 사용되어 왔습니다. 아래 (4)번 수식은 위에서 봐왔던 대로 두 플레이어를 매칭했을 때 계산되는 이탈율을 의미합니다. 이를 (5)번 수식과 동일한 것으로 보는데요. o(i,j)는 플레이어 i의 경기 결과를 의미합니다. o(i,j)가 승리라면 반대로 o(j,i)는 패배가 됩니다. 다시 말하면, 승리,패배,무승부의 경우에 계산되는 이탈율의 합으로 나타냅니다.

(6)에서 경기 결과에 대한 확률 분포를 구할 때, 플레이어의 능력치 s가 μ로 바뀌는데 이 값은 Elo, Glicko와 같은 평가 시스템을 도입했을 때 사용하는 값입니다. 마지막으로, 이탈 함수 c에서 상대방 플레이어 정보가 제거되었는데요. 논문에서는 경기 결과에 대한 확률 분포를 구했다면 이탈율은 상대방 정보와 독립적일 수 있다고 하는데요. 저는 랜덤 매칭보다 EOMM이 더 낫다는 가정하에 설정된 수식이라고 이해했습니다.

EOMM의 예측모델은 이 이탈율을 계산하기 위해 로지스틱 회귀를 사용합니다. 회귀 모델의 입력값으로는 플레이어의 상태값과 플레이어의 최근 10경기, 지난 경기 대비 흐른 시간 등을 참고해서 플레이어가 경기 이후에 8시간 이내로 게임을 즐길 것인지 아니면 게임을 이탈해버릴 것인지를 분류합니다.

예측 모델 까지 준비가 되었으니, 이제 플레이어 풀에서 실제 매칭을 해야하는데요. 완전 그래프에서 각 정점을 중복 없이 1:1로 매칭하는 문제를 완전 매칭(perfect matching)문제라 부릅니다. EOMM은 가중치의 합을 최소화 하는 것이 목적이기에 최소 가중치 완전 매칭(WMPM)이라고 부릅니다. 대표적으로 헝가리안 알고리즘[16][17]으로 계산할 수 있습니다 .알고리즘 자체는 시간 복잡도가 O(N³)으로 느린편이긴 하지만, 매칭 풀에 플레이어 수가 평균 500명 정도라면 평범한 스펙을 가진 서버에서 1~2초 정도에 전부 매칭시킬 수 있습니다.

온라인 경쟁 프로그래밍 대회에서 수행 시간 1초를 사용하는데 필요한 시간복잡도가 흔히 10⁸인 것으로 알려져 있습니다. 이건 어떤 스펙의 서버를 사용하느냐에 따라 다를 수 있습니다. 추가로 EOMM을 사용한다면 완전 그래프를 형성해야 하는 만큼 매칭 서버가 수평 확장하는 것을 기대하기 어렵겠다는 생각을 햇습니다.

EOMM 평가

EOMM의 평가에는 알아두면 좋을 내용들이 몇 가지 있습니다. 아래 표는 EA가 운영하는 게임에서 데이터를 가져 왔구요. 플레이어들이 마지막 3경기를 어떤 양상으로 보냈는지에 따른 이탈율을 보여줍니다.

예를 들어 연속된 3번의 승리(WWW)를 경험한 플레이어의 이탈율은 3.7% 였고, 두번의 패배와 한 번의 승리(LLW)를 경험한 사람은 2.6%, 3번 연속 패배한 사람은 5.1%로 가장 높은 이탈율을 보여주었습니다. 계속 이기기만 하는 게임의 이탈율이 제법 높았다는 게 재밌었습니다.

EOMM의 성능 평가 부분에서는 스킬 기반의 SBMM과 랜덤 매칭을 비교합니다. 아래 표는 한 번의 매칭 이후에 플레이어 잔존율을 보여주는데요. SBMM과 비교해서 최대 1.1% 정도의 성능 향상을 보여줍니다. 당장은 크기가 작아보이지만 같은 플레이어가 EOMM 매칭을 20번 정도 경험하면 SBMM대비 15% 높은 잔존율을 보여줍니다.

EnMatch

EnMatch는 올해 개최된 AAAI’24 컨퍼런스에서 중국의 대형 게임사인 넷이즈(NetEase)산하의 Fuxi AI Lab에서 발표한 매치메이킹 알고리즘입니다.

EOMM이 전통적인 머신러닝 기법인 로지스틱 회귀를 이용했다면 EnMatch는 구글이 조합 최적화 문제(e.g. Convex Hull, 외판원 순회)를 인공신경망으로 계산할 수 있도록 개발한 포인터 네트워크[19]를 활용한게 특징입니다.

포인터 네트워크에 대한 자세한 설명은 별도 포스팅에서 따로 다루려고 합니다. 이 포스팅에서는 EnMatch에 대한 원리보다는 실험 결과 위주로 소개하겠습니다.

EnMatch 평가

넷이즈의 Fuxi AI Lab에서도 본인들이 운영하는 게임의 라이브 데이터를 가지고 실험을 진행했습니다. EOMM에서 확장해서 경기 도중에 주고받은 채팅 수와 좋아요(Upvote), 싫어요(Downvote) 버튼을 누른 회수를 수집했습니다.

그리고 실력이 비등한 사람끼리 매칭한 게임 결과(fair)와 고수준의 플레이어와 실력이 부족한 플레이어 끼리 팀을 이루게 한 경우(diversity)의 사회적인 인터랙션을 분석합니다. 다양성을 갖춘 팀 일수록 뚜렷하게 높은 사회적인 상호작용을 보여주는데요. 이를 논문에서는 Collaboration Engagement 라고 부릅니다. 그리고 다음과 같이 결론을 냅니다.

이 결과는 공평한 게임만으로는 좋은 유저 경험을 유지할 수 없습니다. cross-tier 매치메이킹은 유저의 몰입을 최적화 하기 위해 필연적으로 사용되어야 합니다.
the results also show that ensuring fair games alone is not suffcient to maintain a good user experience, and cross-tier matchmaking is necessary to optimize player engagement

EOMM이 마지막 3경기 결과를 토대로 이탈율을 분석했다면, EnMatch는 플레이어가 선택한 직업군에 따른 이탈율을 분석했습니다. 논문에는 어떤 게임의 데이터인지는 안나와있지만 넷이즈가 오버워치를 퍼블리싱하고 있으니까 대입해서 상상해 봅시다.

공격군 캐릭터(Main)로 3번 이긴 유저의 이탈율보다, 지원형 캐릭터(Support)로만 3번 이긴 유저의 이탈율이 더 높았습니다. 반대로 패배한 경우에는 공격군으로 연속해서 진 사람의 이탈율이 8.4%로 가장 높았는데요. 지원형 캐릭터를 고른 유저보다 패배에 따른 좌절감을 더 크게 느끼나 봅니다.

이제 모든 걸 다 건너 뛰어서 실험 결과에 대한 내용입니다. 학습에 사용된 데이터셋은 SPG, RPGPVP라는 이름으로 등장한 2개의 게임 데이터를 사용했습니다. 모델이 알고싶은 건 플레이어가 게임이 끝난 이후에 30분 동안 남아있었는지, 화나서 게임을 꺼버렸는지 여부입니다.

다음으로 등장하는 건 실험 결과인데요. 분류 모델을 평가할 때 사용하는 메트릭인 정확도(ACC)와 AUC를 비교했고 가장 높은 성능을 보여줍니다. 참고로 평가 표에 등장하는 OptMatch도 같은 연구실에서 발표한 논문입니다.

EnMatch 실제 적용 후기

이 부분이 논문에서 가장 재밌는 파트입니다. 넷이즈는 EnMatch를 실제로 본인들이 운영중인 게임에 적용해서 성능을 평가했습니다. OptMatch(KDD’20)와 GloMatch (KDD’20)를 비교했는데요. 둘 다 같은 연구실에서 예전에 발표한 매치메이킹 논문입니다.

게임이 끝난 이후에 30분 안에 다시 게임을 진행한 플레이어를 기준으로 평가했으며 EnMatch가 가장 높은 성능을 보여주었다고 합니다.

마무리

이번 포스팅에서는 공정한 게임을 만들기 위해 플레이어의 능력을 객관적으로 평가하고자 하는 Elo, Glicko, TrueSkill을 소개했습니다. 다음으로는 게임을 스포츠가 아닌 서비스로 바라보면서 고객 이탈율을 줄이기 위한 목적으로 설계된 EOMM과 EnMatch 논문을 살펴봤습니다.

만약 이런 매치메이킹 알고리즘을 진짜로 사용한다고 하면, 실제로는 고려해야 할 변수가 더 많습니다. 한 예시를 들자면 논문에서는 매칭 대기시간은 평가 대상으로 고려하지 않는데요. 하지만, 아마존이 A/B 테스트에서 100ms의 레이턴시가 증가하면 매출이 1% 감소하는 것을 발견하고, 구글이 0.5초의 딜레이가 발생하면 20% 트래픽 감소를 경험한 것 처럼 길어진 매칭 대기시간이 주는 부정적인 영향도 함께 고려해야 합니다.

마지막으로 EOMM으로 부터 시작한 이탈율 개선을 위한 매치메이킹 시스템이 이탈 위험 고객을 위해 게임에 장기적으로 충성하는 유저들의 경험을 해친다는 주장이 있습니다. 이에 대한 자세한 내용은 아래 유튜브에 소개되어 있으니, 흥미 있으신 분들은 같이 보시면 재밌으실 것 같습니다.