다인전 매치메이킹 벤치마크

#matchmaking
#elo
#glicko
#glicko2
#benchmark

2019년 10월 01일 작성

TL;DR

코드는 여기¹

개인전이든 다인전이든, 특별한 일 없으면 Glicko2² 쓰자.

시작하며

4:4 다인전에서 랭킹 시스템을 구현할 일이 생겨서 조사를 하던 중 기존에 사용중이던 ELO³ 는 다인전에서 동작하지 않는다는 글을 보게 되었다.⁴⁵ 그래서 Glicko2 라는 알고리즘으로 변경을 하려고 했는데, 2가지 의문이 생겼다.

ELO 가 정말 4:4 다인전에서 동작안하는지
Glicko2 로 바꾸면 ELO 보다 매칭 퀄리티가 좋아지는지, 그리고 얼마나 좋아지는지

본 글에서는 위의 2가지 의문을 풀어본다.

실험방법

매치 진행 순서는 아래와 같으며 각 순서별로 처리는 후술한다.

더미 사용자 생성
매치메이킹 큐에 등록
매치메이킹
대전!!
결과 반영
더미 사용자 생성
총 1만명의 사용자를 생성한다.

더미 사용자 생성

10000개의 사용자를 생성한다. 이 때 사용자의 실력(strength 또는 skill)은 정규분포로 (평균 1500, 표준편차 400) 으로 생성하고 모든 사용자에게 1500 점 레이팅을 부여한다.

매치메이킹 큐에 등록

사용자를 랜덤하게 3000명씩 뽑아서 큐에 등록한다.

큐는 redis 를 사용하거나 직접구현하거나 해도 되지만,

redis 는 외부 툴의 의존성이 생기도, 직접구현은 우선순위 큐 range 구현이 귀찮다.

따라서 본 문서는 sqlite3 를 메모리 드라이버로 사용하여 db 를 큐처럼 사용한다.(고전적인 큐 방식)

매치메이킹

사용자의 레이팅은 최대 200 차이까지 날 수 있다. 대상 사용자를 모두 가져온 뒤 셔플하여 랜덤 매칭한다.

대전!!

승패에 대한 결과는, 팀의 평균 실력 눈수를 가진 다면주사위를 던진다고 생각하자.(사용자의 실력이 1500 이면 1500개의 면을 가진 주사위를 던짐)

각 팀은 해당 주사위를 동시에 던져서 높은 숫자가 나오는 팀이 승리! 단, 단판은 운적인 요소가 많으니까 50 라운드를 진행해서 많이 이긴쪽이 경기를 이긴것으로 한다.

개인전은 두 알고리즘 다 튜닝없이 알고리즘 대로 한다.

다인전에서 ELO는 양팀 평균점수로 하고 K 값을 각각 1/4 로 나눠서 업데이트 하기 때문에 K 값을 64로 크게 잡아 주었다.

glicko는 팀 컴포지션 방식으로 상대방의 평균점수와 나의 실제 점수를 이용하여 1:1 을 여러번 한 것처럼 처리한다.³

결과반영

결과는 알고리즘별로 적절히 반영해준다.

실험결과

그래프가 1차원 함수형태로 보여야 사용자의 실력이 레이팅에 잘 반영되었다고 할 수 있다.

또한 레이팅의 최저점(left-bottom) 에서 최고점(right-top) 차이가 커야 실력차이가 나는 경우에는 매칭이 잘 안잡힌다고 볼 수 있다.

1:1 매치

ELO로 1:1 에서 사용자당 10판 정도를 돌리면 아래와 같은 결과를 얻을 수 있다.

ELO 가 잘 동작한다고 알려진 1:1 에서도 10판으로는 약간 모자라 보이지만 대체적으로 만족 할 만하다.

대략 30판정도 돌리면 자기 자리를 찾아가는 느낌인데 완전하지는 않다.

다만 실력에 비해 레이팅의 분산이 제대로 이뤄지지 않아서 실력차가 많이 나는 사람끼리도 매칭이 잘될 위험이 있다.

K 값이 너무 낮으면 수렴도 늦고 분산도 작아지기 때문에 K 값을 사용자의 게임수 및 레이팅에 따라 적절히 조절해주면 분산을 시킬 수 있을것으로 보인다.

반면 glicko 는 10판정도만 돌려도 대충 쭉쭉 분산되어서 실제 실력이랑 레이팅이 적절히 반영되는 느낌이다.

30판 정도 돌리면 자기자리를 완전히 찾아간 느낌이다. 위에서 언급한대로 시그마 업데이트를 하지 않았고 업데이트를 하면 좀 더 빠르게 찾아가지 않을까 생각된다.

4:4 매치

다인전은 ELO의 경우 10판으로는 아예 실력 반영이 안된다. 20판을 해도 마찬가지이며, 40판을 돌려도 사실상 수렴이 안된다고 보인다.

개인적으로 테스트 했을때 K 를 4배로 올리고 매칭시켜도 전혀 수렴하지 않는다.

알고리즘 외적으로 튜닝을 하거나 ELO 에서 팀단위의 계산방식을 바꿔야할 것 같다.

glicko 의 경우 10판 정도 돌려면 아주 대략의 모양이 나오고, 30판이면 어느정도 직선 형태로 모양이 갖춰진다. 이미 10판정도에서 방향성은 갖춰진 상태라 큰 차이는 안보이는 느낌

마치며

개인전에서는 ELO 가 수렴에 필요한 판수는 비슷해보이지만 판 수가 추가될 수록 glicko 가 더 잘 동작한다.

다인전에서는 ELO 가 동작하지 않는다. glicko 는 납득할만 한 수준으로 동작하는 것 같다. (물론 튜닝이 필요한 수준)

사용자 랜덤생성시 시드를 동일하게 주고 똑같이 생성하는게 좀 더 정확하다. 해당 내용을 추가로 실험했으나 큰 차이가 없어서 본 글의 내용을 수정하지는 않았다.

Haandol