Ligaverwaltung, Teil 3: Spielpläne generieren

Für die meisten Sportarten gibt es Wettbewerbe in Ligen. Oder zumindest Turniere, die ja meist auch als kleine Liga angesehen werden können mit Spielpaarungen und Tabellen. Jedenfalls gibt eine Verwaltung solcher Ligen jede Menge Stoff für eine Datenbankanwendung – mit Datenmodell, Abfragen, Formularen zur Eingabe der Daten und Berichten, um Spielpläne und Tabellen auszugeben. Im dritten Teil der Artikelreihe entwickeln wir einen Algorithmus, der es uns erlaubt, Spielpläne für Ligen mit beliebig vielen Mannschaften zu generieren.

Beispieldatenbank

Die Beispiele dieses Artikels finden Sie in der Datenbank 1906_Ligaverwaltung.accdb.

Aufgabenstellung

Die Aufgabe lautet: Wir wollen für eine Anzahl von Mannschaften, egal ob 4, 6 oder 18, programmgesteuert einen Spielplan erstellen. Dieser Spielplan soll folgene Bedingungen erfüllen:

• Jede Mannschaft soll ein Heimspiel gegen jede andere Mannschaft haben. Für die Fußball-Bundesliga bedeutet das beispielsweise: Jede Mannschaft macht 17 Heimspiele plus, resultierend aus den 17 Spielen, in denen die anderen Mannschaften ein Heimspiel gegen diese Mannschaft haben, 17 Auswärtsspiele. Dementsprechend gibt es 2 mal n-1 Spieltage, wobei n der Anzahl der Mannschaften entspricht.
• Jede Mannschaft soll auch nur genau einmal in einem Heimspiel gegen jede andere Mannschaft spielen.
• Die Spielpaarungen sind auf Spieltage aufgeteilt, wobei an jedem Spieltag jede Mannschaft einmal spielt.
• Die Spiele sollen in zwei Runden ausgetragen werden, wobei die Hin- und die Rückrunde identisch zusammengestellt werden – nur mit umgedrehtem Heimrecht. Es reicht also prinzipiell, nur die Hinrunde zu generieren und daraus die Spielpaarungen der Rückrunde abzuleiten.
• Um es nicht zu einfach zu machen: Jede Mannschaft soll maximal einmal pro Spielrunde (also bezogen auf Hin- und Rückrunde) zwei Heim- oder Auswärtsspiele hintereinander bestreiten. Und das soll auch erst ab dem zweiten Spieltag und bis zum vorletzten Spieltag möglich sein (also keine zwei Heim- oder Auswärtsspiele am ersten und zweiten oder vorletzten und letzten Spieltag).
• Die Krönung wäre – und so ist es in den echten Spielplänen der Fußballbundesliga -, wenn die Abfolge der Gegner einer jeden Mannschaft ungefährt gleich wäre. Also wenn Mannschaft 1 nacheinander gegen Mannschaft 2, Mannschaft 3 und Mannschaft 4 spielt, dann wird Mannschaft 5 auch irgendwann in dieser Abfolge gegen diese Mannschaften spielen. Das funktioniert natürlich nicht durchgehend, denn wenn man die Abfolge der 17 Spiele der Hinrunde einer Mannschaft auf eine andere Mannschaft übertragen wollte, müsste diese ja gegen sich selbst spielen – und spätestens an dieser Stelle müssten wir die Mannschaft dann austauschen.

Ablauf

Wie könnte das programmatisch ablaufen Man könnte auf verschiedene Arten vorgehen. Die erste Idee ist, zuerst alle Spiele für Mannschaft 1 festzulegen, dann die verbleibenden Spiele für Mannschaft 2 und so weiter.

Wir könnten auch einfach alle Spiele von Spieltag 1 an komplett durchbesetzen, indem wir immer die Mannschaft mit dem kleinsten Index eintragen, die noch verfügbar ist. Am erste Spieltag sieht der Spielplan dann so aus:

1-2
3-4
5-6
...

Am zweiten Spieltag beginnen wir dann wieder mit Mannschaft 1 und suchen die Mannschaft mit dem kleinsten Index, gegen den diese Mannschaft noch nicht gespielt hat – in diesem Fall Mannschaft 3 -, und tauschen das Heimrecht um:

3-1

Dann hätte allerdings Mannschaft 3 direkt an den ersten beiden Spieltagen zwei Heimspiele, was frühestens ab dem zweiten Spieltag möglich sein soll. Mannschaft 1 müsste dann also bei Mannschaft 4 antreten:

4-1

Sie sehen: Es ist nicht einfach. Und das wollen wir gleich auch noch programmieren! Abzusehen ist, dass wir dann irgendwann bei der Ermittlung der Paarungen für die hinteren Spieltage auf das Problem stoßen werden, dass wir je Spieltag nicht mehr ausreichend Spiele zusammenstellen und gleichzeitig alle Bedingungen erfüllen können.

Das heißt, wir können keinen starren Ablauf programmieren, sondern müssen die Möglichkeit der Korrektur vorheriger Spieltage berücksichtigen.

In der Programmierung bekommt man das am besten mit rekursiven Funktionen hin. Das heißt, wir legen ein Spiel an, prüfen, ob wir das nächste Spiel nach anlegen können, und wenn nicht, löschen wir das zuvor angelegte Spiel wieder, um ein anderes Spiel anzulegen. Auf diese Weise arbeiten wir uns durch die Kombinationen, um am Ende einen Spielplan zu erhalten, der alle Bedingungen erfüllt. Gegebenenfalls müssen wir uns dabei bis zurück zum Anfang bewegen.

Alternative: Erst Spiele anlegen, dann auf Spieltage aufteilen

Es gibt allerdings noch andere Herangehensweisen. Eine, die vielleicht etwas anschaulicher ist, sieht so aus: Wir tragen erst einmal alle Paarungen in die Tabelle tblSpielpaarungen ein. Das ist einfach: Wir brauchen ja nur zwei Recordsets mit den Mannschaften der Liga/Spielzeit in zwei verschachtelten Do While-Schleifen zu durchlaufen und darin jeweils die Heim- und die Auswärtsmannschaft in die Felder der Tabelle tblSpielpaarungen einzutragen. Dabei müssen wir nur prüfen, ob die Heim- und die Auswärtsmannschaft identisch sind und in diesem Fall keinen Datensatz anlegen.

Programmierung der Spielplangenerierung

Wir beginnen mit dem Anlegen der Spiele einer Liga. Dazu verwenden wir die Prozedur aus Listing 1. Die Prozedur erwartet die LigaSpieljahrID für die Liga, für deren Mannschaften der Spielplan angelegt werden soll. Wir haben zunächst eine kleine Liga angelegt, die nur vier Mannschaften enthält.

<font color=blue>Public Sub </font>PaarungenAnlegen(lngLigaSpieljahrID<font color=blue> As Long</font>)
     <font color=blue>Dim </font>db<font color=blue> As </font>DAO.Database
     <font color=blue>Dim </font>rstSpielpaarungen<font color=blue> As </font>DAO.Recordset
     <font color=blue>Dim </font>rstHeimmannschaften<font color=blue> As </font>DAO.Recordset
     <font color=blue>Dim </font>rstAuswaertsmannschaften<font color=blue> As </font>DAO.Recordset
     <font color=blue>Set</font> db = CurrentDb
     <font color=blue>Set</font> rstSpielpaarungen = db.OpenRecordset("SELECT * FROM tblSpielpaarungen", dbOpenDynaset)
     <font color=blue>Set</font> rstHeimmannschaften = db.OpenRecordset("SELECT MannschaftID FROM tblLigenSpieljahreMannschaften " _
         & "WHERE LigaSpieljahrID = " & lngLigaSpieljahrID, dbOpenDynaset)
     <font color=blue>Set</font> rstAuswaertsmannschaften = db.OpenRecordset("SELECT MannschaftID FROM tblLigenSpieljahreMannschaften " _
         & "WHERE LigaSpieljahrID = " & lngLigaSpieljahrID, dbOpenDynaset)
     <font color=blue>Do While</font> <font color=blue>Not</font> rstHeimmannschaften.EOF
         <font color=blue>Do While</font> <font color=blue>Not</font> rstAuswaertsmannschaften.EOF
             <font color=blue>If </font><font color=blue>Not</font> rstHeimmannschaften!ID = rstAuswaertsmannschaften!ID<font color=blue> Then</font>
                 rstSpielpaarungen.Add<font color=blue>New</font>
                 rstSpielpaarungen!HeimmannschaftID = rstHeimmannschaften!ID
                 rstSpielpaarungen!AuswaertsmannschaftID = rstAuswaertsmannschaften!ID
                 rstSpielpaarungen.Update
             <font color=blue>End If</font>
             rstAuswaertsmannschaften.Move<font color=blue>Next</font>
         <font color=blue>Loop</font>
         rstAuswaertsmannschaften.MoveFirst
         rstHeimmannschaften.Move<font color=blue>Next</font>
     <font color=blue>Loop</font>
End Sub

Listing 1: Anlegen von Spielpaarungen

Die Prozedur verwendet drei Recordset-Objekte: rstSpielpaarungen liefert die Daten der Tabelle tblSpielpaarungen und rstHeimmannschaften und rstAuswaertsmannschaften jeweils die Daten des Feldes MannschaftID der Tabelle tblLigenSpieljahreMannschaften. Dabei werden die Daten dieser beiden Recordsets nach dem Wert des Parameters lngLigaSpieljahrID gefiltert.

In einer äußeren Schleife durchlaufen wir die Elemente des Recordsets rstHeimmannschaften, in einer inneren die Elemente aus rstAuswaertsmannschaften. Dabei stellen wir den Datensatzzeiger der inneren Schleife immer wieder mit rst.MoveFirst auf den ersten Datensatz zurück, wenn wir alle Auswärtsmannschaften für die aktuelle Heimmannschaft durchlaufen haben. Innerhalb der Schleife prüfen wir dann, ob die aktuelle Heimmannschaft gleich der aktuellen Auswärtsmannschaft ist. In diesem Fall legen wir keine neue Spielpaarung an. Anderenfalls fügt die Prozedur einen neuen Datensatz zum Recordset rstSpielpaarungen hinzu und trägt die jeweiligen IDs für die Felder HeimmannschaftID und AuswaertsmannschaftID ein. Danach sieht die Tabelle tblSpielpaarungen für vier Mannschaften etwa wie in Bild 1 aus.

Bild 1: Spielpaarungen einer Vierer-Liga

Nun brauchen wir hier nur noch die Spieltage einzutragen. Und das wird eine interessante Aufgabe. Die Grundidee ist: Wir beginnen mit dem ersten Spieltag und suchen uns für diesen Paarungen heraus. Für das erste Spiel am ersten Spieltag kein Problem: Hier können wir einfach das erste Spiel auswählen. Danach wollen wir das erste Spiel aus der Tabelle tblSpielpaarungen suchen, dessen Heimmannschaft und dessen Auswärtsmannschaft nicht am ersten Spiel beteiligt sind. Soweit kein Problem – der erste Spieltag könnte so aussehen:

FC Bayern München - Borussia Dortmund
Eintracht Frankfurt - TSG Hoffenheim 1899

Für den zweiten Spieltag können wir dann eines der verbleibenden Spiele als Startpunkt nehmen, und zwar das nächste verfügbare in der Tabelle. Hier also:

FC Bayern München - Eintracht Frankfurt

Dazu passt dann:

Borussia Dortmund - TSG Hoffenheim 1899

Damit hat Bayern München allerdings direkt zwei Heimspiele und Hoffenheim gleich zwei Auswärtsspiele. Aber gut, das lässt sich bei einer Vierergruppe nicht vermeiden. Würden wir eine der beiden Paarungen umdrehen, hätten die beiden anderen Mannschaften entweder zweimal zuhause oder auswärts gespielt. Für den dritten Spieltag erhalten wir dann, wenn wir wieder das nächste noch nicht an einen Spieltag vergebene Spiel holen und dann das nächste Spiel mit den übrigen Mannschaften:

FC Bayern München - TSG Hoffenheim 1899
Borussia Dortmund - Eintracht Frankfurt

Spätestens hier ist die Verteilung von Heim- und Auswärtsspielen auffällig, denn FC Bayern München hätte nun drei Heimspiele in Folge.

Uns wurde schnell klar, dass es ein sehr aufwendiges Unterfangen werden würde, selbst mit Verfahren wie Rekursion eine programmgesteuerte Methode zum Erstellen eines Spielplans mit beispielsweise 18 Mannschaften zu erstellen.

Algorithmus nachbauen

Also haben wir im Internet geschaut, ob es nicht Informationen gibt, wie so ein Bundesligaplan zusammengestellt wird. Und Wikipedia hat unter https://de.wikipedia.org/wiki/Spielplan_(Sport) eine passende Erläuterung präsentiert, die wir nun in Form einer Prozedur für unser Datenmodell umsetzen wollen.

Hier lautet es zunächst:

“Im ersten Schritt wird dazu jeder der 18 Mannschaften außer einer, dem “Joker” (in diesem Fall dem Hamburger SV) eine zufällige Zahl zwischen 1 und 17 zugeordnet, woraufhin der “Joker” selbst die Nummer 18 erhält.”

Das ergibt eine Liste mit 17 Mannschaften:

1 Bayern München
2 Borussia Dortmund
...
17 Union Berlin

Weiter lautet es:

“Am Spieltag n (hier: 1 ? n ? 17) tritt der Verein mit der Nummer k gegen genau die gegnerische Mannschaft mit der Nummer l an, so dass der Rest der Summe beider Nummern k + l bei Division durch 17 genau den Rest n ergibt. Der “Joker” mit der Nummer 18 (in diesem Fall also der Hamburger SV) tritt schließlich gegen den Verein an, für den sich nach obiger Regel an dem betreffenden Spieltag kein Partner findet.”

Und schließlich für die Entscheidung, ob eine Mannschaft daheim oder auswärts antritt:

“Um zu ermitteln, welche Mannschaft Heimrecht hat, gilt in der Hinrunde folgendes: Ist die Summe der beiden Nummern k + l eine gerade Zahl, hat die Mannschaft mit der höheren Nummer Heimrecht; ist die Summe dagegen eine ungerade Zahl, hat die Mannschaft mit der niedrigeren Nummer Heimrecht. Der “Joker” mit der Nummer 18 schließlich hat nur Heimrecht gegen die Mannschaften mit den Nummern 8 bis 16, nicht aber 1 bis 7 und 17.”

Schauen wir, wie wir das in Programmform umsetzen können.

Als Erstes brauchen wir eine Liste der Mannschaften mit dem Index von 1 bis 18. Wir haben kein entsprechendes Feld in der Tabelle tblMannschaften vorgesehen, was auch keinen Sinn macht, da die Mannschaften ja in verschiedenen Spieljahren verschiedenen Ligen zugeordnet werden sollen. Viel praktischer wäre es, wenn wir in der Tabelle tblLigenSpieljahreMannschaften ein Feld hätten, wo wir jeder Mannschaft in der Zuordnung zu Liga/Spieljahr eine Nummer vergeben können.

Wir könnten zwar auch einfach die Mannschaften einer Liga einlesen und diesen dann die Zahlen von 1 bis 18 zuweisen, etwa in einer Collection, aber wenn wir die Zahlen direkt in der Tabelle tblLigenSpieljahreMannschaften speichern, kann der Benutzer auch die Zahlenzuordnung ändern und den Spielplan neu generieren, wenn dieser nicht seinen Anforderungen entspricht. Die Tabelle sieht nach dieser änderung in der Entwurfsansicht wie in Bild 2 aus.

Bild 2: Neues Feld in der Tabelle tblLigenSpieljahreMannschaften

Das neue Feld fügen wir auch zum Formular frmLigenSpieljahreMannschaften hinzu (siehe Bild 3).

Bild 3: Neues Feld im Formular frmLigenSpieljahreMannschaften

Username or Email

Passwort

Angemeldet bleiben