Fußball: Explosion der Möglichkeiten

Inhaltsverzeichnis

Für den Spielplan der Bundesliga gibt es mehr Möglichkeiten als Teilchen im Universum. Stephan Westphal hat eine Software geschrieben, die trotzdem eine fast optimale Lösung findet.

Westphal, 38, ist Professor an der TU Clausthal in der Arbeitsgruppe "Diskrete Optimierung". Er hat in Kaiserslautern über Online-Routenplanung und Maschineneinsatzplanung promoviert und danach als Berater für ein Unternehmen gearbeitet, das mathematische Optimierungssoftware herstellt. Einer der Kunden war die Deutsche Fußball Liga (DFL). So kam er in Kontakt mit der Sportbranche. Seitdem berät Westphal die DFL, die Basketball-Bundesliga und die Deutsche Eishockey Liga bei der Spielplangestaltung.

Technology Review: Herr Westphal, 18 Vereine müssen irgendwie gegeneinander spielen, das klingt überschaubar. Wozu braucht man da eine mathematische Optimierung?

Stephan Westphal: Es gibt bei 18 Mannschaften bereits mehr mögliche Spielpläne als Teile im Universum. Nehmen wir zum Beispiel einfach den Spielplan des letzten Jahres und vertauschen darin die Mannschaften. Dann habe ich für die erste Mannschaft 18 Möglichkeiten, für die zweite noch 17 und so weiter. Allein das ergibt 18 Fakultät Möglichkeiten. Das sind 6,4 mal 1015. Jetzt kann ich mir noch aussuchen, mit welchem der 17 Spieltage ich die Saison beginnen möchte und ob ich den Spielplan dann in der gleichen Reihenfolge wie vorher spielen möchte oder rückwärts.

Das sind wieder zwei Möglichkeiten. Jetzt könnte ich noch das Heimrecht bei allen Spielen tauschen, was mir wieder zwei verschiedene Möglichkeiten einräumt. Schließlich können Sie auch noch die einzelnen Spieltage hin und her tauschen. Und wenn man sich jetzt noch ein bisschen mehr Mühe gibt und weitere Optionen hinzuzieht, kommt man ruck, zuck auf eine Größe von 1080.

TR: Wie wurde es denn früher gemacht, ohne Computer?

Westphal: Im Wesentlichen so wie bei einem Blitzschachturnier: An einer Tischreihe spielt jeder gegen den, der ihm gegenübersitzt. Nach jedem Zug rutschen alle einen Stuhl weiter. Es gab für Spielplaner ein Buch, wo solche Spielpläne exemplarisch drinstanden. Dann brauchten sie nur noch die Platzhalter mit den entsprechenden Mannschaften zu besetzen.

TR: Und wo war dabei das Problem?

Westphal: Mittlerweile haben wir sehr viele Nebenbedingungen. In den Stadien finden zum Beispiel deutlich mehr große Konzerte und andere Veranstaltungen statt. Zudem sollte jede Mannschaft abwechselnd zu Hause und auswärts spielen. Es gibt auch Paare von Mannschaften, die nicht gleichzeitig zu Hause spielen sollten.

Dazu kommen noch dramaturgische Kriterien wie ein besonders tolles Eröffnungsspiel oder ein gelungener Saisonabschluss. Außerdem sollen alle Mannschaften den Spielplan als fair empfinden. Der Aufsteiger sollte also beispielsweise nicht gleich zu Beginn dreimal hintereinander gegen starke Mannschaften spielen müssen. Wenn Sie nur mit einem einzigen Spielplan antreten und jedes Jahr nur die Mannschaften austauschen, kommen Sie da ziemlich schnell an Ihre Grenzen.

TR: Also haben Sie den Computer zu Rate gezogen.

Westphal: Genau. Die DFL verwendet computergenerierte Spielpläne etwa seit Mitte der 2000er. Ich habe das Projekt 2008 übernommen und zwei Jahre später ein ganz neues Modell eingesetzt, mit dem es nun möglich ist, mehr Wünsche zu erfüllen, zum Beispiel können mehr andere Veranstaltungen in den Stadien abgehalten werden.

Das Entscheidende sind aber natürlich ausgeglichene Spielpläne. Wir können mit Fug und Recht behaupten, dass wir aus der Menge aller denkbaren Spielpläne den besten aussuchen können – oder zumindest einen, der bis auf 0,3 Prozent optimal ist.

TR: Auch der Computer macht also nicht alle wunschlos glücklich?

Westphal: Nein. Fast alle Mannschaften haben zum Beispiel zwei Heim- oder zwei Auswärtsspiele nacheinander. So etwas lässt sich nicht vermeiden, das kann man auch beweisen. Die Wünsche stehen manchmal auch direkt im Konflikt zueinander. Für jeden nicht erfüllten Wunsch vergibt das Programm Strafpunkte. Der Plan mit den wenigsten Strafpunkten ist der beste. Das Schöne an dem Algorithmus ist, dass er einem gleichzeitig auch eine untere Schranke angibt.