Шахматный рейтинг

[green_fr]

На работе устроили чемпионат по шахматам. Играют самые разные люди — от тех, кто выигрывает у меня, до тех, кто только в начале турнира узнал правила игры. Турнир медленный и ленивый, то есть все со всеми не сыграют. Да и незачем — слишком разный уровень. Но и на группы «новички» — «продвинутые» тоже не хочется разделяться.

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

И тут я вспомнил про старую статью в Pour la science о ретроактивных рейтингах.
К слову о пользе ЖЖ — тут же нашёл нужный номер журнала и нужную статью, перечитал и сел за Excel.

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

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

Написал вероятность каждого матча, перемножил (1E-120), запустил Excel Solver искать максимум. Максимум находится мгновенно, но его положение (то есть рейтинги) сильно зависит от изначальных рейтингов, порядка игроков и т.п. — а не должны бы. Покопавшись, понял (показалось), что Excel очень плохо работает с критерием остановки поиска. На малых числах он в какой-то момент решает, что он уже нашёл максимум, потому что абсолютное приращение мало.

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

Мрачно посмотрел на возможности автоматизации Excel Solver через VBA... Пересел за MatLab.

У MatLab не оказалось (не нашёл) функции поиска максимума, есть только поиск минимума. Сначала сделал глупость, перейдя от вероятности реализации мира p к вероятности не реализации мира 1-p. Очевидно, точность расчётов совершенно не та же самая: 1E-120 в памяти держится нормально, а вот 1 — 1E-120 уверенно округляется до единицы. Логично.
Перешёл на поиск максимума у -p (называть отрицательную величину вероятностью язык не поворачивается).

Результат прекрасный: десяти итераций хватает для стабилизации рейтинга, и сам результат кажется правдоподобным.

На всякий случай сделал проверку, оптимизируя переменные не с первой по последнюю, а с последней по первую.
Через те же 10 итераций результат практически неотличим от первого — есть стабильность!

P.S. Вот такими нехитрыми комбинациями я поднялся в общем рейтинге с 12-го места на 5-е :-)

Comments

[crazyhome.livejournal.com]

Швейцарская система хорошо подходит, когда людей много и играть "каждый с каждым" не хочется.
Помню, в детстве мы в шахматном кружке так играли.

[green-fr.livejournal.com]

Когда я писал «на глазок», я именно её и имел в виду.

[andreylv.livejournal.com]

Перечитал сейчас комменты в твоем старом посте про рейтинги. Неожиданно понял, что именно такая система очень хорошо подходит к ММА (mixed martial arts). Там профессиональные бойцы бьются довольно редко, особенно на самом высшем уровне, и часто травмируются. А как считать, кто круче? Поэтому очень важно не только то, сколько раз ты выиграл, но и у кого, когда и как, и что потом этот побежденный тобой боец сделал. А то вот Фабрицио Вердум неожиданно победил Федора Емельяненко, который до этого десять лет никому не проигрывал - и его сразу превознесли до небес. А Федор потом проиграл еще два раза подряд, причем более слабым соперникам, чем Вердум, и это сразу победу Вердума сильно обесценило.

[green-fr.livejournal.com]

Да, но там есть один сильный недостаток — не учитывается прогресс игрока. Если я выиграл у Бобби Фишера, когда тот только правила учил, это не то же самое, что выиграть у него же уже в 15 лет.
У нас как раз эта проблема — есть люди, которые только учатся, они сейчас себе «карму» испортят, а через месяц начнут друг друга обыгрывать, но чтобы правильный рейтинг устаканился, им придётся по сотне партий отыграть.
Так что думаем теперь над периодическим обнулением истории...

[prokofyev.livejournal.com]

Саня, а эту статью, интересно, примут на Хабре?

[green-fr.livejournal.com]

Ты не поверишь, сегодня думал её туда переписать :-)

[green-fr.livejournal.com]

А ты туда тоже что-то пишешь? И что читаешь? Я таги android (по диагонали, программы новые смотрю) и matlab (один пост в месяц, и то в лучшем случае).

[green-fr.livejournal.com]

http://habrahabr.ru/blogs/programming/134720/