틀릴 수 있다고 말하는 평점 시스템, Glicko

lichess에 새 계정을 만들고 한 판을 두면, 내 평점은 1500?으로 표시됩니다.

대부분은 이 물음표를 “아직 잠정치니까 신경 쓰지 말라는 뜻” 정도로 읽고 넘어갑니다. 실제로는 훨씬 구체적입니다. lichess 소스에서 이 물음표는 비교 한 줄입니다. 플레이어의 편차(deviation)가 110 이상이면 잠정 평점으로 취급합니다. UI 상의 친절한 표시가 아니라 내부 숫자가 화면으로 새어 나온 것이고, 바로 그 숫자가 Glicko가 존재하는 이유 전부입니다.

제가 이걸 들여다보게 된 계기는 사이드 프로젝트에 랭크 래더를 붙이고 싶어서였습니다. 평점은 이미 풀린 문제라고 생각했고요. Elo 가져다가 K 값 정하고 배포하면 끝. 그 가정은 이틀쯤 갔습니다.

Elo가 실제로 주는 것

Arpad Elo는 물리학 교수이자 체스 마스터였고, 그가 1960년 USCF를 위해 설계한 시스템(FIDE는 1970년에 채택)은 한 가지 일을 아주 잘합니다. 승패의 나열을 비교 가능한 숫자 하나로 바꿔 주는 것이죠. 평점 차이로 기대 결과를 계산하고, 실제 결과와 비교해서, 그 차이만큼 양쪽을 움직입니다.

조절할 수 있는 값은 K 하나뿐입니다. 한 판이 평점을 최대 얼마나 움직일 수 있는지를 정하죠. FIDE는 현재 신규 선수에게 K=40, 30판 이후에는 20, 2400을 넘으면 10을 씁니다. 이 계단이 바로 단서입니다. K는 서로 무관한 두 가지 일을 동시에 하고 있습니다. 시스템이 얼마나 빨리 학습하는지, 그리고 한 판의 결과가 얼마나 중요한지. 이 둘은 같은 것이 아닌데 Elo에는 다이얼이 하나뿐입니다.

결국 K 계단은 모델이 갖지 못한 무언가를 흉내 내기 위해 존재합니다. 신규 플레이어에게 큰 K가 필요한 이유는 시스템이 그를 전혀 모르기 때문이고, 2400 플레이어에게 작은 K가 필요한 이유는 시스템이 이미 충분히 알기 때문입니다. 두 문장 모두 확신에 대한 이야기인데, 확신은 Elo가 어디에도 저장하지 않는 값입니다.

Elo에서 어색하게 느껴지는 것들은 전부 이 빈칸에서 나옵니다.

• 둘 다 1500인데 한 명은 5판, 한 명은 5,000판을 둔 플레이어가 동일한 상대로 취급됩니다.
• 3년간 한 판도 두지 않은 사람의 평점을, 시스템은 여전히 보증해야 할 근거도 없이 들고 있습니다.
• 잠정 평점 기간, 평점 하한선, 최소 대국 수 같은 장치는 전부 모델이 표현하지 못하는 구멍을 나중에 덧대어 막은 것입니다.

Elo는 경기력이 정규분포를 따른다고 가정했습니다. 실제 데이터에는 로지스틱 분포가 더 잘 맞는 것으로 밝혀졌고, 오늘날 대부분의 구현은 후자를 씁니다. 모두가 “Elo”라고 부르는 시스템이 이미 수정된 Elo라는 사실은 기억해 둘 만합니다.

오차 범위를 함께 들고 다니는 평점

Mark Glickman이 1993년 하버드 박사 논문에서 다듬고 90년대에 Glicko라는 이름으로 발표한 답은 민망할 만큼 직접적입니다. 확신을 저장하면 된다는 것이죠.

모든 플레이어는 두 번째 숫자를 갖습니다. 평점 편차, RD입니다. 평점 추정치에 대한 표준편차이고, 따라서 평점과 RD를 묶으면 점이 아니라 구간이 됩니다. RD가 50인 1500 플레이어는 “이 사람의 진짜 실력은 거의 확실히 1400에서 1600 사이”라는 주장입니다. 똑같은 1500이라도 RD가 350이면, 즉 갓 가입한 계정의 기본값이라면, 사실상 아무 주장도 하지 않은 것에 가깝습니다.

같은 평점, 세 가지 다른 주장. 구간은 대략 평점에서 RD의 두 배만큼 벌어진 범위입니다.

RD는 양방향으로 움직입니다. 경기를 하면 줄어듭니다. 결과가 곧 증거니까요. 가만히 있으면 늘어납니다. 시스템의 믿음이 “1년이나 지났는데 이제 누가 알겠어” 쪽으로 서서히 흘러가기 때문입니다.

그리고 여기서부터가 Glicko를 “장식이 붙은 Elo” 이상으로 만드는 부분입니다. RD는 평점 갱신 자체에, 그것도 양쪽 모두에 개입합니다.

내 RD는 한 판의 결과가 나를 얼마나 움직일 수 있는지를 정합니다. RD가 크면 시스템이 내 숫자를 신뢰하지 않으니 자유롭게 움직입니다. RD가 작으면 수백 판에 걸쳐 쌓아 올린 평점이라는 뜻이고, 한 번의 패배로 크게 흔들려서는 안 됩니다. FIDE의 K 계단과 같은 결론인데, 선언된 것이 아니라 유도된 것이라는 점이 다릅니다.

상대의 RD는 그 결과가 얼마나 많은 정보를 담고 있는지를 정합니다. 평점 자체가 “글쎄요” 수준인 사람을 이긴 결과는 시스템에 거의 아무것도 알려주지 않으므로 내 평점도 거의 움직이지 않습니다. 반면 충분히 굳어진 1700을 이긴 것은 실제 정보이고, 그만큼 움직입니다. Elo에는 “이 결과는 저 결과보다 정보가 적다”고 말할 방법이 없습니다. 이 구분을 한 번 보고 나면 그것이 빠져 있는 자리가 여기저기서 눈에 들어옵니다.

기능을 쳐내야 한다면 마지막까지 지킬 속성이 이것입니다. 평점에 확신을 붙이는 것과, 그 확신으로 증거에 가중치를 주는 것은 같은 메커니즘을 두 번 쓰는 것입니다. 그래서 시스템이 작게 유지됩니다. 원래 Glicko의 설명은 3단계짜리입니다.

모두가 어기는 가정, 평점 주기

구현이 어긋나기 시작하는 지점이 여기입니다. 제 첫 구현도 포함해서요.

Glicko는 경기를 한 판씩 처리하지 않습니다. 평점 주기(rating period) 단위로 처리합니다. 수식이 동시에 일어난 것으로 취급하는 경기 묶음이죠. 모든 플레이어가 평점·RD·변동성을 들고 주기에 들어가고, 결과들이 관측되고, 주기가 끝날 때 새 값이 나옵니다. Glicko-2 논문에서 Glickman은 이 묶음의 크기에 대해 분명하게 말합니다.

The Glicko-2 system works best when the number of games in a rating period is moderate to large, say an average of at least 10-15 games per player in a rating period. The length of time for a rating period is at the discretion of the administrator.

온라인 래더는 정확히 그 반대를 원합니다. 매치가 끝났는데 평점 변화를 일요일까지 기다리는 사람은 없으니까요. 그래서 거의 모든 구현이 한 판을 한 주기로 돌립니다. 논문이 경고한 바로 그 영역이죠. 그리고 이건 사소한 이탈이 아닙니다. 시스템이 추정하는 대상 자체가 달라지기 때문입니다. 묶어서 처리하면 “이 플레이어가 이 상대군을 상대로 어땠는가”라는 하나의 질문에 한 번 답하는 것이 됩니다. 한 판씩 처리하면, 관측치 하나로 플레이어의 실력을 매번 자신 있게 다시 추정하는 갱신의 연쇄가 됩니다.

lichess는 흥미로운 중간 지점을 택했습니다. 갱신은 판이 끝날 때마다 진행된 순서대로 하되, 경과 시간 개념은 평점 주기를 소수로 쪼개어 유지합니다. 소스에 박혀 있는 상수는 하루당 0.21436 주기이고, 왜 하필 그 숫자인지가 주석에 그대로 적혀 있습니다.

// Chosen so a typical player's RD goes from 60 -> 110 in 1 year
val ratingPeriodsPerDay = 0.21436d

한 번 더 읽어 볼 만합니다. 상수로 위장한 제품 결정이거든요. 110은 잠정 평점 임계값입니다. 즉 평범한 활동 플레이어가 손을 놓으면 정확히 1년 뒤에 물음표를 달고 돌아오도록 맞춘 숫자입니다. 논문은 감쇠 메커니즘까지만 줍니다. 평점을 언제부터 믿지 않을지는 알려주지 않습니다. 그 판단은 래더를 운영하는 쪽의 몫입니다.

이 글에서 하나만 가져가신다면 이것입니다. 평점 주기는 의도를 갖고 정하고, 왜 그렇게 정했는지 적어 두세요. 주기 길이는 학습 속도와 비활동 감쇠와 시스템을 얼마나 악용할 수 있는지를 한꺼번에 결정합니다. “라이브러리가 그렇게 하길래 한 판에 한 주기”로 두는 것은, 그 세 가지 성질을 남이 정해 준 채로 쓰겠다는 뜻입니다.

Glicko-2와 변동성이라는 손잡이

Glickman이 2001년에 발표한 Glicko-2는 플레이어마다 세 번째 숫자를 추가합니다. 변동성(volatility)입니다. RD가 “우리가 얼마나 확신하는가”를 묻는다면, 변동성은 “이 사람의 경기력이 얼마나 들쭉날쭉했는가”를 묻습니다.

이 구분은 실제로 유의미합니다. 평점도 RD도 똑같은 두 플레이어를 생각해 보죠. 한 명은 매주 기대치에 정확히 부합하는 결과를 냅니다. 다른 한 명은 화요일에 2000을 잡고 목요일에 1100에게 집니다. 첫 번째 플레이어의 평점은 꽤 쓸 만한 예측값입니다. 두 번째 플레이어의 평점은 결과가 계속 부정하는 숫자이고, 변동성은 시스템이 그것을 알아채는 방식입니다.

변동성이 높은 플레이어는 평점이 더 크게 출렁입니다. 계속 틀리는 평점이라면 더 빨리 움직일 수 있어야 한다는 논리죠. 신규 플레이어의 기본값은 0.06입니다.

변동성은 시스템 상수 τ로 제약됩니다. 플레이어별이 아니라 래더 전체에 한 번 정하는 값입니다. 논문의 문장은 이렇습니다.

Reasonable choices are between 0.3 and 1.2, though the system should be tested to decide which value results in greatest predictive accuracy. Smaller values of τ prevent the volatility measures from changing by large amounts, which in turn prevent enormous changes in ratings based on very improbable results.

저 문장에서 “should be tested”가 많은 일을 짊어지고 있는데, 실제로 테스트하는 곳은 거의 없습니다. τ는 대개 갖다 쓴 라이브러리 README의 예제값 그대로 굳습니다.

알아 둘 만한 구현 역사가 하나 있습니다. Glicko-2에서 반복적 근 찾기가 필요한 단계는 변동성 계산뿐인데, 초기 절차는 시작값이 나쁠 때 가끔 수렴에 실패했습니다. Glickman은 2012년 2월에 이 단계를 regula falsi의 변형인 Illinois 알고리즘 기반으로 교체했습니다. 그의 시뮬레이션에서 새 절차는 반복 횟수 중앙값 5회, 10,000회 실행 중 최대 19회였습니다. 2012년 이전에 작성된 구현을 포팅하고 있다면 Step 5가 어느 쪽을 물려받았는지 확인해 보시는 편이 좋습니다.

변동성 파밍

변동성에는 말로 꺼내 놓고 보면 명백한 문제가 있습니다. 이것은 증폭기이고, 그 증폭기를 플레이어가 조종할 수 있습니다.

이 공격은 2020년 포켓몬 GO의 배틀 리그 리더보드를 대상으로 Farming Volatility라는 글에 기록되었습니다. 불편할 정도로 깔끔합니다.

이걸 가능하게 만드는 건 수식이 아니라 매치메이커입니다. 충분히 떨어지고 나면 상대가 마음대로 이길 수 있는 사람들로 채워지고, 그때부터 원하는 승패 패턴을 만드는 데 드는 비용은 시간뿐입니다. 이 지점에서 하고 있는 일은 평점을 속이는 것이 아니라, 변동성 추정기에 직접 만든 수열을 먹이는 것입니다.

Elo-MMR 논문(Ebtekar & Liu, WWW 2021)은 이를 TopCoder 래더 시뮬레이션에서 수치로 보여 줍니다. 변동성을 파밍한 플레이어는 조건이 동일한 정직한 플레이어보다 523점 앞선 채 끝났고, 그중 1,000점 가까이가 마지막 15개 대회에서 나왔습니다. 반올림 오차 수준이 아니라 리더보드 최상단이 걸린 차이입니다.

체스판도 이 질문을 피해 가지는 못했습니다. 2021년 1월 5일에 열린 lichess 이슈 #7862의 제목은 “Glicko2 may be flawed”이고, 내용은 정확히 이것입니다. 일부러 져서 변동성을 부풀린 다음, 정직하게 두면서 증폭된 상승분을 회수한다는 것이죠.

Glicko-2의 변동성은 플레이어가 이기려고 한다는 것을 전제합니다. 이 전제는 원래 대상이었던 공식 체스 대회에서는 성립하지만, 익명 계정과 무료 재대국과 진입 비용 없음이 결합된 래더에서는 무너집니다. Glicko-2를 도입하기 전에 “내 시스템에서 지는 비용이 싼가”를 먼저 물어보세요. 싸다면 변동성은 공격 표면이고, 반드시 상한을 걸어야 합니다.

완화책은 전부 저 순환 고리에서 다리 하나를 빼는 방식입니다. 변동성에 상한을 걸어 증폭기를 포화시키거나, 평점에 하한을 두어 일부러 떨어지는 비용을 비싸고 되돌리기 느리게 만들거나, 매치메이킹 범위를 충분히 넓게 유지해서 일부러 떨어진 계정도 여전히 불확실한 상대를 만나게 하는 것입니다. 마지막 방법이 “결과를 마음대로 고를 수 있다”는 전제 자체를 깹니다. 아니면 학술적인 경로를 택해, 애초에 전략적 조작에 견디도록 설계된 시스템을 쓰는 방법도 있습니다. Elo-MMR이 주장하는 쪽이죠.

실제 운영 구현은 어떻게 생겼는가

이 주제에서 제일 유용했던 한 시간은 설명글을 하나 더 읽는 대신 lichess의 rating 모듈을 읽은 시간이었습니다. 논문 그대로의 Glicko-2에, 어떤 논문에도 없는 안전장치가 열댓 개 둘러쳐져 있습니다.

val minRating = IntRating(400)
val maxRating = IntRating(4000)

val minDeviation              = 45
val variantRankableDeviation  = 65
val standardRankableDeviation = 75
val maxDeviation              = 500d

// past this, it might not stabilize ever again
val maxVolatility     = 0.1d
val defaultVolatility = 0.09d

// rating that can be lost or gained with a single game
val maxRatingDelta = 700

val tau = 0.75d

논문의 기본값과 나란히 놓으면 일치하는 게 거의 없습니다.

maxVolatility에 달린 주석, past this, it might not stabilize ever again이 제일 솔직한 문장입니다. 누군가 라이브 시스템이 스스로 빠져나오지 못하는 상태로 걸어 들어가는 것을 보고 그 위에 판자를 덧대어 못을 박은 것이죠. 학술지에서는 볼 수 없고, 운영에서는 반드시 필요해지는 종류의 코드입니다.

표시 규칙은 나머지 절반이고, 이쪽은 순수하게 제품 영역입니다.

제일 먼저 베끼고 싶은 것은 리더보드 게이트입니다. RD를 가리지 않는 랭킹은 최근 표본에서 제일 운이 좋았던 사람의 목록이 됩니다. TrueSkill이 평균 대신 보수적인 하한값을 노출해서 피하는 것과 같은 병리죠. RD 75 이하를 요구한다는 것은 결국 “이 보드는 시스템이 실제로 확신하는 플레이어의 자리”라는 선언입니다.

그리고 RD 하한은 제가 예상하지 못했던 문제를 해결합니다. 하한이 없으면 베테랑의 RD가 지나치게 낮아져서 시스템이 사실상 그 사람을 더 이상 갱신하지 않게 됩니다. 실력을 이미 안다고 결론 내리고 귀를 닫는 것이죠. RD에 바닥을 깔아 두면 시스템은 놀랄 준비를 최소한만큼은 항상 남겨 둡니다.

Glicko가 맞지 않는 지점

Glicko는 쌍대비교 모델입니다. 두 경쟁자, 하나의 결과, 그리고 반복. 내 문제가 그 모양이 아니라면, 파라미터를 아무리 조정해도 맞지 않습니다.

가장 흔한 경우가 팀전입니다. 5대5 결과는 열 명에 대한 정보 1비트이고, 그것을 개인에게 배분하는 것은 Glicko가 답하지 않는 모델링 문제입니다. 흔히 쓰는 편법은 상대 팀 평균 평점을 상대로 각자를 평가하는 것인데, 들리는 그대로의 성능을 냅니다. 집계로 보면 그럭저럭 맞고, 항의가 들어올 개별 사례마다 불공정합니다.

배틀로얄은 더 나쁩니다. 100명이 전체 순위로 끝나는 경기는 애초에 쌍대비교가 아니고, 이를 수천 개의 짝 결과로 분해하는 것은 틀린 동시에 비쌉니다.

TrueSkill은 정확히 이 문제를 위해 만들어졌습니다. Microsoft가 Halo 2 베타 데이터로 학습시켜 2005년 Xbox Live에 올린 시스템이죠. 플레이어마다 실력을 가우시안으로 모델링하고, 팀 성능을 구성원의 합으로 보며, 다자간 순위를 그대로 다룹니다. 리더보드에는 평균이 아니라 보수적인 추정치를 노출합니다. 2018년의 TrueSkill 2는 여기에 경험치, 중도 이탈 행동, 개인 스탯까지 얹었습니다.

그런데 왜 어디를 가도 보이는 쪽은 Glicko일까요. lichess, Chess.com, Pokémon Showdown, Online-Go, TETR.IO, Guild Wars 2, 스플래툰, 그리고 이름 없는 수많은 래더까지요. 이유는 두 가지고, 둘 다 수학과 무관합니다.

퍼블릭 도메인이라는 점이 첫째입니다. Glickman은 Glicko와 Glicko-2를 모두 의도적으로 퍼블릭 도메인에 두었고, TrueSkill은 특허가 걸려 있습니다. 작은 팀에게 “변호사 없이 쓸 수 있는가”는 예측 정확도 몇 퍼센트포인트보다 앞에 오는 질문입니다.

둘째는 하루면 구현할 수 있을 만큼 작다는 점입니다. 플레이어당 숫자 셋, 단계 몇 개, 반복 루프 하나. 운영 중에 평점이 이상해 보일 때 이유를 실제로 추적할 수 있습니다. 제가 소스를 읽어 본 베이지안 시스템 전부가 그렇지는 않았습니다.

1대1이고 플레이어가 정직하게 임하는 환경이라면 Glicko-2가 올바른 기본값입니다. 팀전이나 배틀로얄이라면, 쌍대비교로 안 되는 일을 억지로 시키기 전에 TrueSkill이나 OpenSkill(Weng-Lin 모델의 관대한 라이선스 구현)을 먼저 보시는 편이 낫습니다.

내 시스템에 가져갈 것들

제가 만들던 래더는 1대1이라 결국 Glicko-2로 갔습니다. 다만 마지막에 제가 신경 쓰게 된 부분은 처음에 예상했던 것들이 아니었습니다.

불확실성은 저장하되, 화면에는 다른 것을 보여 주세요. 평점과 RD는 시스템이 추론에 쓰는 값입니다. 플레이어가 보는 것은 티어든 랭크 이름이든 보수적인 하한값이든, 나중에 마이그레이션 없이 바꿀 수 있는 무언가면 됩니다. 원시 숫자가 노출되는 순간 플레이어는 그 숫자를 향해 최적화하고, 그때부터는 그 숫자를 고칠 자유가 사라집니다.

리더보드는 확신을 기준으로 막으세요. RD 75 이하든, 우리 시스템의 수치로 환산한 그에 준하는 기준이든 상관없습니다. 비용은 없고, “6판 두고 보드 최상단에 있는 저 사람은 누구인가” 부류의 문의가 통째로 사라집니다.

폭주할 수 있는 값에는 전부 상한을 거세요. 변동성, 한 판 변동폭, 평점 하한, RD 상·하한. 이 상한들은 하나하나가 “모델에는 오작동하는 구간이 있다”는 인정이고, 그 구간이 어디였는지를 새벽 2시에 알아내는 것보다 전부 싸게 먹힙니다.

평점 주기는 의도적으로 결정하세요. 한 판에 한 주기도 정당한 선택입니다. 동시에 논문에 실린 것과는 다른 시스템이기도 합니다. 그 차이는 라이브러리 기본값에서 물려받는 것이 아니라 스스로 고른 결과여야 합니다.

그리고 누군가는 반드시 일부러 진다고 가정하세요. 지고 싶어 하는 플레이어가 내 시스템에서 무엇을 뽑아낼 수 있는지 물어보는 겁니다. 그 답에 내가 쥐고 있는 증폭기가 등장한다면, 리더보드가 이미 망가진 다음이 아니라 출시 전에 묶어 두는 편이 낫습니다.

Glicko에서 제가 정말 좋다고 생각하는 지점은, 오래된 상식을 정직하게 적용했다는 것입니다. 오차 범위가 없는 측정은 측정이 아니라는 상식이요. Elo는 숫자를 줬습니다. Glicko는 숫자에 더해 그것을 얼마나 믿을지를 줬고, 설계의 나머지 전부를 그 신뢰도가 실제로 일하게 만드는 데 썼습니다.

그 밖의 것들, 상한과 하한과 소수 단위 주기와 일부러 지는 행위를 막는 규칙들은 통계 모델이 이기고 싶어 하는 사람들과 만났을 때 생겨나는 부분입니다. 논문에는 그 부분이 없습니다. 소스 코드에는 있습니다.

참고 자료

• Glicko rating system — Wikipedia
• Mark Glickman의 Glicko 페이지: Glicko, Glicko-2, Glicko-Boost 논문
• Glickman (1999), Parameter Estimation in Large Dynamic Paired Comparison Experiments, JRSS-C 48(3)
• The Glicko-2 system (PDF)
• lichess-org/lila — modules/rating/src/main/Glicko.scala
• lichess 이슈 #7862, “Glicko2 may be flawed”
• Ebtekar & Liu, Elo-MMR: A Rating System for Massive Multiplayer Competitions (WWW 2021)
• TrueSkill — Wikipedia
• Elo rating system — Wikipedia