Nalosování soutěže je věčné a vděčné téma. Otázku obsahující výčitku v podobě: „Proč zrovna já letím s XY čtyřikrát? To je přeci nespravedlivé.“ slýchám dosti pravidelně. Až mě jednou napadlo, jaké je tedy vlastně „nejspravedlivější“ nalosování. Odpověď není ani trochu jednoduchá.
Upozorňuji dopředu, že následující text obsahuje matematiku, kterou někdo nemusí mít rád. Já sám jsem při psaní tohoto článku měl co dělat 🙂 .
Začněme jednoduchou otázkou:
Kolik je možností výběru soutěžního kola.
Nejlépe je to demonstrovat na příkladech.
Příklad 1:
Začnu se 4 piloty A B C D a 2 skupinami, tj. v každé skupině jsou jen dva piloti.
Možných kombinací je 6 a lze je snadno vyjmenovat: AB, AC, AD, BC, BD a CD.
První skupinu je tedy možné vybrat šesti způsoby, druhá skupina je tvořena „zbytkem“ pilotů. Tedy, jedno kolo lze nalosovat právě šesti způsoby: AB-CD, AC-BD, AD-BC, BC-AD, BD-AC a CD-AB. Protože pro účely této úvahy není podstatné, jestli skupina poletí první nebo druhá, ani z jakého startoviště konkrétní pilot poletí (skupiny i piloty na jednotlivých startovištích lze nakonec proházet libovolně), lze považovat AB-CD a CD-AB za stejné případy.
Kolo lze tedy při 4 pilotech a dvou skupinách vybrat právě ze tří možností AB-CD, AC-BD, AD-BC.
Příklad 2:
Další příklad je 6 pilotů A B C D E F ve 2 skupinách.
Možných kombinací je 20. I zde je lze vyjmenovat, pro názornost v několika řádcích:
ABC, ABD, ABE, ABF, ACD, ACE, ACF, ADE, ADF, AEF
BCD, BCE, BCF, BDE, BDF, BEF
CDE, CDF, CEF
DEF
Jako v předchozím případě i zde je unikátních možností (bez ohledu na pořadí skupin) právě polovina, tj. 10, protože každé volbě v první skupině odpovídá jediná možnost druhé skupiny.
Příklad 3:
Teď to bude těžší, 6 pilotů ve třech skupinách.
Možných kombinací je 15:
AB, AC, AD, AE, AF
BC, BD, BE, BF
CD, CE, CF
DE, DF
EF
Do první skupiny vyberu první dvojici, takže mi pro druhou a třetí skupinu zbydou 4 piloti, které mohu „rozhodit“ šesti způsoby (viz první příklad). Poslední skupina je „doplněk“. Následující tabulka vypisuje všechny možnosti:
Celkem je tedy 15*6=90 možností, řádky 2 a 3 jsou vzájemně svázané.
Žlutě jsou vyznačeny stejné kombinace AB-CD-EF, kterých je 6. V 90 možnostech je tedy 15 šestic. Jedinečné jsou tedy pouze kombinace vyznačené tučně, kterých je 15.
Už z těchto jednoduchých příkladů je zřejmé, že na výpis všech možností obvyklé soutěže by nestačil papír. Například pro soutěž s 18 piloty ve třech skupinách je možností nalosování jednoho kola 2 858 856.
Odvození (klidně přeskočte)
V matematice se používají termíny kombinace a permutace. Kombinace je výběr prvků, v němž nezáleží na pořadí, při permutaci na pořadí záleží. Kombinace písmen A a B je jen jedna AB, permutace jsou dvě AB a BA. Matematická funkce C(n,p) vrátí počet kombinací p prvků z celkem n prvků. Matematická funkce P(n,p) vrátí počet permutací p prvků z celkem n prvků. Obě tyto funkce má každá lepší kalkulačka.
N … počet pilotů
s … počet skupin
m … počet pilotů v každé skupině (platí, že N = s*m)
Pro první skupinu je C(N,m) kombinací, další se skupina se vybírá už jen z N-m pilotů, takže pro druhou skupinu existuje C(N-m,m) kombinací. Pro předposlední skupinu je to C(2m,m) a poslední skupina je „zbytková“, C(m,m)=1.
Některé kombinace se v tomto počtu možností opakují. V počtu možností první skupiny jsou všechny m-tice. Ve druhé skupině se objeví m-tice, které už jsou uvedený i pro první skupinu. V losování každé další skupiny se objeví m-tice, které už byly nalosovány dříve. M-tice z jedné skupiny je M1, z druhé M2, ze třetí M3, atd. Když jsou dvě skupiny, objeví se ve výpisu možností M1-M2 i M2-M1. Když budou skupiny tři, objeví se M1-M2-M3, M1-M3-M2, M2-M1-M3, M2-M3-M1, M3-M1-M2, M3-M2-M1. To je ovšem permutace P(s,s).
Celkový počet možností, jak vybrat piloty do „s“ skupin jednoho kola je tedy dán výrazem
n=C(N, m)*C(M-m,m)*…*C(2m, m)*C(m, m)/P(s,s)
Konec odvození
Kolik je možností výběru soutěže.
Soutěž nemívá jen jedno kolo. Jestliže je pro jedno kolo X možností, potom pro dvě kola je to X*X, pro 3 kolo X*X*X atd. A číslo počtu nalosování celé soutěže se zvětšuje, nul utěšeně přibývá 🙂 , výsledná čísla jsou nepředstavitelně vysoká.
Závěrem této kapitoly tedy může být to, při větším počtu pilotů a kol nelze hledat „nejspravedlivější“ výběr systematicky. Dovedu si představit (byť obtížně), že při šesti pilotech v soutěži si vypíši všechny varianty a vyberu tu nejlepší. Při velkém počtu pilotů je systematický přístup mimo schopnosti člověka a pravděpodobně i soudobé výpočetní techniky, proto je nutné použít jinou strategii, jak bude ukázáno níže.
Bez ohledu na to, zda hledám to správný výběr systematicky nebo náhodně (losováním), potřebuji vědět, podle jakého kritéria mám varianty prohledávat a vybírat tu nejlepší.
Kritérium spravedlivosti.
„Nespravedlivé“ nalosování obvykle znamená, že někdo letí proti někomu vícekrát. Proto lze kritérium výběru sestavit na základě počtů, kolikrát proti sobě jednotliví piloti letí. Lze si ale vymyslet i libovolné jiné.
Opět teoretická vložka k přeskočení.
Když má N pilotů letět každý s každým, je to N*(N-1)/2 možností. V jedné skupině s m piloty takových soubojů najednou proběhne m*(m-1)/2. Pokud se má 18 pilotů utkat každý s každým, bude soubojů 153. V jedné skupině 6 pilotů se najednou těchto soubojů odehraje najednou 15. V kole 45 a v soutěži o 6 kolech 270. Takže už z těchto čísel je jasné, že někteří budou muset proti některým letět vícekrát.
Ve skutečnosti lze mít samé jedničky v tabulce „kdo s kým“ jen v případě, že počet startovišť krát (počet kol minus 1) je počtem pilotů. Třeba 16 pilotů může na 4 startovištích odlétat 5 kol a všichni se potkají právě jednou. Opravdu, počet dvojic je 16*15/2 = 120, počet soubojů v každé skupině 4*3/2=6, v kole tedy 24 a v pěti kolech 120.
Ona ale tato shoda 120=120 je podmínkou nutnou, nikoliv však postačující.
Konec teorie.
Z výbrané varianty lze zjistit, kolikrát proti sobě jednotlivé dvojice pilotů letí. Kritérium poté může definovat následující tabulka
Pokud chceme omezit to, aby proti sobě piloti letěli vícekrát, měly by to váhy zohledňovat. Po pokusech jsem zvolil váhy v podobě 3. mocniny, tj. w0=0, w1 = 1^3 = 1, w2 = 2^3 = 8, w3 = 3^3 = 27 atd. V takovém případě algoritmus upřednostní variantu, v níž například 3 páry pilotů proti sobě poletí 2x, oproti variantě, ve které by jeden pár pilotů proti sobě letěl 3x (protože 3*8 = 24, což je méně než 1*27 = 27).
Není to ale jediná možnost, například se mi nemusí líbit, že by se některé dvojice nepotkaly vůbec, a potom mohu nějakou váhu přiřadit i nulám. Výběr to samozřejmě ovlivní.
Pro 6 pilotů ve dvou skupinách a čtyřech kolech dostanu v závislosti na váze u nuly následující výsledky. Váha 0 znamená, že mi vůbec nevadí, pokud se někteří piloti v soutěži nepotkají, váha 8 znamená, že nepotkat se je stejně špatné jako potkat se dvakrát, váha 27 potom odpovídá 3 společným soubojům.
Nejlepší výsledek pro w0=8 znamená, že sice bude jen jeden pár pilotů, který nezměří síly přímo, ale zato 2 dvojice proti sobě poletí 3x, což už mohou nemile nést. Ještě větší váha u nuly zajistí, že poletí každý proti každému, ovšem za cenu toho, že se jedna dvojice potká 4x.
Mně přijde pocitově nejspravedlivější výsledek pro váhu 0. Tři dvojice pilotů se nepotkají vůbec a ostatní možné dvojice poletí každý s každým právě dvakrát. Dále se budu tedy držet tohoto kritéria. Nicméně závěrem této části může být, že kritérium spravedlivosti je velmi subjektivní pojem.
Počítačové losování.
Jak je uvedeno výše, pro malý počet pilotů je celkem dobře možné vypsat všechny varianty soutěže, spočítat skóre jednotlivých možností a vybrat tu nejlepší. Pro větší počet už to možné není, počet variant jsou čísla s desítkami nul.
Počítače jsou snadno a rychle nalosovat soutěž náhodným způsobem (což se samozřejmě v programech, jako je Sorg nebo Gliderscore, děje). Při náhodném losování je ovšem vždy namístě otázka, zda je takový výsledek „spravedlivý“. Má odpověď je opatrné ne, jak se pokusím vysvětlit dále.
Počítač dokáže vygenerovat tisíce nalosování soutěže v rozumném čase. Tisíce jsou ovšem stále pouze nepatrný zlomek všech možností, ale zdá se, že to nevadí, i náhoda má své zákonitosti (asi jako když se provádí průzkum volebních preferencí na vzorku 1000 lidí, zatímco voličů jsou miliony).
Tedy, modelovým příkladem je již zmíněná soutěž s 18 piloty, 3 skupinami, 6 koly. Váhy jsou 3. mocniny.
Program proběhne 1000x. Oproti počtu všech možností, které vyjadřuje číslo se 38 nulami, je to zdánlivě málo. Ale zdá se, že to stačí, neboť všechny běhy (1000 losování v každém běhu) vrací velmi podobné výsledky.
Tedy, program proběhne 1000x a spočítá skóre pro všech 1000 variant. Interval mezi minimálním a maximálním skóre se rozdělí na intervaly a spočítají se počty hodnot, které spadají do daného intervalu.
Hezky ostře ohraničený „kopeček“ ukazuje, že většina losování (řekněme 70%) spadá do průměru mezi řekněme 1850 a 2100. Minimálních skóre, tj. dobrých, či spravedlivých nalosování se dosahuje jen asi v 1%.
Rozdíly mezi dobrým a průměrným nalosováním ukazuje tato tabulka.
Když se zaměřím jen na vysoké počty vzájemných letů, tak v průměrném losování se spolu 4x utká 8 dvojic pilotů a 5x 1 až 2 dvojice. Při dobrém nalosování budou „4-letových nešťastníků“ jen 4 páry a pětinásobný souboj nebude žádný.
Nicméně lze uzavřít, že dobré řešení je o dost lepší než průměrné.
Zde je dobré připomenout, že popsaný způsob nenalezne nejlepší řešení, jen poměrně dobré řešení. Při mých pokusech mi program našel variantu se skóre 1500, ale obvykle je nejmenší skóre z běhu 1000 pokusů okolo 1600. Takže nelze s jistotou určit, zda někde neexistuje varianta s ještě menším skóre. Pravděpodobně ano, ale vzhledem k ostrému „kopečku“ je tato pravděpodobnost extrémně malá.
Shrnutí.
Tedy, náhodně nalosovaná soutěž s velkou pravděpodobností není spravedlivá (ve smyslu definovaného kritéria). Otázkou je, zda to vadí. Podle mě ne (viz tento předchozí článek), ale vykládejte to někomu, kdo se cítí ukřivděný, pocity jsou víc než nějaký teoretický rozbor.
Řešení vidím dvě:
(a) Provést losování mnohokrát (řekněme 100-1000x) a vybrat to, které nejlépe splňuje požadované kritérium; v větším počtu losování je pravděpodobné, že se vybraná varianta bude nacházet na levém úpatí „kopečku“. Pro obvyklý počítač je to úloha na desítky sekund až jednotky minut.
(b) Použít předdefinované šablony; pro každou kombinaci počtu pilotů, startovišť a kol by musela být připravená předem. Například pro popisovaný příklad 18 pilotů, 3 skupin a 6 kol může matice vypadat takto:
Písmenům A až R lze jména pilotů přiřadit libovolně, rovněž lze libovolně prohodit řádky (skupiny) v jednotlivých kolech a sloupce (startoviště) v jednotlivých řádcích (skupinách). Uznávám ale, že řešení podle (a) je lepší.
Předpokládám, že už to někdy někdo dávno řešil a vyřešil přede mnou. Ale mě takové intelektuální výzvy baví, i když praktický užitek asi nemají.
Honza
11.10.2019
Sice jsem se ztratil na konci třetího odstavcie ale čte se to hezky ?
Teda matiku mám rád a rád si taky hraju, ale tohle je trošku maso a „sebemrskačství“ 🙂
Jak píše Ruda, hezky se to čte. Je krásně vidět, že při standartním počtu startujících je prakticky nemožné nalosovat spravedlivě. Ale jak píšeš v odkazovaném článku, je to prostě fuk, jde hlavně o pilota.
Moc hezky jsi si v tom porochňal 🙂
Kluci, děkuji za pochvalu, jak jsem napsal, vzal jsem to spíše jako intelektuální výzvu, mě totiž kombinatorika nikdy moc nešla 🙂 .
A taky si říkám, že namísto „jak já k tomu přijdu, že musím 4x letět proti XY“ je lepší „chudák XY, letí 4x se mnou“ 🙂 . H.
Aneb na chudáka prší všude!!
On je docela rozdíl mezi různými akcemi… Upřímně třeba na Eurotour F5J či dokonce MS/ME je nalosování relativně nepodstatné – člověk má ve skupině piloty, jejichž poražení je velký problém, naprosto vždy a jestli má v losu štěstí či smůlu tak maximálně mírně změní důraz. Najít „lehkou skupinu“ však v podstatě nejde a vliv na výsledky je spíš okrajový.
Přiznejme si ale, že když na menší akci RCEV přijede ve volném víkendu nejmenovaný RM, tak pokud ho někdo dostane do skupiny 4x, tak to už může mít na výsledek dopad naprosto fatální (ještě zvedlý o to, že se nelétá finále).
Jinak z praxe – letos byla ze začátku sezóny velká nespokojenost daná tím, že nový SORG losoval čistě náhodně a ukázalo se, že losy stály za prd vlastně všechny, těch opakovaných situací bylo opravdu dost. V druhé půlce po doplnění dalších metod se situace hodně zlepšila. Co vím, tak celkem dobře skutečně fungují připravené matice a popravdě ta zmíněná varianta „losovat tak dlouho, až kontrola opakovaných letů vypadá dobře“ ve výsledku fakticky vede k tomu samému…
„… V druhé půlce po doplnění dalších metod se situace hodně zlepšila.“
Toto tvrzení bych silně rozporoval, v novém SORGu bohužel i po kosmetické úpravě rozlosování funguje žalostně, pouze pořadatelé už jsou znalí situace a tak si to začali více hlídat. Přesně podle uvedeného hesla – losovat náhodně tak dlouho, až to vypadá trochu přijatelně… a nebo někteří používají starý Sorg.
Snad na tom Aleš přes zimu zapracuje.
Jojo, máš pravdu, vlastně mi pak docvaklo, že víc lidí tohle zmiňovalo (tedy že pořadatelé už to víc hlídali a „mysleli za sw“ 🙂
Tomáši, nemyslím si, že je problém v silných a slabých skupinách, o nějakých „fatálních“ následcích už vůbec nemůže být řeč. Kdo chce vyhrát, musí „polétat“ všechny, a ne spoléhat na slabé skupiny (pokud už se nějaké takové vyskytnou).
Mně šlo opravdu jen o zjištění, kde se berou ta nalosování, která mohou někteří prohlašovat za nespravedlivá. Zdá se, že jsou přirozená, že při losování v jednotkách pokusů tam velké počty opakovaných letů jsou vždy. Druhý poznatek je, že při troše „počítačového úsilí“ lze tyto počty zmenšit.
Třetí závěr je, že čím víc o tom přemýšlím, tím méně tomu rozumím 🙂 . Ale zajímavé to je. Měl jsem článek rozepsaný asi 14 dní, pořád jsem ho předělával a doplňoval, myslím si, že ještě bude mít pokračování. Nakonec je po sezóně, máme času dost. H.
Sám jsi dal do titulku slovo „spravedlnost“…
A pokud uvažuješ tímto směrem, tak je prostě věta „Kdo chce vyhrát, musí „polétat“ všechny, a ne spoléhat na slabé skupiny“ nesmyslná – tohle je sice fakticky pravda, ale pro spravedlivé pojetí musíš zajistit korektní los a ne pokrčit rameny s tím, že máš pilota X zkrátka porazit 4x a na 1-2x.
Buď platí tato věta, pak se můžeš na los vykašlat, článek smazat a hlavně vynechat pojem spravedlnost 🙂 Pokud ale los a spravedlnost řešíš, tak pak prostě nemůžeš nad důsledky různě silných skupin mávnout rukou – musíš si vybrat jedno nebo druhé …
Tomáši, je tam v „spravedlivé“ uvozovkách. K zamyšlení a napsání článku mě vyprovokovaly poznámky kluků, sám bych to nevymyslel. Krčím tedy rameny 🙂 , ale článek nemažu. Pro mě je to intelektuální cvičení, hodně zajímavý a perný problém, ne životní potřeba.
Nicméně mi došlo, že pro spravedlivost je potřeba mít stupnici (kritérium, užitkovou funkci). Já jsem si ji vymyslel sám, každý ji může mít jinou (třeba nikdy neletět proti nejlepším pilotům). To všechno jde vhodným postupem vybrat. Takže nejspravedlivější může být i první (neopakované) losování, vše záleží na kritériu.
A děkuji za připomínky, vážím si jich, i když někdy nesouhlasím 😉
Shodou okolností jsem si včera večer hrál se starým Sorgem, do kterého jsem dal současných deset přihlášených na tři skupiny po max. čtyřech na šest kol. Žreboval jsem furt a furt s maticí náhodnou, inteligentní i žádnou. Ve všech případech jsem viděl i stav s některými šestkrát, s ostatními ani jednou. Vždy jsem tam měl někde nuly a aspoň jednu čtyřku, chtěl jsem se dostat ke stavu maximálně třikrát, ale asi jsem měl malou výdrž. To stejné jsem dal do Glider score a hned na poprvé tam bylo minimálně jednou a maximálně dvakrát (jen jedničky a dvojky).
Milane, podle mě Gliderscore „nelosuje“, nýbrž „prohledává graf“. Popíšu to v pokračování článku, ale stručně to spočívá v přidávání jednoho pilota po druhém do matice vždy na takové místo, aby bylo nějaké kritérium co nejlepší.
Zjednodušeně a například pro 6 pilotů ve dvou skupinách
1. kolo: ABC DEF
2. kolo
– A__ ___
– B už s A letěl, proto A__ B__
– C už letěl s A i B, jsou tedy dvě možnosti, kam ho dát, volím AC_ B__
– D neletěl s ABC, takže ho mohu dát do první i druhé skupiny, volím ACD
Takže druhé kolo je ACD BEF
Kontrola:
AB – 1 AC – 2 AD – 1 AE – 0 AF – 0
BC – 1 BD – 0 BE – 1 BF – 1
CD – 1 CE – 0 CF – 0
DE – 1 DF – 1
EF – 2
3. kolo
– A__ ___
– A__ B__
– A__ BC_ (AC už je 2x, BC jen jednou)
– AD_ BC_ (AD je 1x; BD je 0x, CD je 1x, volím tedy 1. skupinu)
– ADE BCF (AE je 0x, DE je 1x; BE je 1x, CE ke 0x, volím zase 1. skupinu)
Tedy, třetí kolo je ADE BCF
Kontrola
AB – 1 AC – 2 AD – 2 AE – 1 AF – 0
BC – 2 BD – 0 BE – 1 BF – 2
CD – 1 CE – 0 CF – 1
DE – 2 DF – 1
EF – 2
atd.
Pro víc pilotů, skupin, kol je to náročnější, ale lineárně, každého pilota „beru do ruky“ jen jednou v každém kole 🙂
Takhle nějak si představuju „inteligentní rotační matici“…
GliderScore sice nabízí možnost při rozlosování „uložit nejlepší z X losování“, kde za X se dá zvolit od 1 do 50 (implicitně je nastaveno 10), ale má to jen velmi malý vliv na výsledek. Mezi volbou 1 a 50 se jen nepatrně zvýší počet jedniček v matici na úkor ostatních počtů. Takže už i to základní jedno „losování“ bez opakování je nastaveno dostatečně inteligentně.
Předpokládám tedy, že pokud GS rozmisťuje matici tak jak popisuješ, tak při opakovaném pokusu, v místech kde je volba mezi rovnocenými možnostmi, volí druhou nebo další volbu atd. Na konci potom dochází k téměř rovnoceným výsledkům. Jde jen o to, podle jaké váhy vybírá tu nejlepší variantu z těch třeba 50ti. Možná je to podle nejvyššího počtu jedniček, já bych spíš upřednostnil co nejnižší (ideálně nulový) počet vyšších čísel v matici.
Podle mne je z technického hlediska nejjednodušší losování založené na tom, že v softu jsou pevně uložené „optimální matice“ pro různé počty skupin/soutěžících (klidně ať počítač stráví při vývoji celý den výpočty, to se udělá jen jednou), načež se u konkrétní soutěže pro piloty vylosuje víceméně jen číslo, které se pak zařadí na patřičné místo té předem hotové matice (případně ještě v každé rundě vylosuje pozice, ale to je snadné).
Ono těch variant není zase tolik, matice dejme tomu od 15 do 150 soutěžících, přičemž počet variant počtu rund k počtu startovišť není nekonečný (s počtem pilotů roste, ale ani u sto pilotů to nebude reálně víc než 10 (pod 10 a nad 20 míst v rundě nemá cenu řešit). A jelikož se ty varianty lehce kryjí (nechávat jistý počet volných míst vždy chceme kvůli reflightům), tak to není ani 1000 takto připravených „supermatic“, spíš něco kolem půlky a to při výkonnosti dnešních počítačů není problém nachystat (tohle fakt není simulace pohybu neutronů při jaderném testu)…
Ve výsledku je to postup, jak v posledním příspěvku popsal Honza, jen trochu naopak – tobě totiž reálně stačí vytvořit matice jen jednou a pak už se nic kontrolovat nemusí.
Tohle se týká normální soutěže F5J do úrovně EC, pro MS/ME a jakékoli F3J to je o něco složitější, tam se ještě musí řešit team protection, ale dost možná by i pak bylo nejlepší provést los nejprve viz výše a pak jen projet kola jednodušším algoritmem pro doladění týmů…
Tomáši, teď ještě aby se tyto informace dostaly do správných rukou. Aleš na Stoupáku sliboval, že do února 2020 jeho Sorg určitě bude bezchybný, ale nevím, jestli měl v plánu i losovací matice.
A ještě „šťouravou“ poznámku k pravidlům, kde se (u RCEV) praví, že „Složení skupin by mělo minimalizovat situace, kdy dva soutěžící letí vícekrát proti sobě.“ To není zrovna matematická definice. Nechtěl bych být v roli pořadatele, u něhož protestuje soutěžící s vytištěnou tabulkou, že v soutěži použitá matice neminimalizuje a že má nalosování lepší. Zvlášť kdybych tím soutěžícím byl já 😀
Zajímavý počtení, zlatá RCEP 🙂 Ale vážně, já po těch našich premiérových jarních RCEV a nepředpokládaném trápení se s rozlosováním, došel právě k tomu řešení b), tedy předdefinované šablony. Nemuselo by to myslím ani být pro konkrétní počet soutěžících, ale např 15, 20, 25 atd. Nějaké to neobsazené místo v soupisce by se asi sneslo. Takto rozlosované ,,šablony soutěže“ pro daný počet soutěžících, kol a startovišť uložit v sorgu a pak si už jen vybrat tu nejvhodnější a dosadit jména. Jinak pokud se někdo s třetinou soupeřů nepotká a s jiným letí polovinu soutěžních kol, tak to je potom ta snaha o spravedlivou soutěž trochu zbytečná bych řekl.
Ahoj Pavle, tak já si myslím, že právě na nepřepočítávání RCEP skončí, resp. ho jednou budeš muset zavést 🙂 .
Jinak souhlas, zdá se, že předdefinované matice budou tou nejschůdnější cestou. Zdá se mi také, že počet kol nebude hrát roli, matice se může připravit třeba pro 15 kol a bude jedno, kolik se jich (odshora) odlétá, rozlosování bude pořád optimální (pokud se pro sestavení matice využije tedy metoda prohledávání sítě, co je popsaná v pokračování, pokud jen hrubá síla náhodného losování, tak bude muset být tolik matic, kolik je kol). Tím se to hodně zjednoduší. Dále se dá omezit počet soutěžích třeba na 32 (stejně většina pořadatelů dává max. 30 pilotů, ale to je spíše proto, že nás ani více nebývá). Potom už je těch kombinací počtu skupin x počet startovišť jen několik, řekněme (když budu vynechávat pro případné opakovací lety apod.) 2×6, 3×6, 3×8, 3×10, 3×12, 4×6, 4×8, takže asi 7 matic pro nejběžnější případy. Jak psal nahoře Tomáš, že bych jich mohlo být klidně 1000, tak si myslím, že jich tolik potřeba nebude, v nejhorším případě nízké desítky. Uvidíme příští rok 🙂 . H.
Tak abych tak přidal trošku světla do této otázky…
ve starém Sorgu „inteligentní“ matice fungovala tak, že náhodně rozsázely kola, a poté se procházela skupina po skupině v kole po kole, a dělal se bodový ranking celé skupiny. (to znamená, že skupina se vysčítaly opakující se kombinace kdo s kým v soutěži letí) a poté se ústřely směrem nahoru snažil program pozměnit tak,aby se dostal celkovým rankingem skupiny na průměrnou hodnotu.
Abych to osvětlil. Pokud byli ve skupině 4 soutěžící, a A letěl s B celkem 5x, C a D s ostatními 0x, tak ranking byl 10 (A=5,B=5C=0D=0)
Nový Sorg náhodně nalosuje všechny skupiny, a poté prochází soutěžícího po soutěžícím skrze celou soutěž a hledá jejich vzájemné lety. Pak udělá v každé skupině každého kola ranking soutěžícího, a pokud je moc vysoký, tak projde všechny skupiny v daném kole, a hledá s kým letí nejméněkrát. Až najde, tak je přehodí mezi sebou.
V obou případech jde o náhodný los, a poté eliminaci maxim buďto skupiny (Sorg5) nebo jednotlivce v každé skupině (SorgAIR)
Celé se to ještě rozbíjí hlídáním poslední-první pro neletění 2x po sobě.
Ahoj,
já už sice nějaký ten pátek nelítám, ale dostal jsem se přes tátu k tomuto článku a chtěl jsem to vyřešit. Napsal jsem program, který používá stejnou užitkovou (fitness) funkci jako píše Honza v článku – vzoreček je v příloze (p_i je počet soubojů mezi libovolnou dvojicí pilotů, které proběhnou během soutěže celkem i-krát).
Při použití této užitkové funkce a metaheuristik pro vyhledávání ve stavovém prostoru dostávám tyto výsledky:
1) případ zmíněný v článku s grafem – 18 pilotů, 6 startovišť, 6 kol:
konkrétní rozlosování:
R1: 13-6-17-10-8-12 ; 11-4-3-2-9-5 ; 0-14-1-7-16-15
R2: 14-8-6-11-5-15 ; 12-4-7-3-10-0 ; 16-9-17-2-13-1
R3: 0-1-9-5-12-8 ; 11-16-10-14-17-4 ; 7-2-6-15-13-3
R4: 17-6-14-3-9-0 ; 7-1-11-2-8-10 ; 4-16-5-13-15-12
R5: 13-14-7-8-4-9 ; 2-6-16-0-5-10 ; 12-15-1-3-17-11
R6: 8-0-17-15-2-4 ; 1-10-3-5-14-13 ; 7-16-12-9-11-6
počet soubojů:
0x -> 18
2x -> 135
celkový výsledek: 1080
2) případ zmíněný v komentáři mch – 10 pilotů, 4 startoviště, 6 kol
konkrétní rozlosování:
R1: 7-4-5-2 ; 9-3-8-_ ; 0-_-6-1
R2: 3-7-0-5 ; _-6-8-2 ; 4-1-_-9
R3: 5-_-6-3 ; 2-9-7-_ ; 0-8-1-4
R4: 8-0-5-_ ; 6-9-7-4 ; 3-2-1-_
R5: 8-_-7-6 ; 1-5-9-_ ; 4-2-3-0
R6: _-2-0-9 ; 3-7-1-8 ; 4-5-6-_
počet soubojů:
1x -> 18
2x -> 27
celkový výsledek: 234
Když bych to shrnul, tak si myslím, že moje výsledky se blíží globálnímu optimu (pokud jím přímo nejsou). V případě 1) se výsledky pohybují stabilně s hodnotou okolo 1100, přičemž náhodné losování je v průměru 1900 (jak je vidět i z grafu v článku). V případě 2) je celkem vyrovnaný počet soubojů 1x a 2x.
Samozřejmě pocit spravedlnosti závisí na definici právě užitkové funkce, osobně si myslím, že takto zvolená je velmi spravedlivá.
TCH
Ahoj Tomáši, to je skvělé, díky moc. Prosím, ozvi se Alešovi (ales@sgames.cz), ať to zahrne do nového Sorgu (jestli bude mít zájem 😉 ). Dík, H.