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

Question

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

我想到的只是简单地遍历所有可能的球员组合(每支球队 6 名)，球队平均 ELO 之间的最低差异是最终创建的名单。我已经测试了这个选项，它为 18 个注册玩家(玩家数量通常不应超过 24 个)提供了超过 1700 万次计算，因此它是可行的，但绝对是最未优化的方法。

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

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

更新:

• 输入:包含player_id 和elo 的player 列表[]，
• 输出:两个列表: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

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