20

We are a group of people playing floorball together on a regular basis. Every session starts with the daunting task of dividing teams...

So what would be better than an application to pick teams automatically?

So, given a history of team-combinations and results, and a list of people showing up for this particular session, what would be a good strategy to find the optimal teams? By optimal, I mean teams as equal as possible.

Any ideas?

Edit: To make it clear, the data that I have to base the picking on, would be something like this: 

[{ team1: ["playerA", "playerB", "playerC"],
   team2: ["playerD", "playerE", "playerF"],
   goals_team1: 10,
   goals_team2:  8 
 },
 { team1: ["playerD", "playerB", "playerC"],
   team2: ["playerA", "playerE", "playerG"],
   goals_team1:  2,
   goals_team2:  5
 },
 { team1: ["playerD", "playerB", "playerF"],
   team2: ["playerA", "playerE", "playerC"],
   goals_team1:  4,
   goals_team2:  2
 }]
Improve this question
13
  • 4
    What's floorball?
    – Dynamic
    May 29, 2012 at 19:58
  • 1
    I presume that you only have team scores, and no individual contribution score?
    – Gort the Robot
    May 29, 2012 at 19:58
  • 1
    @Dynamic: I'm going to guess it's another name for Floor Hockey - hockey played on a gym floor with a small rubber ball instead of on ice with a puck (and no skates, of course).
    – FrustratedWithFormsDesigner
    May 29, 2012 at 20:05
  • 2
    You may want to clarify that the only information to be used in this algorithm is how many winning/losing teams each player has been on.
    – TehShrike
    May 30, 2012 at 1:56
  • 2
    @TehShrike For each matched played, I have information on who played on what team, and what the end score was. Eg. { Team1: ["a", "b", "c"], Team2: ["d", "e", "f"], Score: "10-5" }
    – Vegar
    May 30, 2012 at 8:59

8 Answers 8

Reset to default
6
+50

The first thing to consider, this is a for something casual. It isn't designing a system to determine rounds for the world cup of floor ball. Its for casual pick up games with a group of people who enjoy a good game rather than a lopsided win.

I recall something of Google having a foosball odds generator. Quite a bit more work was done on that than I am doing on this. Looking for a refrence for that, I found an article in SO and a True Skill calculator that is used by Microsoft for the xbox.

Taking a much more simplistic approach, each player gets the score of the ratio of points their team has for the game. For Game 1, player A would get 1.25 (10/8) while player D would get 0.8 points (8/10). Find the mean of all the numbers and that is the player's score.

For the set of games described, this provides:

  A 1.42
  B 1.22
  C 0.72
  D 1.07
  E 1.27
  F 1.40
  G 2.50

At this point, you have a problem similar to that of the partition problem with the constraint that each team needs the same number of players and values need not be exact (but just as close as possible).

Improve this answer
2
  • Same number of players, or as close as it gets if it shows up an odd number of players ;-)
    – Vegar
    Jun 2, 2012 at 16:00
  • Thanks for the reference to partition problem! You rock, @user40980
    – Eric Gopak
    Jan 4, 2017 at 20:09
3

Quick and dirty approach:

Calculate a score for every player that is the total points for the side that player was on divided by the total points in the game for every game they participated in. Then sort players by score. Place the first player on team A. Then for each player, add them to the team with the lowest aggregate score until half the players are on one team. All remaining players go on the other team.

Improve this answer
3
  • This approach may work, even if the given combination of people is totally new.
    – Vegar
    May 29, 2012 at 21:07
  • Doing better looks like a variant of the knapsack problem. The weights might be relevant too - the way I remember it, the heaviest player (me) was always picked last.
    – user8709
    Jun 1, 2012 at 20:54
  • This greedy approach is known to give a 4/3-approximation to the optimal solution (Wikipedia)
    – Radek
    Jun 24, 2012 at 13:39
3

If you don't want to dig into the heady world of Bayesian priors(pdf) and such, an interesting approach is to assign a total order to all players (based on win/loss ration, cumulative points, etc) and then divide into teams using the parity function as follows.

Take the sorted list of players (best to worst) and separate them into teams Even and Odd based on the number of 1 bits in their index (starting at 0). That gives the following distribution:

  • 0000 (best) - Even
  • 0001 - Odd
  • 0010 - Odd
  • 0011 - Even
  • 0100 - Odd
  • 0101 - Even
  • 0110 - Even
  • 0111 - Odd

...etc.

The parity function will ensure an equal number of players on each team, for any even number of players. It will then alternate giving the advantage of the odd numbered player to one team or the other in such a way that the effects tend to balance out over time.

This function works best when the distribution of player skill is flat. In reality, player skill tends to follow the "sum of random values" distribution, a.k.a. the Gaussian (although beware blanket applications of that assumption in systems such as TruSkill.)

In order to compensate for large skill gaps, you can apply permutations to this list. For example, to counter a very strong top player 0000, you can swap player 0011 with a lower-ranked Odd player, such as 0100. This is where things get hand wavy, but at least it provides a good starting point that doesn't require an accurate measure of absolute skill, but simply an ordering based on relative skill.

Improve this answer
2

Depending on how much time you have, start the first few sessions by randomly selecting team captains, and have a draft before each game. Keep track of which pick a players goes. Earlier picks get higher ratings:

Round #1 = 8 pts, Round #2 = 6 pts, Round #3 = 4 pts, etc

Winning a game = 5 pts

All of this will depend on number of players per team. The total points may need to be converted to a daily or game average if there is a large discrepancy in participation. You may also award a team for a larger margin of victory.

Players who were selected early and played on a winning team get the most power points.

Then let the computer do the drafting (selecting of teams) by balancing the power points for each team and putting teams with near equal ratings against one another. Players who get selected early, but continue to play on losing teams will drop in the rankings.

Improve this answer
2
  • Great answer! This can work for the average team, but some teams are strategic. For example, if you want you're entire team to be defenders, then you would have worse overall players going in higher rounds. But, I guess I didn't ask for canonical :P. Thanks!
    – Dynamic
    Jun 1, 2012 at 21:16
  • That's a great way to start. For the first few rounds, anything based on team score isn't going to apply individually as you'll have team members that play together in every round.
    – Gort the Robot
    Jun 1, 2012 at 23:30
1

Easiest solution would be to provide a grade/weight of the estimated skill and try to balance the score for each team.

From there, you could seed a bayesian network with these values and then you'd infer backwards based on the observed result of each matchup in the historical data you have.

As a point of interest on my part: Infer.NET makes this relatively easy to envision and potentially implement, and it could predict the odds of a win given team matchups. Infer.NET is something that I'm really starting to get into lately.

Improve this answer
3
  • Would you have enough data to be meaningful give that there would likely be only a handful of games?
    – Gort the Robot
    May 29, 2012 at 20:01
  • I was hoping to solve this with javascript or ruby, but infer.net looks interesting anyway.
    – Vegar
    May 29, 2012 at 21:03
  • @StevenBurnap: Depends on how good/accurate your initial guesses are as to player ability - which you'll have to do for most or all systems. The benefit of using the network is that you'll be able to infer new scores for each player as time goes on to improve that value.
    – Steven Evers
    May 30, 2012 at 0:47
1

Let us assume for the sake of discussion you can assign each player an integer value and those values add up, that is a player with score X is as valuable as three players with scores A,B and C, if A+B+C = X. The goal is then to separate the group into two teams so that both teams have about equal summed value.

This is the optimisation version of the famous PARTITION problem which is NP-complete. Therefore, your problem is for all we know hard to solve. However, PARTITION is weakly NP-complete and admits some reasonable approximation strategies.

One example is a greedy approach similar to what Steven proposes. This is a 4/3-approximation, that is the stronger team is never more than about 33% stronger than an in optimal split.

Note that you probably have additional constraints such as you need at least a fixed amount of players per team. So if you put Michael Jordan in a class of preschoolers, you won't be able to create nearly fair teams that have full number. Such a (constant) lower bound on team size should not impact the hardness of the underlying problem but it might destroy approximation bounds valid for the general problem.

Improve this answer
5
  • 1
    You can't fit very many players on a gym floor. With as many as 20 players, assuming you want 10 on a side, there are only 92378 combinations to check. But it doesn't take very many players before the number of combinations makes an exhaustive search impractical.
    – kevin cline
    May 29, 2012 at 22:43
  • @kevincline: Right. I implicitly assumed that brute force was not an option (otherwise, why ask?).
    – Raphael
    May 30, 2012 at 7:22
  • There would never be more than six persons on each team. More often four.
    – Vegar
    May 30, 2012 at 9:01
  • @Vegar: Then your question is more how to exploit team scores to model player value and less about algorithms, right?
    – Raphael
    May 30, 2012 at 9:10
  • 1
    Unless you can figure out a way to truly score people exactly by their talent, accuracy in the algorithm is probably not that important. With the problem at hand, we only have team score and a handful of trials. Any player rating is going to be a wild estimate.
    – Gort the Robot
    Jun 1, 2012 at 20:28
0

How ridiculous do you want to get? You can always use multiple linear regression to generate coefficients for each player based on the scores of their teams in previous games. Then sort the list and select.

In reality it probably wouldn't work since it doesn't model the dynamic between players, but it'll give you a reason to play around with R. (<-- see, I kept it programming related)

Improve this answer
1
  • 1
    I'm considering making an application to avoid a 2 min task twice a week, forcing me to spend nearly the same amount of time recording results for future computations. So quite ridiculous I guess...
    – Vegar
    May 30, 2012 at 10:19
-1

If you want your algorithm to be reasonably, simple algorithms just won't cut it. They will often give you strange results

You will have to go with something like ELO or Trueskill system (ELO does not work for teams without modifications, though).

Improve this answer
1
  • 1
    This isn't true. There has to be an algorithm that would work.
    – Dynamic
    Jun 3, 2012 at 0:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.