- inleiding
- kwaliteitsfactor
- ontmoetingenmatrix, competitiematrix en coincidentiematrix
- strategie
- Klik hier voor de homepage .
Op deze pagina worden enkele technische aspecten van picolo behandeld.
Tijdens het werk aan het progamma balans ontstond het idee, om ook
een programma te maken voor het optimaliseren van de indeling bij
competities van meerdere zittingen. Dit programma zou niet alleen
rekening moeten houden met een gelijkmatige verdeling van ontmoetingen
maar ook met het aantal keren dat paren spelen in gelijke en
tegengestelde windrichtingen. De kwaliteitsfactor Qf
leek hiervoor een goed criterium. Immers als beide aspecten van de
balans in orde zijn betekent dat een hoge waarde van Qf. Helaas bleek
deze stelling niet omkeerbaar ...
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 Mij is het effectieve aantal ontmoetingen
tussen paar i en paar j. Vergelijk dit met de ontmoetingenmatrix
waar element Mij 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.
De competitiematrix bevat niet langer, zoals de scorematrix, gehele getallen. Daarom is ook
de kwaliteitsfactor anders gekozen. Qf was immers
gebaseerd op een set van gehele getallen met gegeven som, met een minimale som van
kwadraten.
We gebruiken niet Qf, maar Qc, zoals onder gedefiniëerd.
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.
|
Uit de ontmoetingenmatrix kan men aflezen hoe vaak twee paren elkaar in de
lopende competitie ontmoet hebben. Horizontaal en verticaal staan de paarnummers
uitgezet en het element behorend bij i horiontaal en j verticaal is
gelijk aan het aantal keren dat paar i en paar j tegen elkaar gespeeld hebben. Het is dus
een symmetrische matrix en de diagonaal is onbepaald. Bij het bepalen van het gemiddelde
nemen we dan ook de diagonale elementen niet mee. Het is de bedoeling dat de spreiding
van deze getallen minimaal wordt. Dit kan bereikt worden door de som van de kwadraten
van alle afwijkingen van het gemiddelde te minimaliseren. Een alternatief is het te werken met
de som van de 4e machten van deze afwijkingen. Dit criterium
heeft als voordeel dat extreme afwijkingen effectiever bestreden worden.
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
Hierbij is h gelijk aan de halve top, oftewel het aantal keren - 1 dat een spel
gespeeld wordt.
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.
De strategie die picolo volgt is een combinatie van op toeval gebaseerde beginwaarden en
een gerichte zoektactiek vanuit die beginwaarden.
De gang van zaken bij het commando OPT is als volgt.
- 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.
- 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.
- 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.
- 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.
- 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.
- Uitgaande van een gegeven, random, indeling zoeken we de gunstigste indeling die bereikt kan worden door
telkens twee paren te verwisselen.
- Is deze indeling gunstiger dan de beste indeling tot dusver, dan wordt dit nu de beste indeling.
Proces (A) verloopt als volgt:
- bereken de waarden van Sr, So, Sp, Sc die volgen uit de beginwaarden.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.