Эло рейтинг в ориентировании. Часть 3.

Я, вообще то, планировал уложить все в пару частей, но мысли о том, что еще написать, все появляются. Правда, спамить на гостевой OBelarus я уже перестану. Так что, если еще интересно, следите за обновлениями тут.

Хотелось все формулы и алгоритмы второй части сопроводить примерном из реальной жизни, так что очередной тур BNTU Open прошел как раз вовремя (конечно, можно было привести пример прошлогоднего уже расчитанного соревнования, но это не так свежо и злободневно получится). Для удобства (моего), результаты я сложу в отдельный документ, а дальше сопровожу их своими комментариями.

Рассчет рейтинга

Результаты разделены по вкладкам на мужские и женские, общие и спринтерские. Колонки - имя, рейтинг до старта, изменение рейтинга, рейтинг после старта, суммарный коэфициент до старта (об этом я писал в прошлой части) и место (0 - снят). Тут важно напомнить, что спортсмены с суммарным коэфициентом меньшим или равным 200 считаются новичками. Для новичков, напомню, коэфициент старта удвоен (20 вместо 10 в нашем случае), фактически удваивая величину изменения (в реальности увеличение даже больше, поскольку для новичков другие новички считаются с обычным весом).

Теперь к самим результатам подсчета (они отсортированы по величине изменения рейтинга). В общем рейтинге у мужчин Томашев Олег и Чучва Дмитрий получили максимально возможные для них 20 баллов. Большая группа новичков заработала более 10 баллов, для этого хватило даже 25 места (что не так удивительно, учитывая 77 участников старта). Из спортсменов с устоявшимся рейтингом только Марков Виталий достиг лимита в 10 баллов. Интересно посмотреть глубже, где первое и второе места старта, Стрельцов Василий и Солодкин Сергей, они же наиболее высокорейтинговые спортсмены старта набрали, соответственно всего 2 и 1 балл, что является довольно характерным примеров работы рейтинга. Думаю, введение подобного рода массовых стартов в рейтинг должно иметь очень позитивный эффект. Не сильно влияя на рейтинг лидеров, оно позволит намного быстрее выставить соответствующий действительности рейтинг для остальных, заодно добавив в рейтинг представителей разных возрастов, дав им возможность соревноваться между собой.

Дальше вниз таблицы все достаточно просто: учитывая примерное равенство рейтинга у большинства спортсменов в этой части, изменения примерно соответствуют занятым местам. Я говорил раньше, что в рейтинг иностранные спортсмены включены не были, но это все определялось исключительно протоколами, в результате правило было довольно расплывчатым. Подумав, я решил убрать ограничения - все спортсмены, принимающие участие в старте будут рассчитаны (прошедшие старты я уже вносить по новой в базу не буду, естественно).

У женшин картина несколько иная. Тут можно заметить, что Кунцевич Наталья, заняв четвертое место из 29 участниц, уменьшила свой рейтинг (правда всего на 0.1 балла) - исходя из ее высокого рейтинга, такой результат был ниже ожидаемого. А вот Лебедева Елена, заняв 23-е место, свой рейтинг улучшила. Вторая по рейтингу, Волкова Яна, свой последний старт в качестве новичка (ее суммарный коэфициент на начало старта был равен 200) прошла неудачно и потеряла 20 баллов.

В спринтерском рейтинге картина похожая, но у некоторых спортсменов спринтерский и общий рейтинг различались настолько сильно, что и результаты получились разными. Например Громов Алексей потерял 1 балл в общем рейтинге, но поднялся сразу на 6 баллов в общем. Спринтерский рейтинг Маркова Виталия был значительно выше, соответственно, и прогресс составил не 10, а 6 баллов.

В целом, надеюсь, этот пример для понимания общей схемы работы будет полезен. Есть еще некоторые задумки, про которые я планирую написать позже. В перспективе хочется выложить все в открытый доступ, с возможностью для каждого посмотреть и покликать. Там и всяких графических фишек на сайте можно будет добавить, что-то вроде такого:

Эло рейтинг в ориентировании. А так можно? Часть 2.

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

Для тех, кто остался, я продолжу. Первым в алгоритме подсчета идет определение вероятности победы (или ожидаемого результата) спортсменов исходя из разности их рейтинга. Здесь я использовал наиболее классический подход, где результат спортсмена считается нормально (Гауссово) распределенным относительно среднего уровня (за который принимается текущий уровень). При рейтингах R1 и R2, ожидаемые результаты вычисляются по формулам:

E1 = 1 / (1 + 10^((R2 - R1) / D))

E2 = 1 / (1 + 10^((R1 - R2) / D))

Важным свойством является то, что E1 + E2 = 1 (то есть суммарная вероятность победы обоих спортсменов равняется 100%). D - коэфициент, который и будет определять, как разница в рейтинге соответствует вероятности победы, но важно только его отношение к величинам коэфициентов стартов (о которых дальше). Я принял D = 300. Подставив это значение в формулы, получим, что разница в 100 очков рейтинга соответствует вероятностям 68% / 32%, 200 ~ 82% / 18%, 300 ~ 91% / 9%, 400 ~ 95% / 5%. Наличие физического смысла я считаю одной из приятных мелочей Эло рейтинга, ведь речь идет не только о функциях подсчета, но и о том, что, в конечном итоге, значат сами числа рейтинга спортсменов. Хотя, с практической точки зрения, наличие такой обратной связи может быть не так и велико.

Идем дальше подсчитав ожидаемые результаты E и сравним с ними реальные результаты С (0, 1 или 0.5) получаем некое значение B = С - E. Как я писал в первой части, для каждого спортсмена мы проводим сравнение с каждым из соперников, то есть для каждого спортсмена мы имеем N-1 значений B (где N - число участников старта). Тут возникает вопрос: что с этим всем делать дальше? Вариантов несколько:

1. Взять среднее значение.
2. Взять сумму.
3. Что-то посередине между 1 и 2

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

Вt = Sum(B) * log(4, N) / (N - 1)

То есть среднее значение умножается на логарифм количества участников по основанию 4. Четыре означает, что множитель будет равен 3, при числе участников 64, что на данный момент близко к практическому максимуму.

Остается умножить значение Вt на коэфициент значимости старта K и изменение рейтинга готово. Правда перед этим я ограничиваю -1 <= Вt <= 1 и ставлю его -1 или 1 его оно из этих границ вылезает. Это тоже одна из опций, означающая, что модуль изменения рейтинга никогда не может быть больше коэфициента старта. Основная цель - избежать резких падений при сходах высокорейтинговых спортсменов на старте с большим количеством участников. Теперь о коэфициентах стартов, соревнования я разбил на 4 уровня:

1. K = 40. Мастерские старты и старты WRE.
2. К = 30. Старты кубка БФО.
3. К = 20. Чемпионаты и кубки областей, старты на соревнованиях с этапами кубка БФО.
4. К = 10. Все остальное

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

Для подсчета рейтинга я собрал старты последних 5 лет, элитные группы у мужчин и женщин. В теории можно пойти дальше и расчитывать в один рейтинг все участвующие группы, но есть опасение, что пересечений между участниками разных групп будет слишком мало для стабилизации рейтинга и возможности достоверно отображать, например, разницу в уровне М16 и М60. Женские и мужские рейтинги, естественно, сичтаются отдельно и соотношение чисел между ними не говорит ни о чем. Источником служили протоколы на OBelarus.net и Orient.by, за исключением массовых открытых стартов вроде ЗС было посчитано практически все (хотя и ЗС не является каким-то ограничением, скорее экономией времени, при внесении текущего рейтинга я планирую учитывать все старты по максимуму, так в последнюю версию уже попали туры BNTU Open). Из расчета исключались спортсмены с пометкой в/к и иностранные спортсмены, хотя в отношении некоторых спортсменов мнения протоколов о гражданстве не сходились (Ласкаржевский Владислав - самый яркий пример), тут, в целях экономии времени, я просто доверял протоколам. Всего вышло около 540 стартов (считая отдельно мужчин и женщин). Начальный рейтинг каждого спортсмена устанавливается в 1500.

Само написание подсчет рейтинга уместилось в 15 минут работы и 20 строчек кода, что идет в слабое сравнение со всей подготовительной работой. Осталось нажать кнопку и получить примерно следующее (в списке присутствуют спортсмены, пробежавшие за последний год стартов с суммарным коэфициентом не менее 60, поля таблицы после рейтинга: старты за год, прогресс за год и суммарный коэфициент за год):

Пожалуй, вышло что-то похожее на правду. Что еще мне хотелось добавить - это часто используемые в рейтингах Эло особые правила для новичков. В нашем случае они будут выглядеть так:

1. Для спортсмена новичка все коэфициенты К удвоены.
2. Для спортсмена неновичка, при сравнении с новичком при расчете рейтинга, результат сравнения учитывается с весом 0.5 при расчете среднего значения (соответственно и в формуле Вt = Sum(B) * log(4, N) / (N - 1), N - это взвешенное количество участников).

Остается еще решить, кого считать новичком. Учитывая разные коэфициенты стартов, простое количество будет работать не слишком хорошо. Я ввел подсчет суммы коэфициентов стартов, спортсмен, у которого эта сумма <= 200 - новичок (с точки зрения системы его рейтинг вызывает меньше доверия и его нужно побыстрее привести к нужным значениям).

Говоря о новичках, стоит понимать, что рейтинг стартует с начала 2014 года, все спортсмены на отметке 1500. Происходит некий "большой взрыв" - спортсмены резко начинают разлетаться в разные стороны исходя из своих результатов. Дальше эта растягивание рейтинга должно начать быстро замедляться, рано или поздно рейтинг должен прийти к некоему балансу, соответствующему реальной силе спортсменов, но вопрос, как понять, что рейтинг уже прошел фазу инициализации, остается открытым.

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

Рейтинг растянулся, при этом не пережив слишком существенных изменений - это достаточно позитивно. Тут мне захотелось проверить, насколько время начала рейтинга влияет на его значение сейчас, и я добавил еще 2 года стартов, на этот раз ограничившись стартами кубка БФО. Результат (полные таблицы ниже) - не слишком-то влияет, просто рейтинг еще слегка растянулся. В целом - это то что от рейтинга и ожидалось - давние результаты должны быть практически незаметны сейчас, но тут получить ожидаемый результат приятно.

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

Рейтинг

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

Эло рейтинг в ориентировании. А так можно? Часть 1.

Перед тем как отвечать на вопрос заголовка, стоит вкратце рассказать об Эло рейтинге. Эло рейтинг был разработан Арпадом Эло для подсчета рейтинга шахматистов в середине XX века, вскоре он стал официальным рейтингов международной шахматной федерации. В настоящий момент рейтинг Эло является официальным и в других, подобных шахматам, видах спорта, а неофициально подсчет ведется уже практически для любого вида спорта с матчами 1 на 1 (включая и командные). Вот, например, футбол или теннис. В футболе, кстати, и официальный рейтинг ФИФА недавно перешел на такую систему. При этом, говоря о рейтинге Эло, я имею в виду именно общие принципы подсчета, в каждом конкретном случае сами формулы подсчета могут отличатся.

Теперь, собственно, об этих принципах (пока по-прежнему о матчах 1 на 1).

Основной: рейтинг соперников на начало матча и результат матча определяют новый рейтинг соперников; рейтинг - это всегда просто одно число, он не хранит истории и не считается ни за какой конкретный период; рейтинг - показатель силы спорстмена на данный момент времени. Можно сравнить это с циклической системой (например в теннисе), где рейтинг - это сумма очков за последний год, по достижении года эти очки из рейтинга сгорают.

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

Еще один принцип Эло заключается в механизме подсчета нового рейтинга на основе изначальных рейтингов и результата. Попробую объяснить это не слишком загружая математикой. Определяющим являются не сами рейтинги спортсменов, а их разница. Предположим встречаются спортсмены с рейтингами R1 = 1400 и R2 = 1600. Рейтинг Эло исходя из своей формулы определяет вероятности победы каждого из спортсменов (тут уже подключается теория вероятностей, скажу только что существует несколько разных используемых вариантов определения вероятности). Пусть, для примера, в нашем рейтинге разница в 200 очков соответствует вероятности победы 25% на 75%. Соответственно, ожидаемый результат E1 = 0.25, E2 = 0.75. Дальше смотрим на реальный результат C: победа = 1, поражение = 0, ничья = 0.5. Допустим, спортсмен 1, несмотря на разницу в рейтинге, добился победы. Изменение рейтинга - разность между реальным и ожидаемым результатом. B1 = C1 - E1 = 1 - 0.25 = 0.75. У проигравшего спортсмена, соответственно, B2 = C2 - E2 = 0 - 0.75 = -0.75. Остается умножить результат на коэфициент старта K, обычно они различаются для стартов разного уровня - это уже правила каждого конкретного рейтинга. Пусть, в нашем случае K = 30. Тогда в результате R1 = 1400 + 0.75 * 30 = 1422.5, R2 = 1577.5

Теперь можно вернуться к ориентированию. Эло хорошо работает для матчей 1 на 1, но как переложить его на соревнования с несколькими спортсменами? Тут будет работать следующий принцип: для каждого спортсмена результат разбивается на отдельные матчи против всех остальных участников (то есть на старте с 30 участниками таких матчей у каждого будет 29). Изменение рейтинга считается по принципу, описанному выше, дальше останется только определить, как скомбинировать эти отдельные результаты в общий итог старта для спортсмена. Вариантами могут быть: среднее значение, сумма изменений либо какая-то более сложная формула. Об этом я напишу уже во второй части. Пока же нужно собрать в базу результаты соревнований последних лет - это более трудоемкая задача. Имея базу, можно будет экспериментировать.

Несколько картинок, для привлечения внимания:

А подробнее о результатах экспериментов - уже во второй части.