Turnier-Plan Teams

[java123]

Hallo,

vielleicht kann mir jemand bei folgendem Problem helfen. Ich suche einen Algorithmus der mir Matchups aus einer Gruppe von Teams baut. Folgendes soll gelten:
1. Jede Paarung darf es im laufe des Turniers nur einmal geben.
2. Ich möchte die Paarungen so gestalten das möglichst gleichstarke Spieler gegeneinander antreten.
3. Das ganze nicht durch bruteforce lösen.
Ich habe schon ein paar Versuche hinter mir und das Problem ist jedes mal das die letzte zu losende Paarung aus zwei Teams bestehen kann die schoneinmal aufeinandergetroffen sind.
Ein Denkanstoß oder grober Algorithmus wäre super.

Grüße

 

[SlaterB]

was für eine Art von Turnier, aus dem Wort an sich kann man doch überhaupt nichts herauslesen,
wenn man an ein KO-System wie DFB-Pokal denkt, ist doch ausgeschlossen, dass zwei Teams mehrmals aufeinander treffen

sortierte dafür z.B. alle Teams der Stärke nach und nimm dann je 2, die gegeneinander spielen,
falls es nicht genau 32, 64 usw. Teams sind, bekommen ein paar Freilose, evtl. erst in höheren Runden

(30 Teams:
14 spielen gegen gegeneinder, 2 Freilose, dann bleiben 16 über für die nächste saubere Runde,
oder 15 spielen gegeneinander, 0 Freilose, dann in der Runde der letzten 15 ein Freilos und 7 Duelle
-> erst VF komplett, weniger unfaire Freilose)

 

[Tharsonius]

Ich entwickle gerade selber an einem Turnierplaner. Meiner ist für Tabletop Spiele.
Da ist die allgemeine Anforderung auch, dass möglichst gleichstarke Spieler gegeneinander treten sollen und vorallem eine Paarung nicht doppelt vorkommen darf, im laufe des Turniers. Von Runde zu Runde fliegt aber niemand raus, das heisst der Spielerpool jeder Runde bleibt konstant (von einigen extrem seltenen Ausnahmen abgesehen).

Ich habe den Paarungs-Algorithmus zwar selber noch nicht (weil ich noch nicht soweit bin), aber paarungen werden üblicherweise so gebildet:
1. Aus allen vorherigen Runden wird ein Ranking gebildet.
2. Paarung 1 bilden: Position 1 spielt gegen Position 2 des Rankings.
3. Sollte die Paarung bereits zuvor einmal gewesen sein, dann wird Position 2 durch 3 ersetzt. Gibt es die auch schon spielt 1 gegen 4 usw. Bis eine Paarung gefunden wurde.
4. Jetzt wird Paarung 2 gebildet: Position 3 gegen Position 4 des Rankings (wenn 1. gegen. 2. spielt)
5. Das ganze geht nun solange weiter bis alle Spieler vergeben wurden.

Kniffelig wird das ganze gegen Ende hin, wenn die Ausweichmöglichkeiten eingeschränkter sind. Bei meinen Erfahrungen aus mehreren Turnieren, die ich bisher abgehalten habe (habs bisher immer mit Excell gemacht) fangen die wirklichen Paarungsbildungsprobleme etwa ab der 4. Runde an.

 

[java123]

Tharsonius beschreibt genau mein Problem, bzw den Algorithmus den ich schon ausprobiert habe Hab meine Frage sehr undeutlich gestellt.
(Du spielst nicht zufällig MTG?)

Ich kann ja mal ein Beispiel nennen. Es wird gelost für 6 Spieler, nach Ihrer Spielstärke von 1-6 geordnet:
Erste Runde: (1,2) (3,4) (5,6)
Zweite Runde: (1,3) (2,4) (5,6)

Schaue mir gerade einen Algorithmus zur Kantenfärbung an, der hilft evtl. weiter.

Grüße

 

[Gast2]

Läuft das ganze denn später auf ein "alle gegen alle" hinaus?
Wenn ja dann kommst du ja nicht drumrum, dass irgendwann mal der Stärkste gegen den Schwächsten spielt. Ich würde mir einfach zuerst alle Spieltage mit dem dazugehörigen Paarungen bilden. Bei z.b. vier Teams würdest du auf 4 Spieltage kommen. Jetzt könntest du diese Spieltage so sortieren, dass am Anfang immer möglichs gleichstarke Teams gegeneinander spielen, im späteren Verlauf des Turniers würden dann diejenigen Gegeneinander spielen deren Stärkenunterschied groß ist.

Für die Sortierung würde ich folgendes verwenden:
Jedes Team besitzt einen Stärkewert. Für jede Paarung eines Spieltages bestimmt du den Stärkeunterschied (|StärkeA - StärkeB|). um einen Spieltag bewerten zu können addierst du alle Stärkeunterschiede der Paarungen auf und erhälst so eine Größe nach der du sortieren kannst. (Um zu gewährleisten dass die Stärken/Schwächeren Teams am anfang möglichst gegeneinander spielen kannst du den Stärkeunterschied noch mit der Stärke des Stärkeren/Schwächeren Teams multiplizieren, da hast du dann noch viele Variationsmöglichkeiten )

Implementieren würd ich das in etwa so:
Du hast ne Klasse Turnier mit ner ArrayList<Spieltag> in der du alle Spieltage des Turniers hälst.
Die Klasse Spieltag beinhaltet eine ArrayList<Paarung>, bewertet sich (z.b. mit der oben genannten Methode) und implementiert Comparable (damit man die ArrayList<Spieltag> aus Turnier sortieren kann ).
Paarung besteht auf 2 Teams, etc.


Oder so ähnlich

 

[andiv]

Wenn jeder gegen jeden einmal spielen soll, dann Rundenturnier ? Wikipedia
Wenn Leute rausfliegen sollen, dann K.-o.-System ? Wikipedia
Wenn es zuviele Teilnehmer gibt um Jeder-gegen-Jeden durchzuführen, dann evtl. Schweizer System ? Wikipedia

Wenn eines dieser Systeme für dich passen sollte, dann findest du sicher auch im Internet passende Algorithmen dazu.

 

[java123]

Läuft das ganze denn später auf ein "alle gegen alle" hinaus?

Nein, definitiv nicht, das würde zu lange dauern und es soll an einem Tag ausgetragen werden.

Für die Sortierung würde ich folgendes verwenden:
Jedes Team besitzt einen Stärkewert. Für jede Paarung eines Spieltages bestimmt du den Stärkeunterschied (|StärkeA - StärkeB|). um einen Spieltag bewerten zu können addierst du alle Stärkeunterschiede der Paarungen auf und erhälst so eine Größe nach der du sortieren kannst. (Um zu gewährleisten dass die Stärken/Schwächeren Teams am anfang möglichst gegeneinander spielen kannst du den Stärkeunterschied noch mit der Stärke des Stärkeren/Schwächeren Teams multiplizieren, da hast du dann noch viele Variationsmöglichkeiten )

So eine ähnliche Idee hatte ich auch. Aber wie sieht es mit dem Rechenaufwand bei steigender Teilnehmerzahl aus? Und wie berechne ich die Tupel passen für die einzelnen Runden?
Bei sechs Teilnehmern wäre es ja folgendes:
(1,6) (2,5) (4,3)
(1,3) (2,6) (4,5)
(1,5) (2,4) (3,6)
(1,2) (3,5) (4,6)
(1,4) (2,3) (5,6)

Das Schweizer System wäre eventuell noch etwas, wobei es eher für eine sehr große Anzahl an Teilnehmern geeignet scheint. Das ganze wird sich bei uns nur im Rahmen von 8-20 Teilnehmern bewegen.

 

[mvitz]

Als ehemaliger Schachspieler, kann ich dir versichern, dass sich das Schweizer System auch für kleinere Gruppen eignet und funktioniert.

 

[Tharsonius]

@Java123: Ich spiele MTG, aber nicht Turniermäßig. Nur sporadisch mal gegen Freunde. Die Karten sind mir zu teuer, das verträgt sich nicht mit meinen anderen Hobbies ;-)


Allgemein, im Tabletop wird üblicherweise das Schweizer System verwendet. Das hatte ich auch vom Ablauf beschrieben.

Bei Tabletopturnieren haben wir immer 3 Spiele bei ~30 Teilnehmer. Ergo geht jeder gegen jeden nicht.
Wir haben bereits verschiedene Paarungssysteme ausprobiert, teils sogar eigene Konstrukte, das alles hat sich aber nicht als praktikabel erwiesen. Daher sind wir seit Jahren nur noch beim Schweizer System, auch wenn 3 Spiele eigentlich etwas wenig sind um vernünftig einen Sieger ausspielen zu können.


Zu dem Problem hin, gegen Ende doppelte Paarungen zu haben, das habe ich immer so gehandhabt, dass ich (bei 30 Spielern) die letzten 3 Paarungen immer erst normal gebildet habe und wenn das nicht passt, dann die einfach so untereinander gemischt habe, dass das passt. Beschwert hat sich bisher keiner und bei 30 Spielern sind die letzten 6 auch etwa gleich gut.

 

[java123]

Ich mache das ganze nun so das ich erstmal mehrere Listen anlege mit allen möglichen Matchups. Zwei Teilnehmer werden maximal einmal aufeinander treffen. Von den Listen wähle ich dann die aus, bei der die Summe der Beträge der Punktdifferenzen aller Matchups am geringsten ist.
Wie gut das in der Praxis funktioniert wird sich noch zeigen.