Главная
Регистрация
Вход
RSS |
Зал славы
|
|
HellBrick | Дата: Суббота, 02 Ноября 2013, 22:06 | Сообщение # 1 |
The lamplighter
Группа: Архимаги
Сообщений: 3501
Награды: 0
Репутация: 288
Статус: Offline
| [cut=Вступительное слово]
- Привет, меня зовут АК и я... *срывающимся неуверенным голосом* разработчик Зала славы. - *хором* Привет, АК!
Много лет прошло с тех пор, как Зал славы II был закрыт на капитальный ремонт. За это время вышло 3 штуки больших релизов MPE, было проведено 9 турниров, сменилось несчётное количество поколений игроков. Зажигались новые звёзды, гасли старые... И вот настал момент, когда не осталось практически никого, кто в курсе что, зачем, как и почему происходит (или не происходит) со старательно собираемой статистикой игр. На исправление данного недоразумения и направлен этот топик.
Начну с небольшого экскурса в прошлое. Первый Зал был создан где-то летом-осенью 2008 года стараниями Geograf-а, NooK-а и, отчасти, вашего покорного слуги. Заварил всю эту кашу Географ (в своей домедвежьей ипостаси): он начал вести упорядоченный список игр (и агитировал остальных присоединяться к нему) с целью что-нибудь интересное на его основе посчитать. Именно тогда появились такие понятия, как взятые "головы" для учёта активности игроков в FFA и "смерть от нейтралов" для отделения плевел от реальных дуэлей. Всё шло хорошо, но потом Географа внезапно съел тигр. На самом деле не тигр, а медведица. И не совсем съела... Но суть в том, что Географ на долгое время выпал из жизни комьюнити, и его инициативу подхватил Нук.
Итак, был список игр, и нужно было как-то оценивать по ним результаты игроков. Путём хитрого шевеления извилинами с потолка была взята формула Rating = sqrt( Kills * ( Wins + Ties / 2 ) ) / Loses и началось ежемесячное вывешивание таблички с результатами.
Прошло несколько месяцев, и стало ясно, что дальше так жить нельзя. По сути формула первого Зала сводилась к отношению побед к поражениям, остальное - несложные выкрутасы с целью увязать взятые головы и ничьи. И это отношение оказалось настолько непоказательным, насколько это вообще возможно. Во-первых, оно напрочь игнорировало силу соперников игрока. Во-вторых, оно давало неоправданно большое преимущество новым игрокам с небольшим количеством игр - они получали более высокий рейтинг за счёт того, что не успевали нахватать поражений. В-третьих, с течением времени развитие рейтинга игрока очень сильно замедлялось, до такой степени, что особой интриги в наблюдении за табличкой не было. В-четвёртых, сами единицы измерениям рейтинга представляли собой абстрактных попугаев, делённых на сферических коней, и не содержали в себе ровным счётом никакого физического смысла.
Эти проблемы была призвана решить реинкарнация Зала, бесхитростно названная Зал славы II. В отличие от своего предшественника, он сохранился в архиве по сей день, и его можно поразглядывать вот тут. Всё стало несколько сложнее, но, вместе с тем, заметно логичнее. За основу был взят шахматный рейтинг Эло; любопытствующим советую повикипедить но вкратце суть такова: сила игрока описывается неким случайным распределением, рейтинг игрока определяется его матожиданием, после каждой игры расчитываются шансы игроков на победу, сравниваются с реальным результатом, и победитель откусывает от проигравшего определённое количество единиц рейтинга, прямо пропорциональное "неожиданности" исхода. Наш рейтинг отличался рядом деталей. Во-первых, использовалось нормальное распределение вместо логистического. Во-вторых, изменение рейтинга расчитывалось дважды: для взятых голов и для общего результата игры, и эти компоненты складывались (таким образом, даже проигравший FFA игрок мог оказаться в плюсе, взяв достаточно голов, а поражения от нейтралов практически не влияли на рейтинг). В-третьих, коэффициент прогресса (множитель, определяющий как быстро меняется рейтинг игрока) был одинаковым для всех без исключения.
В итоге получилась достаточно интересная штука. С одной стороны, основываясь на результатах игр, рейтинги самобалансировались, стремясь к чему-то вроде точки покоя. Попробую проиллюстрировать эту мысль на простом примере. Предположим, что в мире есть всего 2 игрока, и первый играет сильнее и выигрывает, скажем, 9 дуэлей из 10. В этом случае рейтинги игроков стремятся к такой разнице, что за 9 побед первый игрок получит суммарно примерно такой же бонус, который у него отберёт второй игрок, "неожиданно" выиграв 10ю игру. Рейтинги возвращаются к точке равновесия, всё начинается сначала.
С другой стороны - рейтинг не был закостенелым, за ним было достаточно интересно наблюдать. Неудачные серии позволяли даже опытным лидерам сваливаться в середину таблицы, а оседлавшие волну середнячки вполне могли в разумное время добраться до первой пятёрки. Плюс постоянно появлялись новые игроки, подкидывая на игровое поле свежий рейтинг для дележа между более опытными игроками =)
Что же пошло не так? Было несколько причин, по которым Зал II был неидеален. Во-первых, не совсем корректно обрабатывалось появление новых игроков. Как показала практика, реальный уровень новых игроков в среднем сильно отставал от рейтинга, с которым они начинали свой путь, в результате чего первые несколько игр новички представляли собой неадекватно халявный корм для лидеров, чем последние активно пользовались. Во-вторых, большим фиаско обернулась обработка гандикап-игр (1vs2): из-за неудачной оценки силы команды такие игры опять же были халявой для одиночного игрока, т.к. при поражении он ничего не терял, а при победе приобретал очень многое. В-третьих, наладить адекватный учёт взятых голов в ффа так и не получилось, и по сей день каждый извращается с их записью как хочет. В-четвёртых, ошибкой было объединять в один рейтинг ффа, дуэли и командные игры, они слишком разнородны и слишком по-разному просчитываются. И в-пятых, однажды я обнаружил что допустил идиотскую ошибку в формуле расчёта плотности распределения, тем самым заменив правильное нормальное распределение на какую-то хрень, которая худо-бедно работала только благодаря удачному стечению обстоятельств =) В силу всех этих причин Зал был закрыт на доработку...
А потом случился MPE, и Зал был задвинут далеко-далеко в списке приоритетов. Шёл год, второй, третий... И вот только полгода назад мы наконец смогли поставить точку в этом масштабнейшем проекте и освободиться для других дел.
Где-то в июле-августе этого года я начал работу над Залом III. Потом внезапно произошли AoW 3 и ряд приключений IRL, но вот на этих выходных я снова обнаружил себя в студии за этим проектом =) Лёд тронулся, идеи бьют ключом, работа кипит и очень хочется всем этим поделиться с вами, чем я собственно сейчас и занимаюсь.
Наверное на сегодня всё, в следующий раз расскажу о той нелёгкой и местами даже жестокой судьбе, которая постигнет (спойлер: на самом деле уже постигла) собранные за эти годы игры.[/cut]
Ветряные мельницы побеждены. Что дальше?
http://twitter.com/hellbrick
|
|
| |
AnS | Дата: Понедельник, 03 Февраля 2014, 15:09 | Сообщение # 31 |
Мудрец
Группа: Полководцы
Сообщений: 53
Награды: 0
Репутация: 8
Статус: Offline
| Я даже выиграл пару игр, самому не верится, вот времена были. Еще я пробовал играть под другими именами, но все равно проигрывал.
Добро всегда побеждает! Кто победил, тот и добро.
|
|
| |
Faler | Дата: Понедельник, 17 Февраля 2014, 10:58 | Сообщение # 32 |
Архимаг
Группа: Полководцы
Сообщений: 548
Награды: 0
Репутация: 82
Статус: Offline
| может ссылку на http://aow2.net/ сделать на главной странице? а то я периодически забываю где ее искать.
|
|
| |
HellBrick | Дата: Понедельник, 17 Февраля 2014, 18:38 | Сообщение # 33 |
The lamplighter
Группа: Архимаги
Сообщений: 3501
Награды: 0
Репутация: 288
Статус: Offline
| Добавил (в правое-верхнее меню).
Ветряные мельницы побеждены. Что дальше?
http://twitter.com/hellbrick
|
|
| |
Faler | Дата: Вторник, 18 Февраля 2014, 09:46 | Сообщение # 34 |
Архимаг
Группа: Полководцы
Сообщений: 548
Награды: 0
Репутация: 82
Статус: Offline
| благодарю
|
|
| |
HellBrick | Дата: Воскресенье, 02 Марта 2014, 11:50 | Сообщение # 35 |
The lamplighter
Группа: Архимаги
Сообщений: 3501
Награды: 0
Репутация: 288
Статус: Offline
| За последние несколько недель случились 2 знаменательных события.
Во-первых, в статистику была добавлена первая новая игра. Если честно, я не был уверен, что это вообще когда-либо случится, но оказалось, что мы несколько менее мертвы чем кажется =) Крайне приятно было узнать, что это всё нужно хоть кому-то ещё кроме меня.
Этот факт меня и побуждает продолжить рассказ о том что сейчас происходит за кулисами. Второе знаменательное событие: я вчера реализовал наивную версию рейтингового движка. Он сейчас умеет ровно то же самое, что умел движок Зала №2, только без идиотских косяков в формулах. Как именно он это делает хорошо расписано вот тут: http://aow2.clan.su/forum/9-375-12294-16-1286475924 - за прошедшие 3 с лишним года концепция не поменялась. Единственное отличие: я забил на частный случай с дуэлями и для них используется формула для FFA. Во-первых, она более общая; во-вторых, я окончательно забыл математику и не смог понять как я вывел упрощённую формулу для дуэлей =)
Дальше начинается полнейшая терра инкогнита: настал час модернизации и тюнинга алгоритма. Определённые мысли на этот счёт есть, но о них в следующий раз.
Ветряные мельницы побеждены. Что дальше?
http://twitter.com/hellbrick
|
|
| |
Merlin1 | Дата: Четверг, 13 Марта 2014, 00:26 | Сообщение # 36 |
Волшебник
Группа: Полководцы
Сообщений: 314
Награды: 0
Репутация: 78
Статус: Offline
| HellBrick,игр играется много,только мало что постится. Лично мое мнение-неудобно теперь постить игры,записывать результаты. А может кто-то не знает как это сделать.
Lovers and dangerous love Will find a way through everything Sick at the thought of losing you No one else in my room Soft as the snow that comes You move like electric window We take love where it comes To the world we run
|
|
| |
HellBrick | Дата: Четверг, 13 Марта 2014, 08:11 | Сообщение # 37 |
The lamplighter
Группа: Архимаги
Сообщений: 3501
Награды: 0
Репутация: 288
Статус: Offline
| Что именно неудобно? Есть идеи как сделать лучше?
Я самую большую проблему вижу в необходимости +1 аккаунта, особенно для новых игроков. Но, увы, авторизоваться через юкоз нет технической возможности, а классический логин через фейсбук/гуглоплюс/whatever тут мало что даст. Привязки к стиму, на который можно (в большинстве случаев (чёртов GoG >_<)) рассчитывать для АоВ 3, у игры нет. Я обдумывал автоматический постинг с помощью софтины, ставящейся вместе с MPE и мониторящей окончание игры, но тут возникает ещё больше разнообразных проблем.
Вторая проблема: отсутствие коментов для постинга отчётов, они в планах есть.
Ветряные мельницы побеждены. Что дальше?
http://twitter.com/hellbrick
|
|
| |
HellBrick | Дата: Воскресенье, 16 Марта 2014, 22:36 | Сообщение # 38 |
The lamplighter
Группа: Архимаги
Сообщений: 3501
Награды: 0
Репутация: 288
Статус: Offline
| Тем временем работа над ретйингом продолжается. Я обещал рассказать про настройку движка - рассказываю.
Итак, у нас есть формулы для расчёта рейтинга, но они пестрят константами, со значениями которых нужно как-то определиться. Начинаем определяться.
Самое простое - стартовый рейтинг игрока. Это число не играет абсолютно никакой роли (т.к. шансы на победу зависят от разницы рейтингов, но не от их абсолютных значений), поэтому можно выбрать просто что-нибудь удобное. Я выбрал 1000.
Среднеквадратичное отклонение распределения силы игрока (вот не могли наши математики изобрести нормальный термин для перевода слова deviation?..). Его "физический смысл" - показывать насколько сильно сила игрока варьируется вокруг мат. ожидания (то бишь рейтинга), но такая трактовка слабо помогает продвинуться дальше: абстрактные попугаи есть абстрактные попугаи, и ориентироваться в них не очень удобно. Нужно связать попугаев с реальным миром; я выбрал следующий способ: методом научного тыка подобрать такое значение отклонения, при котором перевес в 200 единиц рейтинга означает шанс на победу в 80%. Получилось примерно 166.1.
В итоге шанс на победу зависит от разницы рейтингов примерно вот так:
20 53,12% 40 56,49% 60 59,81% 80 63,06% 100 66,21% 120 69,26% 140 72,17% 160 74,94% 180 77,55% 200 80,00% 220 82,28% 240 84,38% 260 86,31% 280 88,06% 300 89,64% 320 91,06% 340 92,33% 360 93,44% 380 94,42% 400 95,27%
А вот дальше начинается жесть. Следующий параметр - коэффициент прогресса (K-factor) - число, которое будучи умноженным на "неожиданность" результата игрока даёт прирост его рейтинга в конкретной игре. В отличие от первой пары параметров здесь нет ни грамма вкусовщины, а есть строгая и важная характеристика рейтинга. По сути это скорость реакции системы на действия игроков. Более низкие значения приводят к тяжело изменяющемуся нединамичному рейтингу с акцентом на старых играх. Более высокие - наоборот, заставляют рейтинг изменяться более резко, что делает свежие игры более приоритетными. Где находится золотая середина и как её отыскать?
Тут в игру вступает наша замечательная база игр. Вспоминаем основную идею рейтинга: по разнице рейтингов игроков можно оценить вероятность победы каждого из них. И проходимся по всем играм, сравнивая "предсказания" рейтинга на момент перед игрой с реальными результатами, накапливая суммарную ошибку. Получается объективный критерий качества настроек рейтинга; теперь нужно найти такое значение параметров (в конкретном случае - коэффициента прогресса), при котором эта суммарная ошибка минимальна.
Оптимальное значение я вычислил, оно давало относительно приличные результаты, но тут я осознал, что у меня в руках оказался отличный инструмент для оценки корректности рейтингового движка, а значит, можно как следует с ним поиграться в попытке повысить точность. И я начал играться.
Первой попыткой уйти в сторону была смена распределения с нормального на логистическое (http://en.wikipedia.org/wiki/Logistic_distribution). Выигрыша в точности это не дало, но и особо хуже не стало, а расчёт рейтинга заметно ускорился, что положительным образом сказалось на свободе экспериментирования. Взвесив все "за" и "против" я решил оставить логистическое распределение и копать дальше.
Дальше последовала проверка теории, что для нескольких первых матчей игрока нужен другой k-factor. Теория достаточно быстро подтвердилась, но подбор оптимальной зависимости коэффициента от кол-ва игр подвесил меня где-то на пару дней. В конечном итоге дошло до того, что я стал строить эту зависимость по точкам: просчитываем коэффициент для первых игр - пересчитываем коэффициент для всего остального - просчитываем коэффициент для вторых игр - пересчитываем основной коэффициент ещё раз - и т.д. Получилось нечто очень похожее на экспоненту; ещё один сеанс расчётов для подбора её параметров дал следующую формулу:
KFactor = 41.257 + 88 * e ^ ( - 1.979 * g )
(где g - это кол-во игр игрока)
С новичками разобрались; остался ещё один волновавший меня концептуально пункт. Одна из проблем прошлого Зала и рейтинга Эло в принципе - возможность почивать на лаврах бесконечно, избегая игр. Тогда как на самом деле без практики игроки теряют форму и по возвращению (если оно случается) обычно показывают худшие результаты, чем предсказывает рейтинг. Я давно обдумывал возможные варианты борьбы с этим эксплоитом, планом А был плавно падающий в периоды неактивности рейтинг. Но когда я попробовал реализовать эту задумку, всплыла целая армада подводных камней. Нужно постоянно корректировать рейтинг новичков, перерасчитывая его исходя из времени, прошедшего с момента "большого взрыва". Нужно при расчёте таблицы с рейтингом отдельно учитывать кол-во времени, прошедшее с даты последней игры каждого игрока. Нужно подобрать оптимальный механизм отмены падения. В общем, кругом сплошной геморрой.
Тогда я решил попробовать вывернуть идею наизнанку: добавить бонус за регулярную активность. В чём её измерить? В играх - плохо, их легко набивать. Нужна привязка ко времени, например, добавлять бонус раз в N дней при условии наличия активности в этот промежуток. Проверяем идею на 2 неделях - работает! Налицо заметный прирост точности. Либо сказывается относительная потеря формы, либо просто статистически опыт играет большую роль... Хотя если подумать, это две стороны одной медали. Anyway, поигравшись со сроками и размером бонуса остановился на 3.313 единиц за неделю активности. Было опасение, что в таком виде эта фича может осложнить жизнь новичкам, позволив активным опытным игрокам уйти в слишком большой отрыв, но они оказались беспочвенными: как вы вскоре увидите, в топ 15 попали три игрока, сыгравшие менее 30 дуэлей.
Были ещё попытки модифицировать схему, но они не увенчались успехом - либо приводили к понижению точности, либо механизм оптимизации оной в попытке минимизировать погрешность успешно отключал неугодные фичи. В итоге на этом было решено остановиться. Дуэльным рейтингом я доволен, дальшу буду работать над его отображением на сайте. Маленький тизер: на сегодняшний день первое место занимает игрок, от которого я лично этого не очень ожидал. Кто же сумел вскрабкаться на самый верх, равно как и кто занял остальные 128 позиций, вы все узнаете уже очень скоро Следите за новостями!
Ветряные мельницы побеждены. Что дальше?
http://twitter.com/hellbrick
|
|
| |
Faler | Дата: Понедельник, 17 Марта 2014, 10:10 | Сообщение # 39 |
Архимаг
Группа: Полководцы
Сообщений: 548
Награды: 0
Репутация: 82
Статус: Offline
| Захватывающий исследовательский сюжет - такого уже нигде не прочтешь
Благодарю, очень занимательно.
Сам люблю возню с циферками, но так глубоко копать не умею, да и терпения не хватает, но за чужими успехами следить тоже приятно, если подано интересно.
|
|
| |
Merlin1 | Дата: Четверг, 20 Марта 2014, 18:44 | Сообщение # 40 |
Волшебник
Группа: Полководцы
Сообщений: 314
Награды: 0
Репутация: 78
Статус: Offline
| После словосочетаня "коэфициент прогресса" я закрыл тему,однако нельзя не заметить чужие труды и с нетерпением жду детища АК.
Lovers and dangerous love Will find a way through everything Sick at the thought of losing you No one else in my room Soft as the snow that comes You move like electric window We take love where it comes To the world we run
|
|
| |
HellBrick | Дата: Суббота, 22 Марта 2014, 22:42 | Сообщение # 41 |
The lamplighter
Группа: Архимаги
Сообщений: 3501
Награды: 0
Репутация: 288
Статус: Offline
| Без лишних прелюдий: дуэльный рейтинг. Ура!
Пара технических моментов. Рейтинг сейчас обновляется раз в несколько минут, так что свежевнесённые игры учитываются с небольшой задержкой. Возможно в будущем я это исправлю, но не прямо сейчас.
Момент номер два. Навигация на сайте позволяет смотреть старые результаты с точностью до месяца, но в случае интереса к какой-то конкретной точке во времени в неё можно попасть по ссылке типа http://aow2.net/Games/DuelRating?date=2008-10-10 (уж хз зачем это может понадобиться, но мало ли ;)).
На сегодня всё, в следующий раз расскажу что-нибудь про FFA. *ушёл любоваться результатами*
Ветряные мельницы побеждены. Что дальше?
http://twitter.com/hellbrick
|
|
| |
Faler | Дата: Воскресенье, 23 Марта 2014, 10:50 | Сообщение # 42 |
Архимаг
Группа: Полководцы
Сообщений: 548
Награды: 0
Репутация: 82
Статус: Offline
| HellBrick, отличная работа!
а можешь сделать так чтобы можно смотреть за какой-то отдельный период, скажем с 1 января 2012 по 1 июля 2013 и т.п.?
|
|
| |
HellBrick | Дата: Воскресенье, 23 Марта 2014, 13:45 | Сообщение # 43 |
The lamplighter
Группа: Архимаги
Сообщений: 3501
Награды: 0
Репутация: 288
Статус: Offline
| Да, это есть в планах, но несколько попозже. Сначала надо разобраться с FFA-шным рейтингом и понять как эту фичу аккуратно вписать в интерфейс.
Ветряные мельницы побеждены. Что дальше?
http://twitter.com/hellbrick
|
|
| |
HellBrick | Дата: Воскресенье, 23 Марта 2014, 19:51 | Сообщение # 44 |
The lamplighter
Группа: Архимаги
Сообщений: 3501
Награды: 0
Репутация: 288
Статус: Offline
| Сел делать FFA - они приподнесли даже больше сюрпризов, чем я ожидал. Если подумать, то большая их часть имеет рациональное объяснение, но суммарный результат их совокупности привёл к немного удивительной картине.
Я взял уже отточенную методику настройки параметров движка и стал по очереди подбирать их. Начальный рейтинг и отклонение остались теми же, ибо нет смысла их трогать; k-factor по умлочанию оказался равен 51.35 (против 41.26 у дуэлей). Но уже тут я подметил интересную особенность номер раз: ффа намного более рандомны чем дуэли, и их результаты предсказанию поддаются с большим трудом. Конкретно это выражается в том, что суммарная ошибка рейтинга на глаз заметно выше, чем у дуэлей (если сделать поправку на разное кол-во игр, конечно же).
Дальше стал подбирать поправку к прогрессу для первой игры новичка... и с удивлением обнаружил, что реальные данные сводят её к нулю. Если быть точным, то не к нулю, а примерно к -3, но значение настолько мизерное и даёт настолько незаметную прибавку к точности, что я решил этим моментом пренебречь. В итоге при расчёте ффа используется константный k-factor. Если честно, затрудняюсь сказать чем обусловлен такой феномен. Две основные теории: либо новички сначала набираются опыта в дуэлях и им этого для счастья хватает, либо небольшие шансы на победу в любом ффа в принципе ликвидируют необходимость как-то по-особому просчитывать их рейтинг.
По аналогии с дуэльным рейтингом был расчитан бонус за активность, и в отличие от попытки выделить игры новичков, он дал заметные результаты, как и в случае с дуэлями. Этот бонус оказался равен 6.037 за неделю.
Вроде бы всё ок, просчитываю рейтинг с оптимальными параметрами, смотрю на результаты... И тут меня начинают терзать сомнения, что что-то здесь не так. Несмотря на то, что в целом распределение игроков выглядит довольно разумно (в том числе первую строчку с заметным отрывом занял очевиднейший претендент на звание короля FFA), результаты некоторых игроков мне показались неожиданно высокими. Когда увидите таблицу для ффа, поймёте о ком я Чешу репу, сажусь анализировать динамику их рейтингов...
В итоге вырисовывается достаточно любопытная картина. Наличие на карте кучи игроков делает шансы большинства из них на победу довольно небольшими. Звучит довольно очевидно, я знаю =) Несколько менее очевидны следствия из этого факта. Во-первых, победы в ффа дают намного больший профит, чем возможные потери от поражения. Во-вторых, играть ффа с сильным составом чертовски выгодно - риск практически нулевой, а потенциальная выгода велика. В-третьих, столь распространённые ничьи обычно становятся выгодными тем кто дожил до финиша. Потенциальный эксплоит? Не знаю, может быть.
Вроде если врубиться в эту специфику и проследить за результатами, то всё кажется объяснимым и оправданным. Подсознательное ощущение странности происходящего остаётся, но идей как сделать лучше у меня нет, так что видимо имеем что имеем. На этой загадочной ноте я пока остановлюсь и буду прикручивать ффа в интерфейс.
Ветряные мельницы побеждены. Что дальше?
http://twitter.com/hellbrick
|
|
| |
Jean_de_Metz | Дата: Понедельник, 24 Марта 2014, 01:35 | Сообщение # 45 |
Mr. Закидон
Группа: Маги
Сообщений: 1064
Награды: 7
Репутация: 359
Статус: Offline
| HellBrick, ты большой молодец =) Спасибо за старания!
Жан 7 турниров подряд был в призах, а чего добился ты? (с) PLANET JEAN
Ladies and Gentlemen, welcome to AowClan.
The first rule of AowClan is you must play in AowClan.
The second rule of AowClan is you must constantly play in AowClan.
And the last rule of AowClan is if this is your first day in AowClan, you have to play!
|
|
| |
|
|
|