게임 속 랭킹, 어떻게 정할까? (1) 입문

 

 

*이 글을 온전히 이해하기 위해서 확률, 평균, 분산 등 기본적인 통계 개념이 필요함을 알려드립니다*

 

 GLICKO 알고리즘은 기존의 레이팅 방식이 갖는 여러 가지 비현실적인 부분들을 개선한 레이팅(점수 매기기) 알고리즘이다. 실제 GLICKO 알고리즘의 유도 과정은 정규분포 CDF의 로지스틱 근사, 로그우도(Loglikelihood)와 베이즈 정리(Bayes theorem) 및 수치해석의 뉴턴-랩슨법(Newton-Rhapson method)을 활용하기 때문에 수학과 2학년 이상의 백그라운드가 있지 않다면 이해하기 어렵다. 따라서 이하에서는 독자의 이해를 돕기 위해 직관적인 접근을 취한다. 논문의 유도과정은 세번째 글에서 설명하고 있다.

 

1. 레이팅의 기본 아이디어

 플레이어 A와 B가 경기를 가진 후, 플레이어 A의 새로운 점수를 계산하는 것을 목표로 정하자. 우선, 레이팅을 논하려면 다음과 같은 미지수 정의가 필요하다.

 

$r_A$ = 플레이어 A의 현재 점수

$r_{A,new}$ = 플레이어 A의 다음 점수

$r_B$ = 플레이어 B의 현재 점수

 

A와 B가 경기를 해서 A가 이기면 A는 점수를 얻고 B는 점수를 잃어야 한다. 그렇다면 얼마를 잃고 얼마를 얻어야 하는지가 관건이다.

 

(1) 가장 단순한 모델

 가장 간단한 모델은 항상 일정한 점수 $r$을 얻는 것이다. 이 경우 레이팅 알고리즘은 다음과 같다.

 

$r_{A,new} = r_A + W \times r$

 

단, $W$는 경기 결과를 나타내는 값으로 승리시 $W = 1$, 비기면 $W = 0$, 그리고 패하면 $W = -1$으로 정의한다. 이 부분은 설계자가 다르게 정할 수도 있다.

 

예1) A의 현재 점수가 $1500$점이고 $r=10$일 때, 경기에서 패하면 A의 새로운 점수는 $1490$이 된다.

 

이 모델은 다음과 같은 단점들이 있다.

 

① 매우 이기기 어려운 상대를 이기나 쉬운 상대를 이기나 얻는 점수가 같다.

② 과거에 1500점인 사람이 오랜만에 게임을 접속하더라도 여전히 같은 실력으로 계산에 반영된다.

 

즉, 실력차이와 시간에 의한 실력변화를 반영하지 못하는 식이다.

 

(2) 실력차를 반영한 모델

 두 사람의 실력 차이를 어떻게 수학적으로 표현할 것인가? 가장 단순한 방법은 실력 차를 곧 점수 차로 간주하는 것이다. 다음 식을 보면

 

$r_{A,new} = r_A + W \times | r_A - r_B | $

 

실력 차가 클수록 더 많은 점수를 얻거나 잃을 수 있다. 그런데 고수 한명 운좋게 이겼다고 점수가 급상승하거나 하수 한명한테 재수없게 졌다고 점수가 크게 변하는 것은 비합리적이므로 적당한 상수를 도입해서 점수 변동 폭을 줄여야 한다. 그래서 식은 다음과 같다.

 

$ r_{A,new} = r_A + W \times k \times | r_A - r_B | $

 

여기서 $k$는 적당한 값으로 세팅하면 된다.

 

예2) 점수 1500인 A가 점수 1900인 B를 이겼다. $k = 0.1$이라 하면 A의 새로운 점수는 1540점이다.

 

이 모델은 굉장히 초급 모델임에도 꽤 합리적인 면이 많다. 그렇지만 실제로 사용하기엔 아쉬운 부분이 많다. 예를 들면,

 

① 점수가 같은 사람을 상대로 이기거나 지더라도 점수 변화가 없다.

② 점수 차이가 실제 실력 차이를 어떻게 반영하는지도 알기 어렵다. 예를 들어, 200점 높은 상대면 얼마나 나보다 잘하는지 알기 어렵다.

③ $k$값이 얼마가 되어야 합리적인지 판단하는 것이 어렵다.

 

2. FIDE 알고리즘 소개

새계체스연맹(FIDE)에서 만든 레이팅 방법이다. FIDE는 점수 차이를 통해 승률을 예상할 수 있는 모델을 만들었고 지금 널리 사용되고 있다. 우선, FIDE는 다음을 가정했다.

 

FIDE의 대전제 : 점수 차이가 400점이 나면 승리 가능성이 1:10이 되어야 한다

 

위와 같은 기능을 갖는 확률식 $W_e$ 다음과 같다.

 

$W_e = \dfrac{ 1 }{ 10^{ -\frac{ r_A - r_B }{ 400 } } + 1 }$

 

($W_e$ 는 Expected winning probability를 나타내는 표현인 것 같다)

 

그리고 여기선 $W$의 정의를 다르게 한다. 승리하면 $W=1$, 무승부시 $W=0.5$, 그리고 패배시 $W=0$. 그러면 레이팅 공식은 다음과 같다.

 

$r_{A,new} = r_A + k \times (W - W_e)$

 

$W$를 수정하여 동일한 실력의 상대를 이기더라도 점수가 변하지 않는 단점을 없앴다. 게다가 확률모델을 도입하여 점수 차이가 실력 차이를 얼마나 나타내는지도 예측할 수 있게 되었다.

 

다만, 여기서도 단점이 있다.

 

① 경기를 갖지 못한 시간에 따른 실력 변화를 반영하지 못한다.

② 여전히 적정 $k$값을 얼마로 해야 하는지 알기 어렵다

 

$k$값이야 단체를 운영하면서 적정한 값을 경험적으로 찾아볼 수 있겠지만 1번은 극복이 어렵다. 이 부분들을 합리적으로 해결한 알고리즘이 GLICKO알고리즘이다.

 

다음 글에서..