Алгоритм организации командных матчей на основе ELO

Question

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

То, о чем я думал, - это просто проходить все возможные комбинации игроков (по 6 в каждой команде), и самая низкая разница между средним ELO команд - это финальные списки, которые создаются. Я проверил эту опцию, и она дает мне более 17 миллионов вычислений для 18 зарегистрированных игроков (количество игроков обычно не должно превышать 24), так что это выполнимо, но это, безусловно, самый неоптимизированный способ сделать это.

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

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

UPD. в основном входные данные должны представлять собой список [] объектов игрока, которые содержат «id» и «elo» игрока, выходные данные должны быть 2 списками команд team1 [] и team2 [], содержащие объекты игрока. Средний ELO обеих команд должен быть как можно ближе.

Answer 1

Мы можем записать это как математическую задачу оптимизации:

Скажем, у нас есть игроки i=1..24 и команды j=1,2. Введите переменные решения:

 x(i,j) = 1 if player i is assigned to team j
          0 otherwise

Тогда мы можем написать:

 Min |avg(2)-avg(1)|
 subject to
     sum(j, x(i,j)) <= 1    for all i  (a player can be assigned only once)
     sum(i, x(i,j)) = 6     for all j  (a team needs 6 players)
     avg(j) = sum(i, rating(i)*x(i,j)) / 6   (calculate the average)
     avg(j) >= 0         

Мы можем линеаризовать абсолютное значение в задаче:

 Min z
 subject to
     sum(j, x(i,j)) <= 1    for all i
     sum(i, x(i,j)) = 6     for all j
     avg(j) = sum(i, rating(i)*x(i,j)) / 6
     -z <= avg(2)-avg(1) <= z
     z >= 0, avg(j) >= 0

Теперь это задача линейного смешанного целочисленного программирования. Решатели MIP легко доступны.

Используя некоторые случайные данные, я получаю:

----     43 PARAMETER r  ELO rating

player1  1275,    player2  1531,    player3  1585,    player4   668,    player5  1107,    player6  1011
player7  1242,    player8  1774,    player9  1096,    player10 1400,    player11 1036,    player12 1538
player13 1135,    player14 1206,    player15 2153,    player16 1112,    player17  880,    player18  850
player19 1528,    player20 1875,    player21  939,    player22 1684,    player23 1807,    player24 1110


----     43 VARIABLE x.L  assignment

               team1       team2

player1        1.000
player2                    1.000
player4        1.000
player5                    1.000
player6                    1.000
player7        1.000
player8        1.000
player9        1.000
player10                   1.000
player11                   1.000
player17       1.000
player18                   1.000


----     43 VARIABLE avg.L  average rating of team

team1 1155.833,    team2 1155.833


----     43 PARAMETER report  solution report

               team1       team2

player1     1275.000
player2                 1531.000
player4      668.000
player5                 1107.000
player6                 1011.000
player7     1242.000
player8     1774.000
player9     1096.000
player10                1400.000
player11                1036.000
player17     880.000
player18                 850.000
sum         6935.000    6935.000
avg         1155.833    1155.833

Удивительно, но для этого набора данных мы можем найти идеальное совпадение.

Answer 2

Вот решение в MiniZinc:

% Selecting Chess Players

include "globals.mzn";

int: noOfTeams = 2;
int: noOfPlayers = 24;
int: playersPerTeam = 6;

set of int: Players = 1..noOfPlayers;
set of int: Teams = 1..noOfTeams;

array[Players] of int: elo = 
  [1275, 1531, 1585,  668, 1107, 1011,
   1242, 1774, 1096, 1400, 1036, 1538,
   1135, 1206, 2153, 1112,  880,  850,
   1528, 1875,  939, 1684, 1807, 1110];

array[Players] of var 0..noOfTeams: team;
array[Teams] of var int: eloSums;

%  same number of players per team
constraint forall(t in Teams) (
     playersPerTeam == sum([team[p] == t | p in Players])
  );

%  sum up the ELO numbers per team
constraint forall(t in Teams) (
     eloSums[t] == sum([if team[p] == t then elo[p] else 0 endif | p in Players])
  );

%  enforce sorted sums to break symmetries
%  and avoid minimum/maximum predicates          
constraint forall(t1 in Teams, t2 in Teams where t1 < t2) (
    eloSums[t1] <= eloSums[t2]
);

solve minimize eloSums[noOfTeams] - eloSums[1];

output ["\n             "] ++ ["team" ++ show(t) ++ "  " | t in Teams] ++
       ["\n"] ++
       [ if fix(team[p]) != 0 then
             if t == 1 then 
                "\nplayer" ++ show_int(-2,p) ++ " " 
             else 
                "" 
             endif ++
             if fix(team[p]) == t then
                show_int(8, elo[p])
             else
                "       "
             endif
         else 
           "" 
         endif 
         | p in Players, t in Teams ] ++
         ["\nsum     "] ++
         [show_int(8, eloSums[t]) | t in Teams ] ++
         ["\navg        "] ++
         [show_float(8,2,eloSums[t]/playersPerTeam) | t in Teams ];

Основной переменной решения является массив team. Он назначает каждого игрока в одну из команд (0 = нет команды). Чтобы найти среднее значение ELO , я суммирую суммы ELO и обеспечиваю, чтобы минимум и максимум всех командных сумм были близки друг к другу.

Answer 3

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

Я бы предложил вам отсортировать список игроков по ELO, а затем объединить их в пару. Эти люди будут в противоположных командах, если они включены. Если есть нечетное количество людей, оставьте человека, который находится дальше всех. Сортируйте пары по разности и объединяйте их одинаково. Это дает вам достаточно равномерно подобранные группы по 4, и команды будут лучшими и худшими по сравнению со средними 2. Эти группы из 4, как правило, должны быть относительно близки к четным. Оцените это как лучшую группу минус худшая. (Любая половина может оказаться лучше в зависимости от фактических результатов.)

Теперь найдите 3 группы из 4, чтобы A было как можно ближе к сумме B и C. Лучшая группа из A пойдет с худшими группами из B и C.

Для 24 человек это будет практически мгновенный расчет и даст разумные результаты.

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

---

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

1. Сортировка ваших игроков. Поместите каждого игрока в пару с человеком выше и ниже. С n игроками это будет n-1 пар. Дайте каждой паре оценку либо разницы ELO, либо того, насколько более вероятно, что чем лучше, тем лучше. (То, что я выбрал бы, зависит от того, как эти двое играют.)
2. Сортировка ваших пар. Соедините каждую пару с ближайшей парой сверху и снизу, которая не пересекает ее. С n-1 парами это обычно приводит к n-2 группам по 4.
3. Создайте отсортированный список групп из 4. Назовите его list4. Обратите внимание, что этот список имеет размер n + O(1).
4. Составьте список всех групп по 8, которые можно составить из 2 групп по 4, которые не пересекаются. Сортируй это. Назовите это list8. Формула того, насколько большой этот список, сложна, но составляет n^2/2 + O(n) и заняла время O(n^2 log(n)) для сортировки.
5. Для каждого элемента list4 найдите ближайшие элементы в list8, которые находятся над / под ним и не имеют общих игроков с ним. Для O(n) элементов это O(log(n)) ожидаемая работа.

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

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