Beim wöchentlichen Fußballspiel der Hobbymannschaft in meiner Wahlheimat San Francisco stellt sich bei 16 eingetragenen Teilnehmern und einem Spiel acht gegen acht immer die Frage, wer nun am Spieltag gegen wen antritt. Die Erstellung des sogenannten "Team Sheets" nehmen normalerweise erfahrene Spieler in die Hand, doch das ist zeitaufwändig und führt zu Diskussionen darüber, ob die acht Spieler der einen Mannschaft dem anderen Achter nicht haushoch überlegen sind. Ein Computerprogramm schafft da Abhilfe und erlaubt in dieser Ausgabe einen interessanten Ausflug in die Kombinatorik und die Entwicklung geeigneter Algorithmen.
Wieviele Möglichkeiten gibt es, 16 Teilnehmer in zwei Mannschaften zu je 8 Spielern einzuteilen? Steht ein Team fest, ergibt sich das gegnerische automatisch aus den verbliebenen Teilnehmern, also schreibt sich das Ergebnis kombinatorisch als "8 über 16", was sich als (16*15*...*10*9) / (8*7*...*2*1) errechnet, also 12.870 ergibt. Solche Mengen kann ein selbst ein Heimcomputer mit vertretbarem Aufwand bearbeiten, und selbst 22 Spieler in zwei Teams zu je 11 einzuteilen liegt mit 705.432 Möglichkeiten in der gleichen Liga.
In derart kleinen Ereignisräumen ist es vertretbar, einfach alle Möglichkeiten durchzuprobieren, bei jedem Durchgang eine Bewertungsfunktion aufzurufen, die besten Ergebnisse zu behalten, und am Ende auszugeben. Diese Methode firmiert unter der Bezeichnung "Brute Force". Es geht also darum, auf Biegen und Brechen alles abzugrasen. Bei einem weiter ausgedehnten Ergeignisraum wäre es hingegen sinnvoll, zunächst eine halbwegs brauchbare Lösung als Ausgangspunkt zu wählen, diese in kleinen Schritten zu verändern und zu sehen, ob sich das Ergebnis verschlechtert oder verbessert. "Simulated annealing" heißt dieser Prozess in der Fachsprache ([3]).
Doch bevor es daran geht, Aufstellungen schrittweise zu verbessern, muss zunächst eine Messfunktion her, die bestimmt, wie gut eine Mannschaft ist. Damit lassen sich dann verschiedene Konstellationen miteinander vergleichen und die besten auswählen. Wie heißt es so schön im Mantra aller Managementkurse: "You can't manage what you don't measure"! Und bevor es überhaupt ans Probieren oder schrittweise Verbessern geht, muss ein Fachmann die einzelnen Spieler vorher in einigen Kategorien bewerten und es dann Kollege Computer überlassen, die Mitspieler in zwei ebenbürtige Mannschaften einzuteilen, deren Stärke sich aus den aufkumulierten Spielerbewertungen ergibt.
Die Einzelbewertungen der Spieler zeigt die die .yaml-Datei in Listing 1, zu Illustrationszwecken in einem auf 6 Spieler heruntergefahrenen Modell: Jeder Eintrag unter "Players" identifiziert einen Spieler mit Namen und legt dessen Bewertung in drei Kategorien mit Werten von 0 bis 9 fest: "offense" (Sturm), "defense" (Verteidigung) und "goalie" also die Eignung zum Torwart. Listing 1 weist zum Beispiel dem Spieler "tony" eine 3 in puncto Torwartqualität zu, und der Spieler "manuel" führt einen goalie-Wert von 9. Übereinstimmungen mit den Namen real existierender Torhüter wären rein zufällig. Da jede Mannschaft einen Torwart braucht, und kein weiterer Spieler Torwartqualitäten aufweist, sollte der Algorithmus später also tony und manuel nicht miteinander, sondern gegeneinander spielen lassen.
Außerdem sollte der Algorithmus darauf achten, dass in beiden Mannschaften in etwa gleichwertige Offensiv- und Defensivspieler spielen, damit das Match spannend und offen und nicht von vornherein besiegelt ist. Fehlt übrigens für einen Spieler die Bewertung in einer Kategorie, soll der Algorithmus einfach 0 annehmen.
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
Das Einlesen der Yaml-Daten und die Datenhaltung des später mannschaftbildenden Go-Binaries implementiert Listing 2. Das Rahmenprogramm mit der Hauptfunktion main() definiert Listing 3. Zum Warmwerden zeigt Listing 4 einen simplen Algorithmus, der die Mitspieler nach dem Zufallsprinzip auf zwei Mannschaften verteilt. Die Ausgabe ist in Abbildung 1 zu sehen. Das Ganze ist offensichtlich noch nicht optimal, aber Verbesserungen kommen noch.
| |
| Abbildung 1: Zufällig erstellte Mannschaften sind oft schieflastig. |
Damit das Go-Programm später die Yaml-Daten versteht, muss es in Listing 2 erstmal gleichartige Datenstrukturen definieren, das ist wegen der strengen Typprüfung in Go notwendig. Die gesamte Yaml-Struktur in Listing 1 besteht aus einem Dictionary mit dem Eintrag players, unter dem ein Array von Spielern liegt, deren Einträge jeweils den Namen (name) und die Talente (skills) mit numerischen Bewertungen von 0-9 auflisten.
01 package main
02 import (
03 "gopkg.in/yaml.v2"
04 "io/ioutil"
05 )
06 type Skills struct {
07 Offense int `yaml:offense`
08 Defense int `yaml:defense`
09 Goalie int `yaml:goalie`
10 }
11 type Player struct {
12 Name string `yaml:name`
13 Skills Skills `yaml:skills`
14 }
15 type Config struct {
16 Players []Player `yaml:players`
17 }
18 func yamlParse() ([]Player, error) {
19 config := Config{}
20 text, err := ioutil.ReadFile("teams.yaml")
21 if err != nil {
22 return config.Players, err
23 }
24 err = yaml.Unmarshal([]byte(text), &config)
25 if err != nil {
26 return config.Players, err
27 }
28 return config.Players, nil
29 }
Folglich definiert der Go-Code in Listing 2 in Zeile 15 die Struktur Config mit einem Feld Players, dessen Wert ein Array-Slice mit Elementen vom Typ Player ist. Dieser in Zeile 11 definierte Typ enthält wiederum das Feld Name für den Namen des Spielers und ein Feld Skills vom gleichnamigen Typ Skills. Letzterer ist ab Zeile 6 definiert und gibt mit den Feldern Goalie, Offense und Defense die Stärke des Spielers in Werten vom Typ int an.
Da Go die Verarbeitung von Yaml-Daten von Haus aus unterstützt, darf der Code hinter den Feldnamen und -typen jeweils in rückwertigen Anführungszeichen nützliche Hinweise geben, falls der in Yaml verwendete Feldname vom im Typ genutzten abweicht. Im vorliegenden Fall sind die Feldnamen jeweils groß geschrieben (die Yaml-Library will es so), die Yaml-Felder in der Konfiguration aber klein. So definiert zum Beispiel Zeile 7 mit Goalie int `yaml:goalie` das Feld "Goalie" als vom Typ int, dessen Pendant im Yaml-Daten goalie heißt. Mehr braucht der Yaml-Evaluierer yaml.Unmarshal() in Zeile 24 nicht, er frisst sich in einem Rutsch durch alle Elemente des Yaml-Arrays der Konfiguration, füllt die programminternen Go-Strukturen damit und sorgt auch noch für's Allozieren des benötigten Speichers. Ein wahres Wunderwerk. Möchte der Code später zum Beispiel auf die Sturmeigenschaften des dritten Spielers von oben zugreifen, bekommt er mit config.Players[2].Offense den zugehörigen Integer-Wert geliefert.
01 package main
02 import (
03 "fmt"
04 )
05 func main() {
06 players, err := yamlParse()
07 if err != nil {
08 panic(err)
09 }
10 teams := mkTeams(players)
11 if err != nil {
12 panic(err)
13 }
14 teamNames := []string{"A", "B"}
15 for tIdx, team := range teams {
16 fmt.Printf("Team %s\n", teamNames[tIdx])
17 for pIdx, player := range team {
18 fmt.Printf("%d. %8s [off:%d def:%d goa:%d]\n",
19 pIdx+1, player.Name, player.Skills.Offense,
20 player.Skills.Defense, player.Skills.Goalie)
21 }
22 fmt.Print("\n")
23 }
24 }
Listing 3 definiert das Hauptprogramm main, das als erstes die Yaml-Daten mit yamlParse() aus Listing 2 einliest. Zeile 12 ruft dann das später definierte mkTeams() zum Aufstellen der beiden Mannschaften auf. Zurück kommt ein Array-Slice teams mit den Mannschaften, dessen Elemente wiederum aus Array-Slices von Spielern vom Typ Player bestehen. Die for-Schleife ab Zeile 15 iteriert über beide Mannschaften, die innere for-Schleife ab Zeile 17 dann über die einzelnen Spieler. Neben dem Namen jedes Spielers einer Mannschaft druckt Printf() jeweils noch eine Zusammenfassung der Bewertung des Spielers nach den drei vordefinierten Kriterien.
Zum Aufwärmen soll nun ein simpler Algorithmus die Mannschaften einfach zufällig zusammenwürfeln. Die Implementierung von mkTeams() in Listing 4 initialisiert zunächst einen Zufallsgenerator aus dem Standardpaket math/rand anhand eines "Seeds" mit der aktuellen Uhrzeit, damit weitere Aufrufe des virtuellen Trainers immer unterschiedliche Mannschaften liefern. Die Funktion rand.Shuffle() wirbelt dann ab Zeile 8 die Elemente des Array-Slices mit den 16 Spielern durcheinander, und die return-Anweisung ab Zeile 14 gibt die erste und die zweite Hälfte des Slices an den Aufrufer zurück. Fertig ist die Mannschaftsaufstellung.
Wegen des in Listing 2 verwendeten Yaml-Pakets, muss der Compiler vor dem eigentlichen Befehl zum Erzeugen des Binaries erst noch das Yaml-Paket von Github abholen und übersetzen. Die Befehle go mod init teams und go mod tidy erledigen das. Anschließend läuft
$ go build random.go teams.go data.goglatt durch und bindet alles zu einem Binary random zusammen, dessen Aufruf auf der Kommandozeile Abbildung 1 mitsamt der generierten Ausgabe zeigt.
01 package main
02 import (
03 "math/rand"
04 "time"
05 )
06 func mkTeams(players []Player) [][]Player {
07 rand.Seed(time.Now().UnixNano())
08 rand.Shuffle(len(players), func(i, j int) {
09 players[i], players[j] = players[j], players[i]
10 })
11 if len(players) < 2 || len(players)%2 != 0 {
12 panic("Needs even number of players")
13 }
14 return [][]Player{
15 players[0 : len(players)/2],
16 players[len(players)/2:],
17 }
18 }
Doch dieser Algorithmus ist noch nicht das Gelbe vom Ei. Wie Abbildung 1 zeigt, hat der Zufallsgenerator die beiden einzigen Spieler mit Torwartqualitäten demselben Team zugewiesen, aber jedes Team braucht mindestens einen Torwart. Auch die Angriffs- und Verteidigungslinien sind ungleich, also sollte die nächste Stufe im Algorithmus-Design die Spieler entsprechend ihrer individuellen Stärken in zwei ebenbürtige Mannschaften aufteilen.
Wie eingangs erwähnt ist es wegen des kleinen Ereignisraums ein Leichtes, alle Möglichkeiten durchzuspielen und die Tauglichkeit einzelner Lösungen zu ermitteln und miteinander zu vergleichen. Dazu bietet Listing 5 erstmal eine Tauglichkeitsfunktion diff, die eine Begegnung zweier Mannschaften teamA und teamB mit einem Score bewertet. Ist diese Integerzahl nahe Null, ist die Begegnung ausgeglichen, und je größer ihr Wert, desto schieflastiger wird das Match voraussichtlich. Dazu addiert die Funktion die absoluten Differenzen der Mannschaften in puncto Angriff, Verteidigung und Torwartverfügbarkeit, gewichtet mit dem Faktor 2 für Angriff und dem Faktor 10 für den Torwart, denn fehlt der, ist das Spiel schon verloren.
Man sollte meinen, dass eine Programmiersprache von Haus aus eine Funktion zur Ermittlung des absoluten Wertes einer Integerzahl bereitstellt, aber Gos schrullige Entwickler haben sich dagegen entschieden. Das math-Paket bietet zwar eine Abs()-Funktion für Floats, aber deren Verwendung mit Integern erfordert soviel Konvertierungsoperationen, so dass Listing 5 ab Zeile 13 lieber gleich eine Funktion abs() implementiert, die das Ergebnis auch noch positiv macht.
01 package main
02 func diff(teamA []Player, teamB []Player) int {
03 d := Skills{}
04 for idx, player := range teamA {
05 s1 := player.Skills
06 s2 := teamB[idx].Skills
07 d.Offense += s1.Offense - s2.Offense
08 d.Defense += s1.Defense - s2.Defense
09 d.Goalie += s1.Goalie - s2.Goalie
10 }
11 return 2 * abs(d.Offense) +
12 abs(d.Defense) +
13 10 * abs(d.Goalie)
14 }
15 func abs(x int) int {
16 if x < 0 {
17 return -x
18 }
19 return x
20 }
Damit kann nun Listing 6 als Alternative zur Zufallsproduktion in Listing 4 eine neue Version der Funktion mkTeams() präsentieren, die mit perm() alle Möglichkeiten durchspielt, die entstehenden Gruppierungen mit diff() bewertet und die beste Konstellation mit dem niedrigsten Wert in bestTeams und bestDiff speichert.
 |
| Abbildung 2: Ein Array-Slice in Go referenziert nur einen realen Array. |
Beim Merken des besten Ergebnisses gilt es allerdings eine nicht gerade offensichtliche Stolperfalle zu umgehen: Wer dachte, man könne einfach die Werte der Variablen t1 und t2 mit den Teams an einem sicheren Ort aufbewahren, sieht sich getäuscht und wacht zu absurden Spielbegegnungen auf, die dadurch entstehen, dass die Go-Runtime die von t1 und t2 referenzierten Mannschaften in dem darunterliegenden Array modifiziert. Ein Array-Slice in Go ist ja immer nur ein Pointer auf einen echten Array (Abbildung 2), und wer nur den Pointer speichert, bekommt hinterher etwaige Änderungen am darunterliegenden Array aufgetischt.
Die Zeilen 9 bis 12 umgehen diese Falle, indem sie einmal gefundene Mannschaften mit der in Go eingebauten Funktion copy() duplizieren. Darauf zu achten ist übrigens auch noch, dass das Ziel-Array-Slice (erstes Argument von copy()) die gleiche Länge wie das zu kopierende Original hat -- hätte ersteres die Länge 0, würde copy() einfach 0 Bytes kopieren und der User sich die Haare raufen.
01 package main
02 func mkTeams(players []Player) [][]Player {
03 bestTeams := make([][]Player, 2)
04 bestDiff := -1
05 perm(players, func(t1 []Player, t2 []Player) {
06 d := diff(t1, t2)
07 if bestDiff < 0 || d < bestDiff {
08 bestDiff = d
09 t1c := make([]Player, len(t1))
10 copy(t1c, t1)
11 t2c := make([]Player, len(t2))
12 copy(t2c, t2)
13 bestTeams = [][]Player{t1c, t2c}
14 }
15 })
16 return bestTeams
17 }
Wie nun findet Listing 6 alle möglichen Konstellation von Mannschaften? Dazu ruft es in Zeile 5 die Funktion perm() aus Listing 7 auf, die ein Array-Slice mit verfügbaren Spielern entgegennimmt sowie eine Callback-Funktion, die es für alle gefundenen Spielerkombinationen einmal anspringt. Dort kann dann der User, wie in Listing 6 ab Zeile 6, Aktionen auf die beiden Mannschaften loslassen, wie zum Beispiel deren Bewertung vorzunehmen und das beste soweit gefundene Ergebnis zu behalten.
Für ein Verfahren, alle Möglichkeiten zu finden, einen Array mit N Spielern in alle möglichen Kombinationen von zwei Mannschaften aufzuteilen, fragte ich einfach das Elektronengehirn hinter chatGPT, und innerhalb von 10 Sekunden hatte es eine Lösung parat (Abbildung 3).
 |
| Abbildung 3: ChatGPT schreibt Teile des Go-Codes für diese Kolumne. |
Was für eine Arbeitserleichterung für ermüdete Programmierer! Zu tun blieb lediglich, den Code an die für die Mannschaften verwendete Player-Datenstruktur der Arrayelemente anzupassen und schon war Listing 7 fertig. So macht das Programmieren Spaß! Es sei allerdings angemerkt, dass die Lösungen, die ChatGPT präsentiert, oftmals nicht 100% korrekt sind. Weist man die AI aber in einer Nachfrage auf etwaige Fehler hin, entschuldigt sie sich artig und präsentiert prompt eine bessere Lösung.
01 package main
02 func perm(players []Player, f func([]Player, []Player)) {
03 _perm(players, 0, []Player{}, []Player{}, f)
04 }
05 func _perm(players []Player, idx int,
06 subset1 []Player, subset2 []Player,
07 f func([]Player, []Player)) {
08 if len(subset1) == len(players)/2 && len(subset2) == len(players)/2 {
09 f(subset1, subset2)
10 return
11 }
12 if idx == len(players) {
13 return
14 }
15 _perm(players, idx+1, append(subset1, players[idx]), subset2, f)
16 _perm(players, idx+1, subset1, append(subset2, players[idx]), f)
17 }
Der von chatGPT entworfene Algorithmus basiert auf Rekursion und ruft die Funktion perm() zweimal mit zwei anfangs leeren Team-Slices subset1 und subset2 auf. Die exportierte Funktion perm() ruft hierzu in Zeile 3 von Listing 7 die mit einem Unterstrich versteckte Funktion _perm() auf, wobei es die beiden Subset-Parameter, sowie den Index des gerade bearbeiteten Elements einfüllt. Mit einem Anfangs auf 0 gesetzten idx merkt es sich, wo es sich im Array-Slice der verfügbaren Spieler players es sich gerade befindet und ruft sich selbst dann zweimal mit zwei neuen Teamversuchen auf: einmal indem es das aktuelle per idx referenzierte Element an subset1 anhängt und einmal an subset2 (Zeilen 15 und 16 in Listing 7).
 |
| Abbildung 4: Gültige 2x2 Aufstellungen für 4 Spieler |
So generiert es rekursiv alle möglichen Konstellationen, die die Arrayelemente in zwei Untergruppen aufteilen, allerdings ohne darauf zu achten, ob diese auch die für die Mannschafsbildung notwendigen Spieler enthalten. In der Tat lässt es die Subsets auch teilweise leer (Abbildung 4).
Das ist aber kein Beinbruch, da der Code in Listing 7 ab Zeile 8 prüft, ob die generierten Gruppen die erforderliche Spielerzahl haben, und ignoriert die Lösungen, die dem Kriterium nicht genügen. Nur für zahlenmäßig passende Konstellationen (markiert durch rote Pfeile in Abbildung 4) ruft Zeile 7 den Callback f mit den beiden gefundenen Mannschaften auf, den der Aufrufer dann nutzt, um die Konstellation zu bewerten und das beste Ergebnis einzukreisen.
Dieses kompakt zu implementierende Verfahren erzeugt, wie Abbildung 5 zeigt, alle möglichen Begegnungen (zu Illustrationszwecken reduziert auf 6 Spieler), ist allerdings nicht ganz optimal, da es auch symmetrische Begegnungen (Team A gegen Team B, beziehungsweise B gegen A) als neu bewertet, aber das ist wegen des kleinen Ereignisraums nicht so schlimm.
 |
| Abbildung 5: Alle Permutationen von 6 Spielern zu 3er-Mannschaften |
Fertig ist der Lack! Das mittels
$ go build brute.go teams.go diff.go perm.go data.goerzeugte Binary brute wirft sich auf die Yaml-Datei teams.yaml, nudelt alle möglichen Team-Konstellationen durch und gibt die nach der Bewertungsfunktion ermittelten Bestwerte aus.
 |
| Abbildung 6: Nach der Brute-Force-Methode ermittelte Verteilung |
 |
| Abbildung 7: Auch bei zwei Teams zu je 8 Spielern macht der Algorithmus eine gute Figur. |
Die Abbildungen 6 und 7 zeigen zwei Beispiele von brauchbaren Aufstellungen, einmal für die eingangs gestellte Aufgabe mit einen Pool von 6 Spielern, und dann für ein Spiel acht gegen acht. In beiden Lösungen hat der Algorithmus Verteilungen gefunden, bei denen in der jede Mannschaft einen Torwart hat und die Spielerwerte für Angriff und Verteidigung in etwa ausgewogen sind. So bleibt die Begegnung spannend bis zur letzten Minute und alle Spieler geben 110%, wie es im Fußballerdeutsch so schön heißt.
Listings zu diesem Artikel: http://www.linux-magazin.de/static/listings/magazin/2023/06/snapshot/
Michael Schilli, "Titel": Linux-Magazin 12/16, S.104, <U>http://www.linux-magazin.de/Ausgaben/2016/12/Perl-Snapshot<U>
"How to Solve It: Modern Heuristics", Zbigniew Michalewicz, Springer 2004
 |
Michael Schilliarbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen. |
Hey! The above document had some coding errors, which are explained below:
Unknown directive: =desc