Про вероятность выигрыша

[eterevsky]

Осторожно, математика.

Немного про мотивацию к задаче из предыдущего постаВсе знают, что у шахматистов бывают рейтинги в промежутке примерно между 1000 и 3000, но не все знают, что эти рейтинги означают. Рейтинг называется рейтингом Эло (Elo -- это фамилия, а не акроним) и вычисляется исходя из следующего предположения: если рейтинги двух

Comments

[shurik_s]

Забавно, но пока я неспешно писал тебе комментарий про рейтинги в предыдущий пост, ты написал про них целый новый пост.

Мы с Сергеем как раз недавно подумали, что неплохо бы поиграться с рейтингами и сделать, что-то хорошее, благо наш фикс к TrueSkill в 2011 взяли на ICML.

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

[eterevsky]

Да, я за, конечно. Понятно, что тот метод вычисления рейтингов, который я описываю, не очень практичен -- запускать ML оптимизацию после каждой игры дорого. Но с помощью глобальной оптимизации можно достаточно точно определить форму той самой функции f, и придумать локальное правило обновления рейтинга.

[shurik_s]

Ну в наше время не так уж и дорого. Люди из Microsoft создавшие Trueskill говорили, что у них очень быстро работает пересчет всей шахматной истории. И это 10 минут на P4 в 2008 году.
http://research.microsoft.com/pubs/74417/NIPS2007_0931.pdf
Тут их код на F#: http://blogs.msdn.com/b/dsyme/archive/2012/04/19/updated-version-of-quot-trueskill-through-time-quot-bayesian-inference-code.aspx

[eterevsky]

У меня есть точно такой же код на питоне. Как я говорил, отлично справляется с миллионами партий.

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

[shurik_s]

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

A нормальный игрок который очень быстро учится и к концу месяца он бог. Но тогда его рейтинг примерно соответствует его умениям в каждый момент времени.

Мне кажется, что здесь лучше всего делать приблизительную переоценку сразу и существенный пересчет раз в день/месяц/год.

[eterevsky]

Да, можно аптейтить онлайн, а раз в день/месяц пересчитывать все рейтинги за всё время.

Две ситуации, которые ты описал легко различаются, если оптимизировать всю историю рейтингов.

[nikolenko]

Совсем не дорого, все ок. Просто надо апдейт делать, а не всю историю пересчитывать. Это еще будет иметь правильный эффект в том, что более поздние игры будут иметь больший вес.

[eterevsky]

Хе. Я делал по-другому. Я пересчитывал и рейтинги из прошлого. Представь себе что новый игрок в начале случайно выиграл партию у сравнительно сильного игрока. Тогда у него изначально будет слишком высокий рейтинг и это повлияет на всех, кто с ним играет. А если при каждом пересчёте обновлять и исторические рейтинги, то после нескольких партий его рейтинг после первой партии уменьшится, и всё встанет на места.

Я делал так. Создавал переменную для рейтинга игрока за определённый период времени (для шахмат -- за год), регуляризовал по скорости изменения рейтинга и оптимизировал это дело.