基于ELO的团队匹配算法

Question

我正在寻找一种非常简单的方法，用未知（但已知）数量的球员组建2支球队。因此，这实际上不是一个标准的配对，因为它只为特定的比赛在整个注册球员池中创建一场比赛。我几乎只有一个变量，它是每个球员的ELO分数，这意味着它是唯一可以用来计算的选项。

我想到的只是简单地检查每一个可能的球员组合（每队6名），球队平均ELO之间的最小差异是最终创建的名册。我已经测试过这个选项，它为18名注册玩家提供了超过1700万次的计算（玩家数量通常不应该超过24名），所以这是可行的，但绝对是最不理想的方法。

所以我决定在这里问一个问题，也许你能以某种方式帮助我。在所有可能的组合的直接比较中，我可以使用什么简单的算法或者优化某些东西的方法。

如果你想提供任何代码示例，我几乎可以阅读任何代码语言，所以这并不重要。

UPD。基本上，输入是包含玩家“id”和“elo”的玩家对象列表[]，输出应该是包含玩家对象的2个团队列表team1[]和team2[]。两个团队的平均ELO应尽可能接近。

Answer 1

以下是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 ];

主要决策变量是数组团队。它将每个玩家分配到其中一个团队（0=无团队）。为了找到接近的ELO平均值，我将ELO总和相加，并强制执行所有团队总和的最小值和最大值是相近的。

Answer 2

考虑到你的方法是一个近似的方法，付出太多的努力来产生一个完美的答案是一个失败的原因。取而代之的是选择一个合理的差异，并从那里开始。

我建议你按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））预期的工作。

结果是，您摆脱了偶数/奇数逻辑。是的，您添加了一些额外的工作，但是最大的工作是排序list8。这是足够快的，即使你有100人投它，你仍然会产生非常快的答案。

结果将是两个势均力敌的球队，这样当他们靠实力配对时，较弱的球队至少有合理的机会表现出令人信服的沮丧。

Answer 3

我们可以把它写成数学最佳化问题：

假设我们有球员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

令人惊讶的是，对于这个数据集，我们可以找到一个完美的匹配。