时间戳

首页 > 解决方案 > 基于ELO的团队匹配算法

python - 基于ELO的团队匹配算法

问题描述

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

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

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

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

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

标签： pythonc++algorithmmathcombinations

解决方案

我们可以把它写成一个数学优化问题：

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

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

推荐阅读