[PHP / Algemeen] Swiss tournament berekening

[Ypho]

Ik ben bezig met een stukje code om op basis van een aantal spelers een swiss tournament in te delen (à la MtG). Dit maak ik in PHP, maar de taal is hier niet belangrijk. De code kan ik wel maken, de vraag die ik heb is meer *hoe* ik het laatste stuk van de code kan gaan maken, welke berekeningen ik moet gaan doen, daar heb ik wat hulp bij nodig.

Voor de mensen die zich afvragen wat een swiss toernooi is:
- X aantal spelers, daarbij een Y aantal ronden (t/m 8 spelers 3 ronden, t/m 16 spelers 4 ronden etc)
- Winst 3 punten, verlies 0 punten, draw 1 punt
- Spelers nooit 2x tegen elkaar
- Bij oneven spelers, krijgt de laagste speler in de ranking een bye en 3 punten (mits niet eerder bye gehad dit toernooi)
- Spelers worden gepaired tegen elkaar op basis van ranking (sterksten tegen elkaar)
- Als spelers evenveel punten hebben, wordt de ranking bepaald op basis van andere statistieken (niet belangrijk in dit geval)
- Info: Wikipedia: Swiss-system tournament

In het kort betekent dit dat alle spelers "random" gepaired worden tegen elkaar (ronde 1). Ronde twee is vrij eenvoudig te maken, namelijk de spelers met 3 punten pair je tegen elkaar, de spelers met 0 punten en eventueel de spelers met 1 punt.

Tot zover gaat alles iedere keer zonder problemen!

Wat ik tot nu toe heb:
De code die ik tot nu toe heb is eigenlijk compleet, ik heb meerdere "testruns" gedraaid, en hier kwamen bijna altijd goede pairings uit. Tot het moment dat ik met een oneven aantal spelers ging spelen en er BYEs in het spel kwamen, en volgens mij ook een keer toen er in een ronde gelijkspel was, maar dat kan ik me niet zo snel herinneren, want dit ging later wel weer goed volgens mij.

Wat ik doe bij het maken van pairings in de code.
1. Ik zoek alle spelers die meedoen in het toernooi, die zijn gesorteerd op volgorde van standings en gaan in een array (#1 t/m #X)
2. Ik haal alle pairings op uit de database van eerdere ronden.
3. (Indien oneven aantal spelers) Ik kijk of de onderste speler een BYE heeft gehad, zo niet, geef ik de BYE, zo ja, kijk ik naar de een-na onderste speler etc... Totdat ik een speler met een BYE heb. Deze haal ik uit de array.
4. Ik pak de speler #1 uit de standings, kijk of deze al tegen speler #2 heeft gespeeld. Zo niet, pair ik deze en haal ze uit de array. Hebben #1 en #2 al tegen elkaar gespeeld, kijk ik of #1 al tegen #3 heeft gespeeld. Zo niet, pair ik deze, zo ja, kijk ik naar #1 en #4 etc. Iedere keer als spelers gepaired worden, haal ik ze uit de array.
5. Zo ga ik door totdat iedereen gepaired is.

Dit gaat goed in ongeveer 80% van de gevallen die ik getest heb. Echter kwam ik een testrun tegen waarbij speler #7 en #8 al eerder tegen elkaar gespeeld hebben. Deze kon ik dus niet pairen. Maar omdat er geen speler #9 was (ivm BYE) kon ik dit ook niet controleren.

Waar ik nu hulp bij zoek is het geval dat het fout gaat. Wat kan ik het beste doen als speler #7 en #8 al tegen elkaar gespeeld hebben. Omdat #1 t/m #6 al gepaired zijn, kan ik hier wat lastig in schuiven. (Op dit moment is er nog niets opgeslagen dus er kan nog van alles gewijzigd worden)

Waar ik zelf aan zat te denken:
Optie 1: Eerst pairen, en dan de speler die overblijft de BYE geven. Mogelijk probleem is dat niet de "slechtste" speler de BYE krijgt.
Optie 2: Groeperen op punten, en dan random gaan pairen tot iedereen met evenveel punten is gepaired, het probleem daarbij is alleen als je een oneven aantal mensen hebt met hetzelfde aantal punten.

Helaas kon ik met Googlen niet een manier vinden hoe ik precies deze berekeningen moet doen. Als iemand dit wel weet, of kan vinden, houd ik me aanbevolen. Ik weet bijvoorbeeld niet of het juist is om eerste de BYE te bepalen, of dat ik de laatst overgebleven speler de BYE moet geven.

TL;DR: Hulp nodig bij ontwikkelen pairing systeem. Werkt nu in ~80% van de gevallen, soms fout ivm dubbele pairing.

[KopjeThee]

Zou dit helpen?
http://www.fide.com/fide/....html?id=18&view=category
Bijvoorbeeld "Dutch":
http://www.fide.com/fide/....html?id=167&view=article

Verder gewoon debuggen? Veel tussenresultaten bekijken, code stap voor stap doorlopen.

[ Voor 20% gewijzigd door KopjeThee op 14-07-2014 10:43 ]

[Ypho]

Die pagina's had ik ook gezien. Dit is vooral gericht op schaken waarbij ook rekening wordt gehouden met startkleur (Z/W). Dat is hier niet zo van toepassing. Even iets verder verdiept in die website, er staat veel informatie.

In ieder geval ben ik eruit dat ik de BYE aan het einde van de pairings moet gaan uitdelen aan de overblijvende speler.

Echter lost dit (misschient) nog niet het probleem op bij een even aantal spelers, dat spelers toch dubbel gepaired kunnen worden. Hoe ik dit kan voorkomen zit wel in mijn hoofd, maar programmeer-technisch kan ik er niet mijn vinger op leggen hoe ik dit moet maken (qua logica, code is geen probleem).

Ik zal toch eens kijken of ook (een deel van) optie 2 mogelijk is, en dan up- en downpairen. Helaas heb ik nergens een open source stukje software kunnen vinden waar in in de code kan bladeren om eens te kijken hoe het daar zit...

Als ik het eerste deel heb gemaakt zal ik weer eens wat tests runnen.

[ Voor 4% gewijzigd door Ypho op 15-07-2014 09:35 ]

[Rannasha]

Sowieso zou ik de BYE interpreteren als een extra speler, die altijd een negatief puntenaantaal heeft. Op die manier hoef je geen aparte code te schrijven die de BYE uitdeelt, maar kun je gewoon de pairing-functie gebruiken. Met een negatief puntenaantal zal de pairing-functie proberen om de BYE te pairen met de laagste reguliere speler (die altijd een niet-negatief puntenaantal zal hebben), voor zover deze pairing niet al eerder plaats heeft gevonden.

edit: Eventueel kan de BYE-speler ook constant 0 punten hebben als je werkt met unsigned integers voor het puntenaantal, dat maakt verder niet uit.

[ Voor 14% gewijzigd door Rannasha op 15-07-2014 09:45 ]

[naitsoezn]

Optie 1 lost het probleem niet helemaal op: Je kunt immers met een even aantal spelers ook met 2 spelers overblijven die al tegen elkaar gepaard zijn geweest.

Een derde optie (die het probleem waarschijnlijk ook niet helemaal oplost) is om de pairing opnieuw te doen als je merkt dat het 'mis' gaat, maar dan van onderaf. Of, in het algemeen gezegd, zou je net zo lang opnieuw kunnen beginnen met pairen, maar dan telkens met een ander beginpaar.

[Janoz]

Je kunt een depth first aanpak toepassen. Je pakt telkens het meest voor de hand liggende paar totdat je alles gematched hebt. Komt het niet uit dan doe je 1 stap terug en match je het op 1 na voor de hand liggende paar. Dat doe je net zo lang totdat alles ingedeeld is.

[Sgreehder]

Misschien heb je hier wat aan:

http://pastebin.com/3THq9bZj

Ik sorteer op het aantal punten, in het zeldzame geval dat iemand met een Bye op zijn naam in een oneven groep onderaan komt te staan (en dus weer een Bye toevalt), schuif ik deze persoon eenvoudigweg weer bovenaan de lijst. Dit kan een natuurlijk een tikkeltje beter, maar eenvoudiger wordt het niet.

[Ypho]

Bedankt voor de tips, ik kan hier wel wat mee.

Sgreehder schreef op dinsdag 15 juli 2014 @ 17:22:
Misschien heb je hier wat aan:

http://pastebin.com/3THq9bZj

Ik sorteer op het aantal punten, in het zeldzame geval dat iemand met een Bye op zijn naam in een oneven groep onderaan komt te staan (en dus weer een Bye toevalt), schuif ik deze persoon eenvoudigweg weer bovenaan de lijst. Dit kan een natuurlijk een tikkeltje beter, maar eenvoudiger wordt het niet.

Top! Nu is mijn code niet veel verschillend van wat jij hebt. Maar is het in jouw code niet ook gewoon mogelijk dat spelers twee keer gepaired worden tegen elkaar? Waar bij mij het probleem zit/zat is wanneer de onderste speler (test speler 2) in de array al tegen de huidige speler (speler 1) heeft gespeeld. Als ik jouw code even heel snel doorlees, kan hij blijven hangen in de while ($player1->hasPlayedAgainst($player2)) (of hij moet onderuit gaan als $player2 geen array item meer is...

Mijn code lijkt qua werking op de jouwe, dus ik was niet heel verkeerd bezig ofzo

naitsoezn schreef op dinsdag 15 juli 2014 @ 09:43:
Optie 1 lost het probleem niet helemaal op: Je kunt immers met een even aantal spelers ook met 2 spelers overblijven die al tegen elkaar gepaard zijn geweest.

Een derde optie (die het probleem waarschijnlijk ook niet helemaal oplost) is om de pairing opnieuw te doen als je merkt dat het 'mis' gaat, maar dan van onderaf. Of, in het algemeen gezegd, zou je net zo lang opnieuw kunnen beginnen met pairen, maar dan telkens met een ander beginpaar.

Wat ik inderdaad zou kunnen doen is de array die ik heb shufflen en dan sorteren op puntenaantal, nu gaat dit op basis van ranking (puntenaantal, winstpercentage, tegenstander winstpercentage en nog wat statistieken). En dan inderdaad bijvoorbeeld 10x proberen random pairings te maken.

Rannasha schreef op dinsdag 15 juli 2014 @ 09:43:
Sowieso zou ik de BYE interpreteren als een extra speler, die altijd een negatief puntenaantaal heeft. Op die manier hoef je geen aparte code te schrijven die de BYE uitdeelt, maar kun je gewoon de pairing-functie gebruiken. Met een negatief puntenaantal zal de pairing-functie proberen om de BYE te pairen met de laagste reguliere speler (die altijd een niet-negatief puntenaantal zal hebben), voor zover deze pairing niet al eerder plaats heeft gevonden.

edit: Eventueel kan de BYE-speler ook constant 0 punten hebben als je werkt met unsigned integers voor het puntenaantal, dat maakt verder niet uit.

Dit is zeker een idee ja, ik ga even kijken wat hier de eventuele consequenties zijn (ivm eventuele foreign keys). Ik denk dat dit een betere oplossing is voor het hele BYE verhaal. Ik moet alleen wel zeker weten dat dan niet een speler die hoog in de ranking staat de BYE krijgt. Uiteindelijk denk ik dat dit hetzelfde oplevert als de laatst overgebleven speler de BYE geven (of wellicht is dat zelfs handiger). Maar stel dat ik 9 spelers heb, en speler 7 heeft al gespeeld tegen 8 en 9, dan moet ik dus gaan kijken of ik 7 de BYE geef, en 8+9 dan pair.

De Wizards Event Reporter (van Magic: The Gathering) doet eigenlijk precies wat ik wil, alleen hebben zij geen uitgebreide uitleg hoe hun pairing procedure precies werkt (wel het berekenen van de statistieken, dat heb ik al geimplementeerd).

[Sgreehder]

Ypho schreef op woensdag 16 juli 2014 @ 08:03:
Top! Nu is mijn code niet veel verschillend van wat jij hebt. Maar is het in jouw code niet ook gewoon mogelijk dat spelers twee keer gepaired worden tegen elkaar? Waar bij mij het probleem zit/zat is wanneer de onderste speler (test speler 2) in de array al tegen de huidige speler (speler 1) heeft gespeeld. Als ik jouw code even heel snel doorlees, kan hij blijven hangen in de while ($player1->hasPlayedAgainst($player2)) (of hij moet onderuit gaan als $player2 geen array item meer is...

Er moet inderdaad een kleine toevoeging worden gemaakt om te voorkomen dat hij blijft hangen (wat met php toch niet echt een risico is), maar daar kan Janoz' tip gelijk worden toegepast - je houdt aan met welke speler je bent gestart, en als het pairen volledig mislukt (dus je laat $players leeglopen in een andere array ipv. achteraan plakken) begin je met de volgende vanaf boven, and so on. En als het dan niet echt lukt, doe je een shuffle.

[ Voor 5% gewijzigd door Sgreehder op 16-07-2014 09:58 ]

[Janoz]

Mijn bedoeling is niet om helemaal opnieuw te beginnen, maar telkens een stapje terug doen en dan de volgende kiezen. Een methode die de het meest gunstige paar neemt, en vervolgens zichzelf aanroept met de overgebleven spelers. Als het resultaat van die aanroep is dat er geen mogelijke verdeling is dan neem je de op 1 na gunstigste en roep je de methode weer aan. Eigenlijk is het een bruteforce methode die alle combinaties bij langs gaat, maar dan wel met de meest gunstigste begint en stopt zodra er een combinatie gevonden is.

[Ypho]

Janoz schreef op woensdag 16 juli 2014 @ 12:30:
Mijn bedoeling is niet om helemaal opnieuw te beginnen, maar telkens een stapje terug doen en dan de volgende kiezen. Een methode die de het meest gunstige paar neemt, en vervolgens zichzelf aanroept met de overgebleven spelers. Als het resultaat van die aanroep is dat er geen mogelijke verdeling is dan neem je de op 1 na gunstigste en roep je de methode weer aan. Eigenlijk is het een bruteforce methode die alle combinaties bij langs gaat, maar dan wel met de meest gunstigste begint en stopt zodra er een combinatie gevonden is.

Dit is wat mijn code doet, alleen als er geen mogelijke pairing overblijft gaat hij niet terug, dat is het enige waar ik wat op moet verzinnen.

Ik ben er inmiddels wel achter dat de "laatst overgebleven" speler de BYE geven niet succesvol is, omdat het zo kan zijn dat niet de "slechtste" speler de BYE krijgt, of dat de slechtste speler al een BYE heeft gehad.

Verder heb ik nog wat kleine aanpassingen gedaan qua pairings, de tests die ik gisteren heb gedaan, zijn succesvol verlopen, beter dan voorheen! Ik zal eens een scriptje unit test schrijven die 1000 toernooien aanmaakt, inclusief de ronden, scores en pairings. Dan eens kijken wat het resultaat is. Het wordt dan ook wat makkelijker om gericht naar foutjes te zoeken.

Voor zover bedankt voor de hulp!