CODEWITHSUNDEEP
math
user1162099
user1162099

Reputation: 33

Multi player team game: Auto team-balancing algorithm based on player rank

Setting: Multiplayer team game.

Problem: Each player has a 1 to 5 star rating which is calculated based on their player stats. I was hoping to find an algorithm that assigns teams to these players in the fairest possible way.

There are two teams, with a maximum of 5 players per team.

Let's say 6 players join the server. It would be desirable that the server assign the teams like this:

  1. 5 star player
  2. 3 star player
  3. 3 star player

VS

  1. 5 star player
  2. 4 star player
  3. 2 star player

..as opposed to this

  1. 5 star player
  2. 5 star player
  3. 4 star player

VS

  1. 3 star player
  2. 3 star player
  3. 2 star player

In the first example, there are a total of 11 stars per team, whereas in the second example, one team has a total 14 stars, while the other has 8.

Sorry I couldn't be any more succinct.

Upvotes: 3

Views: 3949

Answers (6)

adrianton3
adrianton3

Reputation: 2358

Check this: http://www.stanford.edu/class/cme305/References/approx.pdf (archived: https://web.archive.org/web/20120115104738/http://www.stanford.edu/class/cme305/References/approx.pdf)

Alternative #1: you could try 100 random ways of grouping players and keep the best solution.

Alternative #2: if you have under 20 players or so you can check EVERY possible configuration (2^20 ~= 1 million candidate configurations).

Upvotes: 3

Elementrix
Elementrix

Reputation: 11

I was actually coding an algorithm for this problem. And the solution I came up with was this.

Let's take players with scores: {1, 6, 2, 1, 6, 7, 4, 2}

Sorting these players yields: {1, 1, 2, 2, 4, 6, 6, 7}

Now for a close approximation of the final result, we take each alternate player for team 1, and the remaining players are in team 2. So we have these:

Team 1: {1, 2, 4, 6} -> sum of players = 13

Team 2: {1, 2, 6, 7} -> sum of players = 16

So the difference between Team 1 and Team 2's scores is 3. We want to minimize the difference between their scores. So now we can check if swapping two player's give a smaller difference between the sums of the scores.

So we can start this process at the first player since they have the same score, it wouldn't improve the difference between the teams. So would the second player. However, when we get to the third player in both teams, if we swap those players, the sum of Team 1 now becomes 15 and the sum of Team 2 becomes 14. The difference would then be 1, which is better than our previous difference of 3. So now the teams would be like so:

Team 1: {1, 2, 6, 6} -> sum = 15

Team 2: {1, 2, 4, 7} -> sum = 14

We then compare the 4th player in both teams. Does swapping these players make the difference between the sums any better?

If we swap these players, the sum of Team 1 would become 16 and the sum of Team 2 would become 13. This is a difference of 3. This swap would create a difference in the sum that is larger than the current difference. So we don't do this swap.

In terms of time complexity, this is an O(nlogn) algorithm since we're sorting which is O(nLogn) and we're doing linear searches through the teams.

This is an NP-Hard problem and so this algorithm is a very good approximate of the best team if not the best.

Upvotes: 1

Sibbo
Sibbo

Reputation: 3914

First, add up all stars and divide the sum by 2. The sort your player list by the count of stars they have. Next, add the best player to team one, the second to team two, the third to team one and so on. This will give good results, but they can be far away from being perfect. For example if you have 5,1,1,1 stars players. It would result in 5,1 VS 1,1.

Now you can calculate the difference between the teams and pick some players from both teams to exchange them. You could do this by picking the strongest player from the stronger team and picking a weaker player from the other team, so that exchanging them would result in perfect teams. If this is impossible, pick a player with one star less than the strongest from the stronger team and try to perform the same action and so on.

But you should be careful if you assign different player counts to each team, because every player is an agent on his own, being able to act simultaneously. Adding a "one player more star addition" could help here. But without knowing your game, I can't tell you more about that.

Upvotes: 2

Dialecticus
Dialecticus

Reputation: 16761

Those stars should be treated as hints, and not as actual skill level. I would pair up the best and the worst in one team, and second best and second worst in another, and distribute the rest so that sum of stars in each team is closest to half of total sum.

Upvotes: 1

Silly Freak
Silly Freak

Reputation: 4231

the most basic solution is to first add up all player ranks, divide it by two, and then try to reach that number by adding players. It's the same as collecting exact change, for which are probably nice algorithms out there.

this doesn't account for some special cases. for example, if there are players 1, 1, 1, 1, 2, 2, putting together all ones and all twos is not the fairest distribution.

but when something is fair is an even harder question, teamwork between good players coming in. also, considering that player ranking is probably far from perfect, I'm not sure overoptimizing this algorithm would be productive.

Upvotes: 1

PfhorSlayer
PfhorSlayer

Reputation: 1366

Couldn't you just average the scores of all the players, then pick the three for each team whose average score is closest to the average of all players?

You could select the correct players for each team by assigning the highest two players to separate teams, then average the permutations of the remaining four numbers and choose the one that most closely balances the teams.

I'm sure there would be a more logic-based solution for getting the last two members of each team as well.

Upvotes: 3

Related Questions