Algorithm-driven team building
Programming Snapshot – Go Algorithms
![© Lead Image © bowie15, 123RF.com © Lead Image © bowie15, 123RF.com](/var/linux_magazin/storage/images/issues/2023/273/team-spirit/123rf-jorg_stober_gears-binary.png/825366-1-eng-US/123RF-Jorg_Stober_Gears-binary.png_medium.png)
© Lead Image © bowie15, 123RF.com
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 0
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 0
.
Listing 1
teams.yaml
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
Listing 3
teams.go
Listing 4
random.go
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 0
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.
![Learn More](https://www.linux-magazine.com/var/linux_magazin/storage/images/media/linux-magazine-eng-us/images/misc/learn-more/834592-1-eng-US/Learn-More_medium.png)
News
-
Canonical Offers 12-Year LTS for Open Source Docker Images
Canonical is expanding its LTS offering to reach beyond the DEB packages with a new distro-less Docker image.
-
Plasma Desktop 6.1 Released with Several Enhancements
If you're a fan of Plasma Desktop, you should be excited about this new point release.
-
SUSE Offers CentOS 7 Support with Liberty Linux Lite
SUSE's Liberty Linux support offering now includes CentOS 7, which means businesses won't be forced to migrate those servers for some time.
-
Ubuntu's App Center Finally Supports Local Installs Again
If you regularly download .deb files and would prefer a GUI method of installing, Ubuntu has your back.
-
AlmaLinux Now Supports Raspberry Pi 5
If you're looking to create with the Raspberry Pi 5 and want to use AlmaLinux as your OS, you're in luck because it's now possible.
-
Kubuntu Focus Releases New Iterations of Ir14 and Ir16 Laptops
If you're a fan of the Kubuntu Focus laptops or have been waiting for the right time to purchase one, that time might be now.
-
NixOS 24.05 Is Ready for Prime Time
The latest release of NixOS (Uakari) has arrived and offers its usual reproducible, declarative, and reliable goodness.
-
Linux Lite 7.0 Officially Released
Based on Ubuntu 24.04 and kernel 6.8, Linux Lite version 7 now offers more options than ever.
-
KaOS Linux 2024.05 Adds Bcachfs Support and More
With updates all around, KaOS Linux now includes support for the bcachefs file system.
-
TUXEDO Computers Unveils New Iteration of the Stellaris Laptop Line
The Stellaris Slim 15 is the 6th generation and includes either an AMD or Intel CPU