저는 지난번 글에서 마재윤을 언급한 적이 없었는데 댓글은 자료에 대한 이야기보다는 그에 대한 갑론을박이 벌어지고 있더군요. 의도치 않게 분란 글을 쓴 듯한 느낌도 들고, 내가 왜 이걸 시작했지 싶은 후회도 약간 들었네요. 그러나 추가적인 분석을 기다리는 분들도 분명 있을 것으로 믿고 새로 글을 씁니다.

  어떤 종목이든 선수들 사이에 실력으로 줄을 세워보고 싶은 사람들의 욕망은 끝이 없습니다. 이런 랭킹 시스템은 몇 가지로 나눌 수 있습니다. 각 경기의 중요도에 따라서 가중치를 정하고 그 결과에 따라서 더한 것을 점수로 하는 방식이 있고, 오래 된 경기의 가중치는 낮추고 최근 경기의 가중치를 높이는 식으로 계산하는 방식이 있습니다. WP랭킹은 두 가지를 혼합한 방식이 되겠지요. 한 편으로, ELO나 Glicko, Trueskill처럼 수학 이론을 바탕으로 확률적, 통계적으로 나타내고자 하는 레이팅 시스템이 있습니다.

  Trueskill은 Microsoft에서 개발한 알고리즘으로, 선수의 실력이 어느 정도 될 것이다라는 '확신'을 점수로 삼습니다.

  정규 분포라는 말을 들어 보셨습니까? 예를 들어서 (무게중심이 정확히 중앙에 있는) 동전을 위로 던져 봅시다. 앞면이 나올 확률과 뒷면이 나올 확률은 정확히 1/2일 것입니다. 그리고 동전을 제 아무리 여러 번 던지더라도 이 확률은 바뀌지 않습니다. 다시 말해서 동전 던지기는 독립 시행입니다. 지금까지 앞면이 499번, 뒷면이 500번이 나왔다고 해서 이번에 던질 동전이 앞면이 나올 확률이 올라가는 건 아닌 것이죠.

  그러나 이런 경우에도 최종적인 결과에 있어서는 그 확률이 같지 않습니다. 여러분이 동전을 1000번 던져서 앞면이 나온 횟수를 종이에 기록한다고 생각해 봅시다. 500번이 나올 수도, 단 한번도 나오지 않을 수도 있습니다. 그리고 이런 과정을 수만 번씩 반복한다고 생각해 봅시다. 동전의 앞뒷면이 나올 확률이 동일하게 1/2이므로 시행을 반복할 수록 1000번의 절반인 500번에 가까운 결과들이 많이 등장하게 될 것입니다.

  사실 이항계수를 이용해서 결과가 어떤 모양이 될 것인지 예측이 가능합니다. 그래프를 그려 보면 다음과 비슷한 모양이 되겠지요.

from  ( 

  대신 어떤 두 선수 사이에 어떤 결과가 나왔느냐에 따라서 '음? 얘가 쟤를 이길 확률이 몇 퍼센트 정도였는데 쟤가 이겼으니까… 실제 실력은 아마 이렇게 되지 않을까?' 하는 식으로 정규분포의 모양을 조절하는 것이죠.

  ELO랑 다른 점이 있다면 ELO는 정규분포를 가정하긴 하는데, 모든 선수의 가 같다고 생각해 버립니다. 그래서 계산하기는 편한데 새로운 선수가 기존 선수들 사이에 끼어들었을 경우 선수의 실제 실력에 수렴하기까지 시간이 너무 오래 걸립니다. 그래서 관성 개념도 도입하고, 랭크에 따라 동적 계수를 다르게 적용하고 하는 식의 경험적 튜닝을 많이 사용하죠. 어찌저찌 동작은 하는데 우아한 방법이라고 하긴 어렵습니다.

  이 조절하는 부분이 사실 Glicko나 Trueskill 같은 베이지안 레이팅의 핵심적인 부분인데, 상당히 복잡합니다. 이건 논문을 보셔야 돼요. 저도 전공이 완전 다른 분야라서 완전히 이해하고 있다고는 할 수 없겠네요. 그러나 한가지는 말씀드릴 수 있는데, 현재 알려진 ELO-like 시스템 중에서는 Trueskill이 가장 믿을만한 시스템입니다. (Trueskill의 업그레이드 버전인 Trueskill through time을 제외하면요)

  아무튼 저는 Trueskill을 스타1에 적용해 보았습니다. 그것이 아래 글의 내용이었고요. 적용한 방법은 간단히 설명하면 다음과 같습니다.

1. 각 선수들은 대 테란전, 대 프로토스전, 대 저그전 레이팅을 따로 가집니다.

2. 경기 결과를 시간 순으로 Trueskill 시스템이 적용합니다.

3. 각 레이팅에 대해서 를 구합니다. 위에서 설명했듯이 Trueskill Rating은 정규분포를 가정하기 때문에, Trueskill이 선수의 실력이 보다 높을 확률이 99%라고 믿고 있는 지점이 됩니다.

4. 각 종족전 rank의 평균을 냅니다.

5. 주요 선수들에 대해서 시간에 따라서 어떻게 변화하였는지 그래프를 그려 봅니다.

(여기까지가 처음 버전)

   그런데 여기에는 문제점이 있었습니다. 바로 은퇴한 선수들이나 한동안 슬럼프를 겪으며 경기에 나오지 못한 선수들의 레이팅이 변화하지 않는다는 것입니다.

그래서 저는 decaying 시스템을 적용하기 위해서 다음과 같이 하였습니다.

1. decay가 적용되기까지 필요한 날 수 를 정의합니다.

2. 일 이상 경기에 나오지 못한 선수는 그 날 이후 매일 점씩 가 깎입니다.

3. 는 일마다 배가 됩니다.

  그 외에 Trueskill에서 사용하고 있는 다음 상수들도 있죠.

1. Beta (두 선수 간에 점수가 Beta점 차이나면 승률이 76%가 됩니다)

2. Tau (시스템의 레이팅이 얼마나 빠르게 변화하는지를 정합니다)

3. Draw Probability (두 선수 사이에 실력이 같을 때 비길 확률입니다)

4. 처음 시작하는 선수의 

  저는 이들 상수들의 최소값과 최대값을 임의로 정한 후, 유전 알고리즘을 적용했습니다. 유전 알고리즘이란 '적자 생존의 법칙'을 문제 풀이에 응용하는 것으로 빠른 시간 내에 최적해를 구하기 어려운 문제들에 적용되는 방법입니다. 우선 난수를 생성하여 임의의 해 집단을 생성하고, 각각의 해의 품질을 측정한 다음, 뛰어난 해들을 섞어서 새로운 해를 만들고 해 집단에 추가하는 것입니다. 좋은 품질의 해를 섞으면 더 좋은 품질의 해를 만들 가능성이 높다고 보는 것이죠. 일종의 품종 개량 원리입니다.

해의 품질은 어떻게 평가했을까요? 저는 각각의 경기에 대해서 다음의 식을 적용하였습니다.

  p는 Trueskill에서 (실제로 승리한 선수가) 예측했던 승리 확률입니다. 확률이 낮다고 생각했는데 이겼다면 예측 결과가 나빴으니까 log loss가 커질 것이고, 확률이 높다고 생각했는데 이겼다면 뭐 이상할 것 없으니 log loss가 작아지겠죠. 이후 모든 log loss의 평균을 내어 이것을 기준으로 적합도를 산정합니다.

  가장 좋은 해가 가장 나쁜 해보다 선택될 확률이 4배 높도록 하여 한참을 실행했습니다. 그것이 아래 글의 1차 수정 결과입니다. 그러나 같은 시대의 선수들끼리 상대적인 위치를 예상하기는 나쁘지 않았지만, 전체적으로 계속 decay가 일어나고 있으므로, 경기가 상대적으로 적은 뒷세대 선수들이 점수 상으로는 너무 큰 손해를 보는 듯한 느낌을 지울 수가 없었습니다.

(여기까지 1차 수정)

그래서 이번에는 Mean 점수를 깎는 상한선을 정했습니다. 아무리 오래 쉬어도 이 상한선보다 많이 깎이지는 않도록 한 것이죠. 그러고 나서 다시 유전알고리즘을 돌렸더니, 모양은 그럴싸한데 이번엔 영 결과 예측 정확도가 좋지 않았습니다.

그래서 여기저기 둘러보던 중, glicko 레이팅 시스템을 제안했던 glickman 교수가 제안한 decaying 시스템이 있더군요. 시간 t만큼 게임을 하지 않은 선수의 deviation을 다음과 같이 조정하자는 것이었습니다.

저는 단순히 시간에 따라서 계속 증가하게 했었는데 말이죠. 그래서 mean 부분은 그대로 두고, deviation을 glickoman의 제안대로 고쳐 보았습니다. 상당한 품질 향상을 발견할 수 있었습니다...만, 막상 예측 결과를 보니까 그렇게 뛰어나지 않더군요.

문제는 이것이었습니다. Trueskill에서 예측한 승리확률과 실제 승률을 비교해 보니 상당히 차이가 컸던 것입니다. 예를 들어 시스템에서 어떤 선수의 승률이 30%라고 예측한 경기들을 모아놓고 실제 그 경기 결과들과 비교하면 30%에 가깝게 나와야 시스템이 믿을만하다고 생각할 수가 있겠죠. 그런데 막상 해 보니까 어떤 부분에서나 실제 승률이 50%에 가깝게 나오는 것 아니겠습니까.

아, 이거 뭔가 잘못됐구나 하고 느끼고 적합도를 평가하는 방법을 바꿨습니다.

1. 예상 승리 확률에 따라 경기들을 나눕니다. 예를 들어, 한 선수의 예상 승리확률의 5~10% 였던 경기들의 실제 승률을 구합니다. 이 구간의 중간값이 7.5%이므로, 이 구간에 대해 실제 승률과의 차이를 계산합니다. 이를 이 구간에 대한 오차 diff로 합니다.

2. 각각의 구간들에 대해서 diff의 제곱을 더합니다.

3. 2의 결과에 제곱근을 취합니다.

다른 말로 하면 '예상 승률과 실제 승률 사이의 MSE를 구한다' 정도가 되겠습니다. MSE는 평균제곱오차를 말하는 것으로 이것이 낮을 수록 좋은 해인 것이죠.

또 유전 알고리즘 역시 수정이 있었습니다. 바로 섬식 교배를 사용한 것인데요. 이건 4개인 CPU 코어를 최대로 사용하기 위해 동일한 코드를 네 번 실행한 다음, 중간중간에 해를 섞어준 것입니다. 이는 단순히 동시에 4배의 연산을 하는 것 이상의 의미를 가집니다. 유전 알고리즘은 시간이 흐르면서 해 집단에 속한 염색체들이 점점 비슷해져서 거의 차이가 없게 됩니다. 이것을 억제하기 위해 돌연변이 비율을 높이는 식으로 교란하기도 합니다만, 아무튼 시간이 흐르면 반드시 발생하는 필연적인 현상입니다.

이렇게 이해하시면 됩니다. 작은 섬에 고립된 동물들은 섬의 환경에 맞게 진화하여 원래의 모습과 전혀 다른 형태가 되는데, 같은 섬의 각 개체 사이 유전적 차이는 거의 없어지게 되죠. 유명한 예로 갈라파고스 제도의 동물들을 생각하면 됩니다. 원래는 하나의 큰 땅덩이였던 곳이 있다고 생각해 봅시다. 그런데 갑자기 해수면이 높아지면서 이 땅이 여러 개의 작은 섬으로 나뉘어 버렸습니다. 원래는 동일한 생태계였던 섬들이지만 시간이 지나면서 각 섬의 환경에 맞춰서 서로 다른 모습으로 동물들이 진화하게 되었습니다. 물론 같은 종이긴 하지만, 모양이라던지 크기라던지 색이라던지가 서로 전혀 다르게 변한 것이죠.

이런 상황에 갑자기 해수면이 다시 내려가서 이 섬들이 하나가 되었습니다. 떨어졌던 동물들이 서로 오고 갈 수 있게 되는 거죠. 이 상태로 시간이 흐르면, 아주 오래 전의 종과는 완전히 다르면서도, 섬이 갈라져 있던 때와는 또 다른 특징을 지닌 생태계가 형성이 될 것입니다.

유전 알고리즘에서도 마찬가지 효과를 바라는 것입니다. 동일한 알고리즘을 여러 해 집단에 대해서 실행하면, 기본적으로 각 해집단의 품질 차이가 많이 나지는 않을 겁니다. 하지만 해를 이루는 염색체의 구성 면에서는 해 집단마다 다른 특성을 갖겠지요. 이럴 때에 서로 간에 해가 이동하게 함으로써 서로 다른 해 집단 사이에서 발생한 장점들을 모두 갖는 더 좋은 해가 발생할 수 있기를 바라는 것입니다. 하는 김에 각 섬에서 사용하는 교배 연산을 다른 걸로 해 봤습니다. 어떤 놈이 더 좋은 해를 찾아내는지 지켜보는 재미도 쏠쏠하네요.

최종 결과입니다.

생각보다 시간에 따른 Decaying 효과가 크지 않아서 이거 이러려고 일주일 내내 계산 돌리고 있었나 싶긴 한데… 제가 원하는(예상했던) 모양 나오게 만들자고 데이터를 주작작주작작할 수는 없는 것 아니겠어요?

시대에 따른 평균 레이팅에 차이가 있을 것이므로 전 세대와 후 세대를 일대일로 비교할 수는 없을 겁니다. 하지만 어쨌든 Decaying 시스템도 구현하고 상수도 유전알고리즘으로 구하는 등 현재 해볼 수 있는 것들은 모두 해 보았기 때문에, 이후에 시간에 따른 변화를 고려해서 더 발전된 알고리즘을 적용한다고 하더라도 극적인 차이를 보이지는 않을 것 같습니다. 뭐, 기껏해야 차이가 약간 더 벌어지는 정도겠고 오히려 줄어들지도 모르죠.

이 데이터를 가지고 해석하는 방법은 여러 가지가 있을 겁니다. 다만 제가 나름대로 해석을 붙여 본다면 … 이전 세대 선수들 역시 그들 나름대로 그 당시에 알려진 전술적 전략적 한계, 그리고 당시의 맵 풀 안에서는 한계에 가까운 실력을 가지고 있었을 것이라는 겁니다. 비교적 최근에 활동했던 선수들이 과거로 간다면 그 시대의 선수들을 모두 물리치고 최강의 위치에 설 수 있을까요? 글쎄요. 그래프를 보아서는 그리 쉽지는 않아 보입니다. 새로 등장한 운영 또한 흡수해버리고 결국 동등한 위치에서 경쟁하게 되지 않을까요.

https://dl.dropboxusercontent.com/u/175928434/sc_trueskill/%EC%A3%BC%EC%9A%94%20%EC%84%A0%EC%88%98.xlsx

시간에 따른 플레이어 레이팅 변화 데이터(vs T, vs P, vs Z, Overall 순) https://dl.dropboxusercontent.com/u/175928434/sc_trueskill/PlayerRatings.zip

이번엔 데이터 자체를 공개합니다. 테란전, 플토전, 저그전 레이팅 자체가 존재하므로 이를 바탕으로 또 다른 그래프를 그려보는 것도 가능할 겁니다.

여기 나타나지 않은 다른 선수들에 대해서도 구하려면 구할 수 있는데 계산 시간이 길어지는 관계로 일부만 탑재한 것입니다, 꼭 알고 싶은 선수가 있으면 아이디와 종족을 알려 주세요.