1. inleiding
2. kwaliteitsfactor
3. ontmoetingenmatrix, competitiematrix en coincidentiematrix
4. strategie
5. Klik hier voor de homepage .

inleiding

De eerste versie optimaliseerde alleen maar de kwaliteitsfactor. Al bij het eerste het beste testgeval bleek dat dit niet voldoende was. Voor een competitie van 5 zittingen van 6 ronden, met 16 paren, vond ik zomaar een Qf van 100. Maar bij inspectie van de resultaten bleek dat de ontmoetingen helemaal niet gelijkmatig verdeeld waren. Er waren zelfs paren die elkaar helemaal niet ontmoet hadden! Dat vindt natuurlijk niemand acceptabel na 5 zittingen, ook al is de kwaliteitsfactor optimaal. Het criterium voor een optimale balans diende dus te worden aangepast.

Volgende versies optimaliseren in eerste instantie de eerlijke verdeling van de directe ontmoetingen, en pas bij oplossingen van gelijke kwaliteit qua ontmoetingen wordt er gekeken naar de balans.

Later kwam er bij die ontmoetingen nog een verfijning. Niet alleen de ontmoetingenmatrix als geheel moet zo vlak mogelijk zijn, maar je wil ook dat overblijvende uitschieters zo gelijkmatig mogelijk over de deelnemende paren verdeeld zijn.

Tenslotte kwam er nog een wens bij. Je wil niet alleen dat de ontmoetingen en de balans in evenwicht zijn, maar ook rusttafels die optreden bij een oneven aantal paren moeten eerlijk verdeeld worden.

Omdat het programma ook moet kunnen werken met wegblijvers en dus met zittingen met verschillende aantallen deelnemers was een meer algemene versie van de scorematrix nodig. In de originele versie is het gewicht van een ontmoeting de halve top h (oftewel het aantal keren dat een spel gespeeld wordt - 1). Als je 2 zittingen optelt met verschillende waarden van h is dat niet langer acceptabel. In een normale competitie telt immers ieder spel even zwaar mee. We willen dus graag iedere directe ontmoeting hetzelfde gewicht geven, ook in een competitie van meerdere zittingen met wisselende opkomst, waarbij het getal h dus kan verschillen per zitting. Dus werden de gewichten geschaald: voor een directe ontmoeting 1, voor een indirecte vergelijking 1/h. Ter onderscheid met de scorematrix zoals die bij de balans gebruikt wordt noem ik deze geschaalde matrix de competitiematrix.

Deze competitiematrix heeft een eenvoudige interpretatie: element M_ij is het effectieve aantal ontmoetingen tussen paar i en paar j. Vergelijk dit met de ontmoetingenmatrix waar element M_ij het werkelijke aantal ontmoetingen is. Het effectieve aantal is gelijk aan het werkelijke aantal, gecorrigeerd voor het effect van het spelen van andere spellen in gelijke dan wel tegengestelde windrichting. Verderop meer over deze matrices.

kwaliteitsfactor

Op soortgelijke wijze wordt ook voor de ontmoetingen een kwaliteitsfactor gedefinieerd. Deze noemen we Qo.

Zowel voor Qo als Qc geldt:

Q = 100·g² / (SS/N + g²)

waarbij:

g	=	het gemiddelde aantal ontmoetingen tussen 2 paren
N	=	het aantal mogelijke combinaties van 2 paren.
SS	=	de som van de N kwadraten ( Mij - g ) ²
		waarin Mij het aantal ontmoetingen, resp. effectieve ontmoetingen, is tussen de paren i en j.
Als alle getallen Mij gelijk zijn wordt Q gelijk aan 100, zo niet dan is de waarde kleiner dan 100.

ontmoetingenmatrix, competitiematrix en coincidentiematrix

Een verdere verfijning is om met een asymmetrische functie te werken. Bijvoorbeeld na 6 zittingen mag je hopen dat alle paren elkaar minstens één keer ontmoet hebben. Als dan het gemiddelde aantal ontmoetingen 2 is, wil je een zwaardere "straf" geven voor een 0 dan voor een 4. Deze twee effecten zijn echter niet onafhankelijk van elkaar. Als er paarcombinaties zijn met minder dan het gemiddelde aantal ontmoetingen zijn er noodzakelijkerwijs ook combinaties met meer dan het gemiddelde. Deze verfijning bleek dan ook weinig effectief en vanaf versie 3.9 zien we er van af.

De competitiematrix heeft dezelfde structuur en is hier nauw mee verwant. Hieruit kunnen we aflezen hoe vaak twee paren elkaar effectief ontmoet hebben. Met effectief bedoelen we dat indirecte ontmoetingen ook meegewogen worden, dat wil zeggen er wordt rekening wordt gehouden met de invloed op de score van het spelen in gelijke en tegengestelde windrichting.

Ieder element i, j van de competitiematrix is gelijk aan

• het aantal keren dat paar i en paar j tegen elkaar gespeeld hebben, vermeerderd met
• 1/h voor iedere keer dat paar i en j in dezelfde windrichting gespeeld hebben
• -1/h voor iedere keer dat paar i en j in tegengestelde windrichting gespeeld hebben maar niet tegen elkaar

Deze matrix is dus in feite de scorematrix zoals we die kennen van de balans maar dan anders genormaliseerd. De normalisatie zoals daar gegeven is hier niet bruikbaar zoals in de inleiding uitgelegd.

Samenvattend: element i,j van de ontmoetingenmatrix is het aantal ontmoetingen, element i,j van de competitiematrix is het aantal effectieve ontmoetingen tussen paar i en paar j, Bij een competitie met een perfecte overall balans zijn na afloop de matrices aan elkaar gelijk, en ieder element van beide is gelijk aan het gemiddeld aantal ontmoetingen.

Tenslotte geeft picolo ook nog een coincidentiematrix waarin wordt aangegeven hoe vaak twee paren gelijktijdig aanwezig geweest zijn. Deze getallen zijn dus een bovengrens van de waarden in de ontmoetingenmatrix.

Strategie

• We gaan uit van een door de gebruiker gegeven indeling. Als deze niet bekend is nemen we een random indeling.

• Iteratie 0. Deze indeling wordt geoptimaliseerd door 2 paren te verwisselen. Hierbij wordt gekozen voor die verwisseling die de grootste verbetering van de indeling oplevert. Voor details van deze procedure zie verderop. Is er geen verdere verbetering te bereiken door het verwisselen van 2 paren, dan is deze indeling "uitgeput". Is het eindresultaat beter dan de oorspronkelijke indeling dan vervangen de oorspronkelijke indeling door dit eindresultaat.

• Volgende iteraties. Met behulp van de toevalsgenerator wordt een "random" indeling gegenereerd. Verder is het proces exact hetzelfde als bij iteratie 0.

• Dit hele proces wordt zo vaak als gewenst herhaald, steeds met een nieuwe set op toeval gebaseerde beginwaarden. Daarbij wordt uiteraard de "overall" beste indeling bewaard.

• Details

  Voor het optimaliseren worden een aantal criteria gebruikt.
  1. De spreiding in de ontmoetingenmatrix, i.e. som van de 4e machten van (het aantal ontmoetingen minus het gemiddelde) gesommeerd over de hele ontmoetingenmatrix. We noemen dit So.
  2. De spreiding in het aantal rusttafels. Een rusttafel wordt hierbij opgevat als een ontmoeting met een denkbeeldig, afwezig, paar. We gebruiken dan dezelfde formule, en nemen de som van de 4e machten van (het aantal ontmoetingen met dit pseudopaar minus het gemiddelde) gesommeerd over alle paren. We noemen dit Sr.
  3. De spreiding in het aantal ontmoetingen per paar. Hiertoe wordt eerst voor ieder paar afzonderlijk de som van de bij (1.) beschreven 4e machten bepaald, gesommeerd over alle tegenstanders van dat paar. De kwadraten van deze resultaten worden bij elkaar opgeteld. De wortel hieruit noemen we Sp.
  4. De spreiding in de competitiematrix, i.e. som van de 4e machten van (het effectieve aantal ontmoetingen minus het gemiddelde) gesommeerd over de hele competitiematrix. We noemen dit Sc.

  De zoektactiek die in de iteraties gebruikt wordt bestaat uit twee fasen.

  1. Uitgaande van een gegeven, random, indeling zoeken we de gunstigste indeling die bereikt kan worden door telkens twee paren te verwisselen.
  2. Is deze indeling gunstiger dan de beste indeling tot dusver, dan wordt dit nu de beste indeling.

  Proces (A) verloopt als volgt:

  1. bereken de waarden van Sr, So, Sp, Sc die volgen uit de beginwaarden.
  2. Nu gaan we één voor één voor alle mogelijke combinaties van 2 paren kijken wat er gebeurt als we die 2 paren omwisselen. Is hierbij So+Sr verbeterd, dan vervangen we Sr, So, Sp en Sc door de nieuwe waarden, en onthouden om welke 2 paren het ging.
  3. Is So+Sr niet verbeterd maar wel gelijk gebleven dan kijken we of Sp verbeterd is. Zo ja, dan vervangen we Sp en Sc door de nieuwe waarden en onthouden weer de 2 paren.
  4. Zijn So en Sp gelijk gebleven dan kijken we of Sc verbeterd is. Zo ja, dan vervangen we Sc door de nieuwe waarde en onthouden weer de 2 paren.
  5. Voor dat we naar de volgende combinatie van 2 paren gaan maken we de vorige verwisseling ongedaan, ook als deze een verbetering was. Daarna terug naar 2 totdat we klaar zijn.
  6. Het resultaat van deze 'loop' is dat we de gunstigste verwisseling van 2 paren gevonden hebben. Deze gunstigste indeling slaan we op en gebruiken we als uitgangspunt voor een herhaling van het proces vanaf stap 1. Of, als er geen verbetering is opgetreden, zijn we klaar met onze gerichte zoekactie. De indeling die we nu hebben kan dus niet verbeterd worden door alleen 2 paren om te wisselen.
     Het is gebleken dat in uitzonderlijke gevallen dit proces tot een herhaling van zetten kan leiden. Dit heeft te maken met het feit dat we bij de bepaling of iets beter of gelijk is met een zekere tolerantie werken. Daarom wordt het proces na een aantal herhalingen afgebroken als het niet vanzelf convergeert.

  In fase (B) wordt de beste oplossing geselecteerd op basis van de criteria Sr, So, Sp en Sc, in deze volgorde van prioriteit. In andere woorden, de gelijkmatige verdeling van de rusttafels heeft topprioriteit, gevolgd door gelijkmatige verdeling van ontmoetingen en pas daarna van de balans van de competitie. Dit is een praktische tegemoetkoming aan de wens van de spelers, die in de eerste plaats zo min mogelijk rusttafels willen, in de tweede plaats zoveel mogelijk verschillende tegenstanders, en pas daarna het ongrijpare aspect balans van belang vinden.
  

  Voetnoten.

  1. Waarom afzonderlijk criteria So en Sp?
     Laat ik dat illustreren aan de hand van een voorbeeld.
     Kijk eens naar 2 regels van een ontmoetingenmatrix die er ofwel zo uitzien (de '*' zijn de ongedefineerde diagonale elementen, het betreft hier dus paren 6 en 7):

        2   1   2   0   1   *   1    0   1   1   1   1   1   0  
        1   0   1   1   1   1   *    1   1   1   1   1   1   1  
     

     ofwel zo:

      
        2   1   1   1   1   *   1    0   1   1   1   1   1   0  
        1   0   1   1   1   1   *    1   1   2   0   1   1   1 
     

     In het eerste geval heeft paar6 10 verschillende tegenstanders ontmoet, waarvan 2 twee keer. Paar7 ontmoet 12 verschillende tegenstanders ieder een keer.
     In het tweede geval ontmoeten ze beide 11 verschillende tegenstanders.
     Het is duidelijk dat het tweede schema beter in balans is dan het eerste. Maar de So is in beide gevallen gelijk! Want de beide matrices bevatten precies even veel 0-en, 1-en en 2-en.

  2. Het gebruik van So+Sr als criterium in fase (A), in plaats van Sr en So afzonderlijk, komt op hetzelfde neer als het consequent beschouwen van het pseudopaar "rusttafel" als een echt paar. Het heeft als voordeel het sneller toewerken naar een gunstige oplossing en het vermijden van "uitschieters" zoals een oplossing met een kleine Sr ten koste van een heel grote So.

  3. Rusttafels
     Het aantal aantal keren dat men een rusttafel heeft wordt voor iedere paar afzonderlijk opgeteld vanaf zitting 1. Het is mogelijk om deze getallen vóór het begin van zitting 1 al een beginwaarde te geven, met name de waarde van de voorafgaande competitieronde. Dit zijn de getallen in de kolom "rust" van de parenfile. Op deze wijze kunnen de rusttafels zo eerlijk mogelijk verdeeld worden over een competitie die uit meerdere ronden bestaat.