?

Log in

Про вероятность выигрыша - Олег Етеревский [entries|archive|friends|userinfo]
Oleg Eterevsky

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Про вероятность выигрыша [12 November 2015|22:17]
Oleg Eterevsky
Осторожно, математика.

Немного про мотивацию к задаче из предыдущего поста.

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

К этому добавляется предположение о том, что вероятность выигрыша имеет нормальное распределение, и исходя из этих предположений получается некоторая фиксированная формула, позволяющая после любой партии двух шахматистов "подправить" рейтинг её участников.

Можно ли сделать лучше? В принципе да. Определим рейтинг следующим образом. Пускай у нас есть набор шахматистов p_i и множество игр между ними g_j. Назовём оптимальным рейтингом набор значений рейтинга для игроков r(p_i) и функцию на вещественных числах f(x), обладающие следующими свойствами:

1. f принимает значения от 0 до 1, монотонно возрастает и симметрична.
2. f(200) = 0.75
3. f(r(p1) - r(p2)) является наилучшим приближением в смысле maximum likelihood для вероятности с которой p1 выигрывает у p2. То бишь функции f() и r() минимизируют следующее произведение по всем играм g_j:

PROD f(r(победитель g_j) - r(проигравший g_j))

Чем хороши такие рейтинги? Во-первых, они нормализованы точно также как обычные рейтинги Эло, то бишь если рейтинг одного игрока выше рейтинга другого на 200, то вероятность выиграть составляет 75%. Во-вторых, такой рейтинг обладает в некотором смысле максимальной предсказательной силой. А именно, если мы знаем про двух игроков только их рейтинги то f от их разности должно быть в хорошей оценкой вероятности того, что первый выиграет у второго.

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

Есть и ещё несколько вопросов: что делать с ничьими, и что делать если вероятность выигрыша зависит от того, кто ходит первым? Ответ прост: ничью можно рассматривать как две половинки партии, в одной из которых выиграл первый, а в другой -- второй. Что касается разной вероятности выигрыша -- тут достаточно поменять нормализацию функции f: усреднить вероятность выиграть за белых и за чёрных: (f(200) - f(-200)) / 2 = 0.75.

Пару лет назад, когда я заинтересовался этим вопросом, я даже написал программу, которая вычисляла рейтинги исходя из этого определения. Оказалось, что вменяемые результаты для тысяч игроков и миллионов партий можно без труда посчитать на обычном компьютере. К сожалению, я не довёл тот проект до конца и не сравнил по-честному качество рейтингов, получаемых таким способом, с рейтингом Эло. С тех пор доведение этой задачи до ума так и висит у меня в списке важных дел, которые нужно как-нибудь сделать.
LinkReply

Comments:
[User Picture]From: bik_top
2015-11-12 09:41 pm (UTC)

Ничья, порядок пересчёта

> Ответ прост: ничью можно рассматривать как две половинки партии, в одной из которых выиграл первый, а в другой -- второй.

Не могу сказать, что прям сильно старался вникнуть в выкладки; но неочевидно: зависит ли рейтинг от порядка засчёта выигрыша или поражения?

Если мы засчитаем выигрыш первому (сильному) игроку, пересчитаем рейтинги, потом засчитаем победу второму (слабому) игроку, пересчитаем рейтинги с учётом первого пересчёта — изменится ли результирующая пара рейтингов, если сначала засчитать победу слабому над сильным, и после пересчёта — выигрыш сильного у слабого?
(Reply) (Thread)
[User Picture]From: eterevsky
2015-11-12 09:48 pm (UTC)
В Ило -- да, зависит. В том что я описываю -- нет, не зависит, так как рейтинги вычисляются все разом, а не обновляются по результатам партий.
(Reply) (Parent) (Thread)
[User Picture]From: bik_top
2015-11-12 09:51 pm (UTC)
Ок.

(Вообще, он обычно «Эло», никогда не встречал написание «Ило».)
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2015-11-12 09:53 pm (UTC)
Упс, сорри. Поленился посмотреть на стандартный перевод его имени. Сейчас поправлю в посте.
(Reply) (Parent) (Thread)
[User Picture]From: shurik_s
2015-11-12 11:39 pm (UTC)
Забавно, но пока я неспешно писал тебе комментарий про рейтинги в предыдущий пост, ты написал про них целый новый пост.

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

Вообще, если тебе все это еще интересно, то можно попробовать поиграться вместе в этой песочнице. Чем больше будет заинтересованных участников, тем больше будет шанс что-то куда-то сдвинуть.
(Reply) (Thread)
[User Picture]From: eterevsky
2015-11-13 06:57 am (UTC)
Да, я за, конечно. Понятно, что тот метод вычисления рейтингов, который я описываю, не очень практичен -- запускать ML оптимизацию после каждой игры дорого. Но с помощью глобальной оптимизации можно достаточно точно определить форму той самой функции f, и придумать локальное правило обновления рейтинга.
(Reply) (Parent) (Thread)
[User Picture]From: shurik_s
2015-11-13 08:42 am (UTC)
Ну в наше время не так уж и дорого. Люди из 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
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2015-11-13 11:06 am (UTC)
У меня есть точно такой же код на питоне. Как я говорил, отлично справляется с миллионами партий.

Это скорее немного непрактично. Представь себе, что у тебя есть миллион игроков в онлайновую игру. И каждый сразу после окончания партии хочет видеть свой обновлённый рейтинг. Хотя, если обновлять рейтинги, скажем, раз в день, то проблемы нет.
(Reply) (Parent) (Thread)
[User Picture]From: shurik_s
2015-11-13 11:13 am (UTC)
Тут есть еще нюанс как различать две ситуации:
A очень крутой игрок который только начал играть и его рейтинг еще очень низкий, но в течении месяца вырастает до невиданных высот. Тогда все кто у него выигрывали должны бы получить больший бонус.

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

Мне кажется, что здесь лучше всего делать приблизительную переоценку сразу и существенный пересчет раз в день/месяц/год.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2015-11-13 11:18 am (UTC)
Да, можно аптейтить онлайн, а раз в день/месяц пересчитывать все рейтинги за всё время.

Две ситуации, которые ты описал легко различаются, если оптимизировать всю историю рейтингов.
(Reply) (Parent) (Thread)
[User Picture]From: nikolenko
2015-11-13 09:00 am (UTC)
Совсем не дорого, все ок. Просто надо апдейт делать, а не всю историю пересчитывать. Это еще будет иметь правильный эффект в том, что более поздние игры будут иметь больший вес.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2015-11-13 11:13 am (UTC)
Хе. Я делал по-другому. Я пересчитывал и рейтинги из прошлого. Представь себе что новый игрок в начале случайно выиграл партию у сравнительно сильного игрока. Тогда у него изначально будет слишком высокий рейтинг и это повлияет на всех, кто с ним играет. А если при каждом пересчёте обновлять и исторические рейтинги, то после нескольких партий его рейтинг после первой партии уменьшится, и всё встанет на места.

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