[Из песочницы] Модели Эло и ЭлоБета в снукере

На протяжении многих лет я слежу за снукером, как за спортом. В нем есть всё: гипнотизирующая красота интеллектуальной игры, элегантность ударов киём и психологическая напряжённость соревнования. Но есть одна вещь, которая мне не нравится — его рейтинговая система.

Её основной недостаток заключается в том, что она учитывает только факт турнирного достижения без учёта «сложности» матчей. Такого недостатка лишена модель Эло, которая следит за «силой» игроков и обновляет её в зависимости от результатов матчей и «силы» соперника. Однако, и она подходит не идеально: считается, что все матчи проходят в равных условиях, а в снукере они играются до определённого количества выигранных фреймов (партий). Для учёта этого факта, я рассмотрел другую модель, которую назвал ЭлоБета.

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

ppcrwkym_jz00_q75dwa4z_k0w0.jpeg

Текущий снукерный рейтинг основан на достижениях игрока в турнирах с их разной «весомостью». Давным давно учитывались только Чемпионаты Мира. После появления множества других соревнований была разработана таблица очков, которые игрок мог заработать, дойдя до определённой стадии турнира. Сейчас рейтинг имеет вид «скользящей» суммы призовых денег, которые игрок заработал в течение (приблизительно) крайних двух календарных лет.

У этой системы есть два главных преимущества: она простая (выигрывай много денег — поднимайся в рейтинге) и прогнозируемая (хочешь подняться на определённое место — выиграй определённое количество денег, при прочих равных). Проблема состоит в том, что при таком способе не учитывается сила (навык, форма) соперников. Обычным контр-аргументом является: «Если игрок достиг поздней стадии турнира, тогда он/она по определению является сильным игроком на текущий момент» («слабые игроки не выигрывают турниры»). Звучит достаточно убедительно. Однако в снукере, как и в любом спорте, должна учитываться роль случая: если игрок «слабее», то это не означает, что он/она никогда не может выиграть в матче против игрока «сильнее». Просто это случается реже, чем обратный сценарий. Именно здесь выходит на сцену модель Эло.

Идея модели Эло заключается в том, что каждый игрок ассоциируется с числовым рейтингом. Вводится предположение о том, что результат игры между двумя игроками может быть предсказан, основываясь на разнице их рейтингов: большие значения означают большую вероятность победы «сильного» (с более высоким рейтингом) игрока. Рейтинг Эло основан на текущей «силе», вычисленной на основании результатов матчей с другими игроками. Это избегает основного недостатка текущей официальной рейтинговой системы. Такой подход также позволяет обновлять рейтинг игрока в течение турнира, чтобы численно реагировать на его хорошее выступление.

Имея практический опыт с рейтингом Эло, мне кажется, что он должен хорошо показать себя в снукере. Однако, есть одно препятствие: он создан для соревнований с единым типом матча. Конечно, существуют вариации для учёта преимуществ домашнего поля в футболе и первого хода в шахматах (обе в виде добавления фиксированного количества рейтинговых очков игроку с преимуществом). В снукере же матчи играются в формате «best of N»: побеждает игрок, который первый выиграет $n = \frac{N + 1}{2}$ фреймов (партий). Мы также будем называть этот формат «до $n$ побед».

Интуитивно, победа в матче до 10 побед (финал серьёзного турнира) должна даваться сложнее «слабому» игроку, чем победа в матче до 4 побед (первый раунд текущих турниров Home Nations). Это учитывается в предложенной мной модели ЭлоБета.

Идея использования рейтинга Эло в снукере отнюдь не нова. Например, есть следующие работы:


  • Snooker Analyst использует «Эло подобную» (больше похожую на модель Брэдли–Терри) рейтинговую систему. Идея заключается в обновлении рейтинга основываясь на разнице между «реальным» и «ожидаемым» количествами выигранных фреймов. Такой подход вызывает вопросы. Конечно, большая разница в количестве фреймов, скорее всего, демонстрирует большую разницу в силе, однако изначально у игрока не стоит такой задачи. В снукере цель «всего лишь» выиграть матч, т.е. выиграть определённое количество фреймов раньше соперника.
  • Данное обсуждение на форуме с реализацией базовой модели Эло.
  • Это и это реальные применения в любительском снукере.
  • Возможно, существуют другие работы, которые я пропустил. Буду очень признателен за любую информацию по данной теме.

Данная статья предназначена для пользователей языка R, заинтересованных в изучении рейтинга Эло, и для любителей снукера. Все эксперименты написаны с идеей быть воспроизводимыми. Код спрятан под спойлерами, имеет комментарии и использует пакеты tidyverse, так что может быть сам по себе интересен для чтения пользователям R. Предполагается последовательное выполнение всего представленного кода. Одним файлом его можно найти здесь.

Статья организована следующим образом:


  • Раздел Модели описывает подходы Эло и ЭлоБета с реализацией в R.
  • Раздел Эксперимент описывает детали и мотивацию вычисления: какие данные и методология используются (и почему), а также какие получены результаты.
  • Раздел Изучение рейтингов ЭлоБета содержит результаты применения модели ЭлоБета к реальным снукерным данным. Он будет больше интересен любителям снукера.

Нам понадобится следующая инициализация.


Код инициализации
# Пакеты для манипуляций с данными
suppressPackageStartupMessages(library(dplyr))
library(tidyr)
library(purrr)
# Пакет для визуализации
library(ggplot2)
# Пакет для рейтингов
suppressPackageStartupMessages(library(comperank))

theme_set(theme_bw())

# Не должно понадобиться. Просто на всякий случай.
set.seed(20180703)

Обе модели основаны на следующих предположениях:


  1. Существует фиксированное множество игроков, которые должны быть проранжированы от «сильнейшего» (первое место) к «слабейшему» (последнее место).
  2. Ранжирование осуществляется ассоциированием игрока $i$ с числовым рейтингом $r_i$: число, отображающее «силу» игрока (большее значение — сильнее игрок).
  3. Чем больше разница рейтингов перед матчем, тем менее вероятна победа «слабого» игрока (с меньшим рейтингом).
  4. Рейтинги обновляются после каждого матча на основании его результата и рейтингов до него.
  5. Победа над соперником «сильнее» должна сопровождаться большим приростом рейтинга, чем победа над соперником «слабее». При поражении верно обратное.


Эло


Код модели Эло
#' @details Данная функция векторизована по всем своим аргументам. Использование
#' `...` критично для возможности передачи других аргументов в будущем.
#' 
#' @return Вероятность того, что игрок 1 (с рейтингом `rating1`) выиграет матч
#'   против игрока 2 (рейтинг `rating2`). Разница рейтингов напрямую влияет на
#'   результат.
elo_win_prob <- function(rating1, rating2, ksi = 400, ...) {
  norm_rating_diff <- (rating2 - rating1) / ksi

  1 / (1 + 10^norm_rating_diff)
}

#' @return Рейтинговая функция для модели Эло, которую можно передать в
#'   `comperank::add_iterative_ratings()`.
elo_fun_gen <- function(K, ksi = 400) {
  function(rating1, score1, rating2, score2) {
    comperank::elo(rating1, score1, rating2, score2, K = K, ksi = ksi)[1, ]
  }
}

Модель Эло обновляет рейтинги по следующей процедуре:

Замечания:


  • Как видно из формул обновления, сумма рейтингов всех учитываемых игроков не изменяется с течением времени: рейтинг увеличивается за счёт уменьшения рейтинга соперника
  • Игроки без сыгранных матчей ассоциируются с начальным рейтингом 0. Обычно используются величины 1500 или 1000, однако я не вижу в этом никакой другой причины, кроме как психологической. С учётом предыдущего замечания использование нуля означает, что сумма всех рейтингов всегда равняется нулю, что по-своему красиво.
  • Необходимо сыграть некоторое количество матчей для того, чтобы рейтинг отображал «силу» игрока. Это представляет проблему: новые добавленные игроки начинают с рейтингом 0, который наверняка не является наименьшим среди текущих игроков. Другими словами, «новички» считаются «сильнее», чем некоторые другие игроки. С этим можно стараться бороться внешними процедурами обновления рейтингов при вводе нового игрока.
  • Почему такой алгоритм имеет смысл? В случае равенства рейтингов $\delta$ всегда равняется $0.5 \cdot K$. Допустим, например, что $r_i = 0$ и $r_j = 400$. Это означает, что вероятность победы первого игрока равна $\frac{1}{1 + 10} \approx 0.0909$, т.е. он/она выиграет 1 матч из 11.


    • В случае победы он/она получит прирост в приблизительно $0.909 \cdot K$, что больше, чем в случае равенства рейтингов.
    • В случае поражения он/она получит уменьшение в приблизительно $0.0909 \cdot K$, что меньше, чем в случае равенства рейтингов.

    Это показывает, что модель Эло подчиняется пятому предположению: победа над соперником «сильнее» сопровождается большим приростом рейтинга, чем победа над соперником «слабее», и наоборот.


Конечно, у модели Эло есть свои (достаточно высокоуровневые) практические особенности. Однако, наиболее важной для нашего исследования является следующая: предполагается, что все матчи проводятся в равных условиях. Это означает, что не учитывается дистанция матча: победа в матче до 4 побед вознаграждается так же, как победа в матче до 10 побед. Здесь выходит на сцену модель ЭлоБета.


ЭлоБета


Код модели ЭлоБета
#' @details Данная функция векторизована по всем своим аргументам.
#' 
#' @return Вероятность того, что игрок 1 (с рейтингом `rating1`) выиграет матч
#'   против игрока 2 (рейтинг `rating2`). Матч играется до `frames_to_win`
#'   победных фреймов. Разница рейтингов напрямую влияет на вероятность победы
#'   в одном фрейме.
elobeta_win_prob <- function(rating1, rating2, frames_to_win, ksi = 400, ...) {
  prob_frame <- elo_win_prob(rating1 = rating1, rating2 = rating2, ksi = ksi)

  # Вероятность того, что первый игрок выиграет `frames_to_win` фреймов раньше
    # второго опираясь на вероятность первого игрока выиграть один фрейм
    # (`prob_frame`). Фреймы считаются независимыми.
  pbeta(prob_frame, frames_to_win, frames_to_win)
}

#' @return Результат матча в терминах победы первого игрока: 1 если он/она
#'   выиграл(а), 0.5 в случае ничьи и 0 если он/она проиграл(а).
get_match_result <- function(score1, score2) {
  # В снукере ничьи (обычно) не бывает, но это учитывает общий случай.
  near_score <- dplyr::near(score1, score2)

  dplyr::if_else(near_score, 0.5, as.numeric(score1 > score2))
}

#' @return Рейтинговая функция для модели ЭлоБета, которую можно передать в
#'   `add_iterative_ratings()`.
elobeta_fun_gen <- function(K, ksi = 400) {
  function(rating1, score1, rating2, score2) {
    prob_win <- elobeta_win_prob(
      rating1 = rating1, rating2 = rating2,
      frames_to_win = pmax(score1, score2), ksi = ksi
    )

    match_result <- get_match_result(score1, score2)
    delta <- K * (match_result - prob_win)

    c(rating1 + delta, rating2 - delta)
  }
}

В модели Эло разница рейтингов напрямую влияет на вероятность победы во всём матче. Главной идеей модели ЭлоБета является прямое влияние разницы рейтингов на вероятность победы в одном фрейме и явное вычисление вероятности игрока выиграть $n$ фреймов раньше соперника.

Остаётся вопрос: как вычислить такую вероятность? Оказывается, это одна из старейших задач в истории теории вероятностей и имеет своё название — задача о разделении ставок (Problem of points). Очень приятное изложение можно найти в этой статье. Используя её обозначения, искомая вероятность равняется:

$ P(n, n) = \sum\limits_{j = n}^{2n-1}{{{2n-1} \choose {j}} p^j (1-p)^{2n-1-j}} $

Здесь $P(n, n)$ — вероятность первого игрока выиграть матч до $n$ побед; $p$ — вероятность его/её победы в одном фрейме (у соперника вероятность $1-p$). При таком подходе предполагается, что результаты фрейма внутри матча не зависят друг от друга. Это может подвергаться сомнению, но является необходимым предположением для данной модели.

Существует ли более быстрый способ вычисления? Оказывается, ответ положительный. После нескольких часов преобразования формул, практических экспериментов и поисков в интернете я нашёл следующее свойство у регуляризованной неполной бета-функции $I_x(a, b)$. Подставив $m = k,~ n = 2k - 1$ в это свойство и заменив $k$ на $n$ получается $P(n, n) = I_p(n, n)$.

Также это является хорошей новостью для пользователей R, т.к. $I_p(n, n)$ может быть вычислено как pbeta(p, n, n). Замечание: общий случай вероятности победы в $n$ фреймах раньше, чем соперник выиграет $m$, также может быть вычислено как $I_p(n, m)$ и pbeta(p, n, m) соответственно. Это раскрывает богатые возможности по обновлению вероятности победы в течение матча.

Процедура обновления рейтингов в рамках модели ЭлоБета имеет следующий вид (при известных рейтингах $r_i$ и $r_j$, необходимом для победы количестве фреймов $n$ и результате матча $S$, как в модели Эло):


  • Вычисление вероятности победы первого игрока в одном фрейме: $p = Pr(r_i , r_j) = \frac{1}{1 + 10^{(r_j - r_i)/400}}$.
  • Вычисление вероятности победы этого игрока в матче: $Pr^{Beta}(r_i, r_j) = I_p(n, n)$. Например, если $p$ равно 0.4, то вероятность победы в матче до 4 побед падает до 0.29, а в «до 18 побед» — до 0.11.
  • Обновление рейтингов:

Замечание: т.к. разность рейтингов напрямую влияет на вероятность победы в одном фрейме, а не во всём матче, следует ожидать меньшее оптимальное значение коэффициента $K$: часть значения $\delta$ исходит от усиливающего эффекта $Pr^{Beta}(r_i, r_j)$.

Идея вычисления результата матча на основании вероятности победы в одном фрейме не очень нова. На этом сайте авторства François Labelle можно найти онлайн вычисление вероятности победы в «best of $N$» матче, наряду с другими функциями. Я был рад увидеть, что наши результаты вычислений совпадают. Однако, не смог найти никаких источников по введению такого подхода в процедуру обновления рейтингов Эло. Как и раньше, буду очень признателен за любую информацию по данной теме.

Я только смог найти эти статью и описание системы Эло на игровом сервере по нардам (FIBS). Есть также русскоязычный аналог. Здесь разная длительность матчей учитываются путём умножения разницы рейтингов на квадратный корень из дистанции матча. Однако, не похоже, чтобы это имело какого-то теоретического обоснования.

У эксперимента есть несколько целей. На основании данных о результатах снукерных матчей:


  • Определить лучшие значения коэффициента $K$ для обеих моделей.
  • Изучить устойчивость моделей в терминах точности прогнозной вероятности.
  • Изучить эффект использования «пригласительных» турниров на рейтинги.
  • Создать «справедливую» историю рейтингов за сезон 2017/18 для всех профессиональных игроков.


Данные


Код создания данных эксперимента
# Функция для разделения наблюдений по типам "train", "validation" и "test"
split_cases <- function(n, props = c(0.5, 0.25, 0.25)) {
  breaks <- n * cumsum(head(props, -1)) / sum(props)
  id_vec <- findInterval(seq_len(n), breaks, left.open = TRUE) + 1

  c("train", "validation", "test")[id_vec]
}

pro_players <- snooker_players %>% filter(status == "pro")

# Матчи только между профессионалами
pro_matches_all <- snooker_matches %>%
  # Используем только реально состоявшиеся матчи
  filter(!walkover1, !walkover2) %>%
  # Оставляем только матчи между профессионалами
  semi_join(y = pro_players, by = c(player1Id = "id")) %>%
  semi_join(y = pro_players, by = c(player2Id = "id")) %>%
  # Добавляем столбец 'season'
  left_join(
    y = snooker_events %>% select(id, season), by = c(eventId = "id")
  ) %>%
  # Обеспечиваем упорядоченность по времени окончания матча
  arrange(endDate) %>%
  # Подготавливаем к формату widecr
  transmute(
    game = seq_len(n()),
    player1 = player1Id, score1, player2 = player2Id, score2,
    matchId = id, endDate, eventId, season,
    # Вычисляем тип матча ("train", "validation" или "test") в пропорции
      # 50/25/25
    matchType = split_cases(n())
  ) %>%
  # Конвертируем в формат widecr
  as_widecr()

# Матчи только между профессионалами в непригласительных турнирах (убираются, в
  # основном, турниры Championship League).
pro_matches_off <- pro_matches_all %>%
  anti_join(
    y = snooker_events %>% filter(type == "Invitational"),
    by = c(eventId = "id")
  )

# Функция для подтверждение разбиения
get_split <- . %>% count(matchType) %>% mutate(share = n / sum(n))

# Это должно давать разбиение 50/25/25 (train/validation/test)
pro_matches_all %>% get_split()
## # A tibble: 3 x 3
##   matchType      n share
##          
## 1 test        1030 0.250
## 2 train       2059 0.5  
## 3 validation  1029 0.250

# Это даёт другое разбиение, потому что пригласительные турниры не распределены
  # равномерно в течение сезона. Однако, при таком подходе матчи разбиты на
  # основании тех же разделителей __по времени__, что и в `pro_matches_all`. Это
  # гарантирует, что матчи с одним типом представляют одинаковые __периоды во
  # времени__.
pro_matches_off %>% get_split()
## # A tibble: 3 x 3
##   matchType      n share
##          
## 1 test         820 0.225
## 2 train       1810 0.497
## 3 validation  1014 0.278

# Сетка для коэффициента K
k_grid <- 1:100

Мы будем использовать данные о снукере из пакета comperank. Оригинальным источником является сайт snooker.org. Результаты взяты из следующих матчей:


  • Матч сыгран в сезоне 2016/17 или 2017/18.
  • Матч является частью «профессионального» снукерного турнира, т.е.:
    • Имеет тип «Invitational» («Пригласительный»), «Qualifying» («Квалификационный») или «Ranking» («Рейтинговый»). Мы также будем отличать два набора матчей: «все матчи» (из всех данных турниров) и «официальные матчи» (без учёта пригласительных турниров). Для этого есть две причины:
      • В пригласительных турнирах не все игроки имеют возможность изменить свой рейтинг. Это не обязательно плохо в рамках моделей Эло и ЭлоБета, но имеет «оттенок несправедливости».
      • Есть убеждение, что игроки «относятся серьёзно» только к официальным рейтинговым матчам. Замечание: большинство «Invitational» турниров являются частью «Championship League», которая, как мне кажется, воспринимается большинством игроков не очень серьёзно в виде практики с возможностью заработать денег. Присутствие этих турниров может повлиять на рейтинг. Помимо «Championship League» имеются другие пригласительные турниры:»2016 China Championship», оба «Champion of Champions», оба «Masters»,»2017 Hong Kong Masters»,»2017 World Games»,»2017 Romanian Masters».
    • Описывает традиционный снукер (не 6 красных или Power Snooker) между индивидуальными игроками (не командами).
    • Оба пола могут принимать участие (не только мужчины или женщины).
    • Игроки всех возрастов могут принимать участие (не только сеньоры или «under 21»).
    • Это не «Shoot-Out», т.к. эти турниры по другому хранятся в базе snooker.org.
  • Матч действительно состоялся: его результат является следствием реальной игры с участием обоих игроков.
  • Матч проводится между двумя профессионалами. Список профессионалов взят за сезон 2017/18 (131 игрок). Это решение кажется наиболее противоречивым, т.к. удаление матчей с участием любителей «закрывает глаза» на поражения профессионалов от любителей. Это ведёт к несправедливому преимуществу данных игроков. Мне кажется, что такое решение необходимо для уменьшения инфляции рейтинга, которая произойдёт при учёте матчей с любителями. Другим подходом является изучение профессионалов и любителей вместе, но это кажется не обоснованным в рамках данного исследования. Поражение профессионала любителю считается потерей возможности повысить рейтинг.

Конечное количество используемых матчей равно 4118 для «всех матчей» и 3644 для «официальных матчей» (62.9 и 55.6 на одного игрока соответственно).


Методология


Код функций эксперимента
#' @param matches Объект класса `longcr` или `widecr` со столбцом `matchType`
#'   (тип матча для эксперимента: "train", "validation" или "test").
#' @param test_type Тип матчей для вычисления качества модели. Для корректности
#'   эксперимента все матчи этого типа должны были проводиться позже всех других
#'   ("разогревочных") матчей. Это означает, что у них должны быть бОльшие
#'   значения столбца `game`.
#' @param k_vec Вектор коэффициентов K для вычисления качества модели.
#' @param rate_fun_gen Функция, которая при передаче коэффициента K возвращает
#'   рейтинговую функцию для передачи в `add_iterative_ratings()`.
#' @param get_win_prob Функция для вычисления вероятности победы на основании
#'   рейтингов игроков (`rating1`, `rating2`) и количества фреймов, необходимого
#'   для победы в матче (`frames_to_win`). __Замечание__: она должна быть
#'   векторизована по всем своим аргументам.
#' @param initial_ratings Начальные рейтинги в формате для
#'   `add_iterative_ratings()`.
#' 
#' @details Данная функция вычисляет:
#' - Историю итеративных рейтингов после упорядочивания `matches` по возрастанию
#' столбца `game`.
#' - Для матчей с типом `test_type`:
#'     - Вероятность победы игрока 1.
#'     - Результат матча в терминах победы первого игрока: 1 если он/она
#'     выиграл(а), 0.5 в случае ничьи и 0 если он/она проиграл(а).
#' - Качество в виде RMSE: квадратный корень из средней квадратичной ошибки, где
#' "ошибка" - разность между прогнозной вероятностью и результатом матча.
#' 
#' @return Tibble со столбцами 'k' для коэффициента K и 'goodness' для
#'   величины качества RMSE.
compute_goodness <- function(matches, test_type, k_vec, rate_fun_gen,
                             get_win_prob, initial_ratings = 0) {
  cat("\n")
  map_dfr(k_vec, function(cur_k) {
    # Отслеживание хода выполнения
    cat(cur_k, " ")
    matches %>%
      arrange(game) %>%
      add_iterative_ratings(
        rate_fun = rate_fun_gen(cur_k), initial_ratings = initial_ratings
      ) %>%
      left_join(y = matches %>% select(game, matchType), by = "game") %>%
      filter(matchType %in% test_type) %>%
      mutate(
        # Количество фреймов для победы в матче
        framesToWin = pmax(score1, score2),
        # Вероятность победы игрока 1 в матче до `framesToWin` побед
        winProb = get_win_prob(
          rating1 = rating1Before, rating2 = rating2Before,
          frames_to_win = framesToWin
        ),
        result = get_match_result(score1, score2),
        squareError = (result - winProb)^2
      ) %>%
      summarise(goodness = sqrt(mean(squareError)))
  }) %>%
    mutate(k = k_vec) %>%
    select(k, goodness)
}

#' Обёртка для `compute_goodness()` для использования с матрицей эксперимента
compute_goodness_wrap <- function(matches_name, test_type, k_vec,
                                  rate_fun_gen_name, win_prob_fun_name,
                                  initial_ratings = 0) {
  matches_tbl <- get(matches_name)
  rate_fun_gen <- get(rate_fun_gen_name)
  get_win_prob <- get(win_prob_fun_name)

  compute_goodness(
    matches_tbl, test_type, k_vec, rate_fun_gen, get_win_prob, initial_ratings
  )
}

#' Функция для осуществления эксперимента
#' 
#' @param test_type Вектор значений `test_type` (тип теста) для
#'   `compute_goodness()`.
#' @param rating_type Имена рейтинговых моделей (типы рейтинга).
#' @param data_type Суффиксы типов данных.
#' @param k_vec,initial_ratings Величины для `compute_goodness()`.
#' 
#' @details Данная функция генерирует матрицу эксперимента и вычисляет несколько
#' значений качества моделей для разных комбинаций типов рейтинга и данных. Для
#' того, чтобы она работала, в глобальном окружении необходимо наличие
#' переменных по следующими комбинациями имён:
#' - "pro_matches_" + `<типы теста>` + `<типы данных>` для результатов матчей.
#' - `<типы рейтинга>` + "_fun_gen" для генераторов рейтинговых функций.
#' - `<типы рейтинга>` + "_win_prob" для функций, вычисляющий вероятность
#' победы.
#' 
#' @return Tibble со следующими столбцами:
#' - __testType__  : Идентификатор типа теста.
#' - __ratingType__  : Идентификатор типа рейтинга.
#' - __dataType__  : Идентификатор типа данных.
#' - __k__  : Значение коэффициента K.
#' - __goodness__  : Значение качества модели.
do_experiment <- function(test_type = c("validation", "test"),
                          rating_type = c("elo", "elobeta"),
                          data_type = c("all", "off"),
                          k_vec = k_grid,
                          initial_ratings = 0) {
  crossing(
    testType = test_type, ratingType = rating_type, dataType = data_type
  ) %>%
    mutate(
      dataName = paste0("pro_matches_", testType, "_", dataType),
      kVec = rep(list(k_vec), n()),
      rateFunGenName = paste0(ratingType, "_fun_gen"),
      winProbFunName = paste0(ratingType, "_win_prob"),
      initialRatings = rep(list(initial_ratings), n()),
      experimentData = pmap(
        list(dataName, testType, kVec,
             rateFunGenName, winProbFunName, initialRatings),
        compute_goodness_wrap
      )
    ) %>%
    unnest(experimentData) %>%
    select(testType, ratingType, dataType, k, goodness)
}

Для нахождения «оптимального» значения $K$ будем использовать равномерную решётку $K = 1, 2, ..., 100$. Учёт больших значений кажется не обоснованным, что подтверждается экспериментом. Используется следующая процедура:


  • Для каждого $K$:
    • Вычисление истории итеративных рейтингов определённой модели на основании определённого набора данных. Это означает, что на выходе будут известны рейтинги игроков перед каждым матчем. Это сделано с помощью функции add_iterative_ratings() из пакета comperank. Такой подход описывает «онлайн рейтинги», т.е. обновление после каждого матча.
    • На основании данных, начиная с определённого (отстающего от начала) момента времени, вычисление качества модели. Будем использовать RMSE (квадратный корень из средней квадратичной ошибки) между результатом матча и вероятностью победы первого игрока (вычисленной на основании модели). Другими словами, $RMSE = \sqrt{\frac{1}{|T|} \sum\limits_{t \in T}{(S_t - P_t)^2}}$, где $T$ — индексы используемых матчей, $|T|$ — количество этих матчей, $S_t$ — результат матча для первого игрока, $P_t$ — вероятность победы первого игрока в матче (вычисленной на основании модели). Удаление матчей с начала данных необходимо для того, чтобы рейтинги успели отойти от начальных и начали отображать «текущую силу» игрока.
  • Величина $K$ с устойчивым минимальным RMSE объявляется оптимальной. Здесь под «устойчивым» понимается, что относительно малое значение RMSE присутствует в некоторой окрестности оптимального $K$ (будет определено не очень строго путём рассматривания графиков). Значения меньше 0.5 (величина для «модели» с постоянным прогнозом 0.5) будет считаться успехом.

Так как одной из целей является изучение стабильности моделей, данные будут разбиты на три подмножества: «train» (обучающее), «validation» (валидационное) и «test» (тестовое). Они отсортированы по времени, т.е. любой матч из «train»/«validation» имеет время окончания раньше, чем любой матч из «validation»/«test». Я решил разбить данные в пропорции 50/25/25 для «всех матчей». Разбиение «официальных матчей» делается путём удаления из «всех матчей» пригласительных турниров. Это даёт не совсем желаемую пропорцию: 49.7/27.8/22.5. Однако, такой подход обеспечивает, что матчи одного типа представляют одинаковые периоды во времени.

Эксперимент будет проведён для всех комбинаций следующих переменных:


  • Тип модели: Эло или ЭлоБета.
  • Тип данных: «Все матчи» или «официальные матчи» (они же «офиц. матчи»).
  • Тип эксперимента: «Валидационный» (матчи «validation» используются для вычисления RMSE после «разогрева» на «train» матчах) и «Тестовый» (матчи «test» используются для вычисления RMSE после «разогрева» на «train» и «validation» матчах).


Результаты


Код проведения эксперимента
pro_matches_validation_all <- pro_matches_all %>% filter(matchType != "test")
pro_matches_validation_off <- pro_matches_off %>% filter(matchType != "test")
pro_matches_test_all <- pro_matches_all
pro_matches_test_off <- pro_matches_off
# Выполнение занимает существенное время
experiment_tbl <- do_experiment()


Код отображения результатов эксперимента
plot_data <- experiment_tbl %>%
  unite(group, ratingType, dataType) %>%
  mutate(
    testType = recode(
      testType, validation = "Валидационный", test = "Тестовый"
    ),
    groupName = recode(
      group, elo_all = "Эло, все матчи", elo_off = "Эло, офиц. матчи",
      elobeta_all = "ЭлоБета, все матчи",
      elobeta_off = "ЭлоБета, офиц. матчи"
    ),
    # Фиксация предпочтительного порядка
    groupName = factor(groupName, levels = unique(groupName))
  )

compute_optimal_k <- . %>% group_by(testType, groupName) %>%
  slice(which.min(goodness)) %>%
  ungroup()
compute_k_labels <- . %>% compute_optimal_k() %>%
  mutate(label = paste0("K = ", k)) %>%
  group_by(groupName) %>%
  # Если оптимальное K в рамках одной панели находится справа от своей пары,
    # её метке необходимо небольшое смещение вправо. Если слева - полное и
    # небольшое смещение влево.
  mutate(hjust = - (k == max(k)) * 1.1 + 1.05) %>%
  ungroup()

plot_experiment_results <- function(results_tbl) {
  ggplot(results_tbl) +
    geom_hline(
      yintercept = 0.5, colour = "#AA5555", size = 0.5, linetype = "dotted"
    ) +
    geom_line(aes(k, goodness, colour = testType)) +
    geom_vline(
      data = compute_optimal_k,
      mapping = aes(xintercept = k, colour = testType),
      linetype = "dashed", show.legend = FALSE
    ) +
    geom_text(
      data = compute_k_labels,
      mapping = aes(k, Inf, label = label, hjust = hjust),
      vjust = 1.2
    ) +
    facet_wrap(~ groupName) +
    scale_colour_manual(
      values = c(`Валидационный` = "#377EB8", `Тестовый` = "#FF7F00"),
      guide = guide_legend(title = "Эксперимент", override.aes = list(size = 4))
    ) +
    labs(
      x = "Коэффициент K", y = "Качество модели (RMSE)",
      title = "Лучшие значения качества моделей Эло и ЭлоБета почти равны",
      subtitle = paste0(
        'Использование официальных матчей (без пригласительных турниров) даёт ',
        'более устойчивые результаты.\n',
        'Оптимальные значения K из тестового эксперимента (с более длительным ',
        '"разогревом") меньше, чем из валидационного.'
      )
    ) +
    theme(title = element_text(size = 13), strip.text = element_text(size = 12))
}

plot_experiment_results(plot_data)

unox40-c1cmbx_9tm4zc7kqzqoc.pngКликабельно

По результатам эксперимента можно сделать следующие выводы:


  • Как и ожидалось, оптимальные значения $K$ для ЭлоБета меньше, чем для Эло.
  • Использование официальных матчей даёт более устойчивые результаты (результаты «Валидационного» и «Тестового» эксперимента отличаются меньше). Это не должно восприниматься как довод в сторону того, что профессионалы играют в пригласительных турнирах не серьёзно. Скорее это из-за качества результатов матчей из турнира «Championship League»: он имеет слабо предсказуемый формат до 3 побед и очень плотный график.
  • Изменение RMSE для оптимального $K$ не сильно существенное. Другими словами, RMSE не изменяется значительно после вычисления оптимального $K$ в «Валидационном» эксперименте и применении его в «Тестовом». Более того, для «официальных матчей» качество даже улучшилось.
  • Все оптимальные значения $K$ из тестового эксперимента (с более длительным «разогревом») меньше, чем из валидационного эксперимента. Это может как как следствием более длительного «разогрева», так и просто особенностью конкретных данных.
  • Лучшие значения RMSE для обеих моделей на одних данных очень близки. Все устойчивы и меньше 0.5. Данные для тестового эксперимента представлены ниже.


Группа Оптимальное K RMSE
Эло, все матчи 24 0.465
Эло, офиц. матчи 29 0.455
ЭлоБета, все матчи 10 0.462
ЭлоБета, офиц. матчи 11 0.453

Т.к. качество не сильно отличается, можно округлить оптимальные $K$ из «официальных матчей» (они демонстрируют большую устойчивость) до 5: для модели Эло это 30, для ЭлоБета — 10.

На основании этих результатов я склонен заключить, что модели Эло с $K = 30$ и ЭлоБета с $K = 10$ могут найти полезное применение в анализе официальных снукерных матчей. Однако, модель ЭлоБета учитывает различный формат матчей до $n$ побед, поэтому из двух следует предпочесть её.

Следующие результаты были вычислены используя «официальные матчи» с моделью ЭлоБета ($K = 10$). Все возможные выводы не следует рассматривать как личные по отношению какому-либо игроку.


Топ-16 на конец сезона 2017/18


Код для топ-16 сезона 2017/18
# Вспомогательная функция
gather_to_longcr <- function(tbl) {
  bind_rows(
    tbl %>% select(-matches("2")) %>% rename_all(funs(gsub("1", "", .))),
    tbl %>% select(-matches("1")) %>% rename_all(funs(gsub("2", "", .)))
  ) %>%
    arrange(game)
}

# Извлечение лучшего значения коэффициента K
best_k <- experiment_tbl %>%
  filter(testType == "test", ratingType == "elobeta", dataType == "off") %>%
  slice(which.min(goodness)) %>%
  pull(k)

  #!!! Округляет к "красивому" числу, т.к. это не сильно влияет на качество !!!
best_k <- round(best_k / 5) * 5

# Вычисление рейтингов на момент окончания данных
elobeta_ratings <- rate_iterative(
  pro_matches_test_off, elobeta_fun_gen(best_k), initial_ratings = 0
) %>%
  rename(ratingEloBeta = rating_iterative) %>%
  arrange(desc(ratingEloBeta)) %>%
  left_join(
    y = snooker_players %>% select(id, playerName = name), by = c(player = "id")
  ) %>%
  mutate(rankEloBeta = order(ratingEloBeta, decreasing = TRUE)) %>%
  select(player, playerName, ratingEloBeta, rankEloBeta)

elobeta_top16 <- elobeta_ratings %>%
  filter(rankEloBeta <= 16) %>%
  mutate(
    rankChr = formatC(rankEloBeta, width = 2, format = "d", flag = "0"),
    ratingEloBeta = round(ratingEloBeta, 1)
  )

official_ratings <- tibble(
  player = c(
         5,      1,    237,      17,     12,     16,    224,     30,
        68,    154,     97,      39,     85,      2,    202,   1260
  ),
  rankOff = c(
         2,      3,      4,       1,      5,      7,      6,     13,
        16,     10,      8,       9,     26,     17,     12,     23
  ),
  ratingOff = c(
    905750, 878750, 751525, 1315275, 660250, 543225, 590525, 324587,
    303862, 356125, 453875,  416250, 180862, 291025, 332450, 215125
  )
)

Топ-16 по модели ЭлоБета на конец сезона 2017/18 имеет следующий вид (официальные данные также взяты с сайта snooker.org):


Игрок ЭлоБета место ЭлоБета рейтинг Офиц. место Офиц. рейтинг Подъём места по ЭлоБета
Ronnie O’Sullivan© Habrahabr.ru