An algorithm to generate balanced pickup soccer teams

Introduction

7 min readDec 1, 2022

In this brief article I will explain an algorithm that I developed to solve a real-life problem I had: Every Wednesday, I gather with some friends in the town I live to play pickup soccer (in Brazil, we call it “pelada”). We tried a couple apps that — allegedly — sort and generate balanced teams, but in reality there was always a team or two that was clearly above the others.

So I decided to delve into the problem and try to come up with a solution, and that’s what we are going to see right now, following the code step-by-step ;)

The code is available in this GitHub repository.

Input Data

First, let’s start by the input data needed for the sorter. The only data needed is a CSV file with three columns: player, rating and is_going. The first is the player name, the second is the player’s ability score (for our games we use a 5 star rating system, but it can be any range) and the last is a boolean column indicating who is going to participate in the game (we need this because we play with 20 people but we have more on the group, so for each game we need to mark who is going) — so, every week before I run the script, I first need to alter the input data to get the players that will come.

Header of the CSV input file — names are fictional

Preprocessing

After reading the CSV file to a pandas DataFrame, we need to filter only the rows where is_going == 1. After that, we get the rating groups (each group is constituted by all the rows with the same rating) and shuffle each group. We concatenate the shuffled groups into a DataFrame and sort by rating in descending order. The result is a DataFrame sorted by best player to worst, but since we shuffle the groups, each time you run the script, the result (within the groups) will be different. This shuffle is important because (as we’ll see in the next section) the solution relies on the order of the rows, and if it was not done, we would always get the same order and hence the same teams.

df = pd.read_csv('PlayersRatings.csv')

df = df.loc[df['is_going'] == 1]
groups = [df for _, df in df.groupby('rating')]
random.shuffle(groups)

df = pd.concat(groups).reset_index(drop=True)
df = df.sort_values(by='rating', ascending=False).reset_index(drop=True)

Resulting DataFrame. For a second run, each group would be different (e.g. [Marcos, Luciano, José, Victor, Wesley] for 5-star group)

Initial Solution

The goal of the algorithm is to produce 4 teams of 5 players which are as balanced as possible. Before I developed an optimized solution, I had a first try that was based on the snake draft concept. In fantasy football (for those who don’t know, it is an online game in which people unite in a league and select players from the NFL, with their performance on the field reflecting in points for your fantasy team), each manager chooses which players he will hold for the whole tournament, and this is done in many rounds (this process is known as draft). The order in which each manager picks is random, but it would be really unfair if the manager who picks first, does so for all the rounds; that’s where the snake part comes in: It basically reverses the picks, so whoever picks first on the first round, will be the last to pick on the second round and the first again on the third round, the second to pick will be the second-to-last and than second again, …, the last to pick in each round always makes consecutive picks. This tends to produce balanced teams (of course, if each manager drafts well), so I thought I could apply it to my problem as well.

Illustration of the snake draft concept — the first three rounds of a league with four managers.

This is why we needed to sort the DataFrame by rating. We will simulate a snake draft, with the first of the 4 teams picking the first player (index 1 of the DataFrame), but the next chosen player will be the 8th (then the 9th, and finally the 16th and 17th). Then, the teams will be like this:

Team 1: 1, 8, 9, 16 and 17;
Team 2: 2, 7, 10, 15 and 18;
Team 3: 3, 6, 11, 14 and 19;
Team 4: 4, 5, 12, 13 and 20

Translating into code, there is a function called find_teams that receives a list of 20 numbers in which each entry is a number from 1 to 4 that indicates the team — so, in our example, this input list would be [1,2,3,4,4,3,2,1,1,2,3,4,4,3,2,1,1,2,3,4]. The function then gets the DataFrame indexes and filters to find each team.

The function returns the four teams and a metric called max_diff, which is what we are trying to optimize: We first calculate the average rating for each team and then the difference between the maximum and minimum averages. The lower this value, the better — if all teams have the same averages, max_diff = 0 and we have teams perfectly balanced (remember that the concept of “balanced” also depends on the ratings you attribute to each player, so it is extremely important to get them right!!).

def find_teams(guess):
    indexes_team1 = [i for i, e in enumerate(guess) if e == 1]
    indexes_team2 = [i for i, e in enumerate(guess) if e == 2]
    indexes_team3 = [i for i, e in enumerate(guess) if e == 3]
    indexes_team4 = [i for i, e in enumerate(guess) if e == 4]

    team1 = df.loc[indexes_team1]
    team2 = df.loc[indexes_team2]
    team3 = df.loc[indexes_team3] 
    team4 = df.loc[indexes_team4]

    avgs = [x["rating"].mean() for x in [team1, team2, team3, team4]]
    max_diff = max(avgs) - min(avgs)
    return team1, team2, team3, team4, max_diff

initial_guess = [1,2,3,4,4,3,2,1,1,2,3,4,4,3,2,1,1,2,3,4]
team1, team2, team3, team4, max_diff = find_teams(initial_guess)

We print the solution on the terminal with the help of a function print_teams:

def print_teams(team1, team2, team3, team4, max_diff):
    for x in [team1, team2, team3, team4]:
        x["aux"] = x["player"] + " (" + x["rating"].astype(str) + ")"
        
    print('Team 1: ', team1.aux.values)
    print('Team 2: ', team2.aux.values)
    print('Team 3: ', team3.aux.values)
    print('Team 4: ', team4.aux.values)
    
    print('\nAverage team 1: {:.2f}'.format(team1['rating'].mean()))
    print('Average team 2: {:.2f}'.format(team2['rating'].mean()))
    print('Average team 3: {:.2f}'.format(team3['rating'].mean()))
    print('Average team 4: {:.2f}'.format(team4['rating'].mean()))
    
    print('Diff best vs worst team: {:.2f}'.format(max_diff))

print('Initial Solution: \n')
print_teams(team1, team2, team3, team4, max_diff)

Output of the Initial Solution. We can see that the teams are fairly balanced, but there is still room for improvement.

Optimized Solution

This initial solution was used for a while and everything was going fine, until a day where the distribution of ratings was more unbalanced than usual (many 5-star to few 3-star players), and the teams generated were not as balanced (max_diff = 0.4 or even 0.6). So I had to go back and try to think of a more optimized solution. I thought about genetic algorithms, permutation testing after initial solution and other crazy stuff, but it was overkill. In reality, a simple brute force approach worked!

Yeah, that’s right: the dreaded brute force. The thing here is: Don’t waste your time and resources if the simpler solution works for you (KISS: Keep It Simple, Stupid!) — sometimes, we tend to automatically favor more elaborated, “elegant” solutions and completely disregard the bread and butter. And the reason why we can use brute force is that the search space (the possible combinations of teams) is not huge: Around 15 thousand distinct teams.

So for the optimized solution we run a while loop that is stopped when we reach max_trials or max_diff = 0 (that is, we find a perfectly balanced team). And in each iteration we shuffle the input list (starting with the initial guess) and calculate the max_diff. If it‘s smaller than the current max_diff_best, we substitute it for the current max_diff and set best_guess to the current guess.

Finally, we run find_teams with the best_guess to retrieve the teams and print the optimized solution.

new_guess = initial_guess.copy()
best_guess = initial_guess.copy()
max_diff_best = max_diff.copy()
max_diff_list = [max_diff]
max_trials = 10000
count = 0
while count < max_trials and max_diff_best > 0:
    random.shuffle(new_guess)
    _, _, _, _, max_diff = find_teams(new_guess)
    max_diff_list.append(max_diff)
    if max_diff < max_diff_best:
        max_diff_best = max_diff
        best_guess = new_guess.copy()
    count += 1
    
#pd.DataFrame({"data": max_diff_list}).plot(kind='hist')

print('\nOptimized Solution: \n')
team1_best, team2_best, team3_best, team4_best, max_diff_best = find_teams(best_guess)
print_teams(team1_best, team2_best, team3_best, team4_best, max_diff_best)

Now the teams are perfectly balanced. Bear in mind that it is not a guarantee that you will have max_diff = 0 because it depends on the distribution of the ratings, but the algorithm will return the most balanced teams possible.

Histogram of each of the max_diff generated inside the while loop. It took 342 shuffles to get the perfectly balanced teams, and you can see we have scores as high as 1.6 and it looks like a Gaussian centered at 0.8.

Performance-wise, even if you shuffle 15 thousand times, it does not take more than twenty seconds or so to run. Most of the times when I use it, it takes only a couple shuffles to find perfectly balanced teams and I can get the results in less than five seconds — so, yeah, I’m definitely not worried about using a brute force approach.

And that’s it! We’ve concluded the step-by-step with code! I hope you enjoyed and, as always, feel free to comment and leave some claps ;)