At the weekly pickup soccer game in my adopted hometown of San Francisco, with 16 players signed up for an eight-on-eight match, there is always the question of who is going to compete against whom on match day. Preparing the team sheet is usually something taken care of by experienced players, but it is time-consuming and it leads to endless discussions about whether the eight players on one side are simply too skilled for the other eight players, leading to a lopsided game that is no fun to play. To resolve this, I've developed an algorithm to generate the team lineup. This allows me to take an interesting excursion into the world of combinatorics and explore the development of suitable algorithms in this month's column.

How many ways are there to assign 16 players to two teams of eight players each? If one team is fixed, the opponent's team is automatically derived from the remaining participants; this means that the result is written in combinatorics style as "8 over 16," which you compute as

(16*15*...*10*9) / (8*7*...*2*1)

with a result of 12,870. Any home computer can churn through that many combinations effortlessly. Even if your task was to assign 22 players to two teams of 11 each, it's in the same league with 705,432 possibilities.

Brute Force

In small event spaces like this, it is definitely an option to simply try out all the combinations, call an evaluation function on each pass, store the best scores, and output the top result at the end. Using this brute force method for a larger event space would simply not work, because combinations can easily spiral out of control exponentially. It would make more sense to first choose a non-perfect but reasonable solution as a starting point and then change it incrementally to see if the results improve or get worse. Simulated annealing is the technical term for this process [1].

Before moving on to find better solutions, you first need a metrics function to grade the quality of each team. This metric can then be used to compare different constellations and select the best one. Like the mantra of all management courses, "You can't manage what you can't measure." However, before you can determine the quality of a team, an expert has to grade the strength of the individual players on a few criteria, and then an algorithm can assign the teammates to teams and compare their cumulative strengths.

Collecting Points

The individual player ratings are shown in the YAML file in Listing 1. For the purpose of illustration, this model is limited to a total of six players. Each entry in players identifies a player by name and specifies their rating in three categories with values from   to 9: offense, defense, and goalie (i.e., the willingness to play as a goalkeeper). If a player does not have a rating in a category, the algorithm simply assumes a value of  .

01 players:
02   - name: joe
03     skills:
04       offense: 3
05   - name: tony
06     skills:
07       defense: 2
08       goalie: 3
09   - name: fred
10     skills:
11       defense: 2
12   - name: mike
13     skills:
14       offense: 9
15   - name: manuel
16     skills:
17       goalie: 9
18   - name: mark
19     skills:
20       defense: 9

For example, Listing 1 rates player tony as a 3 in terms of goalkeeping skills, while player manuel has a goalie value of 9 (any matches with the names of existing goalkeepers are pure coincidence). Because every team needs a goalkeeper and nobody else has goalkeeper qualities, a good algorithm should assign tony and manuel to play on different teams. On top of this, the algorithm needs to ensure that both teams have roughly equal offensive and defensive players to keep the match exciting and open.

Listing 2 reads the YAML data from the file and then stores it in a data structure for the team-building Go binary later. Listing 3 shows the main program that defines what happens after you call it from the command line. As a kind of warm-up, Listing 4 shows a simple algorithm that randomly assigns players to two teams. You can see the output from the program in Figure 1. The teams are quite lopsided and the algorithm obviously far from perfect, but stay tuned, improvements are coming.

01 package main
02
03 import (
04   "gopkg.in/yaml.v2"
05   "io/ioutil"
06 )
07
08 type Skills struct {
09   Goalie  int `yaml:goalie`
10   Offense int `yaml:offense`
11   Defense int `yaml:defense`
12 }
13
14 type Player struct {
15   Name   string `yaml:name`
16   Skills Skills `yaml:skills`
17 }
18
19 type Config struct {
20   Players []Player `yaml:players`
21 }
22
23 func yamlParse() ([]Player, error) {
24   config := Config{}
25
26   text, err := ioutil.ReadFile("teams-real.yaml")
27   if err != nil {
28     return config.Players, err
29   }
30
31   err = yaml.Unmarshal([]byte(text), &config)
32   if err != nil {
33     return config.Players, err
34   }
35
36   return config.Players, nil
37 }

01 package main
02
03 import (
04   "fmt"
05 )
06
07 func main() {
08   players, err := yamlParse()
09   if err != nil {
10     panic(err)
11   }
12
13   teams := mkTeams(players)
14   if err != nil {
15     panic(err)
16   }
17
18   teamNames := []string{"A", "B"}
19   for tIdx, team := range teams {
20     fmt.Printf("Team %s\n", teamNames[tIdx])
21     for pIdx, player := range team {
22       fmt.Printf("%d. %8s [off:%d def:%d goa:%d]\n",
23         pIdx+1, player.Name, player.Skills.Offense,
24         player.Skills.Defense, player.Skills.Goalie)
25     }
26     fmt.Print("\n")
27   }
28 }

01 package main
02
03 import (
04   "math/rand"
05   "time"
06 )
07
08 func mkTeams(players []Player) [][]Player {
09   rand.Seed(time.Now().UnixNano())
10
11   rand.Shuffle(len(players), func(i, j int) {
12     players[i], players[j] = players[j], players[i]
13   })
14
15   if len(players) < 2 || len(players)%2 != 0 {
16     panic("Needs even number of players")
17   }
18
19   return [][]Player{
20     players[0 : len(players)/2],
21     players[len(players)/2:],
22   }
23 }

Figure 1: Randomly created teams often have significant differences in performance.

Strict Types

For the Go program to be able to understand the YAML data with the player skills, it first needs to define similar data structures because of Go's strict type checking. Listing 2 reads in the entire YAML structure from Listing 1 which consists of a dictionary under the players key, containing an array of player structures. Each key contains a name and defines the player's ability under the skills key with the skill name and numerical ratings from   to 9.

Based on this, line 19 of the Go code in Listing 2 defines the Config structure with a Players field, whose value is an array slice with Player type elements. This type, defined in line 14, in turn, contains the Name field for the player's name and a Skills field of the same type. The skills type is defined starting in line 8 and specifies the player's strength in values of the int type in the Goalie, Offense, and Defense fields.

Because Go can handle YAML data natively, the code following the field names and types can provide useful hints in backticks (e.g., if the field name used in YAML differs from the one used in the type). In our case, the field names in the Go data structure are uppercase (the YAML library wants it that way), but the YAML fields in the configuration are lowercase. For example, line 9, Goalie int `yaml:goalie`, defines the Goalie field as being of the int type while its counterpart in the YAML data is named goalie.

That's all the YAML evaluator yaml.Unmarshal() needs in line 31. It works through all the elements of the configuration's YAML array in one go, populates the program's internal Go structures with them, and also takes care of allocating the required memory resources – a miracle of modern computer science. For example, if the code wants to access the offensive skills of the third player from the top later, it can access the associated integer value as config.Players[2].Offense.