Хотя люди давно соревнуются в играх, сила игроков долгое время оценивалась субъективно по выступлениям на турнирах и качеству сыгранных партий. Первые числовые рейтинговые системы стали использоваться лишь в 40-х годах 20 века. Локомотивом этого направления были, конечно, шахматы.

Рейтинг Эло

Шахматная федерация США применяла рейтинговые системы для оценки силы шахматистов с 1950-х годов. И хотя полученные рейтинги, по общему мнению, соответствовали соотношению силы игроков, они были несовершенны и иногда приводили к неожиданным результатам. Например, при большой разнице рейтингов, слабейший игрок мог проиграть все партии на турнире и всё равно повысить свой рейтинг.

В 1959 году Шахматная федерация США поручила своему сотруднику Арпаду Эло разработать новую систему рейтинга. В 1961 году разработанная им система стала широко применяться. Она хорошо зарекомендовала себя, и к тому же была статистически обоснована, поэтому с 1970 года Международная шахматная федерация (ФИДЕ) также стала использовать систему Эло.

Расчёт рейтинга Эло

В системе Эло рейтинг изменяется на основе ожидаемого результата игры двух игроков. Основная идея в том, что более сильный игрок должен выигрывать с большей вероятностью, причём чем больше разница в силе, тем больше вероятность победы. Новые рейтинги игроков A и B пересчитываются в зависимости от результата игры по формуле:

$R_A^{new}=R_A + K(W - W_{E})$

$R_A^{new}$ – новый рейтинг игрока A после партии
$R_A$ – рейтинги игрока A до партии
$K$ – весовой коэффициент. Выбирается в зависимости от уровня игроков
$W$ – результат игрока A (в шахматах 1 - победа, 0.5 - ничья, 0 - поражение)

$W_{E}$ – ожидаемый результат игрока A, который рассчитывается по формуле:
$W_{E} = (1 + 10^{\frac{R_B - R_A}{400}})^{-1}$, где $R_{B}$ – рейтинги игрока B до партии

Соответствие шахматных рейтингов званиям ФИДЕ:

Пример:

Женя и Никита играют в турнире с подсчётом рейтингов по системе Эло с коэффициентом $K=10$. Перед игрой Женя имеет рейтинг 2500, а Никита - 2600. Они сыграли партию вничью (по 0.5 очка каждому).

Новый рейтинг Жени:

$W_{E} = (1 + 10^{\frac{2600 - 2500}{400}})^{-1} = 0.36$
$R = 2500 + 10(0.5 - 0.36) = 2514$

Новый рейтинг Никиты:

$W_{E} = (1 + 10^{\frac{2500 - 2600}{400}})^{-1} = 0.64$
$R = 2500 + 10(0.5 - 0.64) = 2586$

Так как изначально рейтинг Никиты был чуть выше, ничья привела к тому, что рейтинг Никиты немного уменьшился, а рейтинг Жени – увеличился.

∎

Вывод формулы рейтинга Эло

Определение:

$A \sim \mathcal{N}(\mu, \sigma^{2})$ – случайная величина А имеет нормальное распределение с математическим ожиданием $\mu$ и дисперсией $\sigma^{2}$

$\Phi$ – функция стандартного нормального распределения

$(1 + e^{-(x - \mu) / b})^{-1}$ – функция логистического распределения с математическим ожиданием $\mu$

Также нам понадобится вспомогательная лемма о нормальном распределении разницы случайных величин:

Теорема:

∎

Модель нормального распределения

Будем считать, что у игрока есть некоторый уровень мастерства, но из-за различных случайностей в конкретной партии он может сыграть как хуже, так и лучше своего уровня.

Предположения модели:

1. Силы игроков – это независимые случайные величины
2. Сила игрока имеет нормальное распределение
3. Математическое ожидание силы – это оценка уровня мастерства игрока
4. Дисперсия не зависит от игрока и одинакова для всех игроков

То есть, если у игрока сила $p$ и уровень мастерства $s$, то, согласно модели
$p \sim \mathcal{N}(s, \sigma^{2})$, где $\sigma$ одинакова для всех игроков.

Пусть есть два игрока: A и B:
$p_{A} \sim \mathcal{N}(s_{A}, \sigma^{2})$
$p_{B} \sim \mathcal{N}(s_{B}, \sigma^{2})$

Игрок A выиграет в партии, если его сила больше, т.е. если величина $p_A - p_B > 0$

Согласно лемме, величина $p_A - p_B$ имеет распределение $\mathcal{N}(p_A - p_B, 2\sigma^{2})$. Тогда вероятность победы A равна:
$P(p_A - p_B > 0) = \Phi(\frac{s_A - s_B}{\sqrt{2}\sigma})$

Так как уровни мастерства игроков в реальности неизвестны, вместо них используется оценки (рейтинги). Поэтому в качестве оценки вероятности можно использовать величину
$W_E= \Phi(\frac{R_A - R_B}{\sqrt{2}\sigma})$

Из этой формулы сразу следует:

Теорема:

∎

Это означает, что рейтинги определены с точностью до масштаба $\sigma$ и являются сравнительными. То есть имеет смысл сравнивать рейтинги игроков, только если они рассчитаны в рамках одного пула.

В системе Эло был выбран параметр масштаба $\sigma=200$ для совместимости с предыдущими версиями рейтингов. Разница в $200$ пунктов означает, что более сильный игрок выиграет с вероятностью: $\Phi(\frac{1}{\sqrt{2}}) = 76.02%)$%, то есть примерно в трёх четвертых случаев.

Модель логистического распределения

Для величины $W_E$ могут использоваться и другие распределения. Так, было замечено, что логистическое распределение лучше моделирует вероятности победы игроков с меньшим рейтингом.

В настоящее время ФИДЕ использует рейтинг Эло на основе логистического распределения с параметром масштаба $b = \frac{400}{log10}$. В этом случае ожидаемое число очков будет равно:

$W_E = (1 + 10^{(R_B - R_A )/ 400})^{-1} $

Из-за простоты, наглядности и точности система Эло получила распространение и за пределами шахмат.

Рейтинг Глико

Но система Эло имеет также ряд недостатков. Например, в ней считается, что рейтинги оценивают силу игроков с одинаковой точностью. На практике это, конечно, не так: скажем, если два игрока имеют одинаковый рейтинг 2600, но один играет каждый день, а второй играл последний раз год назад, то в рейтинге первого мы уверены значительно сильнее, чем второго.

В 1995 председатель комитета по рейтингам Шахматной федерации США Марк Гликман предложил новую систему рейтинга – систему Глико. В ней, помимо рейтинга игрока, хранится величина RD – степень надёжности рейтинга, которая уменьшается со временем.

Пример:

Рейтинг игрока равен 1700, а RD=100. Используя двойной RD можно сказать, что рейтинг игрока лежит между 1500 и 1900.

Если RD = 25, то рейтинг игрока измеряется точнее: между 1650 и 1750.

∎

Расчёт рейтинга Глико

Игры проводятся “рейтинговыми периодами”. Периодом может быть любое значение: хоть минута, хоть месяц, на усмотрение организаторов турнира. Однако система Глико работает наиболее точно, когда число игр в рейтинговом периоде невелико, где-то 5-10. Формулы в системе Глико намного сложнее, чем в системе Эло.

Определим рейтинг и RD для каждого игрока в начале рейтингового периода.

$RD = min(\sqrt{RD^2_{old} + c^2t}, 350)$, где
t – число рейтинговых периодов со дня последней игры
c – константа, регулирующая увеличение неопределенности со временем
350 - базовое значение рейтинга для нового игрока

Пусть игрок перед началом рейтингового периода имеет рейтинг $r$ и отклонение $RD$. У него $m$ соперников с рейтингами $r_1,…,r_m$ и отклонениями $RD_{1},…RD_{m}$. Результаты игр – $s_1,…,s_m$. Тогда формул пересчёта рейтинга по система Глико таковы:

$r_{new} = r + \frac{q}{1/RD^2 + 1/d^2}\sum_{j=1}^{m} g_j(s_j - E_j) $

$RD_{new} = \sqrt{(\frac{1}{RD^2} + \frac{1}{d^2})^{-1}}$

где

$q = \frac{ln(10)}{400}$

$g_j = \frac{1}{\sqrt{1 + 3q^2(RD_j^2) / \pi^2}}$

$E_j = \frac{1}{1 + 10^{-g_j(r - r_j) / 400}}$

$d^2 = (q^2\sum_{j=1}^{m}g_j^2E_j(1 - E_j))^{-1}$

Рейтинг Гликo-2

В 2000 году Марк Гликман предложил улучшение своей системы: Глико-2. К параметрам рейтинга и степени надёжности добавляется ещё один – изменчивость, которая отражает стабильность ожидаемых результатов. Если игрок выигрывает у игроков слабее и проигрываете более сильным – то его изменчивость падает. А если, будучи начинающим, вдруг обыгрывает мастеров – растёт.

Рейтинговые системы Глико и Глико-2 применялись на шахматных площадках Chess.com и Lichess, а также на игровых серверах Pokemon Go, CS:GO, Team Fortress 2, Dota 2 и соревнованиях по программированию.

TrueSkill

С развитием онлайн-игр интерес к рейтинговым системам сильно вырос. В 2006 году в Microsoft разработали рейтинговую систему TrueSkill и использовали ее в сервисе Xbox Live. В системе TrueSkill, подобно Глико, хранится два значения: рейтинг и степень его надёжности. Но есть и отличия:

1. Система TrueSkill позволяет рассчитывать рейтинги игроков, которые разбиты на команды разных размеров
2. В системе Глико степень надежности рейтинга увеличивается в зависимости от количества рейтинговых периодов, которые игрок пропустил, а в системе TrueSkill она увеличивается на константу после каждого матча игрока
3. В системе Глико для разницы используется логистическое распределение, а в системе TrueSkill – нормальное

Новые подходы

Интерес к рейтинговым системам развивается и появляются новые подходы. Сейчас возможно получить намного больше информации о ходе игры. А значит можно применить её для оценки рейтинга игрока не только в зависимости от результата, а в зависимости от качества его решений во время игры. Например, на платформе Kaggle проводились соревнования по оценке рейтинга шахматистов на основе оценки исторических данных и силы ходов 1, 2, и это направление продолжает развиваться.