회사에서 놀면서 Rating System 을 조사한 것을 대충 정리해보았다.
시작은 여기서부터
Glicko rating system 이 있고, 그건 ELO의 개선판
Glicko 2 같은 경우에는 CS:GO 나 GW2 에서 실제로 응용되어 사용됨 (링크2가 GW2의 매치메이킹)
먼저 링크7 부터 읽었다. survey paper 라 가장 읽기 쉬울 것이라고 생각했기 때문. 초반 내용은 user 들의 skill distribution 을 normal distribution 이라고 가정해도 무방하다는 내용 더하기 약간의 통계학이 있는 기본적인 내용이었다.
처음에 ELO 에 대한 내용이 나왔다. Expectation 을 기준으로 승 패 했을 때 가중치를 다르게 해서 새롭게 rating 을 매기는 방식이었다.
가장 내가 주목한 것은 해당하는 내용이 Zero Sum 에 기반한다는 것이다. 유저가 유입되고 있는 상황에서의 컨트롤을 어떻게 할 건지? 그리고 열심히 하는 유저에게 보상을 더 줘야 하는데 그걸 어떻게 할 지? 그런 것들에 대한 의문이 들었다.
물론 ELO의 가중치에 약간의 customization 을 해서 점점 rating sum inflation 을 유도할 수도 있다. 하지만 이것만으로 절대 충분하지는 않다고 생각.
결국 ELO 는 수학적으로 어떻게 player skill 을 정확히 반영할 것인가 에 초점을 두고 있었다. 하지만 나의 관심은 이것 + 열심히 하는 유저에게 주는 보상 및 참여 유도까지 고려하고 싶은 비즈니스적 마인드를 넣고 싶은데 아직은 별로 만족스럽지 않은 것 같다.
다음 내용은 Glicko 였다. 해당 알고리즘은 ELO 의 부족한 점을 채우는 것인데, Reliability 라는 개념을 도입했다. 플레이어가 시간 내에 많이 플레이하면 할 수록 해당 게임의 Reliability 는 올라간다. 하지만 플레이어가 복귀 유저일 때 Reliability 는 내려간다. (오랜만에 플레이 했으므로 당연하다고 본다) 이를 RD 라는 개념을 이용하여 모델링 하였다.
따라서 이러한 사실을 이용하여 time-factor 을 조정해 해당 게임의 sensitivity 를 조정한다. 오랜만에 플레이한 유저의 경우에는 sensitivity 가 크다.
Glicko 의 식은 간단했던 ELO 와는 다르게 복잡했다. 하지만 결국 Zero Sum 기반의 ELO 에서 time factor 를 추가한 정도? 그러나 시간 이외의 다른 factor 를 쓸 수 있으면 더 정확해질 것 같다
트루스킬 페이퍼와 요 링크를 읽었다. 트루스킬은 먼저 되게 복잡했다. ELO 의 문제점 중, 플레이어의 경험이나 기복 등을 고려하지 않는다는 점이 있었는데 그것을 보완한 것이라고 할 수 있다.
트루스킬에서 가장 인상적이었던 것은 플레이어의 스킬 자체를 그냥 숫자로 나타내는 것이 아닌, (mean, variation) pair 로 나타낸다는 점이었다. 선수의 평균적인 실력, 기복, 경기 수가 적어 정확하지 않은 플레이어의 uncertainty 도 고려한 점이었다.
알고리즘에서 예상한 결과가 나오면 uncertainty 가 줄어들고, 예상하지 못한 upset 이 나왔을 땐 uncertainty 가 늘어난다.
TrueSkill의 수학적인 부분은 이해하기 힘들다. ㅠㅠ 내가 수학이 부족하다.
TrueSkill의 가장 큰 장점은 수렴속도인 것 같다. 유저 당 5게임 정도면 수렴이 되는데 ELO와 비교해보았을 땐 어-썸한 차이이다.
수학적인 내용을 이해하려면 확률론을 더 공부해야 한다.
그리고 TrueSkill의 가장 큰 문제점은 TrueSkill 알고리즘에 특허가 걸려 있어서 라이센스를 사야 한다는 것이다. 윈도우 폰으로 내면 라이센스 무료로 줄라나 ㅎㅎ
TrueSkill 을 제대로 이해하려면 Factor Graph, Belief Propagation 과 같은 확률론에 대한 기본 지식이 있어야 할 것 같다. 확률론도 공부 스택에 넣어놓자.
이걸 읽어보면 결국 ELO 의 처음과 끝은 K-value optimization 인 것 같다. That’s Engineering.
배치는 그냥 일정 ELO 에서 시작하고, 안보여주면 끝인 거 같다 ㅋㅋㅋㅋㅋㅋ 큰 건 없네. 경험적인 부분이 가장 중요한 듯
매치메이킹
죠기 링크 강의를 대충 들어보면, multiple queue 매칭이 뭔가 잘 될 거 같아 보인다. 사실 1:1 이라서 시간별로 정렬해서 끊는 매칭도 괜찮아 보이긴 함.
내가 진행하는 프로젝트에 넣기엔 오버스펙처럼 보이는 방식인, 클러스터링을 쓰는 방식이 있는데 다대다에서만 의미가 있으므로 패스.
현실적인 Rating System 선택
- 결국은 ELO + 양념 vs Glicko + RD Customization
Trueskill 을 쓰기엔 특허도 걸리고, 수학적으로 이해를 못한 것도 걸린다. 내가 이걸 NDC2015에서 발표한 사람처럼 1년동안 이것만 팔 수도 없고…….
ELO를 쓰려면 배치가 필요하다. Glicko는 사실 초반 배치 과정이 필요없긴 하지만 그냥 배치처럼 처음에 안 보여주는 것도 좋을 듯 하다.
만약 신규 프로젝트에서 rating 제대로 쓸려면 이거 둘 중 하나가 될 듯 하다.
양념의 방법으로는 최고 티어에서 보상 주기, Decay 시키기, ELO 에서 K 값 조정 등등이 있을 것이다.
이 둘을 비교하기 위해선 직접 코딩을 해서 테스팅을 해야 하는 방법 밖에는 없는 것 같다. Visualization 까지 하려고 생각하니 귀찮다. 해야 하긴 하니 나중에 하도록 하겠다.
한번 계산할 때 계산량 자체는 Glicko 가 많은 편이지만 유저당 루트 계산 2~3번 지수 계산 1~2번 차이라 그렇게 심한 차이가 날지는 잘 모르겠다. 해당 부분도 테스트 해야 하긴 하다.
Golang으로 짠 Glicko 레이팅 시스템 이 있다. 이거 써먹어야지. ELO 는 사실 쉬우니까.
앞으로
앞으로 더 나아가기 위해선 직접 코드를 짜고 시뮬레이션을 해보아야 한다. 여러가지 케이스에 대해서 시뮬레이션을 하고 결론을 도출해야 한다. 이 부분은 미래의 나에게 맡기겠다.
또한 신규 프로젝트의 경우에는 덱 기반의 게임이 될 것 같은데, 이 경우에는 어떤 식으로 Customization 을 해야할 지 더 고민해봐야 할 것 같다.