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
-
NVIDIA Released Driver for Upcoming NVIDIA 560 GPU for Linux
Not only has NVIDIA released the driver for its upcoming CPU series, it's the first release that defaults to using open-source GPU kernel modules.
-
OpenMandriva Lx 24.07 Released
If you’re into rolling release Linux distributions, OpenMandriva ROME has a new snapshot with a new kernel.
-
Kernel 6.10 Available for General Usage
Linus Torvalds has released the 6.10 kernel and it includes significant performance increases for Intel Core hybrid systems and more.
-
TUXEDO Computers Releases InfinityBook Pro 14 Gen9 Laptop
Sporting either AMD or Intel CPUs, the TUXEDO InfinityBook Pro 14 is an extremely compact, lightweight, sturdy powerhouse.
-
Google Extends Support for Linux Kernels Used for Android
Because the LTS Linux kernel releases are so important to Android, Google has decided to extend the support period beyond that offered by the kernel development team.
-
Linux Mint 22 Stable Delayed
If you're anxious about getting your hands on the stable release of Linux Mint 22, it looks as if you're going to have to wait a bit longer.
-
Nitrux 3.5.1 Available for Install
The latest version of the immutable, systemd-free distribution includes an updated kernel and NVIDIA driver.
-
Debian 12.6 Released with Plenty of Bug Fixes and Updates
The sixth update to Debian "Bookworm" is all about security mitigations and making adjustments for some "serious problems."
-
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.