Алгоритм создания справедливых / равномерно подобранных команд на основе рейтинга игроков

Question

У меня есть набор данных об уровне квалификации игроков, возрасте и поле, и я хотел бы создать команды с равным соответствием.

• Команды будут иметь одинаковое количество игроков (в настоящее время 8 команд по 12 игроков).
• Команды должны иметь одинаковое или похожее соотношение мужчин и женщин.
• Команды должны иметь одинаковую возрастную кривую / распределение.

Я хотел бы попробовать это в Haskell, но выбор языка кодирования является наименее важным аспектом этой проблемы.

Answer 1

Это проблема упаковки бункера или проблема многомерного ранца . Бьорн Б. Бранденбург создал библиотеку эвристики упаковки бинов в Хаскеле , которая может оказаться вам полезной.

Тебе нужно что-то вроде ...

data Player = P { skill :: Int, gender :: Bool, age :: Int }

Определите количество команд n (полагаю, это функция от общего числа игроков).

Найдите желаемый общий навык на команду:

teamSkill n ps = sum (map skill ps) / n

Найдите идеальное соотношение полов:

genderRatio ps = sum (map (\x -> if gender x then 1 else 0)) / length ps

Найдите идеальное возрастное отклонение (вам понадобится пакет Math.Statistics):

ageDist ps = pvar (map age ps)

И вы должны присвоить трем ограничениям несколько весов, чтобы получить оценку для данной команды:

score skillW genderW ageW team = skillW * sk + genderW * g + ageW * a
  where (sk, (g, a)) = (teamSkill 1 &&& genderRatio &&& ageDist) team

Проблема сводится к минимизации разницы в баллах между командами. Подход грубой силы займет время, пропорциональное Θ (n ^{k − 1} ). Учитывая размер вашей проблемы (8 команд по 12 игроков в каждой), это составляет примерно от 6 до 24 часов на типичном современном ПК.

EDIT

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

1. Выберите команды наугад.
2. Получить оценку для этой конфигурации (см. Выше).
3. Случайно меняйте игроков между двумя или более командами.
4. Получить оценку за новую конфигурацию. Если он лучше предыдущего, сохраните его и перейдите к шагу 3. В противном случае отмените новую конфигурацию и повторите шаг 3.
5. Когда счет не улучшится в течение некоторого фиксированного числа итераций (экспериментируйте, чтобы найти колено этой кривой), остановитесь. Вполне вероятно, что конфигурация, которая у вас есть на данный момент, будет достаточно близка к идеальной. Запустите этот алгоритм несколько раз, чтобы убедиться, что вы не достигли какого-то локального оптимума, который значительно хуже идеального.

Answer 2

Учитывая количество игроков в команде и соотношение полов (которое вы можете легко вычислить). Оставшаяся проблема называется проблема n-разбиения , которая, к сожалению, является NP-полной и поэтому очень трудно точно решить. Вам придется использовать приближенные или эвристические алгоритмы (эволюционные алгоритмы), если размер вашей задачи слишком велик для решения методом грубой силы. Очень простым приближением будет сортировка по возрасту и назначение поочередно.

Answer 3

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

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

Почему?

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

Итак, перечислите своих игроков по критериям вы хотите, чтобы они были разделены : сначала мужчины, затем женщины ... отсортированы по возрасту вторым. Получаем (например):

Player 1: Male - 18
Player 2: Male - 26
Player 3: Male - 45
Player 4: Female - 18
Player 5: Female - 26
Player 6: Female - 45

Затем мы применим алгоритм одиночного исключения, который использует их «ранг» (который является просто номером их игрока) для создания «хороших совпадений».

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

Player 1 in binary (001), reversed becomes 100 (4 decimal) = slot 4
Player 2 in binary (010), reversed becomes 010 (2 decimal) = slot 2
Player 3 in binary (011), reversed becomes 110 (6 decimal) = slot 6
Player 4 in binary (100), reversed becomes 001 (1 decimal) = slot 1
Player 5 in binary (101), reversed becomes 101 (5 decimal) = slot 5
Player 6 in binary (110), reversed becomes 011 (3 decimal) = slot 3

В турнире с одиночным отбором слот 1 играет в слот 2, 3 против 4, 5 против 6. Мы собираемся использовать эти «пары» для генерации оптимальных команд.

Глядя на номер игрока выше, упорядоченный по «номеру слота», вот список, который мы придумали:

Slot 1: Female - 18
Slot 2: Male - 26
Slot 3: Female - 45

Slot 4: Male - 18
Slot 5: Female - 26
Slot 6: Male - 45

Когда вы разделяете слоты на команды (две или более), вы получаете игроков в слоте 1-3 против игроков в слоте 4-6. Это лучшая / оптимальная группировка, которую вы можете получить.

Эта техника очень хорошо подходит для большого количества игроков, нескольких критериев (просто сгруппируйте их правильно) и нескольких команд.

Answer 4

1. Присвойте баллы уровням навыков, полу и возрасту
2. Назначьте сумму очков для каждого критерия каждому игроку
3. Сортировка игроков по их подсчитанному значению
4. Назначить следующего игрока первой команде
5. Назначайте игроков во вторую команду, пока она не наберет> = общего количества очков, чем первая команда или команда не наберет максимальное количество игроков.
6. Выполняйте 5 для каждой команды, возвращаясь к первой команде, пока все игроки не будут назначены

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

Answer 5

Ну

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

Привет.

Answer 6

Идея:

1. Сортировка игроков по навыкам
2. Назначьте лучших игроков по порядку (т. Е. Команда A: 1-й игрок, команда B: 2-й игрок, ...)
3. Назначьте худших игроков по порядку
4. Петля на 2
5. Оцените возможные исправления и выполните их (т. Е. Если у команды A общее умение 19 с игроком с умением 5, а у команды B общее умение 21 с игроком с умением 4, меняйте их местами)
6. Оценить возможные исправления по гендерному распределению и выполнить их
7. Оценить возможные корректировки по возрастному распределению и выполнить их

Answer 7

Почти тривиальный подход для двух команд:

1. Сортировка всех игроков по оценке вашего навыка / ранга.
2. Назначьте команду А лучшим игроком.
3. Назначьте команду B следующим двумя лучшими игроками
4. Назначьте команду A следующим двумя лучшими игроками
5. Перейти к 3
6. Конец, когда у вас нет игроков.

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