基于ELO的团队匹配算法

Question

我正在寻找一种非常简单的方法,可以将2支球队从未指定(但已知)的球员中挑出来.所以它实际上并不是一个标准的配对,因为它只为整个特定比赛的注册球员创造了一场比赛.我确实只有单个变量,它是每个玩家的ELO分数,这意味着它是唯一可用于计算的选项.

我想到的只是简单地通过一个球员的每个可能的组合(每个球队6个)和球队的平均ELO之间的最低差异是最终的名单.我已经测试了这个选项,它给了我18个注册玩家超过17mil的计算(玩家的数量通常不应超过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

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