djm03178's profile image

djm03178

July 18, 2020 17:24

서론

현존하는 알고리즘 대회 사이트 중 최대 규모라고 할 수 있는 Codeforces는 유저들의 랭킹을 결정하기 위한 자동화된 레이팅 시스템을 가지고 있습니다. 각 유저가 대회를 참가할 때마다 그 성적에 따라 레이팅이 변화하는 방식으로, 비교적 합리적인 결과를 보여주지만 때로는 논란이 될 수 있는 행동을 보이기도 합니다. 이 글에서는 Codeforces의 레이팅을 산출하는 공식에 대해 분석해 보고, 이 공식이 가진 특징과 경향, 그리고 한계와 문제점을 예시를 통해 확인해 보도록 하겠습니다.

Elo 레이팅

Codeforces의 레이팅은 Elo 레이팅에 기반을 두고 있습니다. Elo 레이팅은 1대1 경기에서의 레이팅을 계산하기 위한 시스템으로, Aprad Elo에 의해 개발되었습니다. Elo 레이팅은 실제로 국제 체스 연맹에서 공식 레이팅에 사용하고 있으며, 다른 1대1 스포츠나 대전 형식의 온라인 게임 등에서도 공식/비공식 레이팅으로 직접 또는 변형해서 사용하고 있습니다.

Codeforces의 경우에는 참가자가 최소 수천에서 수만¹ 명이 되기 때문에 레이팅 공식에도 상당한 변형이 들어가며, 중도에 업데이트가 되기도 했습니다. 또한 대회의 division에 여러 변화가 생기고 최근에 인지도가 급격하게 높아지며 참가자 수 또한 크게 늘어남에 따라 일부 허점이 부각되면서 계속된 변화를 시도하는 중입니다.

레이팅 공식

Codeforces의 레이팅은 각 참가자의 참가 시점에서의 레이팅만을 고려하여 계산됩니다. 즉, 더 이전 대회에서의 결과나 이전의 레이팅 ‘역사’는 관여되지 않습니다.²

여기에 그 대회에서의 등수에 따라 레이팅을 계산하는데, 중요한 것은 절대적인 등수 자체나 백분위에 따라서만 결정되는 것이 아니라 다른 참가자들의 레이팅을 종합적으로 고려하여 레이팅 변화량을 산출한다는 점입니다. 그 수순을 하나씩 살펴보도록 하겠습니다.

확률 구하기

Codeforces 레이팅의 기본 목표는 $n$명의 참가자가 있을 때, 모든 참가자 쌍 ($i$, $j$)에 대해 $i$번 참가자가 $j$번 참가자보다 더 좋은 랭킹을 얻을 확률 $P_{i,j}$를 구하고, 대회의 결과가 이 확률에 잘 부합하도록 레이팅 $r_{1..n}$을 변화시키는 것입니다. $P_{i,j}$는 다음과 같이 계산됩니다.

$P_{i,j}=\cfrac{1}{1+10^\frac{r_j-r_i}{400}}$

이 공식에서 $P_{i,j}$에 영향을 미치는 것은 두 참가자의 레이팅의 차 $r_j-r_i$뿐인 것을 알 수 있습니다. 이 값에 따른 확률을 몇 가지 예시를 들어보면 다음과 같습니다.

$r_j-r_i$	$P_{i,j}$		$r_j-r_i$	$P_{i,j}$
1000	0.0031523		-100	0.6400649
900	0.0055919		-200	0.7597469
800	0.0099009		-300	0.8490204
700	0.0174720		-400	0.9090909
600	0.0306534		-500	0.9467597
500	0.0532402		-600	0.9693465
400	0.0909090		-700	0.9825279
300	0.1509795		-800	0.9900990
200	0.2402530		-900	0.9944080
100	0.3599350		-1000	0.9968476
0	0.5

이 표를 통해 알 수 있는 사실 몇 가지를 정리하면 다음과 같습니다.

• 두 참가자의 레이팅이 같으면 이길 확률과 질 확률이 50%로 같다.
• 한 참가자의 승률이 $p$이면 다른 참가자의 승률은 $1-p$이다. 즉, 대칭 관계이다.
• 레이팅이 200 차이일 경우 75% 정도의 승률을, 400 차이일 경우 90% 정도의 승률을 예측한다.

예상 등수 계산하기

다음은 모든 참가자에 대해 각 참자자가 몇 등을 할 것인지를 예측해야 합니다. $i$번 참가자의 예상 등수를 $seed_i$라고 하면 이는 다음과 같이 계산할 수 있습니다.

$seed_i=\sum_{j=1,j \ne i}^{n}{P_{j,i}}+1$

풀어 쓰자면 $i$번 참가자의 예상 등수 $seed_i$는 자신을 제외한 모든 참가자에 대한 패배 확률 $P_{j,i}$를 모두 더한 값 +1³이 되는 것입니다. 직관적으로, 레이팅이 높은 참가자는 다른 참가자들에 대한 패배 확률이 낮을 테니, 다 더한 값(=예상 등수)이 작으므로 더 좋은 성적을 낼 것으로 기대한다고 볼 수 있습니다.

이 계산 방식에서 눈여겨볼 점은 전체 참가자 중에서의 레이팅 순위가 곧 예상 순위를 의미하지는 않는다는 점입니다. 예를 들어, 다음과 같이 21명의 참가자가 있다면 예측 순위는 이렇게 만들어집니다.

$r_i$	$seed_i$		$r_i$	$seed_i$
2000	3.154771		1450	11.90629
1950	3.723082		1400	12.80588
1900	4.358948		1350	13.69181
1850	5.056741		1300	14.55667
1800	5.809045		1250	15.39253
1750	6.607461		1200	16.19095
1700	7.443322		1150	16.94325
1650	8.308188		1100	17.64105
1600	9.194115		1050	18.27691
1550	10.09370		1000	18.84522
1500	11.00000

레이팅이 2000인 참가자는 전체에서 가장 높은 레이팅을 가지고 있지만 예상 등수는 약 3.15등인 것을 볼 수 있습니다. 언뜻 생각하면 1등은 가장 잘하는 사람이 가져갈 것으로 보아야 하는 것이 아닌가 할 수도 있지만, 주의해야 할 점은 여기에서 말하는 예상 등수는 특정 등수가 나올 확률이 가장 높은 참가자를 찾는 것이 아닌, 그 참가자가 평균적으로 얻게 될 등수를 예측하는 것이라는 점입니다. 자신을 이길 가능성이 높은 사람들이 많아지면 그만큼 자신이 1등을 할 확률도 떨어진다는 것을 직관적으로 생각할 수 있습니다.

레이팅의 변화

이제 예상 등수와 실제 등수를 비교해서 레이팅을 변화시키는 단게입니다. 예상 등수보다 잘한 참가자의 레이팅은 올리고, 예상 등수보다 못한 참가자의 레이팅은 내리는 것이 기본 원칙입니다.

이를 계산하기 위해 먼저 $i$번 참가자의 예상 등수 $seed_i$와 실제로 받은 등수 $rank_i$의 기하 평균 $M_i = \sqrt{seed_i \times rank_i}$를 구합니다. 그 다음은 $M_i$가 예상 등수가 되도록 하는 참가자의 레이팅 $R$을 구하는데, 한 번에 구하는 식이 나오지 않으므로 대신 “특정 레이팅을 가진 참가자의 예상 등수가 $M_i$보다 큰가 혹은 작은가?”를 이용한 이분 탐색을 사용해서 구하게 됩니다.

한 번에 지나치게 레이팅을 많이 변화시키지 않기 위해, 실제 레이팅은 현재 레이팅과 $R$과의 평균으로 맞추게 됩니다. 즉, 레이팅의 변화량 $delta_i$는 $\cfrac{R - r_i}{2}$가 됩니다.

윗 문단의 표의 참가자들에 적당한 등수를 부여하고 여기까지를 적용하면 다음과 같이 만들어집니다.

$r_i$	$seed_i$	$rank_i$	$delta_i$
2000	3.154771	2	+64
1950	3.723082	7	-35
1900	4.358948	4	+26
1850	5.056741	1	+159
1800	5.809045	3	+77
1750	6.607461	11	-42
1700	7.443322	6	+38
1650	8.308188	12	-34
1600	9.194115	8	+31
1550	10.09370	5	+100
1500	11.00000	17	-61
1450	11.90629	10	+41
1400	12.80588	9	+71
1350	13.69181	20	-71
1300	14.55667	15	+8
1250	15.39253	19	-39
1200	16.19095	21	-62
1150	16.94325	13	+81
1100	17.64105	16	+46
1050	18.27691	14	+96
1000	18.84522	18	+39

제로섬으로 만들기

그런데 위까지의 과정에는 치명적인 문제가 있습니다. 대충 보기에도 변화량이 +인 것들은 폭이 굉장히 큰 반면에 -인 것들은 작아 보입니다. 실제로 변화량을 모두 더해보면 +533이라는 큰 값이 나오고, 이는 제로섬의 원칙을 깨뜨리게 됩니다. 이는 위에서 $M_i$를 구할 때 그냥 평균이 아닌 기하 평균을 사용해서 보다 높은 등수를 기준으로 계산이 되었기 때문입니다. 그래서 이를 방지하기 위한 장치가 추가로 들어갑니다.

이 부분은 단순하게 전체 변화량의 합을 참가자의 수로 나눈 값을 각 참가자의 $delta_i$에서 빼주는 것으로 처리합니다.⁴ 여기까지를 적용한 결과는 다음과 같습니다.

$r_i$	$seed_i$	$rank_i$	$delta_i$
2000	3.154771	2	+38
1950	3.723082	7	-61
1900	4.358948	4	0
1850	5.056741	1	+133
1800	5.809045	3	+51
1750	6.607461	11	-68
1700	7.443322	6	+12
1650	8.308188	12	-60
1600	9.194115	8	+5
1550	10.09370	5	+74
1500	11.00000	17	-87
1450	11.90629	10	+15
1400	12.80588	9	+45
1350	13.69181	20	-97
1300	14.55667	15	-18
1250	15.39253	19	-65
1200	16.19095	21	-88
1150	16.94325	13	+55
1100	17.64105	16	+20
1050	18.27691	14	+70
1000	18.84522	18	+13

이제 변화량의 합은 -13으로 이전에 비해 훨씬 제로섬에 근접한 것을 볼 수 있습니다.

인플레이션⁵ 방지

이 부분은 시간이 지날수록 높은 레이팅의 참가자들의 레이팅이 점진적으로 계속 늘어나게 되는 것을 막기 위한 것입니다. 이 공식의 특성상 레이팅이 기존에 높았던 사람들의 레이팅이 더 늘어나기가 쉬운데, 즉 어떤 시점에서 어떤 높은 레이팅에 도달한 참가자가 오랫동안 대회에 참가하지 않고 있으면 그 동안 다른 유저들의 레이팅이 인플레이션되며 점점 그 레이팅의 권위(?)를 잃어버리는 상황이 올 수 있게 됩니다. 그래서 여기에 경험적으로 다음과 같은 부분을 추가했습니다.

대회 이전의 시점에서 가장 높은 레이팅을 가진 상위 $s=\min(n,4\sqrt{n})$명을 뽑아, 그 참가자들의 레이팅의 총합이 제로섬이 되도록 하는 변화량 $inc$를 구합니다. 이를 구하는 공식과 적용 방법은 윗 문단에서 전체 참가자들을 대상으로 한 것과 동일한데, 다만 이로 인해 전체 참가자들에 대해 미치는 영향이 너무 커지지는 않도록 그 제한을 -10으로 두고 있습니다. 이 값이 0보다 큰 경우에는 적용을 시키지 않습니다. 즉, 플러스 섬이 되는 일은 없도록 만들어 줍니다.

$inc$는 모든 참가자들에 대해 동일하게 적용해주기 때문에, 상위 $s$명에 포함되었는가 여부에 관계없이 참가자별 $delta$의 상대적인 차이는 모두 동일하게 유지됩니다.

Codeforces 레이팅의 성질

이런 복잡한 과정을 통해 완성된 레이팅 계산 시스템에는 크게 두 가지 특징이 있습니다. 이것을 목표로 만든 것이기도 합니다.

1. 대회 전의 레이팅이 $r_A \lt r_B$이고, $A$가 $B$보다 나쁜 성적을 내었다면 변화한 레이팅은 항상 $r_A \le r_B$를 만족합니다.
2. 대회 전의 레이팅이 $r_A \lt r_B$이고 $A$가 $B$보다 좋은 성적을 내었다면 레이팅의 변화량은 항상 $delta_A \ge delta_B$를 만족합니다.

풀어서 쓰자면, 1. 원래 레이팅이 더 낮았던 유저가 자신보다 높은 유저보다 대회 성적이 나쁜데 레이팅이 상대적으로 더 높아질 수 없고, 2. 원래 레이팅이 더 낮았던 유저가 자신보다 높은 유저보다 대회를 잘 쳤는데 레이팅 간격이 벌어질 수 없다는 뜻입니다.

이러한 성질들은 Codeforces의 레이팅이 오로지 현재의 레이팅만을 기준으로 판별하는 시스템이라는 점에서 합리적이라고 할 수 있습니다.

한계와 문제점

일반화된 공식으로 ‘평가’하는 시스템들이 대체로 그렇듯이, Codeforces 레이팅 역시도 여러 한계와 문제점이 존재합니다. 대표적으로 자주 지적되는 것들은 다음과 같습니다.

인플레이션

위의 ‘인플레이션 방지’ 문단에서 언급된 것과 같이 기본적인 계산 결과 자체가 대회에서 절대적으로 높은 등수를 기록하는 것 자체에 보상을 높게 주는 경향이 있습니다. 설명글에도 언급된 the rich get richer 현상은 이를 보정한 후에도 상당히 남아있는 느낌입니다.

이는 전체 참가자들을 레이팅 순으로 나열했을 때의 순위와 예상 등수를 비교했을 때 상위권의 사람들은 예상 등수가 더 낮고, 하위권의 사람들은 예상 등수가 더 높기 때문에 발생하는 일입니다. 그래서 레이팅의 변화량을 보았을 때 성적이 상위권인 사람은 주로 기존 레이팅도 상위권이면서 $delta$가 양수인 경우가 많고 하위권인 사람은 주로 기존 레이팅도 하위권이면서 $delta$가 음수인 경우가 많으며, 이 경향은 양 극단으로 갈수록 더 현저해지므로 빈익빈부익부를 피하기가 어렵습니다.

이 때문에 두 디비전 사이에 걸쳐있는 레이팅을 가진 참가자(예를 들면 Div. 1과 Div. 2 only에 모두 참가 가능한 Candidate Master)는 대체로 더 낮은 디비전에 참가했을 때 레이팅이 쉽게 오른다고 느끼게 될 수 있습니다. 물론, 상위 디비전에서는 매우 잘하면 크게 상승하고 아무리 못해도 크게 떨어지지 않는다는 것이 장점이기는 하나, 그 정도로 잘하거나 못할 확률보다는 적당히 자신의 레이팅에 맞는 성적을 낼 확률이 훨씬 높으며 그때 얻는 레이팅의 변화량은 하위 디비전에서 훨씬 긍정적으로 나타나게 됩니다.

새 유저의 초기 레이팅

Codeforces에서 새로 핸들을 만들면 레이팅이 1400으로 계산됩니다. 새로운 유저가 과연 처음에 어느 정도 실력을 가지고 있을지 예측하기 어렵지만, 현재의 레이팅 시스템은 모든 참가자에 대해 반드시 대회 시작 시점에서의 실력을 나타내는 레이팅을 필요로 하기 때문에 임의로 적당한 값을 설정할 수밖에 없습니다.

문제는 초보자에게 있어 1400이라는 레이팅은 상당히 높은 편에 속하기 때문에 처음 몇 개의 대회에서는 대체로 레이팅이 내려갈 가능성이 높다는 것입니다. 또한 새 유저의 레이팅이 첫 대회에서 대체로 내려간다는 것은 반대로 기존 유저들의 레이팅이 그만큼 오른다는 것을 의미하기도 합니다. 그나마 이전에는 시작점이 1500이었는데 최근에 1400으로 내려서 어느 정도 완화된 것이기는 하지만, 이 초기값의 변경 자체가 기존 유저들의 레이팅의 ‘권위’에 영향을 간접적으로 준다는 점에서 논란이 되고 있습니다.

레이팅이 처음에 계속 떨어진다는 느낌을 주지 않기 위해, 새 유저의 첫 6개 대회에서의 레이팅은 겉보기로만 0에서 시작해서 올라가는 것처럼 보이게 최근에 바꾸었는데 이것이 레이팅 시스템을 처음 접한 유저의 혼란을 가중시킨 것은 아닌지 우려되기도 합니다.

역사의 반영

계속해서 살펴본 것과 같이 Codeforces의 레이팅은 항상 대회 시작 시점에서의 레이팅만을 고려하여 계산됩니다. 이는 레이팅이 그 참가자의 현재 실력을 그대로 반영하고 있다는 믿음을 근거로 하는 것인데, 이것도 관점에 따라서는 불합리하게 보일 수도 있습니다.

기본적으로는 각 대회에서의 성적이 레이팅에 미치는 영향이 매우 크다는 것이 이런 논란의 원인입니다. 잘한 대회와 못한 대회에서의 성적의 순서를 바꾸기만 해도 현재 레이팅이 크게 달라지기 때문입니다. 즉, 가장 최근의 대회 서너 개를 제외한 이전의 대회 결과들은 자신의 현재 레이팅에 거의 영향을 미치지 못한다고 볼 수 있고, 이는 레이팅 시스템이 유저를 평가하기 위해 보는 시야가 매우 좁다는 느낌을 줄 수 있습니다.⁶

마치며

이 글에서는 언뜻 보면 복잡해 보이지만 기본적으로는 매우 간단한 식을 통해 레이팅을 계산하는 Codeforces 레이팅 시스템에 대해 알아보았습니다. 또한 이 단순한 방식이 가지는 한계점들을 극복하기 위한 경험적인 조치가 있다는 것도 보았습니다.

그럼에도 불구하고 여전히 여러 문제들이 눈에 띄는데, 이것들을 고치기 어려운 것은 모든 경우에 대해 합리적인 결론을 내릴 수 있는 공식을 작성하는 것이 그만큼 어렵기 때문이라고 생각합니다. 다양한 변수를 고려하면 할수록 파생되는 또 다른 문제들이 있을 수 있기 때문에, 공식 자체는 단순하게 유지하면서도 많은 사람들이 납득할 수 있도록 레이팅 시스템을 개선하는 것이 중요해 보입니다.

참고 자료

• Elo rating system
• Codeforces Rating System
• Open Codeforces Rating System [updated on October 2015]
• Codeforces rating 계산 코드