green_fr (green_fr) wrote,
green_fr
green_fr

Categories:

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

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

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

И тут я вспомнил про старую статью в 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-е :-)
Tags: pour la science, rabota
Subscribe

  • «Хищные вещи века» и «Текст»

    Прослушал «Хищные вещи века» Стругацких. В детстве я их совсем не так понимал. Тогда книга казалось каким-то мрачным детективом: герой куда-то…

  • Акунин, Шекли, Абгарян

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

  • L'Anomalie

    В начале года был выпуск La Conversation Scientifique с совершенно ни о чём не говорящим названием «Que veut dire „être normal“?» (Что такое «быть…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 8 comments