djm03178's profile image

djm03178

November 20, 2020 02:15

서론

이전 글에서 Codeforces의 레이팅 계산법에 대해 다루어 보았습니다. 이번 글에서는 기존 라운드들에서의 통계를 이용하여 이 레이팅 체계가 어떤 경향을 보이고 있는지 살펴보고, 여기서 발견되는 구조적인 문제점의 원인을 분석해 보려고 합니다.

어떤 레이팅 시스템이 이상적이라면 각 참가자가 해당 라운드에서 기록한 ‘성적’에 따라 레이팅의 변화가 이루어져야 할 것인데, 많은 사람들의 경험에 의하면 특정 종류의 라운드에 참가하는 것이 다른 종류의 라운드에 참가하는 것에 비해 레이팅을 얻기가 훨씬 쉽다고 합니다. 이 현상이 어느 정도 심각한지를 집중적으로 조사해 보았습니다.

분석 대상 라운드

약 6개월 전, 레이팅 시스템 일부에 변화가 생겼습니다. 여기서 가장 중요한 요소 두 가지는 다음과 같습니다.

• 최초 레이팅을 1500에서 1400으로 변경
• 최초 다섯 라운드에 대해 ‘실제 레이팅’과 다른 ‘표기 레이팅’ 도입¹

하지만 이 때문에 이 시점 이후의 라운드 데이터를 사용하는 데에 어려움이 생겼습니다.

• API가 ‘실제 레이팅’에 대한 정보를 지원하지 않습니다. 해당 업데이트에도 불구하고 이에 대한 적절한 API 업데이트가 이루어지지 않아, 현재 API에서 받아올 수 있는 참가자의 레이팅 정보는 ‘표기 레이팅’뿐입니다. 물론 각 참가자의 역대 참가 대회 목록을 보고 직접 계산하도록 하는 것이 가능은 하나, API가 라운드 전체 순위표를 한 번에 가져올 수 있는 기능을 제공하는 반면에 각 유저에 대한 참가 대회 목록은 한 번에 한 명씩 요청을 보내야 합니다. API 호출이나 웹 페이지를 여는 속도에 제한이 걸려있어 (1초에 5회까지만 가능) 모든 참가자의 정보를 얻어오는 데에는 매우 긴 시간이 걸리고 예외 발생에 대처가 어려우며, Codeforces 서버 입장에서도 그다지 달가운 요청이 아닐 것입니다.
• 초기 레이팅의 변화 때문에 참가 횟수가 적은 참가자들에 대한 비교가 어렵습니다. 변화 이전에 한 라운드를 참가한 참가자가 변화 이후에 한 라운드를 참가한 참가자와 비슷한 수준의 성적을 냈더라도 그 결과 레이팅이 가지는 차이가 크기 때문에 직접적인 비교에 무리가 생깁니다.

따라서 이 글에서는 부득이하게 해당 업데이트가 적용되기 이전 시점에서, 가능한 최근의 rated 라운드들의 통계를 이용하여 분석을 수행했습니다. 분석 대상으로 사용한 라운드들의 목록은 다음과 같습니다.

• Div. 1: 1290, 1292, 1299, 1314, 1320, 1322, 1329, 1336, 1338, 1349
• (Div. 1이 있는) Div. 2: 1291, 1300, 1315, 1321, 1323, 1330, 1337, 1339, 1341, 1350
• (Div. 1이 없는) Div. 2: 1312, 1313, 1325, 1332, 1333, 1334, 1342, 1348, 1354, 1355
• Div. 1 + Div. 2: 1270, 1284, 1305, 1307, 1326
• Div. 3: 1283, 1294, 1296, 1311, 1324, 1328, 1335, 1343, 1353, 1360

실험 1. Candidate Master는 Div. 2에 참가하는 것이 Div. 1에 참가하는 것보다 유리한가?

Candidate Master(이하 ‘퍼플’)에 머무르는 실력의 참가자들에게서 자주 나오는 말 중 하나가 바로 “Div. 1만 가면 떨어지고, Div. 2에선 잘 오른다” 입니다. 이것이 어느 정도 사실인지 알아보기 위해 다음과 같은 실험을 수행해 보았습니다.

우선 다음과 같은 가정을 합니다. 이와 같은 가정은 이후의 다른 실험들에도 동일한 방식으로 적용됩니다.

• Div. 1에 참가하는 퍼플들과 Div. 2에 참가하는 퍼플들의 레이팅 / 실력 분포는 동일하다.
• 퍼플들 사이에서의 랭킹 백분위는 성적을 평가하기에 적절한 요소이다.

먼저 각 라운드 종류에 참가한 퍼플들의 레이팅 변화량의 (각 라운드에서의 평균)의 평균을 비교해 보았습니다.

rating	Div. 1	Div. 2	Δ
[1900, 1949]	-9.325	13.117	22.442
[1950, 1999]	-8.917	11.924	20.841
[2000, 2049]	-10.692	15.963	26.656
[2050, 2099]	-12.133	22.050	34.183
모든 퍼플	-10.024	15.022	25.045

상당히 큰 차이가 나는 것을 볼 수 있습니다. Div. 1에 참가한 퍼플들의 평균 레이팅 변화는 -10 정도인 반면에 Div. 2에 참가한 퍼플들의 평균 레이팅 변화는 +15 정도나 됩니다. 차이로는 약 25나 나고, 이는 레이팅이 2100에 가까운 참가자일수록 더욱 두드러져 [2050, 2099] 범위의 참가자에게서는 무려 34가 넘었습니다.

그렇다면 각 라운드 종류에서 퍼플인 참가자가 0 이상의 레이팅 변화를 얻으려면 퍼플 중 상위 몇 % 내에 들어야 할까요? 각 라운드에서 특정 레이팅 이상이면서 0 이상의 레이팅 변화가 나타나는 가장 낮은 등수의 참가자들의 백분위를 이용하여 다음과 같이 평균을 내어보았습니다.

rating	Div. 1	Div. 2
1900+	47.390%	67.092%
1920+	44.905%	63.759%
1940+	42.057%	61.330%
1960+	39.344%	56.813%
1980+	36.102%	54.546%
2000+	33.244%	50.992%
2020+	30.284%	48.057%
2040+	28.009%	44.323%
2060+	25.183%	41.119%
2080+	20.872%	36.986%

레이팅이 1900 정도인 참가자가 Div. 1에서 레이팅이 오르기 위해서는 퍼플 두 명 중 한 명 안에는 들어야 하는 반면 Div. 2에서는 세 명 중 두 명 안에만 들어도 되는 것을 볼 수 있습니다. 2100에 근접한 참가자의 경우 Div. 1에서는 다섯 명 중 한 명 안에 들어야 레이팅이 오르는 반면 Div. 2에서는 세 명 중 한 명 안에만 들어도 오를 정도로 두 종류의 라운드에서 퍼플이 느끼는 난이도 격차는 크다는 것을 볼 수 있습니다.

결론적으로 퍼플이 레이팅을 위해 라운드에 참가한다면 Div. 1보다는 Div. 2에 참가하는 것이 절대적으로 유리한 체계라는 것을 볼 수 있습니다. 왜 이런 현상이 발생하는지에 대한 분석은 후술하겠습니다.

실험 2. Unrated 참가자들이 Specialist의 레이팅에 큰 영향을 끼치는가?

실험 1과 비슷한 맥락으로 Div. 3에 참가할 수 있는 가장 높은 등급인 Specialist(이하 시안)도 Div. 2 라운드나 Div. 1 + Div. 2 라운드에 비해 Div. 3에 참가했을 때 이득이 될 수 있지 않을지 생각해 보았습니다. 실제로 지인들 중 해당 레이팅에 머무르는 몇 분들의 레이팅이 Div. 3마다 오르고 Div. 2마다 떨어지는 경향을 보이는 것을 지켜본 바가 있었습니다.

그런데 실험하는 도중 특이한 현상을 하나 볼 수 있었습니다. 우선 Div. 3에 참가한 시안들의 세부 레이팅 구간별 레이팅 변화량은 다음과 같습니다.

rating	Div. 3	# of participants2
[1400, 1449]	-7.197	10478
[1450, 1499]	15.290	7519
[1500, 1549]	-48.973	19411
[1550, 1599]	31.650	5364
모든 시안	-17.331	42772

1600에 가까운 레이팅인 [1550, 1599]의 참가자들은 예상한 대로 매우 높은 레이팅 변화율을 보였지만, 그 아래로는 매우 불규칙적인 양상을 보였을 뿐 아니라 전체적으로 봤을 때도 레이팅 변화율의 평균이 -17이나 됩니다. 이런 현상이 나타나는 원인은 각 레이팅 구간에 속하는 참가자의 수에서 찾을 수 있습니다. [1500, 1549] 구간에 지나치게 많은 참가자가 몰려있고, 이들의 레이팅 변화의 평균이 무려 -49에 가까울 정도로 좋지 않은 것을 볼 수 있습니다. 이들 중 대다수는 정확하게 레이팅이 1500인, 이전까지 한 번도 라운드에 참가하지 않은 unrated 참가자들임을 짐작할 수 있습니다.

위에서 언급한 이유로 인해 이러한 참가자들을 정확하게 분리해내는 것은 어렵지만, 한 번 이상의 라운드에 참가한 참가자가 레이팅이 1500인 상태일 확률은 매우 낮으므로, 레이팅이 정확히 1500인 참가자들을 계산에서 제외하고 다시 통계를 구해보았습니다.

rating	Div. 3	# of participants
[1400, 1449]	-7.197	10478
[1450, 1499]	15.290	7519
[1501, 1549]	27.487	6058
[1550, 1599]	31.650	5364
1500을 제외한 모든 시안	12.776	29419

이제 보다 확실한 경향성이 보이고 시안 전체로 보았을 때도 전체적으로 레이팅이 상승한다는 기존의 예측이 잘 맞는다는 것을 볼 수 있습니다.

또한 이로부터 한 가지 알아낼 수 있는 사실은 이 unrated 참가자들의 수가 전체 시안에서 차지하는 비중이 약 30%에 육박하기 때문에 레이팅에 미치는 영향이 상당히 크며, 대부분은 첫 라운드에서 아주 큰 레이팅 하락을 겪게 된다는 것입니다. 이에 대한 반동으로 다른 참가자들은 상대적으로 레이팅에 긍정적인 변화를 겪게 된다는 것 또한 충분히 예측할 수 있습니다.

[1400, 1449] 구간의 참가자들이 벌써부터 비교적 하락세를 겪게 되는 것도 이의 연장선으로 확장해볼 수 있습니다. 시작한지 얼마 되지 않은 참가자들의 ‘실력’이 평균적으로 1400보다 낮은 레이팅이라면³, 이들의 레이팅은 ‘실력’에 수렴하기까지 몇 차례에 걸쳐서 더 내려갈 것이고, 그 중도에 있는 참가자들의 레이팅이 전체적으로 음수 방향의 변화를 겪게 될 것임을 예측할 수 있습니다.

위의 표를 확장해서 (1500을 제외하지 않고) 1000부터 구간별 레이팅 변화를 살펴보면 다음과 같습니다.

rating	Div. 3	# of participants
[1000, 1049]	4.483303132280611	3863
[1050, 1099]	2.8036760250454456	4951
[1100, 1149]	-1.3941312741312741	6475
[1150, 1199]	-4.265905990326181	8063
[1200, 1249]	-4.202508576329331	9328
[1250, 1299]	-13.035594297648235	11013
[1300, 1349]	-3.398259837848527	10114
[1350, 1399]	-31.0638072357264	14152
[1400, 1449]	-7.197270471464019	10478
[1450, 1499]	15.29046415746775	7519
[1500, 1549]	-48.973211065890474	19411
[1550, 1599]	31.650447427293066	5364
[1000, 1599]	-12.736	110731

[1500, 1549]뿐만 아니라 [1350, 1399]과 [1250, 1299] 구간 또한 다른 구간에 비해 음수 방향으로 크게 튀는 것을 볼 수 있는데, 이들은 각각 라운드를 한 번, 두 번 참가한 참가자들에 의한 영향으로 예측할 수 있습니다. 예시로 1353번 라운드의 레이팅 변화표를 보면 수백 명의 unrated 참가자가 레이팅을 100 이상 잃고 [1350, 1399] 구간에 안착하는 것을 볼 수 있으며, 이러한 참가자들이 두 번째 라운드를 하고 다시 문제를 풀지 못하면 [1250, 1299] 구간으로 많이 들어가게 되는 것을 볼 수 있습니다. 이 구간들에 총 참가자 수가 많은 현상 또한 함께 설명이 됩니다.

실험 3. Specialist는 Div. 3에 참가해야 이득인가?

이제 본래 실험하려고 했던 시안이 참가하는 라운드 종류마다의 평균 레이팅 변화량을 분석해 보았습니다. 1500을 제외하는 것이 보다 매끄러운 결과를 보이므로 모든 실험에서 레이팅이 정확히 1500인 참가자들을 제외했습니다.

rating	Div. 1 + Div. 2	Div. 2 only	Div. 2 with Div. 1	Div. 3
[1400, 1449]	-12.783	-13.102	-15.376	-7.197
[1450, 1499]	1.775	0.631	-3.998	15.290
[1501, 1549]	3.651	4.420	3.174	27.487
[1550, 1599]	4.281	4.877	5.114	31.650

왼쪽에서 오른쪽으로 갈수록 참가자의 폭이 좁아지지만, Div. 1 + Div. 2, Div. 2 only, Div. 2 with Div. 1 라운드에서는 평균 레이팅 변화에 큰 차이가 없는 것을 볼 수 있습니다. 하지만 이들과 Div. 3 라운드에서는 퍼플이 Div. 1과 Div. 2 only 라운드에서 보인 차이와 비슷한 차이가, 특히 1600에 가까운 레이팅에서 크게 나타나는 것을 볼 수 있습니다.

레이팅의 변화량이 0 이상이 되기 위한 시안 사이에서의 최소 백분위 또한 구해 보았습니다.

rating	Div. 1 + Div. 2	Div. 2 only	Div. 2 with Div. 1	Div. 3
1400+	62.071%	61.579%	59.924%	66.572%
1420+	58.711%	59.063%	56.695%	63.280%
1440+	55.875%	55.821%	53.023%	61.133%
1460+	52.036%	51.919%	50.254%	57.998%
1480+	48.001%	49.122%	46.243%	55.115%
1500+	44.889%	45.154%	42.631%	51.745%
1520+	41.302%	41.608%	38.947%	48.616%
1540+	38.084%	38.771%	35.512%	45.483%
1560+	34.767%	35.283%	31.686%	42.138%
1580+	30.964%	31.877%	28.590%	39.851%

역시 예측했던 바와 같이 Div. 3에서의 시안의 성적이 다른 종류의 라운드에서보다 훨씬 유리함을 확인할 수 있습니다.

실험 4. Expert는 Div. 1이 있는 Div. 2에 참가하는 것이 이득인가?

내친 김에 비슷한 마지막 케이스를 하나 더 확인해 보았습니다. 바로 Expert(이하 블루)는 자신이 가장 높은 레이팅이 되는 “Div. 1 라운드가 함께 있는 Div. 2” 라운드에 참가할 때 성적이 가장 좋은지입니다.

위 실험과 마찬가지로 블루가 참가할 수 있는 라운드들 각각에 대해 평균 레이팅 변화량과 변화량이 0 이상이 되기 위한 블루 내 최소 백분위를 구해 보았습니다.

rating	Div. 1 + Div. 2	Div. 2 only	Div. 2 with Div. 1
[1600, 1649]	1.779	6.229	9.489
[1650, 1699]	2.705	6.029	10.631
[1701, 1749]	3.882	8.738	13.403
[1750, 1799]	-2.662	9.968	17.879
[1801, 1849]	-0.912	9.982	20.237
[1850, 1899]	-1.978	9.410	21.457
모든 블루	0.911	7.941	14.128

rating	Div. 1 + Div. 2	Div. 2 only	Div. 2 with Div. 1
1600+	67.493%	71.002%	72.085%
1630+	62.825%	66.306%	68.150%
1660+	58.611%	61.166%	63.034%
1690+	52.076%	55.714%	58.467%
1720+	47.988%	51.448%	53.359%
1750+	43.593%	46.565%	47.471%
1780+	37.387%	41.717%	43.254%
1810+	33.898%	36.296%	38.002%
1840+	29.726%	31.287%	34.194%
1870+	24.393%	27.097%	29.727%

블루 역시 전체적으로 자신이 최상위권이 되는 라운드일수록 레이팅이 수월하게 오르는 것을 확인할 수 있습니다.

종합 및 결론

실험 1~4를 종합했을 때 각 참가자들은 자신이 가장 높은 레이팅 그룹에 속하게 되는 라운드에 참가하는 것이 이득이 되는 것을 볼 수 있었습니다. 이런 경향은 특히 실험 1에서의 퍼플들에게 두드러지게 나타났습니다. 그 이유를 다음과 같이 분석해 보았습니다.

우선 지난 글에서 보았던 것과 같이 Elo 레이팅의 다중 참가자 버전을 사용하는 Codeforces 레이팅 시스템은 태생적으로 빈익빈 부익부 현상을 보이게 됩니다. 이 현상에 지대한 영향을 끼치는 것이 바로 실험 2에서 살펴본 신규 참가자들로, 이들 중 대다수는 소수의 라운드만에 참가하고 몇 차례의 레이팅 하락을 겪은 뒤 그대로 비활동 사용자가 되곤 합니다.⁴ 그 사용자들이 핸들을 만든 이후부터 활동을 중지하기까지 잃은 레이팅은 고스란히 다른 사용자들의 레이팅을 올려주는 데에 사용되고, 그 때문에 활동적인 사용자들 사이에서는 전체적으로 상당한 레이팅 인플레이션이 발생하게 됩니다.

이 인플레이션을 보정하기 위해 레이팅 시스템에서는 참가자 중 기존 레이팅이 가장 높았던 일부 참가자들의 레이팅 총 변화량이 0이 되게끔 모두의 레이팅을 강제로 끌어내리는 등의 방법을 통해 모든 참가자의 총 레이팅 변화량이 상당한 음수가 되도록까지 하고 있습니다.⁵ 이 전략은 활동적인 사용자들 전체에서의 레이팅이 높아지는 것을 막는 효과는 있지만, 새 참가자들이 기부한 거대한 레이팅을 주로 가져가는 계층이 최상위권에 몰리는 것을 막기에는 역부족인 것으로 보입니다. 또한 이 현상이 퍼플들에서 특히 두드러지는 이유는 그만큼 Div. 1 라운드가 열리는 빈도가 낮기 때문에, 여러 차례에 걸쳐 Div. 2에서 부풀려진 퍼플들의 레이팅이 Div. 1에서 그만큼 힘을 발휘하지 못하기 때문일 것입니다.

결국 이러한 문제를 근본적으로 해결하려면 참가자 집단이 고정적이지 않고 새로운 레이팅이 지속적으로 유입된다는 점을 고려할 수 있어야 할 것입니다. 과연 Codeforces는 앞으로도 이런 문제점을 계속 안은 채로 레이팅 시스템을 유지할 것인지, 아니면 언젠가 기발한 아이디어를 통해 더욱 개선된 레이팅 시스템을 도입하게 될 수 있을지 궁금해집니다.