Честная встреча для онлайн-игр

Question

Большинство онлайн-игр произвольно образуют команды.Часто это зависит от пользователя, и он выбирает быстрый сервер со свободным слотом.Такое поведение порождает недобросовестные команды, и люди выходят из себя.Отслеживая статистику игрока (или любую статистику, которая может быть собрана), как вы можете выбирать команды, которые являются максимально справедливыми?

Answer 1

Одной из наиболее известных систем в настоящее время является алгоритм TrueSkill от Microsoft .

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

Answer 2

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

Интуитивная идея использования цепи Маркова выглядит примерно так:

1. Создать график G = (V, E)
2. Пусть каждая вершина в V представляет собой сущность
3. Пусть каждое ребро в E представляет вероятность перехода между сущностями. Это означает, что сумма выходных степеней каждой вершины должна составлять 1.
4. В начале (время t = 0) назначьте каждому объекту единичное значение 1
5. На каждом временном шаге объект формы i, j перехода определяется вероятностью перехода, определенной в 3.
6. Пусть t-> бесконечность, тогда значение каждой сущности при t = бесконечности является равновесием (то есть вероятность перехода в сущность равна общей вероятности перехода из сущности.)

Эта идея, например, успешно использовалась для реализации алгоритма ранжирования страниц Google. Чтобы описать, как вы можете использовать его, рассмотрите следующее:

1. V = игроки E = вероятность перехода игрока из формы в форму игрока на основе относительных коэффициентов выигрыша / проигрыша
2. Каждый игрок является вершиной.
3. Преимущество от игрока A до B (B не равен A) имеет вероятность X / N, где N - общее количество игр, сыгранных A, а X - общее количество проигранных игр B. Добавьте преимущество от A к A с вероятностью M / N, где M - общее количество игр, выигранных A.
4. Назначить уровень мастерства 1 каждому игроку на старте.
5. Используйте Power Method , чтобы найти доминирующий собственный вектор матрицы связи, построенный из вероятностей, определенных в 3.
6. Доминирующий собственный вектор - это количество навыка, которое каждый игрок имеет в t = бесконечность, то есть количество навыков каждого игрока, когда цепь Маркова пришла в равновесие. Это очень надежная мера каждого навыка игрока, использующая топологию пространства выигрыша / проигрыша.

Некоторые предостережения: при непосредственном применении этого есть несколько проблем, самой большой проблемой будут отдельные сети (т. Е. Ваша цепочка Маркова не будет неприводимой, и поэтому метод мощности не будет гарантированно сходиться.) К счастью для вас, Google справился со всеми этими и другими проблемами при реализации алгоритма ранжирования страниц, и вам остается только посмотреть, как они обходят эти проблемы, если вы так склонны.

Answer 3

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

1. отслеживать выигрыши и проигрыши
2. использовать процент выигрышей против проигрышей в качестве статистики для сопоставления игроков (в некотором смысле слова совпадения, то есть групповых игроков с аналогичным процентом)

Это имеет очевидный недостаток в случае, когда у игрока может быть соотношение проигрышей 5-0, а у другого - 50-20, у первого - бесконечный процент, а у другого - более разумный процент. Для системы сопоставления имеет смысл признать это и быть гораздо более уверенным в том, что последний игрок имеет на самом деле больше навыков из-за требуемой последовательности; однако, столкновение двух игроков друг с другом, вероятно, было бы хорошо, потому что игрок 5-0, вероятно, пытается работать с системой, играя против более слабых игроков, поэтому столкновение его с постоянно хорошим игроком принесло бы пользу всем.

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

Answer 4

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

1. Уберите лучших и худших игроков и поместите их в команду 1
2. Удалите лучшего и худшего на данный момент игрока (действительно второго и худшего на втором месте) и поместите его в команду 2
3. Если осталось только два игрока, поместите каждого из них в разные команды, в зависимости от того, у кого наименьший общий счет. В противном случае повторите:
4. Удалите сейчас, лучше, а теперь и хуже, и поместите их в команду 1
5. Удалите сейчас, лучше, а теперь и хуже, и поместите их в команду 2

и т.д.. и т.д. и т. д., пока ваши команды не будут заполнены.

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

В качестве альтернативы, если вы хотите избежать игр, которые объединяют хороших и плохих игроков в одной команде, вы можете разделить всех на уровни , (группы, основанные на их рейтинге) и сопоставлять людей только в одной группе. ярус. Для этого потребуется новый открытый / отсортированный список для каждого дополнительного уровня.

* ** 1023 тысяча двадцать-дв * Пример

Игра 4v4

A - 1000 точек

B - 800 пунктов

C - 600 pnts

D - 400 pnts

E - 200 баллов

F - 100 пунктов

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

Команда 1: A, F, D (общий счет 1500)

Команда 2: B, E, C (общий счет 1600)

Теперь мы ждем присоединения еще двух игроков.

Сначала игрок E приходит с 500 очками. Он идет в Команду 1, потому что у них более низкий комбинированный счет.

Затем игрок F приходит с 800 очками. Он идет в Команду 2, потому что осталась единственная открытая команда.

Всего команд:

Команда 1: A, F, D, E (общий счет 2000)

Команда 2: B, E, C, F (2400)

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

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

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

Answer 5

Совпадение на основе нескольких атрибутов. Я реализовал простую систему поиска совпадений с использованием AWS Cloudsearch (на основе Apache Solr). Например, возможно сопоставление на основе комбинации следующих полей

{
    "fields": {
    "elo_rating": 3121.44,
    "points": 404,
    "randomizer": 35,
    "last_login": "2014-10-09T22:57:57Z",
    "weapons": [
        "CANNON",
        "GUN"
    ]
}

Теперь можно выполнять запросы, включающие несколько полей, как показано ниже.

(and (or weapons:'GUN' weapons:'CANNON' weapons:'DRONE')(and last_login:['2013-05-25T00:00:00Z','2014-10-25T00:00:00Z'])(and points:[100, 200])(and elo_rating:[1000, 2000]))}