[ACCEPTED]-Algorithm to create fair / evenly matched teams based on player rankings-functional-programming

Accepted answer
Score: 21

This is a bin packing problem, or a multi-dimensional knapsack problem. Björn B. Brandenburg 19 has made a bin packing heuristics library in Haskell that you may find useful.

You need 18 something like...

data Player = P { skill :: Int, gender :: Bool, age :: Int }

Decide on a number of teams 17 n (I'm guessing this is a function of the 16 total number of players).

Find the desired 15 total skill per team:

teamSkill n ps = sum (map skill ps) / n

Find the ideal gender 14 ratio:

genderRatio ps = sum (map (\x -> if gender x then 1 else 0)) / length ps

Find the ideal age variance (you'll 13 want the Math.Statistics package):

ageDist ps = pvar (map age ps)

And you 12 must assign the three constraints some weights 11 to come up with a scoring for a given team:

score skillW genderW ageW team = skillW * sk + genderW * g + ageW * a
  where (sk, (g, a)) = (teamSkill 1 &&& genderRatio &&& ageDist) team

The 10 problem reduces to the minimization of the 9 difference in scores between teams. A brute 8 force approach will take time proportional 7 to Θ(nk−1). Given the size of your problem 6 (8 teams of 12 players each), this translates 5 to about 6 to 24 hours on a typical modern 4 PC.

EDIT

An approach that may work well for you 3 (since you don't need an exact solution 2 in practise) is simulated annealing, or 1 continual improvement by random permutation:

  1. Pick teams at random.
  2. Get a score for this configuration (see above).
  3. Randomly swap players between two or more teams.
  4. Get a score for the new configuration. If it's better than the previous one, keep it and recurse to step 3. Otherwise discard the new configuration and try step 3 again.
  5. When the score has not improved for some fixed number of iterations (experiment to find the knee of this curve), stop. It's likely that the configuration you have at this point will be close enough to the ideal. Run this algorithm a few times to gain confidence that you have not hit on some local optimum that is considerably worse than ideal.
Score: 12

Given the number of players per team and 9 the gender ration (which you can easily 8 compute). The remaining problem is called 7 n-partition problem, which is unfortunately NP-complete and 6 thus very hard to solve exactly. You will 5 have to use approximative or heuristic allgorithms 4 (evolutionary algorithms), if your problem 3 size is too big for a brute force solution. A 2 very simple approximation would be sorting 1 by age and assign in an alternating way.

Score: 3
  1. Assign point values to the skill levels, gender, and age
  2. Assign the sum of the points for each criteria to each player
  3. Sort players by their calculated point value
  4. Assign the next player to the first team
  5. Assign players to the second team until it has >= total points than the first team or the team reaches the maximum players.
  6. Perform 5 for each team, looping back to the first team, until all players are assigned

You can tweak the skill level, gender, and 2 age point values to change the distribution 1 of each.

Score: 3

Lets say you have six players (for a simple example). We 37 can use the same algorithm which pairs opponents in single-elimination tournaments and adapt that to generate 36 "even" teams based on any criteria you choose.

First 35 rank your players best-to-worst. Don't take 34 this too literally. You want a list of players 33 sorted by the criteria you wish to separate them.

Why?

Let's 32 look at single elimination tournaments for 31 a second. The idea of using an algorithm 30 to generate optimal single-elimination matches 29 is to avoid the problem of the "top players" meeting 28 too soon in the tournament. If top players 27 meet too soon, one of the top players will 26 be eliminated early on, making the tournament 25 less interesting. We can use this "optimal" pairing 24 to generate teams in which the "top" players 23 are spread out evenly across the teams. Then 22 spread out the the second top players, etc, etc.

So 21 list you players by the criteria you want them separated: men 20 first, then women... sorted by age second. We 19 get (for example):

Player 1: Male - 18
Player 2: Male - 26
Player 3: Male - 45
Player 4: Female - 18
Player 5: Female - 26
Player 6: Female - 45

Then we'll apply the 18 single-elimination algorithm which uses 17 their "rank" (which is just their player 16 number) to create "good match ups".

The single-elimination tournament generator basically works like this: take 15 their rank (player number) and reverse the 14 bits (binary). This new number you come 13 up with become their "slot" in the tournament.

Player 1 in binary (001), reversed becomes 100 (4 decimal) = slot 4
Player 2 in binary (010), reversed becomes 010 (2 decimal) = slot 2
Player 3 in binary (011), reversed becomes 110 (6 decimal) = slot 6
Player 4 in binary (100), reversed becomes 001 (1 decimal) = slot 1
Player 5 in binary (101), reversed becomes 101 (5 decimal) = slot 5
Player 6 in binary (110), reversed becomes 011 (3 decimal) = slot 3

In 12 a single-elimination tournament, slot 1 11 plays slot 2, 3-vs-4, 5-vs-6. We're going 10 to uses these "pair ups" to generate optimal teams.

Looking 9 at the player number above, ordered by their 8 "slot number", here is the list we came 7 up with:

Slot 1: Female - 18
Slot 2: Male - 26
Slot 3: Female - 45

Slot 4: Male - 18
Slot 5: Female - 26
Slot 6: Male - 45

When you split the slots up into 6 teams (two or more) you get the players 5 in slot 1-3 vs players in slot 4-6. That 4 is the best/optimal grouping you can get.

This 3 technique scales very well with many more 2 players, multiple criteria (just group them 1 together correctly), and multiple teams.

Score: 1

Almost trivial approach for two teams:

  1. Sort all player by your skill/rank assessment.
  2. Assign team A the best player.
  3. Assign team B the next two best players
  4. Assign team A the next two best players
  5. goto 3
  6. End when you're out of players.

Not 7 very flexible, and only works on one column 6 ranking, so it won't try to get similar 5 gender or age profiles. But it does make 4 fair well matched teams if the input distribution 3 is reasonably smooth. Plus it doesn't always 2 end with team A have the spare player when 1 there are an odd number.

Score: 1

Idea:

  1. Sort players by skill
  2. Assign best players in order (i.e.: team A: 1st player, team B: 2nd player, ...)
  3. Assign worst players in order
  4. Loop on 2
  5. Evaluate possible corrections and perform them (i.e.: if team A has a total skill of 19 with a player with skill 5 and team B has a total skill of 21 with a player with skill 4, interchange them)
  6. Evaluate possible corrections on gender distribution and perform them
  7. Evaluate possible corrections on age distribution and perform them

0

Score: 1

Well,

My answer is not about scoring strategies of teams/players 3 because all the posted are good, but I would 2 try a brute force or a random search approach. I don't think it's 1 worth create a genetic algorithm.

Regards.

More Related questions