«Змеи»: формулы вычисления рейтингов

[AVA12]

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

• Рейтинг является целым числом. Возможно, со знаком.
• Рейтинг не может устремляться в бесконечность (или минус бесконечность).
• Рейтинг меняется только по результатам боя.
• Если змея съела всех соперников, ее рейтинг не может уменьшиться. Если змея съедена, ее рейтинг не может увеличиться.
• Изменение рейтинга по итогам боя зависит от рейтингов соперников. Награда за победу над сильным соперником выше, штраф за проигрыш сильному сопернику ниже. При слишком большой разнице рейтинг победителя может даже уменьшиться, а рейтинг проигравшего увеличиться (примечание: бой не обязательно заканчивается съедением всех соперников; победитель - самая длинная змея, проигравший - самая короткая).
• Изменение рейтинга по итогам боя зависит от итоговых длин змей: чем больше длина змеи и чем меньше длины змей соперников, тем выше рейтинг.
• Нельзя прокачать рейтинг выше, чем у чемпионов, не вызывая этих чемпионов на бой. Как вариант: итоговый рейтинг не может превышать исходный рейтинг побежденных соперников больше, чем на фиксированную величину.
• Особое внимание нужно уделить начальному рейтингу игрока. Просто назначать новичкам минимально возможный рейтинг не годится: новый игрок, выставивший змею с сильной программой, может серьезно испортить рейтинги чемпионов.
• Нужно избегать резких скачков рейтинга. Как вариант, учитывать не только исходный рейтинг, но и количество боев: чем меньше обычных боев провела змея, тем слабее она влияет на рейтинг других змей.

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

[Рябчиков-Жуй]

Несколько непоняток:

1.

Цитата

Нельзя прокачать рейтинг выше, чем у чемпионов, не вызывая этих чемпионов на бой

Почему? Что делать, если чемпион устранился от дел и (пока) больше не играет?

2.1

Цитата

Изменение рейтинга по итогам боя зависит от рейтингов соперников

Фундаментальное правило всех рейтинговых систем - закон сохранения рейтинга. Суммарный рейтинг участников по итогам матча (турнира) не меняется. Дельта присуждается по отношению достигнутого результата к ожидаемому.

2.2

Цитата

Награда за победу... штраф за проигрыш

В четырехстороннем матче (турнире), кроме победителя и проигравшего есть еще два участника. Что присходит с их рейтингом?
Возвращаясь к 2.1, что такое результат?

3.

Цитата

новый игрок, выставивший змею с сильной программой, может серьезно испортить рейтинги чемпионов

Разве это плохо?

Итого, если определить результаты матча для всех участников, ничего лучше Эло придумывать не придется.

[MIF]

Цитата AVA12 @ 19.09.12, 12:49

Если змея съедена, ее рейтинг не может увеличиться

В турнире учавствовало 25 змей.
Первая змея села 23 змеи но была сьедена 25ой.

Что, ее рейтинг должен снизится?

[AVA12]

Рябчиков-Жуй:

Цитата

Что делать, если чемпион устранился от дел и (пока) больше не играет?

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

Цитата

кроме победителя и проигравшего есть еще два участника. Что присходит с их рейтингом?

Надо придумать. Вообще, "победитель" и "проигравший" - условные термины.

Цитата

Возвращаясь к 2.1, что такое результат?

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

Цитата

Разве это плохо?

Черт его знает. Надо думать.

MIF:

Цитата

В турнире учавствовало 25 змей.
Первая змея села 23 змеи но была сьедена 25ой.

Никаких турниров нет. Есть отдельные бои, в которых участвуют по 4 змеи. Рейтинги пересчитываются после каждого боя.

[amk]

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

[AVA12]

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

[OpenGL]

Цитата Рябчиков-Жуй @ 20.09.12, 06:13

Фундаментальное правило всех рейтинговых систем - закон сохранения рейтинга. Суммарный рейтинг участников по итогам матча (турнира) не меняется. Дельта присуждается по отношению достигнутого результата к ожидаемому.

Не обязательно. В том же topcoder или codeforces обходятся без этого правила. На втором, кстати, оно раньше было, но впоследствии от него отказались.

[Рябчиков-Жуй]

Цитата

Цитата

Что делать, если чемпион устранился от дел и (пока) больше не играет?

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

То есть, однажды созданная змея навеки остается в игре?

В образцовой на сегодняшний день рейтинговой системе (Эло) чемпиона можно превзойти не играя с ним. Фишер ушел из шахмат имея высший рейтинг, Каспаров тоже; и ничего, мир не обрушился. Я не думаю, что это важное требование. Куда важнее не допустить инфляции рейтингов, то есть действительно

Цитата

Особое внимание нужно уделить начальному рейтингу игрока

.

Здесь пока ничего хорошего не придумали (и я думаю, что это тема не одной докторской). Лучшее на сегодняшний день - provisional performance ratings: рейтинг присуждается по самосогласованию результатов первых N матчей (т.е. рейтинг дается такой, чтобы актуальный результат равнялся ожидемому). Реализация довольно громоздка, применение непрактично.

Так или иначе, все сводится к ясному понятию результата. С этого, похоже, и надо начать.

PS: Отдельная проблема - злоупотребления, типа сандбаггинга.

[AVA12]

Цитата

То есть, однажды созданная змея навеки остается в игре?

Нет, змея может быть удалена. Навеки останется игрок, который должен выбрать для рейтинговых боев одну из своих змей.

[amk]

А почему нельзя несколько змей эксплуатировать?

[AVA12]

Цитата

А почему нельзя несколько змей эксплуатировать?

Чтобы не засоряли таблицу рейтингов кучей похожих змей.