Så här fungerar Cup Manager under huven
Vi har under lång tid putsat på algoritmer som ligger i grunden för Cup Managers många automatiska funktioner.
Varje ny turnering har gett oss ny insikt i hur komplicerat det är att designa det perfekta spelschemat.
Här får du inblick i några av våra unika funktioner som använder kunskapen vi samlat in under åren.
Geografisk indelning av lag
För att göra en automatisk funktion som man faktiskt kan förlita sig på när det gäller att dela ut lag i grupper (samma algoritm används faktiskt till slutspelsträd också), gäller det att man inte slutar halvvägs och t.ex. bara tar hänsyn till vilka klubbar lagen kommer ifrån. En sådan algoritm lämnar mycket manuellt arbete för att se till att lag från samma stad (eller land i internationella turneringar) inte hamnar i samma grupp.
I Cup Manager tar vi därför hänsyn till följande konflikter (en konflikt är om två lag med samma egenskap nedan hamnar i samma grupp):
- Förening
- Postkod
- Stad
- Kommun
- Idrottsdistrikt
- Län
- Postkodsområde
- Land
- Landsregion
- E-postadress för admin
- Tröjfärg
Det finns tre olika funktioner i Cup Manager som använder sig av samma konflikter för att skapa ett så bra spelschema som möjligt:
- Gruppindelning av lag
- Slutspel (där tillkommer konflikten att lag gått vidare från samma grupp)
- Matchindelning i kämpande klasser
Gruppindelning av lag
I Cup Manager har vi byggt en “konfliktlösare” som garanterat kan dela ut lag mellan grupper på ett optimalt sätt. Det betyder att Cup Manager alltid delar ut lag till grupper så att antalet konflikter minimeras. Tillsammans med funktionen som låter dig seeda vissa lag innan du använder den automatisk funktionen kan man därför säga att Cup Manager funktion för att dela ut lag är komplett. Konfliktlösaren är faktiskt något av det första som byggdes för Cup Manager och har följt med i alla versioner av Cup Manager sedan ungefär år 2008 (12 år när detta skrivs!).
Optimala slutspel
Är du intresserad va det här i detalj så får du läsa nästa sektion som handlar om slutspel specifikt, men redan här kan vi avslöja att konfliktlösaren spelar en central roll.
Eftersom man inte behöver rangordna lagen i resultatordning i kämpande klasser behöver amn inte heller låta alla lag i en grupp möta varandra. Det öppnar upp för att välja ut vissa matcher från en stor grupp där man undviker konflikter mellan lagen som spelar i matcherna man väljer ut.
Detta kan till synes verka vara ett lika enkelt problem som att dela ut lagen till grupper, men sanningen är att det är väldigt mycket svårare. Till skillnad från tidigare där det går att hitta en garanterat optimal lösning, måste man här (åtminstone med lite större grupper) nöja sig med att hitta en så bra indelning som möjligt. Man kan illustrera svårigheterna genom att beskriva ett delproblem:
Hur många matcher måste lag från samma klubb spela mot varandra om de är i samma grupp av en viss storlek där alla lag ska spela minst ett visst antal matcher?
För en 7-lagsgrupp ser svaret ut så här när man varierar antalet lag från samma klubb (rader) och antalet matcher per lag (kolumner):
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
2 |
0 |
0 |
0 |
0 |
0 |
1 |
|
3 |
0 |
0 |
0 |
0 |
2 |
3 |
|
4 |
0 |
1 |
1 |
2 |
4 |
6 |
|
5 |
1 |
3 |
4 |
6 |
8 |
10 |
|
6 |
2 |
5 |
7 |
10 |
12 |
15 |
|
7 |
4 |
7 |
11 |
14 |
18 |
21 |
Det finns tydliga mönster i tabellen ovan, men sambandet är så komplicerat att vi varit tvugna att simulera fram resultaten för olika gruppstorlekar i förväg i Cup Manager. Det hjälper sedan systemet att avgöra om det hittat en optimal matchindelning.
Eftersom det inte finns något enkelt sätt att hitta de bästa matcherna testar sig sedan Cup Manager fram precis som en människa också hade gjort. Fördelen för Cup Manager är att det går väldigt snabbt och att Cup Manager hela tiden kan hålla reda på att alla lag fått rätt antal matcher. Cup Manager hanterar också alla 11 konflikterna från listan med konflikter. Det är inte helt lätt att själv hålla dem i huvudet! Det är det här testandet som trots allt kan ta några minuter om du lottar en kämpande klass i Cup Manager.
Slutspelsträd
Ett bra slutspelsträd ska uppfylla två krav.
1. Ju högre rankat lag, desto enklare väg till final
2. Lag som mött varandra tidigare under turneringen ska mötas så sent i slutspelet som möjligt
Det första kravet leder till att det bäst rankade laget kommer möta det sämst rankade laget, det nästa bästa laget kommer möta det näst sämsta laget och så vidare. I realiteten så finns det ofta flera lag som har samma ranking (t.ex 1:orna från alla grupperna – med undantaget som nämns i regel 4).
Regel 2 är i många fall enkel att följa. Går till exempel 1:an och 2:an i varje grupp till slutspel A kan man placera 1:an på ena sidan av slutspelsträdet och 2:an på andra sidan. Det blir mer komplicerat om man har 3 lag från samma grupp i samma slutspel. Då får man dela upp slutspelsträdet i 4 delar (vid varje Semifinal) och sedan lägga ett lag i 3 utav de fyra delarna, med följden att två utav lagen kan mötas redan i Semifinal om oturen/turen är framme.
Det är tydligt att man här kan hamna i en väldigt krånglig situation om man har flera grupper med att udda antal lag och kanske i värsta fall även ett ojämnt slutspelsträd. Det är tydligt att det inte går att lösa alla fall som kan uppstå med färdiga mallar. Det behövs en algoritm. Det kan tyvärr blir ännu värre, för ofta vill man också följa ett tredje krav som liknar krav 2:
3. Lag som brukar mötas i seriespel eller som kommer från samma klubb ska mötas så sent i slutspelet som möjligt.
Här kommer man till gränsen för vad som är möjligt i praktiken. I Cup Manager löses regel 3 genom att man efter man skapat grupper och slutspel och placerat ut lagen, kan kontrollera så lag från samma klubb inte möts. Skulle man ha otur får amn hjälp att flytta ett utav lagen till en ny grupp för att på så vis undvika problemet.
Slutligen kan ett slutspelsträd vara ojämnt (om man inte använder sig av t.ex Bästa 3:orna). Att ett slutspelsträd är ojämnt innebär att man t.ex. har 14 lag och därmed kommer ha 1/8-finaler, men bara 6 st. Det betyder att två utav lagen måste gå direkt till 1/4-final. Har man ett ojämnt slutspelsträd finns en regel till:
4. Vid ojämna slutspelsträd, ska de lag som spelat flest matcher ha företräde att hoppa över den inledande rundan.
Det betyder att om det står mellan att 1:an i en 4-lagsgrupp och 1:an i en 5-lagsgrupp så ska laget i 5-lagsgruppen som redan spelat en extra match hoppa över den inledande rundan i slutspelet.
Ett enkelt slutspelsträd med 4 lag som kommer från två grupper. Bästa laget möter sämsta laget (1:or mot 2:or) och lagen från samma grupp möts inte förrän i finalen.
Automatisk schemaläggning
Schemaläggning är ett problem som på ytan kan verka enkelt, men som faktiskt är något av det svåraste som finns för en dator att klara av. Trots det har turneringsadministratörer i alla tider lyckats lägga spelscheman utan dubbelmöten och med tillräckligt med vilotid. Det tog vi fasta på när vi byggde Cup Managers algoritm för automatisk schemaläggning.
Precis som en människa hade gjort placerar Cup Manager en match i taget ut i spelschemat tills alla matcher är placerade. Skulle oturen vara framme plockar man helt enkelt bort de senaste matcherna i schemat och gör ett nytt försök tills alla matcher är placerade.
Vad är då problemet kan man fråga sig? Ett enkelt räkneexempel svarar snabbt på den frågan. Låt oss anta att vi vill placera 100 matcher på 10 olika spelplaner. Om vi måste prova alla 10 spelplanerna för alla 100 matcherna när vi lägger schemat kommer vi testa 100000000000000000000 (100^10) olika placeringar av matcher. Inte ens med världens alla superdatorer förenade hade det gått att schemalägga med en sådan metod. Då har vi inte ens tagit hänsyn till vilken tid matcherna ska spelas. Det självklara knepet (som är enklare sagt än gjort) är att inte göra fel när man placerar matcherna. Plötsligt behöver vi bara testa 1 schema. Istället för att korrigera sina fel i efterhand måste man alltså vara förutseende och se till att inte göra några (eller åtminstone väldigt få) fel.
Att schemalägga kan då delas upp i två problem som behöver lösas, eller två frågor som ska besvaras under tiden man schemalägger:
- Vilken match ska jag placera härnäst?
- Vilken plats och tid ska matchen jag valt få?
Svarar man “rätt” på de två frågorna genom hela sin schemaläggning är man i mål! Tyvärr är metoderna för att svara rätt på de frågorna ett helt vetenskapsfält. Grunden för Cup Managers metod att svara på frågorna kommer från ett examensarbete i datalogi som du kan ladda ner här. Med hjälp av metoden att rangordna matcher och placeringar som beskrivs i det arbetet kommer man alltid få ett balanserat schema med lika många matcher på varje spelplan.
För att svara på frågorna måste också ta hänsyn till alla de regler som finns för hur schemat för en turnering får se ut. T.ex. vilotider och vilka dagar en match ska spelas, men också mer avancerade regler om att alla ska spela minst en match på huvudarenan eller konstgräs. Alla regler man lägger till kommer påverka svaret på de två frågorna eftersom det är med hjälp av de två frågorna systemet undviker att bryta mot reglerna.
Under huven på Cup Managers schemaläggare finns därför en avancerad schemaläggningsmotor som klarar att schemalägga turneringar med flera tusen matcher, trots komplicerade regler. Genom att ta hänsyn till alla de regler du lägger till i ditt schema när de två frågorna besvaras klarar Cup Manager att snabbt schemalägga nästan alla scheman.
Vi gillar att tänka på spelscheman. Utmana oss gärna!
Cup Manager support
Telefon: 046-52580
E-post: support@cupmanager.net
Vill du ha ett enklare liv?
Ta kontakt med oss, eller välj en tid för att boka en demo av Cup Manager. Vi ser fram emot att få visa vårt system för dig.