Hallo!
Ich wollte mal fragen, wie genau die Auslosungen bei Copa durchgeführt werden.
Denn wie hier schön zu sehen ist, tritt an jedem Spieltag fast ein komplettes Land gegen ein anderes an: http://copamundial.eu/stadion/pokal_spielplan.php?auswahl=3&runde=5
Demnach sind auch in den Gruppen hauptsächlich die gleichen Konstellationen an Ländern zu finden.
Könnte man die Auslosungen nicht etwas zufälliger gestalten oder wäre das programmiertechnisch zu aufwendig?
Ohne deinen Link angesehen zu haben, kann es vielleicht daran liegen das in der Gruppenphase einfach keine zwei Länder gleichzeitig spielen dürfen. Deswegen ist es momentan fast immer gleich, liegt vielleicht an der aktiven Länderanzahl?!
Zitat von: Chris am 11. April 2013, 15:46:35
Ohne deinen Link angesehen zu haben, kann es vielleicht daran liegen das in der Gruppenphase einfach keine zwei Länder gleichzeitig spielen dürfen. Deswegen ist es momentan fast immer gleich, liegt vielleicht an der aktiven Länderanzahl?!
Sorry, ich weiß nicht, was du damit meinst ::quest::
Er meint glaube 2 aus selben Land in einer Gruppe.
Zitat von: Marcel am 11. April 2013, 18:49:48
Er meint glaube 2 aus selben Land in einer Gruppe.
Ja, aber trotzdem gäbe es doch zahlreiche Möglichkeiten, bei denen man die Länder komplett frei losen kann, ohne dass zwei aus demselben Land in eine Gruppe müssten. Würde ich zumindest meinen.
ich kann wieder den beitrag nicht finden, hab vor langer zeit schon mal auf so eine frage geantwortet. und andre noch weit früher schon auf eine ähnliche.
lt. Andre ist es glaube ich technisch schwer realisierbar, das alles vollautomatisch läuft, weil irgendwelche zufälle das ganze wieder aus der bahn werfen konnten. ging damals glaube ich, das jedes team aus land 1 in eine zufällige gruppe, dann jedes team aus land 2, land 3, ... usw. gelost werden zB beim letzten land, zwei plätze in der gleichen gruppe freibleiben könnten.
sollte aber jemand einen funktionierenden algorithmus, der alle eventualitäten ausschließt, bereitstellen können wäre es sicher nicht die tragik diesen einzubauen.
schlagt mich wenns nicht so ist, aber ich denke es hieß damals so
die edith wieder mal: http://www.copaforum.de/index.php?topic=1632.msg45624#msg45624
Hab ich auch so in Erinnerung. Obwohl ich auch gedacht hatte, dass Andre was danach geändert hatte. Ich hatte damals eine Idee wie man vorgehen könnte aufgeschrieben...
Die aktuelle Auslosungsvariante ist darauf ausgelegt in jedem erdenklichem Fall ein korrekte/gültige Auslosung zu generieren.
Das setzt natürlich jede Menge Schranken und läßt nur noch wenig Spielraum für Zufall.
Das man die Reihenfolge der Vereine in den Ligen nachträglich nochmal zufällig auslost wäre aber sicher möglich. Ist sicher nur eine kleine Verbesserung, würde da den komplett gleichen Partienablauf zwischen einzelnen Ländern ein wenig aufbrechen.
Ansonsten könnte man über separate Auslosungsmechanismen nachdenken für die weniger problematischen Fälle. z.B. kann in der EL nie der Fall eintreten das ein Land mehr Teilnehmer hat als es Gruppen gibt. Das erspart sehr viele Sonderfälle und man könnte über eine komplett zufällige Auslosung nachdenken mit anschliessendem Tausch der "Problemfälle" bzw. verwerfen der Auslosung und nochmal neu anfangen. Aber da müsste ich mir nochmal detallierte Gedanken machen was davon wirklich praktikabel ist und ob das dann immer zu einer gültigen Auslosung führt.
Zitatkomplett zufällige Auslosung nachdenken mit anschliessendem Tausch der "Problemfälle" bzw. verwerfen der Auslosung und nochmal neu anfangen
Tauschen ist zwar eine mögliche aber keine sichere Strategie und könnte in einer Endlosschleife münden. Zumal hier keine Aussage über den Endzustand getroffen werden kann. Neu berechnen sollte die bessere Variante sein, auch wenn es keine Garantie gibt, dass dies am Ende eine gültige Lösung ist.
Ich kenne die aktuelle Umsetzung leider nicht, aber wenn ein wenig Laufzeit in Kauf genommen wird, liefert ein CSP oder SAT Solver für alle Fälle, in denen mehr Gruppen als Teams aus einem Land vorhanden sind, eine passende Paarung. Die Laufzeit sollte auch nicht so schrecklich sein, zumindest wenn die Anzahl der Teams nicht zu groß wird. Ich habe hier eigentlich ganz gute Erfahrungen gesammelt. Die Algorithmen sind dabei zwar nicht auf Zufall getrimmt, aber es bringt die Illusion mit sich, dass es doch zufälliger aussieht.
Biete auch gerne meine Hilfe an.
Eine Alternative die ich gerade mal raushauen möchte, wäre ein Topf für jedes Land in dem alle Teams enthalten sind, und dann den größten (bei Gleichstand einen zufälligen) Topf zu nehmen, Zufällig ein Team zu ziehen und diese in die Gruppe zu stecken die am wenigsten Teams hat und vorallem keines des gleichen Landes (bei Gleichstand wieder zufällig). Dies gibt zwar keine garantierte gültige Lösung, die Problemdomäne ist einfach zu komplex, sollte aber dazu führen, dass die Gruppen gleichmäßig gefüllt werden und die verbleibenden Teams am Ende noch gut über die Länder verteilt sind. Dies ermöglicht am Ende durch einen Forward-Check recht schnell die verbleibenden Möglichkeiten zu prüfen und eine gültige Lösung zu finden.
Dennoch ist die Lösung nicht zwingend besser als Tauschen.
Wie gesagt, ich hab keine Ahnung wie das zur Zeit läuft und was schon so umgesetzt und versucht wurde.
Einen CSP oder SAT-Solver mit PHP zu programmieren ist Folter. Das werde ich nicht machen :D Wenn du das möchtest. Die Eingabedaten sind: Gruppenanzahl, Gruppengröße, Liste mit Vereinen und Länderzugehörigkeit.
Aktuell sieht die Auslosung für die Gruppen so aus:
Länder werden zufällig gewählt und dann werden die einzelnen Teams aus den Ländern zufällig ausgewählt und der Reihe nach den Gruppen zugeordnet.
ZitatEinen CSP oder SAT-Solver mit PHP zu programmieren ist Folter. Das werde ich nicht machen großes Grinsen
Auf jeden Fall ist das Folter.
Ich kenne mich in PHP leider so gut wie gar nichtt aus und mag da eigentlich auch nicht wirklich viel lernen ;)
Gibt es denn Möglichkeiten direkt C, Java oder sonst irgendwelche Programm aus php heraus zu starten?
Wenn ja, dann bastel ich gerne eine entsprechende Schnittstelle um den Solver anzusteuern.
Ja solche Möglichkeiten gibt es aber ich denke das ist doch ein wenig Overkill für das Problem.
Also das Problem das es mehr Mannschaften als Gruppen gibt könnte man so auf das Problem mit weniger Mannschaften als Gruppen reduzieren indem man erst einmal die erste Reihe mit Mannschaften aus dem Land füllt das zu viele hat. Dann ist das Problem weg und nur die Gruppengröße hat sich geändert und die Anzahl noch zu verteilender Teams aus dem Land.
Wenn man dann bei der Auslosung Länderweise auslost (die mit den meisten Teams zuerst) und die Gruppen aus der Verlosung heraus nimmt in die man schon eine Mannschaft aus dem Land zugelost hat (bzw. die voll sind) sollte es relativ gut aufgehen.
Sollte dann am Ende die Auslosung nicht aufgehen dann könnte man Anfangen zu schauen wenn man in der Gruppe die noch einen Freien Platz hat mit Gruppe A tauschen könnte damit man den Platz besetzen kann... wenn das nicht geht weiter mit Gruppe B ...... so sollten keine Endlosschleifen entstehen. Und wenn man bei der letzten Gruppe angekommen ist und dort auch nicht tauschen konnte dann hat es nicht geklappt. Bin mir aber nicht sicher ob der Fall überhaupt eintreten kann.
Dann könnte man innerhalb der Gruppen nochmal mischen.
@kandara Wenn du Lust hast kannst du das mal in der Programmiersprache deiner Wahl umsetzen und schauen ob du einen Fall findest in dem das nicht funktioniert. Oder du nimmst den Streberweg und machst einen Mathematischen Beweis das es geht oder nicht.
Sobald im meiner WG die Küche renoviert ist, schau ich mir das mal an. Aber ein Beweis über dir richtige Funktion/Terminierung deines Algorithmus lass ich jetzt mal außen vor, Dafür hab ich einfach nicht genug Skills ;)
ZitatJa solche Möglichkeiten gibt es aber ich denke das ist doch ein wenig Overkill für das Problem.
Ja, nein. Der Vorteil ist, dass man sich um fast nichts mehr kümmern muss und das Problem ja auch ein NP-Problem ist. Dazu verwenden die Solver meinst gute Strategien und sind extrem Effektiv implementiert, da kann ein 0815 Entwickler nur mit einem Haufen Aufwand und einem spezialisierten Algorithmus dagegen anstinken. Ein einfacher Backtracking-Algorithmus ist ja schnell implementiert aber der könnte doch was lange rechnen.
ZitatWenn man dann bei der Auslosung Länderweise auslost (die mit den meisten Teams zuerst) und die Gruppen aus der Verlosung heraus nimmt in die man schon eine Mannschaft aus dem Land zugelost hat (bzw. die voll sind) sollte es relativ gut aufgehen.
Ab dem zweiten Land muss entschieden werden in welche Gruppe jetzt Teams gesteckt werden und damit auch welche zuerst voll sind. Mit dieser Entscheidung steht und fällt der ganze Algorithmus.
Potenziell aber sehr interessant. ich mach mich bei Gegelenheit mal daran, die verschiedenen Algorithmen zu implementieren und diese mal gegen Zufallsmengen von Gruppen und Teams antreten zu lassen. Vielleicht springt ja auch ein Gegenbeispiel dabei raus ;)
Zitat von: kandara am 03. Mai 2013, 21:11:55
ZitatWenn man dann bei der Auslosung Länderweise auslost (die mit den meisten Teams zuerst) und die Gruppen aus der Verlosung heraus nimmt in die man schon eine Mannschaft aus dem Land zugelost hat (bzw. die voll sind) sollte es relativ gut aufgehen.
Ab dem zweiten Land muss entschieden werden in welche Gruppe jetzt Teams gesteckt werden und damit auch welche zuerst voll sind. Mit dieser Entscheidung steht und fällt der ganze Algorithmus.
Für jedes Land wählst du zufällig aus den verfügbaren Gruppen (nicht voll und noch keiner aus dem Land) eins aus.
Zufällig bedeutet hier aber auch die Möglichkeit, dass ein Team in eine falsche Gruppe gesteckt wird und diese Gruppe damit voll ist, obwohl es eigentlich die einzige sinnvolle Wahl für ein anderes Team wäre. Du versucht das mit dem Tauschen dann zu fixen aber dies Garantiert ja nicht ,dass das Team dass du dann raus tauscht in der neuen Gruppe besser aufgehoben ist.
Ich rede hier einfach nur von einem ungüstigen Spezialfall.
Welche Laufzeitanforderungen gibt es eigentlich? Wie lange könnte so ein Algorithmus laufen und wielange sollte erlaufen?
Wir reden hier vom Sekundenbereich ;) ... also 5-10 Sekunden pro Auslosung maximal. Aktuell ist es eher so im Bereich < 1 Sekunde.
edit: ich bin mir mittlerweile auch sicher das der Algorithmus theoretische so wie ich ihn beschrieben habe eventuell keine Lösung findet, denke aber das das bei uns nur selten auftreten sollte.
Herausforderung. Wenn ich das in Java halten kann, dann sollte das ja kein Problem sein.
Ziel wäre <5 jedoch max 10 Sekunden.
Unfassbar aber war, ich habe Zeit gefunden und einen kleinen Algorithmus geschrieben. Kannste mir irgendwie Testdaten zur Verfügung stellen? Also Paare von "Name des Teams" und Name des Lands"? Es wäre sogar noch besser wenn du mir eine Anzahl an Ländern und min/max Teamaufkommen pro Land mitteilen könntest.
Ich habe zwar kleine Szenarien aber mit diesen auch gleich ein Extrema gefunden in denen mein reiner Zufallsalgorithmus sich in die Ecke gedrückt fühlt.
Ich habe mal den Tauschalgorithmus evaluiert mit Testläufen die 1000 Teams beinhalten aus 100 Ländern. Jedes Land stellt dabei mindestens 4 maximal 40 Teams.
Szenario 1: 1000 Testläufe mit 4er Gruppen:
Diese Teams habe ich dann in 1000 Testläufen auf den Algorithmus geworfen der dabei 4er Gruppen erstellen soll, also 500 an der Zahl.
Ergebnis:
Durchschnittliche Laufzeit 0.005 ms
Längste laufzeit: 15 ms
Szenario 2: 1000 Testläufe mit 2 er Gruppen:
Diese Teams habe ich dann in 1000 Testläufen auf den Algorithmus geworfen der dabei 2er Gruppen erstellen soll also 250 an der Zahl.
Durchschnittliche Laufzeit 0.008 ms
Längste laufzeit: 74 ms
Ich habe das ganze in Java geschrieben und evaluiert. Der start der JVM ist nicht mit eingerechnet. Die Zeiten beinhalten lediglich die reine Laufzeit des Algorithmus. Die sehr geringe Laufzeit liegt wohl an meinem kleinen Backofen der mit 3.4 Ghz rennt und ordentlich Speicher zur Verfügung hat. Also bitte nicht wundern beim Nachvollziehen.
Der Code ist auf Github [1] zu finden. Wie er zu benutze ist kann entweder aus dem Testprojekt abgeleitet oder durch Fragen an mich herausgefunden werden.
[1] https://github.com/IngoReimund/copamundial
:daumen: ::ap::