스포츠 경기 레이팅 (ELO) 시스템, 사람들의 실력을 어떻게 수학적으로 정의할 것인가?

회사에서 배드민턴 동아리 활동을 했다. 인기가 많은 동아리라 참여 인원이 많았고, 이에 자동 매칭 시스템을 만들어봐야겠다는 동기가 생겼다. 필연적으로 다음 과제를 해결해야한다: 사람들의 실력을 어떤 방식으로 정량화를 할 수 있을까? 그 고민의 결과가 나름 재미있어서 블로그에 옮겨보았다.

 

잘 정립된 기존 방식 중 하나는 FargoRate라는 것이 있다. 상대 전적에 따라 점수가 결정되며, 초보자는 100점, 월드 클래스 선수는 800점대로 분포가 된다. 가장 중요한 특징은 두 플레이어가 맞붙었을 때 승패 확률이 레이팅에 의해 결정된다는 점이다. 300점대의 두 플레이어가 붙었을 때 이길 확률은 서로 동일하며, 300점대 플레이어와 400점대 플레이어가 붙어서 나올 승패의 확률도 어느 정도 결정되어있다. 하지만 이런 시스템은 (1) 유입/이탈 회원이 잦은 회사 동아리 시스템에는 부적격하며, (2) 배드민턴과 같이 복식 게임이 주인 경우에는 "팀"의 레이팅을 정의하기 어렵다는 단점이 있다. 나는 수학적으로 정당한 가정과 증명으로써 납득 가능한 시스템을 구축하고 싶다는 생각에 고민을 해보았다.

 

1.  레이팅 시스템의 확률적 가정 (혹은 설계 의도)

1.A 단식 게임 (Single player game) 레이팅

1. 플레이어의 레이팅들은 평균 $\mu_{ELO}$와 표준편차 $\sigma_{ELO}$ 값을 가진다.
2. 만약 플레이어들의 실력이 고정되어있다면, 무한히 많은 게임을 했을 때 레이팅 값이 고정된 곳으로 각각 수렴하게 된다.
3. 만약 두 플레이어의 레이팅이 $x$와 $y$ 라면 ($x \leq y$), 그들의 게임 스코어가 $A$:$B$로 끝날 확률은 아래와 같이 레이팅 차에 결정되는 정규분포와 같다. $$ \frac{B-A}{\max(A, B)} \sim N(\mu_s, \sigma_s^2) \quad \text{where } \mu_s = t_s \cdot (y-x) $$
   • 즉, $t_s = 0.5 / 300$으로 둔다면, 300점의 레이팅 차이가 나는 두 플레이어가 붙었을 때, 더블 스코어로 끝날 확률이 가장 높다는 뜻이다. 600점 차이가 난다면 4배 차이로 끝날 확률이 가장 높다.

1.B 복식 게임 (Double players game) 레이팅의 가정

만약 두 팀원의 레이팅이 각각 $x$와 $y$ 라고 한다면 ($x \leq y$), 그 팀의 레이팅을 $f(x, y)$라고 정의하자. 아래 조건을 가정한다.

1. $f(x, y) = f(y, x)$ (교환법칙)
2. $x \leq f(x, y) \leq y$
   • 물론 $f(x, y) \leq y$에 대한 부분은 논쟁거리가 있지만.. single player vs double players 상황이 없다고 가정한다.
3. (배드민턴 특이 가정) $f(x, y)$는 $y$보다 $x$에 더 가까워야한다. 상대팀에서 이기기 위해서 못하는 사람에게 공을 더 보낼 것이기 때문이다.

팀 레이팅 함수에 대한 템플릿으로 크게 두 가지를 떠올렸다.

1. $f(x, y) = p \cdot \min(x, y) + (1-p) \cdot \max(x, y)$
2. $f(x, y) = \min(x, y)^p \cdot \max(x, y)^{1-p}$

두 함수 중에서는 첫번째가 마음에 들었다. 왜냐하면 $f(X, Y) \sim N(\mu_{ELO}, (p^2 + (1-p)^2)\cdot \sigma_{ELO}^2)$으로 정규분포성이 유지되며, 계산이 간단했기 때문이다. 1.B-3번 가정에 따라 $p$의 값은 1/2을 초과한다는 조건을 붙일 수 있었다.

2. 게임 스코어 결과에 따른 레이팅 업데이트 계산

게임이 끝나서 스코어가 결정되면 레이팅이 업데이트되도록 시스템을 설계하였다. $x$와 $y$가 각각 경기 전 측정된 두 팀의 레이팅이라고 하자.그들이 $a$:$b$ 스코어로 경기를 마쳤을 때, 업데이트 되는 레이팅을 각각 $x'$과 $y'$이라고 한다. 두 플레이어의 실제 레이팅 (가정 1.A-2에 따라 무한히 경기했을 때 수렴하는 값)을 $\hat{x}$와 $\hat{y}$라고 한다.

• $\Delta = \frac{b-a}{\max(a, b)} \cdot \frac{1}{t_s}$라고 하자.
  • 이는 예측되는 두 플레이어의 레이팅 값 차이(즉, $\hat y - \hat x$의 예측값)에 해당한다. 왜냐하면 경기 스코어에 대한 확률 변수를 $A$:$B$라고 한다면, $P\left(\frac{B-A}{\max(A,B)} = r\right)$은, $r = t_s \cdot (\hat{y} - \hat{x})$ 일 때 가장 크기 때문이다.
  • 결과적으로 $y'-x'$는 $y-x$와 $\Delta$ 사이에 있어야한다.
  • $y'-x' = \alpha \cdot \Delta + (1-\alpha) \cdot (y-x)$ 로 업데이트 된다고 하자. ($0 < \alpha < 1$)
• 그렇다면 레이팅은 아래와 같이 업데이트 된다. $$x' = x + \frac{\alpha}{2} (-x + y-\Delta),\quad y' = y + \frac{\alpha}{2} (x - y + \Delta)$$
  • 플레이어들의 평균은 보존된다! 왜냐하면 $x+y = x' + y'$이기 때문이다.

3. 복식 게임 결과에 따른 레이팅 업데이트 계산

$(x_1, x_2)$와 $(y_1, y_2)$를 각각 두 복식 팀원들의 레이팅 값이라고 가정하자. ($x_1 \leq x_2$, $y_1 \leq y_2$) 그들이 게임을 해서 $a$:$b$ 스코어로 경기를 마쳤을 때 ($a < b$), 업데이트 되는 레이팅을 각각 $(x_1', x_2')$, $(y_1', y_2')$이라고 하자. 편의를 위해 $x = f(x_1, x_2)$, $y = f(y_1, y_2)$, $x' = f(x_1', x_2')$, $y' = f(y_1', y_2')$ 으로 표기한다. 그렇다면 아래가 성립한다.

$$x' = x + \frac{\alpha}{2} (-x + y-\Delta),\quad y' = y + \frac{\alpha}{2} (x - y + \Delta)$$

이제 $x_1', x_2', y_1', y_2'$에 대한 계산이 남았다.

• 우선 가정 1.A-1에 의해 $x_1' + x_2' + y_1' + y_2' = x_1 + x_2 + y_1 + y_2$가 성립해야한다.
• 여전히 4개의 변수에 대한 3개의 연립방정식 밖에 없다.. 그래서 기여도라는 새로운 방정식을 하나 더 도입한다. 기여도 $C$는 승자들의 점수 상승폭에 대한 변수이다. $$ C = \frac{y_2' - y_2}{y_1' - y_1} $$
• 4개의 연립방정식을 풀면 아래와 같은 업데이트 공식을 얻을 수 있다. $$ x_1' = x_1 + \frac{\alpha}{2} \cdot \frac{-\Delta-x+y}{p+C(1-p)},\quad x_2' = x_2 + \frac{\alpha}{2} \cdot \frac{-C\cdot \Delta-x+y}{p+C(1-p)} \\ y_1' = y_1 + \frac{\alpha}{2} \cdot \frac{\Delta + x - y}{p + C(1-p)},\quad y_2' = y_2 + \frac{\alpha}{2} \cdot \frac{C \cdot \Delta + x - y}{p + C(1-p)} $$

4. 시뮬레이션 결과

해당 레이팅 시스템에서 하이퍼파라미터 $p = 0.6$, $\alpha = 0.2$, $C = 1$, $t_s = 0.5 / 300$으로 두고 실험을 해보았다. 각 변수 설정의 뜻은 아래와 같다.

• $p = 0.6$: 못하는 플레이어와 잘하는 플레이어가 팀을 이뤘을 때, 팀 레이팅을 $0.6:0.4$의 가중치로 두고 합산하여 계산한다는 뜻이다.
• $\alpha = 0.2$: 경기가 끝날 때, (예측되는 레이팅 값 - 본래 레이팅 값)에 0.2배 비례하는 만큼만 레이팅을 변화시킨다. $0.8^5 = 0.32$ 이므로, 5경기가 끝나면 대충 예측되는 레이팅 값의 68% 만큼 도달하게 될 것이다.
• $C = 1$: 두 승자는 레이팅 변화 폭을 동등하게 나눠가진다.
• $t_s = 0.5 / 300$: 레이팅 300 차이는 더블 스코어로 끝날 확률이 가장 높다. 레이팅 600 차이는 4배, 900 차이는 8배 스코어로 끝날 확률이 가장 높다는 뜻이다.

100명의 플레이어끼리 10000개의 복식 게임을 랜덤으로 돌린 결과는 아래와 같았다. 가로선이 실제 레이팅 값인데, 경기를 진행함에 따라 해당 값으로 수렴함이 뚜렷히 보인다.

하나의 트랜젝션만 관찰하면 아래와 같이 나온다. 재밌는 점이라고 하면 이미 레이팅 차이가 300점 정도 나는 경우는 더블 스코어로 이겨야 겨우 레이팅이 보존이 되며, 비슷한 점수로 경기가 끝난 경우는 오히려 레이팅이 떨어지기도 한다.

표 읽는 법:

       | x_1 | x_2 | y_1 | y_2

a:b | x_1' | x_2' | y_1' | y_2'

...

 

      | 1000        | 1000        | 1000        | 1000
--------------------------------------------------------------
 5:21 | 954 (-46)   | 954 (-46)   | 1046 (+46)  | 1046 (+46)
10:21 | 969 (-31)   | 969 (-31)   | 1031 (+31)  | 1031 (+31)
15:21 | 983 (-17)   | 983 (-17)   | 1017 (+17)  | 1017 (+17)
20:21 | 997 (-3)    | 997 (-3)    | 1003 (+3)   | 1003 (+3)
21:20 | 1003 (+3)   | 1003 (+3)   | 997 (-3)    | 997 (-3)
21:15 | 1017 (+17)  | 1017 (+17)  | 983 (-17)   | 983 (-17)
21:10 | 1031 (+31)  | 1031 (+31)  | 969 (-31)   | 969 (-31)
 21:5 | 1046 (+46)  | 1046 (+46)  | 954 (-46)   | 954 (-46)

      | 900         | 1100        | 800         | 1200
--------------------------------------------------------------
 5:21 | 852 (-48)   | 1052 (-48)  | 848 (+48)   | 1248 (+48)
10:21 | 867 (-33)   | 1067 (-33)  | 833 (+33)   | 1233 (+33)
15:21 | 881 (-19)   | 1081 (-19)  | 819 (+19)   | 1219 (+19)
20:21 | 895 (-5)    | 1095 (-5)   | 805 (+5)    | 1205 (+5)
21:20 | 901 (+1)    | 1101 (+1)   | 799 (-1)    | 1199 (-1)
21:15 | 915 (+15)   | 1115 (+15)  | 785 (-15)   | 1185 (-15)
21:10 | 929 (+29)   | 1129 (+29)  | 771 (-29)   | 1171 (-29)
 21:5 | 944 (+44)   | 1144 (+44)  | 756 (-44)   | 1156 (-44)

      | 950         | 950         | 1050        | 1050
--------------------------------------------------------------
 5:21 | 914 (-36)   | 914 (-36)   | 1086 (+36)  | 1086 (+36)
10:21 | 929 (-21)   | 929 (-21)   | 1071 (+21)  | 1071 (+21)
15:21 | 943 (-7)    | 943 (-7)    | 1057 (+7)   | 1057 (+7)
20:21 | 957 (+7)    | 957 (+7)    | 1043 (-7)   | 1043 (-7)
21:20 | 963 (+13)   | 963 (+13)   | 1037 (-13)  | 1037 (-13)
21:15 | 977 (+27)   | 977 (+27)   | 1023 (-27)  | 1023 (-27)
21:10 | 991 (+41)   | 991 (+41)   | 1009 (-41)  | 1009 (-41)
 21:5 | 1006 (+56)  | 1006 (+56)  | 994 (-56)   | 994 (-56)

      | 850         | 850         | 1150        | 1150
--------------------------------------------------------------
 5:21 | 834 (-16)   | 834 (-16)   | 1166 (+16)  | 1166 (+16)
10:21 | 849 (-1)    | 849 (-1)    | 1151 (+1)   | 1151 (+1)
15:21 | 863 (+13)   | 863 (+13)   | 1137 (-13)  | 1137 (-13)
20:21 | 877 (+27)   | 877 (+27)   | 1123 (-27)  | 1123 (-27)
21:20 | 883 (+33)   | 883 (+33)   | 1117 (-33)  | 1117 (-33)
21:15 | 897 (+47)   | 897 (+47)   | 1103 (-47)  | 1103 (-47)
21:10 | 911 (+61)   | 911 (+61)   | 1089 (-61)  | 1089 (-61)
 21:5 | 926 (+76)   | 926 (+76)   | 1074 (-76)  | 1074 (-76)

      | 1000        | 1000        | 700         | 1300
--------------------------------------------------------------
 5:21 | 948 (-52)   | 948 (-52)   | 752 (+52)   | 1352 (+52)
10:21 | 963 (-37)   | 963 (-37)   | 737 (+37)   | 1337 (+37)
15:21 | 977 (-23)   | 977 (-23)   | 723 (+23)   | 1323 (+23)
20:21 | 991 (-9)    | 991 (-9)    | 709 (+9)    | 1309 (+9)
21:20 | 997 (-3)    | 997 (-3)    | 703 (+3)    | 1303 (+3)
21:15 | 1011 (+11)  | 1011 (+11)  | 689 (-11)   | 1289 (-11)
21:10 | 1025 (+25)  | 1025 (+25)  | 675 (-25)   | 1275 (-25)
 21:5 | 1040 (+40)  | 1040 (+40)  | 660 (-40)   | 1260 (-40)

마무리

이를 통해 사내 동아리에서 사람들의 배드민턴 실력을 정량적으로 표현할 수 있었고, 경기 결과에 따라 예측값을 업데이트할 수 있었다.

 

사내에 능력있는 개발자들이 정말 많다! 셋이서 웹 페이지 제작에 들어갔다. 한 분은 프론트엔드 UI를, 다른 한 분은 레이팅 기반 매칭 알고리즘을 만들었으며, 나는 파이어베이스 펑션을 이용하여 레이팅 업데이트 백엔드 함수를 구현했다. 요즘 일이 너무 바쁜 탓에 동아리 활동을 제대로 못하고 있지만 ㅠㅠ 그동안 정말 재밌게 사용하였다. 회사 생활 정말 재밌는 것 같다.

부록 증명. 무한히 많은 경기를 펼치면 레이팅은 수렴한다.

두 플레이어의 실제 레이팅을 $\hat x$와 $\hat y$라고 하자. 원래 예측된 레이팅 값을 각각 $x_0$, $y_0$라고 하고, $i$번째 경기는 $a_i$:$b_i$로 마치며, 그 후 $x_i$, $y_i$로 업데이트 된다고 가정한다.

$$ x_i = x_{i-1} + \frac{\alpha}{2} \cdot (-x_{i-1} + y_{i-1} - \Delta_i), \quad y_i = y_{i-1} + \frac{\alpha}{2} \cdot (x_{i-1} - y_{i-1} + \Delta_i)\quad \text{where } \Delta_i = \frac{b_i - a_i}{\max(a_i, b_i)} \cdot \frac{1}{t_s} $$

여기서, 가정 1.A-3에 의해 $E[\Delta_i] = \hat y - \hat x$ 이다.

$$ \begin{align} E[X_i] &= E[X_{i-1}] \cdot (1 - \alpha/2) + E[Y_{i_1}] \cdot \alpha/2 - E[\Delta_i] \cdot \alpha/2 \\ &= E[X_{i-1}] \cdot (1 - \alpha/2) + E[Y_{i-1}] \cdot \alpha/2 + (\hat x - \hat y) \cdot \alpha/2 \end{align} $$

$$ \begin{align} E[Y_i] &= E[Y_{i-1}] \cdot (1 - \alpha/2) + E[X_{i_1}] \cdot \alpha/2 + E[\Delta_i] \cdot \alpha/2 \\ &= E[Y_{i-1}] \cdot (1 - \alpha/2) + E[X_{i-1}] \cdot \alpha/2 + (\hat y - \hat x) \cdot \alpha/2 \end{align} $$

그러므로

$$ \begin{align} E[Y_i - X_i] &= (1-\alpha) \cdot E[Y_{i-1} - X_{i-1}] + \alpha \cdot (\hat y - \hat x) \\ &= (1 - \alpha)^i \cdot (y_0 - x_0) + \alpha \cdot \sum_{k=0}^{i-1} (1-\alpha)^k \cdot (\hat y - \hat x) \\ &= (1 - \alpha)^i \cdot (y_0 - x_0) + (1 - (1-\alpha)^i) \cdot (\hat y - \hat x) \end{align} $$

즉, $\lim_{i \rightarrow \infty} E[Y_i - X_i] = \hat y - \hat x$ 이다. 여기서 레이팅의 평균은 유지되므로, 레이팅은 수렴한다.

$$ \lim_{i \rightarrow \infty} E[X_i] = \hat x, \quad \lim_{i \rightarrow \infty} E[Y_i] = \hat y $$