Многопользовательская командная игра: алгоритм автоматической балансировки команд, основанный на ранге игрока

Question

Параметр: Многопользовательская командная игра.

Проблема: У каждого игрока есть рейтинг от 1 до 5 звезд, который рассчитывается на основе его статистики игрока.Я надеялся найти алгоритм, который назначит команды этим игрокам самым справедливым способом.

Есть две команды, максимум 5 игроков на команду.

Допустим, присоединяются 6 игроковсервер.Было бы желательно, чтобы сервер назначил команды следующим образом:

1. 5-звездный игрок
2. 3-звездочный игрок
3. 3-звездочный игрок

VS

1. 5-звездный игрок
2. 4-звездочный игрок
3. 2-звездочный игрок

..в отличие от этого

1. 5-звездный игрок
2. 5-звездочный игрок
3. 4-звездочный игрок

VS

1. 3-звездный игрок
2. 3-звездочный игрок
3. 2-звездочный игрок

В первом примере всего 11звездочек на команду, тогда как во втором примере у одной команды всего 14 звезд, а у другой - 8.

Извините, я не мог быть более кратким.

Answer 1

Сначала сложите все звезды и разделите сумму на 2. Сортируйте список игроков по количеству звезд.Затем добавьте лучшего игрока в команду 1, второго в команду 2, третьего в команду 1 и так далее.Это даст хорошие результаты, но они могут быть далеки от совершенства.Например, если у вас 5,1,1,1 звездных игроков.В результате получится 5,1 VS 1,1.

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

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

Answer 2

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

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

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

Answer 3

Проверьте это: http://www.stanford.edu/class/cme305/References/approx.pdf Или вы можете попробовать 100 случайных способов группировки игроков и найти лучшее решение.Если у вас менее 20 игроков, вы можете проверить КАЖДУЮ возможную конфигурацию (2 ^ 20).

Answer 4

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

Answer 5

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

это не учитывает некоторые особые случаи. например, если есть игроки 1, 1, 1, 1, 2, 2, объединение всех единиц и всех двойок - не самое справедливое распределение.

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