Постановка задачи
Контекст: есть шахматный турнир с достаточно большим количеством игроков самого разного уровня.
Приняты решения: не разбивать игроков на чётко определённые группы (друг друга не знаем ещё, непонятно, кого куда помещать), не делать турнир «на вылет» (много новичков, им просто обидно будет вылететь после первой партии). Более-менее (вручную) справляемся с выбором партнёром примерно одинакового уровня.
Задача: сделать систему рейтинга по результатам турнира. Поскольку играем не «на вылет», финала нет. Учитывать количество очков несерьёзно из-за разношерстности игроков. То есть система рейтинга должна быть такой, что выигрыш у самого слабого игрока или проигрыш у самого сильного практически не должны влиять на наш рейтинг.
Теория
Выбрали алгоритм максимального правдоподобия: если определить вероятность каждого из возможных результатов партии как функцию рейтингов двух игроков, то можно посчитать вероятность каждого случившегося результата. А перемножив эти вероятности, получим вероятность реализации всего турнира. Затем нужно «всего лишь» максимизировать эту функцию нескольких переменных, чтобы получить наиболее вероятные рейтинги всех игроков.
Следующие 2 параграфа можно пропустить, если вас интересует только программерская часть. Их суть сводится к выбору и калибровке функции вероятности — программисту можно полагать эти функции данными. Математическим гикам же наверняка будет интересно покопаться в самих функциях.
Выбор функции
Поскольку никаких фундаментальных исследований мы проводить не собирались, функция вероятности была выбрана из соображения простоты реализации и минимального правдоподобия — нормальное распределение.
Пусть вероятность выигрыша игрока А у игрока Б будет пропорциональна функции распределения стандартного нормального распределения (извините за тавтологию) в точке разницы двух рейтингов. То есть при разнице рейтингов в 2 балла (2 среднеквадратичных отклонения) вероятность выиграть у более сильного игрока более 95%.
По калибровке: выбор среднего — единственно правильный, выбор среднеквадратичного отклонения не важен, т.к. он определяет лишь масштаб, можно все рейтинги домножить на произвольный коэффициент, что соответствует выбору другого среднеквадратичного отклонения. А больше параметров у нормального распределения нет.
Ничья и калибровка
Теперь нужно принять во внимание возможность ничьи, определить её вероятность как функцию двух рейтингов, и урезать предыдущую функцию на это значение.
Мы решили не заниматься сложным моделированием ничьи — учитывая наш уровень, мы удивились, что в турнире была одна ничья. Поэтому взяли всё то же нормальное распределение, и положили вероятность ничьи пропорциональной плотности распределения нормального распределения в точке разницы двух рейтингов. То есть вероятность ничьи не зависит от уровня игроков, только от разницы их уровней.
Калибровка здесь сложнее: во-первых, выбор среднеквадратичного отклонения (относительно среднеквадратичного отклонения предыдущего закона). Положили равными. Во-вторых, коэффициент пропорциональности, определяющий вероятность ничьи одинаково играющих игроков. Оценив эту вероятность в 20% мы посчитали коэффициент пропорциональности — 50.
Практическая реализация
Excel
Excel прекрасно справляется с поиском максимума функции — Solver. Проблема в том, что значение функции (вероятность реализации турнира) получается достаточно маленькой (при одинаковом рейтинге мы стартуем с вероятности 1E-120), и на таких значениях алгоритм остановки поиска у Excel глючит. По определению он останавливается не на максимуме, а «недалеко от», и вот этот критерий близости работал ужасно на наших данных — в зависимости от начального рейтинга, и даже от порядка игроков в таблице, результаты получались разными.
Решили перейти в систему, где у нас чуть больше возможностей влиять на правила подсчёта.
MatLab
У MatLab тоже есть функциональность для поиска максимума функции. Для большей стабильности метода, и чтобы лучше видеть, что происходит, мы решили максимизировать итеративным методом, переменная за переменной. То есть все рейтинги фиксируются кроме одного, функция вероятности становится функцией одной переменной, находим максимум, фиксируем этот рейтинг, освобождаем следующий и т.д. За несколько проходов функция максимизируется относительно всех переменных.
На практике десяти проходов оказалось достаточно.
Проверка стабильности
Сделали несколько тестов стабильности — если поставить другие начальные значения, если перемешать порядок игроков и т.д. Метод вполне стабильный. В итоге оставили два расчёта: игроки по алфавиту и игроки против алфавита. После десяти итераций результаты сравниваются, если два метода дают разный порядок двух рядом стоящих в таблице игроков, мы постулируем, что они разделили одно место в таблице.
Грабли
В качестве анекдота, опишу одни встреченные грабли. У MatLab функция поиска экстремума ищет не максимум, а минимум. Первая реакция — вместо максимума вероятности реализации мира мы будем искать минимум вероятности не реализации.
Проблема в том, что 1E-120 в обычной переменной держится без проблем, а вот 1 — 1E-120 уверенно округляется до единицы (120 знаков мантиссы не всякая переменная выдержит), и все расчёты идут насмарку.
Очевидное решение — перейти к отрицательной величине, и искать её минимум.
Недостаток модели
Самый большой недостаток модели — её сложно объяснить игрокам. Точнее, не саму даже модель, а тот факт, что ваш рейтинг может меняться в результате партий, в которых вы не участвовали.
Поясню примером: вы выиграли у игрока X с рейтингом в 1. На основании этого факта система вам присвоит рейтинг слегка выше 1, положим 1.1. Предположим, вы больше не играли в турнире, а X проиграл кучу партий, и его рейтинг упал до −1. Ваш рейтинг падает вместе с рейтингом X, поскольку это единственная ваша привязка.
Этот пример достаточно прост, на практике рейтинги пляшут сложно предсказуемым образом.
Теоретическое обоснование такого поведения (точнее отличия от привычного поведения) рейтинга состоит в следующем:
1. Если мы рассматриваем рейтинг как абсолютно точное представление силы игрока, и изменение рейтинга отражает изменение силы, то да, наш рейтинг может меняться только в результате наших игр, и формула расчёта должна принимать во внимание рейтинги наших соперников в момент нашего с ними матча.
2. Если же рассматривать рейтинг как несовершенное приближение к некоторому идеальному значению, а изменение рейтинга — как усовершенствование нашей оценки, принимающее во внимание новые данные, то рейтинг всех игроков может меняться как только становятся известны новые данные о нашем мире.
Из чего непосредственно следует сильное ограничение модели — они не принимает во внимание эволюцию игрока, абсолютный, «истинный» рейтинг полагается постоянным за всё время турнира.
