Блог пользователя WasylF

Автор WasylF, история, 9 лет назад, По-русски

Всем доброго времени суток!

Как известно, в ноябре 2015 были опубликованы формулы для рассчета рейтинга. Как мне кажется, наиболее неоднозначная часть — определение вероятности, что один участник выступит лучше другого:

А где вероятность — там мат. статистика. Уже прошло довольно много рейтинговых раундов на Codeforces, поэтому я задумал вычислить данную вероятность статистически. Было решено провести вычисления на раундах cf №200 — №350 (отдельно по дивизионам). Для этого я написал небольшую программку (иссходники). Закинул полученные результаты в Excel и получил такие графики:

для первого дивизиона

для второго дивизиона

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

но согласитесь, формула выглядит как-то не научно... поэтому легким движением руки превращаем ее в:

Теперь посмотрим, как это выглядит на графиках:

для первого дивизиона

для второго дивизиона

Кажется, так выглядит получше:)

Может возникнуть несколько вопросов, так что попробую ответить:)

1) Почему при нулевой разнице рейтинга статистическая вероятность победы не 50%?
Потому, что пользователи с одинаковыми рейтингами иногда занимают одинаковое место.

2) Почему во втором дивизионе аппроксимация хуже?
Скорее всего это из-за читеров, так как большое расхождение начинается при разнице рейтинга от 200.

P.S. Что побудило меня на эти исследования?

По результатам 3 раунд VK CUP неожиданно для меня понизился рейтинг. По этому, пользуясь открытыми формулами, быстренько посчитал сиды для всех участников контеста, у нашей команды вышел seed = 97.3936 а место — 96.. но причина падения — в этом раунде рейтинг считался не для всех сразу, а отдельно по дивизионам. Но я уже разогрелся и не захотел останавливаться на полученном:)

P.P.S. На всякий случай, отмечу, что я глубоко уважаю Михаила MikeMirzayanov Мирзаянова, Максима Zlobober Ахмедова, Глеба GlebsHP Евстропова и всех остальных причастных к созданию и функционированию Codeforces и у меня нет никаких претензий, только предложения по улучшению:)

  • Проголосовать: нравится
  • +269
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

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

Вопрос: К примеру, были введены новые формулы. Не изменится ли тогда статистика таким образом, что новые формулы будут под нее подходить уже не так хорошо?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    "Вопрос: К примеру, были введены новые формулы. Не изменится ли тогда статистика таким образом, что новые формулы будут под нее подходить уже не так хорошо?"

    я хотел проверить, но к сожалению у меня не вышло быстренько промоделировать обновление рейтинга по предложенным формулам. Попробую сделать это позже:)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Кажется, что при замене коэффициентов в формулах аппроксимирующая формула изменится соответственно. Т.е. вместо ~6 в основании степени появится коэффициент ~3.60 .

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been translated by WasylF (original revision, translated revision, compare)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by WasylF (previous revision, new revision, compare).

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Немного удивляет что в нуле получается что-то отличное от 0.5 (по измерениям). Как у вас ничьи обрабатываются?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    "Может возникнуть несколько вопросов, так что попробую ответить:)
    1) Почему при нулевой разнице рейтинга статистическая вероятность победы не 50%?
    Потому, что пользователи с одинаковыми рейтингами иногда занимают одинаковое место. "

    в случае ничьи считаю, что никто из двух соперников не победил другого. Если считать, что победили оба, тоже не выйдет 50%, будет больше. А как выбрать ОДНОГО победителя — не ясно:)

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      Небольшой пример. Если участники разделили 4-7 место, то для каждого из них rank=5.5 (а не 4 или 7). Если это исправить, то и соотношение Pi, j + Pj, i = 1 будет верным.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        в формуле никак не фигурирует rank, поэтому в случае его изменения (описанным образом) ничего не произойдет:) Важно лиш то, у кого rank меньше, а у кого больше.

                // probability J win I
                int ratingDiff = rating_I - rating_J;
                if (rank_J < rank_I) {
                    win[ratingDiff]++;
                }
        
                // probability I win J
                ratingDiff = rating_J - rating_I;
                if (rank_I < rank_J) {
                   win[ratingDiff]++;
                }
        
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          Нужно ещё добавить:

          if (rank_J == rank_I) {
              win[ratingDiff] += 0.5;
          }
          
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

I believe the formula should satisfy Pi, j + Pj, i = 1.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Кстати, в коде, который выкладывал MikeMirzayanov, как я понимаю, ничьи тоже не обрабатываются (всем указывается наименьший ранк, то есть все друг друга "победили")

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    по крайней мере API возвращает одинаковые ранки для участников с равным количеством очков. Например, по результатам ВК раунд 3 у 4 участников (2 команд) ранк 17.

    http://codeforces.me/api/contest.ratingChanges?contestId=643

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Ну то, что отображается такой ранк в результатах, это логично (это ровно то, что вкладывается в понятие "место")

      Вот при расчете рейтинга, не нужно ли его увеличить до (first + last) / 2.0 — это вопрос.

      (и кажется, что это логично сделать, если формулы несмещенные)

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        Забавно. На многих контестах по несколько сотен участников набирает 0. Если для них считать по first вместо (first + last) / 2.0, то получится, что рейтинг каждого из них уменьшится не так сильно, как должен (а в некоторых случаях должен даже увеличиться).

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Почему-бы не запретить ничью? Точнее сделать его очень невозможным, при равенстве очков сортировать по последнему АС в точности до секунды или по количеству посылок? UPD: не подумал про нули и отрицательные баллы.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Эти две формулы (+меры по борьбе с инфляцией) задают модель рейтингов на Codeforces. Если бы данная модель хорошо описывала участников соревнований, то у WasylF получилось бы именно такое распределение. результаты хорошо аппроксимируются формулой с константой 6^(1/400)=10^(1/514) вместо 10^(1/400), т.е. разность рейтинга между любыми участниками должна быть в 1.285 раз больше текущей. Возникает 2 соображения по этому поводу:

  1. Распределение рейтинга, соответствующее реальному уровню участников ещё не установилось окончательно, а так называемая "инфляция рейтинга" у наиболее сильных участников — это лишь процесс установления соответствующего распределения; меры по борьбе с инфляцией этот процесс сдерживают. В этом контексте, было бы любопытно посмотреть на эти же графики не интегрально за всё время, а в разные моменты времени с интервалом в несколько месяцев.

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я не разбирался с формулами, но есть ощущение что слишком трудно происходит переход между дивизионами. По крайней мере из 2 в 1. Может есть статистика ск-ко человек меняет дивизион за раунд?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Упомянул Zlobober не упомянув Gerald

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Gerald: "Это из-за того, что я уже не красный?"

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      RAD : "=((("

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Надо добавлять какие-нибудь бейджи / списки благодарности / краткие биографии для особо отличившихся членов сообщества! Я, например, даже не знал, что RAD был координатором.