Algorithm-driven team building
Programming Snapshot – Go Algorithms
Instead of the coach determining the team lineup, an algorithm selects the players based on their strengths for Mike Schilli's amateur soccer team.
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
.
Listing 1
teams.yaml
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.
Listing 2
data.go
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 }
Listing 3
teams.go
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 }
Listing 4
random.go
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 }
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
.
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.
News
-
New Slimbook EVO with Raw AMD Ryzen Power
If you're looking for serious power in a 14" ultrabook that is powered by Linux, Slimbook has just the thing for you.
-
The Gnome Foundation Struggling to Stay Afloat
The foundation behind the Gnome desktop environment is having to go through some serious belt-tightening due to continued financial problems.
-
Thousands of Linux Servers Infected with Stealth Malware Since 2021
Perfctl is capable of remaining undetected, which makes it dangerous and hard to mitigate.
-
Halcyon Creates Anti-Ransomware Protection for Linux
As more Linux systems are targeted by ransomware, Halcyon is stepping up its protection.
-
Valve and Arch Linux Announce Collaboration
Valve and Arch have come together for two projects that will have a serious impact on the Linux distribution.
-
Hacker Successfully Runs Linux on a CPU from the Early ‘70s
From the office of "Look what I can do," Dmitry Grinberg was able to get Linux running on a processor that was created in 1971.
-
OSI and LPI Form Strategic Alliance
With a goal of strengthening Linux and open source communities, this new alliance aims to nurture the growth of more highly skilled professionals.
-
Fedora 41 Beta Available with Some Interesting Additions
If you're a Fedora fan, you'll be excited to hear the beta version of the latest release is now available for testing and includes plenty of updates.
-
AlmaLinux Unveils New Hardware Certification Process
The AlmaLinux Hardware Certification Program run by the Certification Special Interest Group (SIG) aims to ensure seamless compatibility between AlmaLinux and a wide range of hardware configurations.
-
Wind River Introduces eLxr Pro Linux Solution
eLxr Pro offers an end-to-end Linux solution backed by expert commercial support.