# Match Making Groups of Players

Given a situation where I have a pool of X people of different scores (ranks) S with game size N. How do I partition the pool into N sized games where the standard deviation of ranks for each games is minimized?

(quality of the game is inversely proportional to STD of ranks)

• Possible duplicate of gamedev.stackexchange.com/questions/464/… though a smaller subset. – The Communist Duck Dec 22 '10 at 15:47
• @The Communist Duck I don't really want a framework. I'm looking to code it myself, so I need an algorithm (or heuristics). – Kendall Hopkins Dec 22 '10 at 16:05
• It's not clear what you want to happen when N|X fails. Does N vary over some range? Can I make games with anywhere between 2 and N players? Are you looking to minimize the mean, total, or some other function of the standard deviations? – user744 Dec 23 '10 at 11:10
• @Joe Wreschnig You can assume N % X == 0. Any N is an acceptable number, but N = 1 is the trivial case. – Kendall Hopkins Dec 23 '10 at 15:33

## 2 Answers

This is probably not mathematically optimal (optimality in this case reeks of NP to me, but I'm not certain), but assuming N is fixed and a unimodal, approximately normal S distribution you should be able to get something close to optimal just sorting by rank and slicing a group off every N players.

If your values for X and N are very large, it would probably make the most sence to keep the player list sorted by Rank such that you could always take the bottom N elements to create a group. This will front-load your computation time (keeping the list sorted every time you add a new item), in contrast with the above algorithm which would require execution every time a new group is to be created.

• I've looked over this algorithm a bit and I can't understand the logic or it's result at all. Could you explain it a bit more? Why would I want a groupMembers filled with the index of players with the smallest rank? I've reworded the question, maybe that'll help make what I'm asking for more clear. – Kendall Hopkins Dec 23 '10 at 0:57
• -1 - I think you're trying to do the same thing I suggested, but your actual code is nonsense. If players[0] has the smallest rank, your code provides garbage in groupMembers. If players[0] has the second-smallest, your code produces a group of N copies of the smallest group member. And so on. – user744 Dec 23 '10 at 11:20
• After rereading the question and your updated explination, my code (even fixed) wouldn't have done what you want; that said, it is wrong, I'd copied it and removed some important bits. – Nate Dec 23 '10 at 16:14