dmagin (dmagin) wrote,
dmagin
dmagin

Categories:

Заметки о расчете рейтинга

Тема, которая занимала меня несколько отпускных дней - как правильно считать рейтинг шахматистов. Рейтинг - это оценка силы игрока.
Не буду здесь вдаваться в долгий исторический экскурс, но кратко скажу, что сейчас для расчета используется формула Эло (в википедии есть небольшой обзор, что и как). Мне же формулы Эло показались несколько искусственными и надуманными (возможно, просто потому, что я не до конца разобрался в теме).

Я нашел другой, более простой и правильный, на мой взгляд, подход, который изложил на шахматном форуме Crest-а. Сюда я просто скопирую посты (с небольшой правкой), чтоб они не затерялись...

31/01/2008 16:09:36 Magin
С формулами легче понимать, кто о чем говорит и что предлагает. Поэтому еще раз о правильной формуле расчета прироста рейтинга.

1. Сила игроков относительна. Поэтому сравнивать силу игроков (А и Б) следует через отношение их рейтингов: R(А)/R(Б). (В логарифмической шкале - разность).
2. Если отношение рейтингов двух игроков равно 2 (один сильнее другого в 2 раза), то это означает, что в матче сильнейший должен набрать 2/3 очков (а другой 1/3) - прогнозирование.
3. Поскольку шкалы все относительные, то результат партии w не может быть отрицательным. w(А) + w(Б) = 1. При ничьей, соответственно, w(А) = w(Б) = 0.5.
4. Вводим коэффициент k - это процент рейтинга, который проигравший отдает победителю. От величины этого коэффициента зависит скорость адаптации (перетекания) текущих рейтингов к показанным результатам.
5. Теперь получаем формулу для расчета приращения рейтинга игрока А:

dR(A) = k* (w(А)*R(Б) - w(Б)*R(А));       (1)

Для игрока Б - симметрично. Сумма приращений равна 0.
Смысл формулы (1). При победе игрока А ему переходит доля рейтинга Б, а при поражении А отдает Б долю своего рейтинга. Таким образом учитывается, что выигрывать выгоднее у сильных - больше очков получаем. В то же время проигрывать - все равно кому - отбирается одна и та же доля.
При ничьей мы частично отдаем свой рейтинг - частично получаем рейтинг соперника, - в выигрыше тот, у кого был меньший рейтинг. Все логично.

Демонстрационные примеры.
1. Сила игроков равна. R(А) = R(Б) = 1000 (у.е.). k примем равным 5%. Тогда при выигрыше А (или Б) получит 50 пунктов. При ничьей рейтинг не изменится.

2. Силы игроков отличаются в 2 раза. R(А) = 2000 у.е. R(Б) = 1000 у.е. При выигрыше А получит также 50 пунктов. При проигрыше отдаст 100 пунктов. При ничьей А отдаст 25 пунктов.

3. Проверим формулу (1). Предположим, что сила игроков также отличается в 2 раза и между ними проведен матч. Как указано выше, если сильнейший набрал 2/3 очков, то рейтинг игроков должен остаться неизменным. Подставляем величины в (1):

dR(A) = k* (2/3*1000 - 1/3*2000) = 0,   независимо от k.

Таким образом, формула (1) справедлива как для оценки результата, так и для предсказания. Думаю, что единственно справедлива.
Пересчитывать ли рейтинги после каждой партии (что на мой взгляд более логично) или для всего матча (турнира) в целом - это, ИМХО, вторично.

От абсолютных рейтингов, ес-но, можно перейти к логарифмическим, - удобнее вычитать, чем делить.

01/02/2008 00:07:52 Magin
(Ответ на замечание) Нет никакой разницы, с какой стороны смотреть - со стороны побед или поражений.
Распишем формулу (1) для А и Б:

dR(A) = k* (w(А)*R(Б) - w(Б)*R(А));       (1)
dR(Б) = k* (w(Б)*R(А) - w(А)*R(Б));       (2)

Отсюда видно, что

dR(A) = -dR(Б).

03/02/2008 02:02:23 Magin
Уточняем термины и обозначения.

1) Wij - матрица результатов игр между игроками i и j. Основное свойство:

Wij + Wji = 1.    (a)

При победе i-го игрока над j-м имеем: Wij = 1, Wji = 0.
При ничьей - Wij = Wji = 0.5.
В принципе можно ввести учет права выступки. Например, за ничью белыми давать 0.4 а черными - 0.6. Или за победу белыми начислять только 0.9 smile.
Матрица Wij может быть статистической,- то есть значения ее элементов могут принимать промежуточные значения между 0 и 1. Например, w(i, j) = 2/3 означает, что игрок i набрал 2/3 возможных очков в матче с игроком j (который, соответственно набрал 1/3).
(Интересно, чему равно Wii?) smile

2) Ri - это безразмерная величина для оценки относительной силы игроков. Сравнительная оценка силы игроков i и j выражается в том, какой ожидается статистический результат между ними. Предполагается, что при большом количестве игр отношение рейтингов игроков должно быть равно отношению результатов:

Ri/Rj = Wij/Wji,    (b)

здесь Wij - статистическая матрица ожидаемого результата.

3) dRi - это на самом деле dRij, - то есть приращение рейтинга i-го игрока после встречи с j-м. В свою очередь dRi - это сумма всех dRij по j. Для статического обсчета турнира начальный R игроков может быть фиксирован на весь турнир. (Хотя, наверное, стоит оценить возникающую при этом динамическую погрешность).

4) Формула для расчета dRij имеет вид:

dRij = k * (Wij*Rj - Wji*Ri),   (с)

Основное свойство: dRij + dRji = 0.    (d)

5) Логарифмическая шкала (IMHO) привычнее для восприятия. Предлагаю для логарифмический рейтинг обозначать через L. Без учета масштабирующих множителей:

L = Ln(R); R = exp(L).

Тогда (c) примет вид:

dLij = k * (Wij*exp(Lj - Li) - Wji);     (e)

Однако для расчетов и анализа удобнее оперировать с R.

03/02/2008 02:17:08 Magin
(Относительно математической модели)
Я следующую аналогию держал в голове. У каждого из игроков есть некая сумма денег. Они играют партию (матч) и по результатам надо оценить, кто кому какую сумму должен отдать. Если я знаю, что мой соперник сильнее, то на равные ставки я не согласен. Поэтому ставки должны быть пропорциональны силе (хотя бы примерно). Вот и все. Сумма денег - рейтинг. Изменение рейтинга - передача денег. При этом отмечаем баланс рейтингов - сколько убыло, столько и прибыло.
Далее следуют различные инварианты, которые приведены в предыдущих постах. Инварианты обеспечивают непротиворечивость выводов из основной формулы.

03/02/2008 03:19:53 Magin
Приведу еще небольшой анализ основной формулы (уравнения?)

dRij = k * (Wij*Rj - Wji*Ri) (*dt)   (с) (надо бы как-то ее назвать)

Пусть игроков всего двое (i=1, j=2) и они играют безлимитный матч. Предположим, что в течение матча сила игроков не меняется. Это эквивалентно утверждению, что W12 (и W21) не зависят от времени. Или по другому, средний результат игроков за любой (статистически значимый) отрезок матча - один и тот же. Для такой модели можно получить решение для динамики рейтингов R1 и R2 в явном виде (с учетом ес-ных допущений о малости приращений).

Итак, имеем систему дифф. уравнений

dR1(t)/dt = k * (W12*R2(t) - W21*R1(t)),   (1)
dR2(t)/dt = k * (W21*R1(t) - W12*R2(t)).

Начальные рейтинги игроков обозначим через R01 и R02. Решая систему (1), получаем для R1(t) следующее выражение:

R1(t) = W12(R01 + R02) + (W21*R01 - W12*R02) * exp(-kt).    (2.1)

Для R2(t) выражение аналогичное:

R2(t) = W21(R01 + R02) + (W12*R02 - W21*R01) * exp(-kt).    (2.2)

Теперь мы можем проверить, как работает наша модель (пары игроков) в разных случаях.

1. Игрок 1 все время проигрывает (W12 = 0, W21 = 1). Получаем:

R1(t) = R01 * exp(-kt).    (3.1)

Видно, что рейтинг проигрывающего игрока постепенно (по экспоненте) сходит на нет.
В это же время рейтинг второго игрока приближается к насыщению:

R2(t) = R02 + R01*(1 - exp(-kt)).    (3.2)

Значение предельного рейтинга выигрывающего игрока равно сумме начальных рейтингов. Что понятно, поскольку все перетекло от одного другому.

2. Игроки оказались равны по силе (W12 = W21 = 0.5). Тогда:

R1(t) = 1/2*(R01 + R02) + 1/2*(R01 - R02) * exp(-kt).    (4.1)
R2(t) = 1/2*(R01 + R02) + 1/2*(R02 - R01) * exp(-kt).    (4.2)

Рейтинги постепенно выравниваются к предельному (среднему) значению 1/2*(R01 + R02).

3. Предельный случай (t -> оо) (оо - символ бесконечности). Экспонента исчезает и мы получаем:

R1(оо) = W12(R01 + R02).    (5.1)
R2(оо) = W21(R01 + R02).    (5.2)

Очевидно, что в пределе (независимо от начальных значений) отношение рейтингов должно равняться отношению статистических результатов (если игрок выигрывает в 2 раза чаще, то и его рейтинг должен быть в 2 раза больше).
Из выражений (5.1) и (5.2) мы получаем подтверждение данного инварианта (а, значит, еще одно подтверждение правильности исходной формулы):

R1(oo)/R2(oo) = W12/W21.   (6)

Ну и краткий вывод. Можем ли мы приведенным выше образом протестировать модель Эло? Другую модель?
Пока мне кажется маловероятным, что существует еще какая-то иная система справедливого расчета рейтингов, которая так же проста, физически прозрачна и логически согласована, как рассмотренная.

04/02/2008 00:05:28 Magin
Теперь становится понятным физический смысл е-рейтинга.
Рассмотрим снова формулу расчета приращения:

dRij = k * (Wij*Rj - Wji*Ri) (*dt)    (1)

Выше мы рассматривали матч между 2 игроками и выяснили, что для того, чтобы результат матча не изменил текущий рейтинг игроков, надо, чтобы отношение рейтингов совпадало с отношением результатов:

dR = 0, => Ri/Rj = Wij/Wji;

Теперь рассмотрим турнир из N участников. По аналогии с матчем можно также поставить вопрос о том, каковы должны быть начальные рейтинги игроков, чтобы результат турнира не изменил ни один рейтинг. Нахождение вектора значений таких рейтингов связано с решением системы линейных уравнений, получающейся из (1) накладыванием условия dRi = 0. Уравнения имеют вид (для каждого i):

Ri*SUMj(Wji) = SUMj(Wij*Rj);    (2) SUMj - это суммирование по j.

В уравнениях (2) нет никакого коэффициента релаксации k (поскольку нет динамики).
Решением будет вектор Ri (рейтинги всех игроков) с точностью до произвольного нормирующего множителя (поскольку физ. смысл есть только у отношения двух рейтингов). По аналогии с математикой (собственные вектора матрицы) данный набор рейтингов также можно назвать собственными рейтингами результатов турнира.

Такой расчет собственных рейтингов (е-рейтинг) удобно применять для начального присваивания рейтингов игрокам, рассматривая все сыгранные турниры и матчи как один большой турнир.

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

В качестве примера расчета собственных е-рейтингов приведем результаты Вейка 2008 (с точностью до произвольного множителя):

Владимир КРАМНИК    236.5
Теймур РАДЖАБОВ    299.7
Шахр. МАМЕДЬЯРОВ    191.7
Павел ЭЛЬЯНОВ    145.0
Майкл АДАМС    235.4
Левон АРОНЯН    354.6
Василий ИВАНЧУК    268.7
Юдит ПОЛГАР    195.6
Веселин ТОПАЛОВ    203.5
Борис ГЕЛЬФАНД    143.5
Петер ЛЕКО    282.2
Магнус КАРЛСЕН    332.9
Виши АНАНД    315.0
Люк ВАН ВЕЛИ    143.3
Tags: Рейтинг, Шахматы
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 1 comment