1
$\begingroup$

I organize amateur tournaments every week with random players. Every week, players sign up, and I get a list with:

  • Name
  • Rank (1, 2 or 3)
  • Role (s) (DPS, TANK and HEALER)

I need to get balanced teams of 6. Ideally, there are 2 DPS, 2 TANKS and 2 HEALERS but in practice there are not enough healers and I have to make 3 DPS, 2 TANKS and 1 HEALER.

The other problem is that some players register together, up to 3 players grouped.

The process is currently done by hand but I would like to automate it.

I learned about the algorithm Knapsack problem, is this a good track?

Do you have any advice to help me in my research?

Thanks you.

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! How should the rank affect the groupings? What makes a team balanced? Is it that it has an equal number of each role (ideally)? $\endgroup$ – D.W. Mar 2 '18 at 17:39
1
$\begingroup$

One plausible approach is to use local search. In its simplest form, you could start by randomly assigning people to teams, then repeatedly picking a random pair of people and swapping them gives a better assignment, and iterating. This kind of approach should be easy to implement and flexible. But there's a lot more to say, so let me explain in more depth.

First, you need an objective function: a way to measure, quantitatively, how good a candidate assignment is. In your case, you might define a way of computing a penalty score for any proposed team grouping (say, 2 point penalty for each extra or missing DPS, 2 point penalty for each extra or missing tank, 2 point penalty for each extra or missing healer, 3 point penalty for each extra person on the team over 6 or each missing person under 6; or whatever, you pick the penalty scheme). Then you could plausibly define the objective function to be the sum of the penalty scores of all of the teams, and your goal is to find an assignment that minimizes this total penalty.

Next, you use some local search procedure to find an assignment that makes the total penalty as small as possible. The simplest is hillclimbing, which works as follows. Pick an arbitrary initial assignment (e.g., randomly assign each person to a team; or use any other heuristic method of computing an assignment -- it doesn't have to be optimal). Then, in each iteration you randomly pick a modification to the assignment, check whether the proposed modification reduces the total penalty, and if so, you apply the proposed modification. Repeat this over and over, until you go a long time with no improvement.

You need a way to generate a random modification. A simple one would be to randomly pick two people, and swap which team they are on. You can also consider more complex modifications. For instance, randomly pick three or fourpeople, and randomly permute them among their teams. Or, randomly pick two people on two different teams, then randomly assign the first person to one of the two teams, then randomly assign the second person to one of the two teams (so this might put both people onto the same team; this modification is useful if you want to consider solutions where some teams have more than 6 people or fewer than 6 people).

This should be easy to program, and I suspect it'll give a reasonable solution. I suggest trying it and see if you're happy with the solutions it generates.

There are a number of ways to make this more sophisticated, to try to generate solutions that are even better (lower total penalty). You can use a more sophisticated form of local search. For instance, you could try hill-climbing with random restarts, where you do the above process 100 times from 100 different random initial assignments, and keep the best solution found. You could also try simulated annealing, where if the modification makes things worse we still have a (small) probability of applying the proposed modification, and we reduce this probability over time in a specific way.

You'll have to modify this to deal with people who pre-register as a group. Fortunately, it should be easy to generate modifications that respect this constraint. For instance, suppose you randomly pick two people to swap, say Alice and John. If you Alice is part of a pre-registered group with one other, then you might randomly pick someone on John's team so you can swap Alice + her partner with John + that additional person. There are many possibilities; you should be able to select something that makes sense for your particular situation.

$\endgroup$
  • $\begingroup$ Hello, I did what you advised me and it worked great! Thanks a lot for that. Now, I would like to know if a deep learning could be viable to achieve the same challenge? $\endgroup$ – LightMan Jul 10 '18 at 8:58
  • 1
    $\begingroup$ @LightMan, no. Deep learning is not magic. It is for supervised machine learning. This is not a supervised machine learning problem. $\endgroup$ – D.W. Jul 10 '18 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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