Ярмарка matchmaking для онлайн-игр

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

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

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

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

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

Пример

Игра 4 на 4

A - 1000 очков

B - 800 очков

C - 600 очков

D - 400 очков

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)

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

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

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

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

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

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 с вероятностью M / N, где M - общее количество игр, выигранных A.
4. Присвойте уровень мастерства 1 каждому игроку в начале.
5. Используйте Power Method , чтобы найти доминирующий собственный вектор матрицы связей, построенной на основе вероятностей, определенных в 3.
6. Доминирующий собственный вектор - это количество навыков, которыми обладает каждый игрок в момент t = бесконечность, что является количество навыков, которыми обладает каждый игрок после того, как марковская цепь пришла в равновесие.Это очень надежная мера навыков каждого игрока с использованием топологии пространства выигрышей / проигрышей.

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

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

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

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

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