Matchmaking algorithm for a game

Question

(This is for a game I am designing) Lets say that there are 2 teams of players in a game. Each team will have 4 players. Each player has a rank(0-9), where 0 indicates a bad player and 9 indicates an amazing player. There is a queue (or list) of players who are waiting to play a game (This could be a small number or a very large number). Lets say that each teams' overall rank is an average of the 4 players within in. There are multiple open games and teams where a player can be placed.

Question: What is a good algorithm that places a player in the waiting queue/list on a team so that each team in a game will have more or less the same overall rank in a game (Does not have to be perfect)? Also, the players should not have to wait more than a minute to be placed on a team(Can be more if very little players) [The faster they are placed, the better]

Answer 1

This completely depends on how closely the teams's combined rankings need to be. If accuracy isn't that important, you can do something simple like this:

1. Take the first eight players off of the list.
2. Place highest-ranking player on team A and second-highest on team B
3. There are six players remaining, which means you have 20 team combinations left. Calculate all 20 and choose the combination that leads to the closest team scores.

This should be fast and simple, although it probably won't produce the most balanced results. Wait times should be minimal because it always uses the players who have been waiting the longest. Step 2 is really a shortcut to eliminate the number of possibilities to calculate. Without step 2, there are 70 possible team combinations ("8 choose 4"). You may find that you can calculate all 70 and find a good solution without taking up too much time. Hint: the ideal team score is (sum of all players / 2). If you stumble across a combination with that particular team score, you can stop.

You can refine this a step further if you'd like. Once you find the best possible matchup of the eight, compare the two team scores. If they are too far apart (you'd have to define what constitutes "too far"), replace two players at random with the next two on the queue and try again. You can even make the definition of "too far" become more lenient based on how long a player has been waiting.

You can also take a slightly different approach to this. Group players into teams randomly, and then look for two teams that have similar rankings (which becomes as simple as comparing a single number). Once a team has gone a specified amount of time without finding a match, return those players to the pool to be re-formed into new teams. If you typically have a large number of players queued (thus a larger pool of ready-made teams), then this might give results faster.

Before you spend too much time on this algorithm, take a good look at the algorithm that generates the player ranking. Human skill and experience can't be summarized in a single digit without a relatively large margin of error. If the error here is likely to be reasonably large, then you can afford to have a less-accurate team building algorithm (any extra accuracy would be nullified by the error in the player ranking system).

Answer 2

You should start to build the table with one person. If person A has a rank of 8, and another player joins the game with a rank of 4, and your placement guide is a factor of 2, then

Player A has the table Player A has a rank of 8

Player B enters the room Does player B not have a rank between 6 & 10?

if (Brank < Arank - 2 || Brank > Arank + 2)

If that is true, then the rank is not within the limits of the table and you should start a new table with Brank as the rank you compare to.

If that is false, then the rank is +- 2 of the table's declared rank and that player can join.

If you really want to get fancy, you can declare the ranking based on the number of people waiting for a table.

If 100 people in lobby, make the limit +- 2. If 15 people in lobby, make the limit +- 4. (make it more uneven game, but will not cause people to wait as long).