Теория построения системы рейтинга (?)

[Андрей1]

Допустим, есть N игроков, которые регулярно играют между собой в игру 1х1, у которой может быть несколько исходов (например, выиграл_1/выиграл_2 или выиграл_1/ничья/выиграл_2). Стоит задача, построить такую систему рейтинга, то есть связать с каждым игроком некоторую характеристику - некоторый математический объект (в самом простом случае - число), так чтобы:
1) из характеристик игроков можно было оценивать вероятности исходов будующей игры между 2-мя заданными игроками;
2) был бы задан закон пересчета рейтингов после каждой игры.

У шахматистов, насколько я понимаю, есть подобная система рейтингов...

Не подскажите, где можно подробно почитать о подобных системах построения рейтинга?
На какие ключевые слова можно искать информацию?

[maxal]

Так, может быть, вам стандартный ЭЛО подойдет (тот, что в шахматах и Го) - он довольно универсален и основывается на статистических оценках результатов.
В английской википедии подробная статья на этот счет:
http://en.wikipedia.org/wiki/Elo_rating_system

[Руст]

Была статья об ЭЛО в "Кванте". Помнится я в тот же день отправил в "Квант", что система подсчёта ЭЛО содержит инфляционную составляющую. Привёл пример, когда двое третьеразрядников и один перворазрядник каждый день играет турнир между собой (каждый играет две партии с другими) и подсчитывают свои ЭЛО. При этом, в среднем проигрыши выигрыши и ничьи соответствуют тому, что должно быть согласно классификации об разнице укоэффициентов ЭЛО. Через год после таких игр их коэффициенты превзойдут 3000 (у перворазрядника первоначальный коэффициент 2000, у третуразрядников 1600), т.е. существенно больше , чем у чемпиона мира.

[Профессор Снэйп]

Вот здесь есть некая система рейтингов. Не берусь судить, насколько она совершенна, но силу игроков по рейтингу обычно можно определить довольно точно. И от описанного выше недостатка она свободна. По крайней мере, у меня как-то после порядка сотни партий с игроками низкого уровня рейтинг поднялся довольно незначительно, в то же время после выигрыша у сильного соперника рейтинг ощутимо увеличивается.

Правда, как там этот рейтинг считается, я не знаю. Это, наверное, секрет Yahoo!

[Руст]

Инфляционная составляющая в рейтинге ЭЛО появляется в основном из-за того, что пересчёт рейтингов проходит не по каждой партии, а после каждого турнира. При этом перерасчёт рейтинга каждого шахматиста происходит по формуле $R_i=R_{i0}+K(f_i-f_{i0})$, где $R_{i0}$ рейтинг даннного (i- го) шахматиста до турнира, $f_i$ количество набранных очков этого шахматиста на турнире, а $f_{i0}$ количество ожидаемых по набору очков, расчитанных, при условии игры с одним партнёром, равным с средним по рейтингу участников турнира. Функция рейтинга и ожидаемого количества очков в турнире нелинейна и из-за нелинейности становится бесполезным пересчёт с среднем рейтингом в турнире. За счёт выпуклости этой функции происходит всегда некоторое увеличение рейтинга, чем при пересчёте рейтинга по каждой партии. Если бы в турнире участвовали только два шахматиста то пересчёт за счёт нелинейности этой функции отражался бы только в коэффициенте K, т.е в более быстром или медленнем стабилизации ЭЛО, но когда участников много эта нелинейность отражается как увеличение среднего рейтинга участников. Хотя с каждым турниром участники действительно повышают своё мастерство, тем не менее нельзя сопоставить это с инфляционным увеличением рейтинга. Например, у таких гениальных шахматистов как Алёхин, Капабланка рейтинги ЭЛО соответствуют примерно рейтингам совремённых обычных гроссмейстров, и они существенно ниже у настоящих чемпионов мира. Но насколько сильнее современные первые шахматисты по сравнению с ними по рейтингам ЭЛО, которые не учитывают инфляционную составляющую, бессмысленно.
В принципе от инфляции можно в основном избежать за счёт того, что в формуле пересчёта внести учёт нелинейности типа:
$R_i=g^{-1}(g(R_{i0})+K_1(f_i-f_{i0}))$.
Однако это так же не полностью решает проблему, связанную с учётом пересчёта по среднему рейтингу участником турнира. Я тогда разрабатывал теорию пересчёта рейтингов по двум параметрам по силе $R_i$ и по его неравномерности $\sigma_i$. В зависимости от $\sigma_i$ зависит функции пересчёта новых рейтингов. Вообще это довольно сложная проблема для описания в одном посте. Хотя я сам за повсеместное внедрение рейтингов всех людей по каждому виду деятельности и изменение демократии в голосовании с учётом рейтингов голосующих по соответствующему предмету голосования, я признаю, что система рейтинга пока далека от совершенства.

[worm2]

Руст писал(а):

Например, у таких гениальных шахматистов как Алёхин

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

[Руст]

worm2 писал(а):

Руст писал(а):

Например, у таких гениальных шахматистов как Алёхин

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

Прошу прощения за свою неграмотность. Вообще то я читал только одну статью про рейтинги в журнале "Квант". Насколько помнится рейтингы Алехина не дотягивает до рейтинга международного гроссмейстера, а у Капабланки до международного мастера. Я думаю, что скорее здесь это вследствие вышеуказанной инфляции рейтингов.
Подсчёт рейтингов происходит по следующей схеме: Пусть $R_{i0}$ рейтингы участников до турнира. Подсчитывается средний рейтинг турнира

$$R_a=\frac 1n \sum_{i=1}^n R_{i0}.$$

Новые рейтингы после турнира просчитываются по формуле:

$$R_i=R_{i0}+K(F_i-\frac{M*3^{(R_{i0}-R_a)/200}}{1+3^{(R_{i0}-R_a)/200}}).$$

Здесь $M$ максимально возможное количество очков (количество очков, который бы набрал шахматист выигрывая все матчи), $F_i$ - фактически набранные очки.

[Sinus]

Насчет инфляции: во второй половине 80-х рейтинги Карпова и Каспарова часто не достигали 2700 (хотя тогда они довольно долгое вермя были значительно выше всех), а сейчас отметку в 2600 преодолевают многие шахматисты.

[Руст]

На самом деле инфляция здесь связано с асимметрией распределения шахматистов по силе в турнирах. Можно ввести коэффициент асимметрии

$$As=\frac{\sum_i (R_i-R_a)^3}{\sum_i(R_i-R_a)^2}.$$

Инфляционная составляющая примерно соответствует этой величине и положительна, когда $As$ положительна. Точнее тут надо считать моменты, связанные с гиперболическим тангенсом. Обычно в турнире сильных мало, больше более слабых. Это приводит к асимметрии и положительности всех нечётных моментов, которое отражается в инфляции рейтингования. Поэтому я демонстрировал инфляцию с двумя третьеразрядниками и перворязрядником. В противном случае средние рейтинги участников даже бы снизились.

[juna]

В системе ЭЛО если предположить, что игрок А всегда выигрывает у игрока В, то рейтинг игрока А будет возрастать даже если рейтинг игрока В пройдет через нуль и станет отрицательным. Т.е. учет влияния количества выигранных партий нивелирует учет взаимоотношения сил, отсюда и инфляция для сильных игроков. Чтобы ее исключить, нужно использовать формулы, которые итерируются к неподвижной точке.

[Руст]

Это не существенно. Так как это приводит только к логарифмическому росту и он за всю жизнь не сможет значительно повысит рейтинг играя только с одним игроком. Инфляция связано с повышением среднего рейтинга, который не происходит при игре двух шахматистов.