게임 속 랭킹, 어떻게 정할까? (2) GLICKO 소개

 

3. GLICKO 알고리즘

 GLICKO 알고리즘은 플레이어의 실력을 하나의 점수로 표현하지 않고 어떤 정규분포를 따르는 확률변수로 바라본다. 예를 들어 현재 점수가 1400인 플레이어의 진짜 점수가 평균이 1400이고 편차가 100인 정규분포를 따른다면 진짜 점수가 1204점과 1596 사이에 있을 확률이 95%이다. 즉, 진짜 점수를 알 수는 거의 없고 이렇게 확률로만 답할 수 있다. 플레이어가 꾸준히 경기를 갖게 되면 누적된 데이터들을 통해 표준편차가 점점 줄어들어 10이 된다면 진짜 점수는 1381점과 1419점 사이에 있을 확률이 95%가 된다.

 

(1) 좀 더 정교한 확률 계산

 실력을 정규분포로 다루므로 확률 계산 방식이 FIDE와는 달라진다. 우선 다음과 같이 미지수들을 정의하자.

 

$r_A$ = A의 현재 점수, $X_A$ = A의 진정한 점수를 나타내는 확률변수

$r_B$ = B의 현재 점수, $X_B$ = B의 진정한 점수를 나타내는 확률변수

(단, $X_A$와 $X_B$는 독립)

 

그러면 Glicko 방법의 전제에 따라 다음이 성립한다.

 

$X_A \sim N(r_A, \sigma_A^2)$

$X_B \sim N(r_B, \sigma_B^2)$

 

이제, A가 B를 이길 확률 $P(\text{A wins})$를 계산해보자. A가 B를 이긴다는 것은 A의 진짜 점수가 B의 진짜 점수보다 크다는 것이므로 다음과 같이 식을 정리할 수 있다.

 

$P = P(\text{A wins}) = P(X_A > X_B) = P(X_A - X_B > 0)$

 

이고 $D = X_A - X_B \sim N(r_A - r_B, \sigma_A^2+\sigma_B^2)$ 이므로 ($V[X] = E[X^2] - \{ E[X] \}^2$과 두 확률변수가 독립임을 이용하여 유도할 수 있다)

 

$P(\text{A wins}) = P(D > 0) = \Phi \Bigg( \dfrac{r_A-r_B}{\sqrt{\sigma_A^2+\sigma_B^2}} \Bigg)$

 

이다. 여기서 $\Phi$는 정규분포 $ N(r_A - r_B, \sigma_A^2+\sigma_B^2)$의 누적분포함수(CDF)이다.

 

$ \Phi(x) = \displaystyle \int_{-\infty}^{x} \dfrac{1}{(\sigma_A^2+\sigma_B^2)\sqrt{2\pi}}  e^{ -\frac{1}{2} \frac{ \{t -( r_A-r_B ) \}^2 }{ \sigma_A^2+\sigma_B^2 } } dt$

 

(2) 근사 - 정규분포 CDF를 로지스틱 함수로

 그런데 정규분포의 누적분포함수는 계산이 버겁기 때문에(특히, 90년대에는 더더욱) 비슷한 함수로 근사해야 한다. 아래 그래프를 보면 알 수 있듯 정규분포의 누적분포함수와 로지스틱 함수는 생김새가 비슷함에도 식은 로지스틱이 훨씬 쉽다. 그래서 여기서 최초로 근사가 들어간다.

 

로지스틱 함수의 식은 $\dfrac{1}{1+e^{-kx}}$인데, 정규분포의 분산이 1일 때, 로지스틱 분포의 분산은 $\dfrac{\pi^2}{3}$이므로 $k=\dfrac{\pi}{\sqrt{3}}$이 되어야 한다. 게다가 ELO에서 점수가 400점 차이 나면 승률이 90%가 되도록 정해두었으므로 이를 따르면 확률은 다음과 같아진다.

 

$P(\text{A wins})=\dfrac{1}{1+10^{-\frac{k(r_A-r_B)}{400}}}$

 

여기서, 상대방의 상대 실력의 불확실성이 높을수록(즉, 분산이 클수록) 경기 정보량이 적다는 걸 반영하기 위해서 다음과 같이 수정한다.

 

$P(\text{A wins})=\dfrac{1}{1+10^{-\frac{g(\sigma_B)(r_A-r_B)}{400}}}$

 

단, $g(\sigma_B) = \dfrac{ 1 }{ \sqrt{ 1 + \frac{3q^2\sigma_B^2}{\pi^2} } }$ 이고 $q=\dfrac{\ln(10)}{400}$이다. $q$는 400점 차이나면 승률이 약 90%가 되도록 조정해주는 상수이다. 이런 식과 값들이 왜 저런 모양이어야 하는지는 실제 유도과정에 나와 있다. 이 부분은 다음 글에서 확인해보자.

 

지금 우리는 예상 승률을 좀 더 현실적으로 구했다. 하지만 식의 본질적인 형태는 전혀 변하지 않았다. 즉, 레이팅 식은 

 

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

 

이다.

(3) 불확실성 등 여러 요소들을 고려

 위의 공식도 분명 지금까지 만든 공식들보다는 좋지만 경기 후 얻거나 잃는 점수의 크기는 다음 요소들을 고려해야 한다.

 

① 400점 차이가 나면 실력이 10배 차이난다

② 상대 실력 불확실성(분산)이 크면 점수 변동이 작아야 한다(경기 결과를 신뢰하기 어려우므로)

③ A의 실력 불확실성(분산)이 크면 점수 변동이 커야 한다(그래야 실제 실력에 빠르게 수렴 가능하므로)

④ 상대에 대한 정보가 많이 주어질 수록 경기 결과가 신뢰할만 하므로 더 많은 점수를 얻어야 한다.

 

①에 의해서 식은 다음과 같이 바뀌고

 

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

 

단, $q=\dfrac{ln10}{400}$ 이다.

②에 의해서는

 

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

 

③에 의해서는

 

$r_{A,new} = r_A +  q  \times \sigma_A^2 \times g(\sigma_B)  (W - W_e)$

 

④까지 고려하면 

 

$r_{A,new} = r_A +  \dfrac{ q }{ \dfrac{1}{\sigma_A^2} + \dfrac{1}{d^2} } \times g(\sigma_B)  (W - W_e)$

 

단, $\dfrac{1}{d^2}=q^2g(\sigma_B)W_e(1-W_e)$ 이다.

 

이렇게 될 수 있다. 조금은 다르게 모델링할 수 있지만 실제 논문에서 로그우도의 최적화와 근사를 이용해서 나온 인자들이므로 함부로 수정하면 안 된다.

 

(4) 시간에 따른 실력의 불확실성을 고려

 그런데 A가 오랜만에 게임을 한다면 그 마지막 게임과의 시간 차에 의한 실력 변화가 있을 수 있으므로 계산에 사용하는 A의 편차를 증가시켜야 한다. 따라서 A의 편차를 다음과 같이 변형한다.

 

$\sigma_A' = \sqrt{\sigma_A^2 + c^2t}$

 

여기서 $c$는 단위 시간당 패널티이고 $t$는 시간으로 기준이 초, 분, 시간, 일 등 설계자가 자유롭게 조정할 수 있다. 그래서 시간에 따른 실력의 불확실성까지 고려하면 식은 다음과 같다.

 

$r_{A,new} = r_A +  \dfrac{ q }{ \dfrac{1}{\sigma_A'^2} + \dfrac{1}{d^2} } \times g(\sigma_B)  (W - W_e)$

 

 

(5) 약간 더 일반화

 여기서 꼭 점수 평가를 한 경기만 가지고 할 필요는 없으므로 임의의 $m$개의 경기 결과를 합산하면 식은 다음과 같이 변한다.

 

$r_{A,new} = r_A +  \dfrac{ q }{ \dfrac{1}{\sigma_A'^2} + \dfrac{1}{d^2} } \displaystyle \sum_{i=1}^{m} g(\sigma_i)  (W_i - W_{i,e})$

 

단, $\dfrac{1}{d^2} = q^2 \displaystyle \sum_{i=1}^{m} g(\sigma_i)^2 W_{i,e}(1-W_{i,e})$으로 바뀐다.

 

이렇게 완성된 식을 보면 기존 레이팅 모델들이 갖는 여러 문제들을 해결했다. 특히, 임의로 정하던 $k$가 사라짐을 알 수 있다.

 

여기까지 보면 왜 저러한 인자들을 곱해야 하는지 의도는 설명했으나 왜 저런 모양이어야 하는지 궁금할 것이다. 왜냐면 동일한 의도를 실현시키기 위해서 여러 가지 식이 가능하기 때문인데, 이는 실제 유도과정에 나와 있으므로 궁금한 사람은 다음 글을 확인해보는 것을 추천한다.