Pravidla počítání žebříčku ČAS

Co je to žebříček

Žebříček (anglicky rating) se sestavuje pro různé sporty (např. tenis) i deskové hry (např. šachy). Jeho cílem je uspořádat určitou skupinu hráčů podle síly, tj. podle pravděpodobnosti, že porazí pomyslného průměrně silného hráče. Každému hráči se počítá jakýsi osobní koeficient, který můžeme nazvat Síla, protože měří sílu hráče v dotyčné hře nebo sportu. Síla je obvykle v přímém vztahu k pravděpodobnosti, že hráč porazí průměrného protivníka. Tuto pravděpodobnost lze ovšem jenom odhadovat na základě již sehraných partií; protože existují různé metody, jak ji odhadnout, mohou pro stejnou skupinu hráčů a partií existovat různé žebříčky, které tyto hráče seřadí různě. Všechny sice zařadí silné hráče na začátek a slabé na konec, ale lokálně se pořadí bude lišit.

Většina metod nicméně vychází z podobných principů, které formuloval maďarský matematik Árpád Elo. Proto si některé žebříčky, resp. jimi definované osobní koeficienty (síly) říkají ELO. Ačkoli by si tedy toto pojmenování zasloužila řada žebříčků, budeme jím označovat pouze žebříček, který používá Mezinárodní federace šachu, protože tam je název ELO nejvíce vžitý.

Síla hráče pochopitelně souvisí s tím, kolik svých partií prohrál a kolik jich vyhrál. Ale na rozdíl od turnajů se také přikládá velký význam tomu, s kým prohrál či vyhrál. Pokud hráč vyhrál všechny partie v turnaji, může to znamenat nejen, že je velmi silný, ale také, že všichni ostatní účastníci turnaje byli slabí. Výhra nad slabým protivníkem pochopitelně říká o síle hráče méně než výhra nad někým silným.

To samé lze do jisté míry říct i o skóre, jakým hráč vyhrál. Na pořadí v turnaji mívá skóre jen podružný vliv, ale dobrý žebříček pro scrabble by ho neměl úplně ignorovat. Pokud nad někým vyhraju o 1 bod, je to ve scrabblu spíše vliv náhody, ale nemohu z toho usuzovat, že jsem silnější než soupeř. Stačilo jen nepatrně odlišné pořadí losování písmen a hra mohla skončit remízou nebo mohl o pár bodů vyhrát soupeř, což však nic nemění na tom, že jsme oba zhruba stejně silní. Naproti tomu výhra o dejme tomu 50 bodů je už přesvědčivá a výhra o 100 bodů svědčí o opravdu rozdílné síle obou hráčů. Přes toto zdůvodnění je však skutečností, že většina existujících žebříčků skóre nijak nezohledňuje. Můžeme se jen dohadovat, zda je to proto, že se jejich autorům zdálo příliš obtížné matematicky popsat vztah síly hráčů a skóre jejich partie, nebo proto, že první žebříčky byly sestavovány pro hry, v nichž skóre buď vůbec neexistuje, nebo existuje, ale na výsledek hry nemá vliv náhoda jako ve scrabblu, což je základní předpoklad výše uvedené úvahy.

Shrňme na závěr, že pro sestavení žebříčku je potřeba znát výsledky partií, které hráči sehráli (výsledek je buď skóre, nebo, pokud na něj žebříček nebere ohled, pouze "vyhrál začínající hráč", "remíza", "prohrál začínající hráč"), a postavení hráčů v žebříčku před sehráním těchto partií. Na základě toho se žebříček upraví, aby pořadí hráčů více odpovídalo jejich současné síle.

Které partie se počítají do žebříčku ČAS

Do žebříčku se počítají partie sehrané v rámci akcí ČAS. Těmito akcemi jsou zejména kvalifikační turnaje, mistrovství republiky (normální i juniorské) a ligová utkání. Počítají se však i obyčejné turnaje, pokud proběhly pod hlavičkou ČAS (jeden takový byl například sehrán po ustavujícím sněmu ČAS v dubnu 1998, další se konal o tři roky později v Brně jako doplňkový B turnaj ke kvalifikačnímu turnaji). O přidělení statusu turnaje ČAS rozhoduje výbor ČAS, přičemž je potřeba, aby turnaj proběhl podle pravidel asociace, aby se o něm všichni členové v dostatečném předstihu dozvěděli a aby měl rozumnou kapacitu.

Kdy se žebříček přepočítává

Volba okamžiku, kdy se žebříček aktualizuje, může mít vliv na to, k jaké síle se u jednotlivých hráčů dospěje. Jak již bylo řečeno, při započítávání nově sehrané partie se bere ohled na to, jaká je síla hráčů, kteří ji sehráli, tj. jaké je jejich stávající postavení v žebříčku. Pokud tedy ihned po započtení partie žebříček upravím a další partii již posuzuji podle tohoto nového žebříčku, dospěju k jiným výsledkům, než když všechny partie jednoho turnaje započtu jako balík a teprve potom žebříček aktualizuji.

Je možné stanovit periodu, například 1 měsíc, a vždy k 1. dni v měsíci žebříček přepočítat. Není to však příliš šťastné, vždyť někdy se za měsíc nesehraje ani jedna partie a jindy proběhne několik turnajů a ligových utkání.

Na druhou stranu není ani vhodné aktualizovat žebříček po každé partii. Jednak by změny v žebříčku měly odrážet spíše dlouhodobější změny výkonnosti, než to, že už hraju tento den sedmou partii a začínám usínat, nebo že mi zrovna jednou nešla písmena. A jednak, což je podstatnější, přílišná citlivost na jednotlivé výsledky může úplně zkazit výsledky žebříčku, jako je tomu v následujícím příkladě: Představme si, že spolu hrají dva hráči, kteří jsou oba stejně silní. Protože ve scrabblu má vliv náhoda, nebudou jejich partie končit remízou, ke které ostatně dochází velmi zřídka, nýbrž budou střídavě vyhrávat a prohrávat. Pokud na začátku byli v žebříčku hodnoceni stejně, výhrou prvního hráče se to změní, výherce si polepší a poražený pohorší. Jenže napodruhé vyhraje druhý hráč. Protože je nyní v žebříčku hodnocen jako slabší, bude jeho výhra považována za neočekávanou a může se stát, že hráč se vyhoupne ještě výše, než byl po prvním kole jeho protivník. Ten se naopak odpovídajícím způsobem propadne. Jeho výhra je tedy napříště (podle žebříčku) ještě méně pravděpodobná, přesto k ní však dojde. Hráči si tedy opět vymění místa, ale budou od sebe ještě dále než dosud. A tak pořád dokola. Místo, aby si hráči udrželi společnou příčku, která odpovídá jejich stejné síle, budou se od ní neomezeně vzdalovat.

Pro žebříček ČAS byl tedy zvolen následující kompromis:

1. Žebříček se přepočítává vždy po turnaji. Všechny partie sehrané na jednom turnaji se započítají najednou.
2. Pokud se dva turnaje překrývají, započítají se po skončení prvního turnaje pouze partie z tohoto turnaje, ale ne již sehraná část druhého turnaje. Ta se započte až po dohrání druhého turnaje.
3. U ligových utkání se pro tyto účely za jeden turnaj považují všechny ligové partie sehrané v jeden den. Typicky je to jedno trojutkání, ale v případě odkládání jednotlivých utkání či dokonce zápasů tomu může být jinak.

Aktivní a neaktivní hráči

Bývá běžné v žebříčcích nějakým způsobem oddělovat hráče, kteří už dlouho nesehráli žádnou žebříčkovou partii. V žebříčku ČAS se za "dlouho" považuje rok. Hráči, kteří již rok nehráli, se řadí až za hráče, kteří jsou aktivnější, i když mají nižší sílu. Žebříček se tedy řadí nejprve podle toho, zda hráč sehrál alespoň jednu partii v posledních dvou letech, potom podle síly.

Pozor! Jde pouze o pořadí hráčů, jejich síla tím není nijak dotčena. Pokud se neaktivní hráči vrátí na turnaje, budou se jejich nově sehrané partie posuzovat podle jejich poslední známé síly.

Důvod oddělení neaktivních hráčů je především estetický. Kdyby tito hráči nebyli odděleni, mohlo by se za pár let stát, že aktivní hráči se mezi nimi úplně ztratí. Bylo by potom matoucí, když by se hráč ze žebříčku dozvěděl, že je třeba devadesátý, ale už by nezjistil, že mezi aktivními hráči je nyní jen třicet takových, kteří jsou silnější než on.

Jak se žebříček počítá

Nakonec zbývá to nejdůležitější. Známe dosavadní žebříček a výsledky nových partií. Jak z toho dostaneme nový žebříček?

ČAS si ze škály existujících metod vybral hned tři a z nich dělá průměr. Velkou výhodou je, že takto vždy dvě metody mohou udržet na uzdě tu třetí všude tam, kde by se od nich chtěla příliš odchýlit. Umístění hráčů je tedy realističtější než kdyby se použila pouze jedna metoda - samozřejmě za předpokladu, že všechny tři použité metody se chovají rozumně a neseřadí například hráče úplně obráceně.

Použité metody jsou následující. Podrobněji popsány budou níže, nicméně všechny tři vycházejí z původního Elova předpokladu o rozdělení pravděpodobnosti výhry nad průměrným hráčem.

Paluba

Metoda používaná již dříve v Klubu deskových her Paluba pro žebříčky ve Vrhcábech a Abalone, byla trochu upravena pro Scrabble a Zatre. Zatím jako jediná bere ohled na skóre partie. Má relativně nejjednodušší výpočet. Na změny ve výsledcích reaguje rychle, takže sleduje spíše krátkodobou výkonnost hráčů.

Dansa

neboli Danova podmnožina z toho, jak žebříček počítá americká National Scrabble Association. Jejich metoda má asi ze všech tří nejblíže k šachovému elu. Monitoruje spíše střednědobou výkonnost hráčů. Protože jsem zatím neměl čas implementovat všechny finesy metody NSA, raději zatím ustupuji od pojmenování NSA.

Peklo

Název této metody vznikl ze jmen Petr Kaňovský a Elo podle obou spoluautorů :-). Sleduje spíše dlouhodobou výkonnost hráčů. Tato metoda jako jediná nepotřebuje znát dosavadní stav žebříčku, místo toho uvažuje vždy tabulku všech partií sehraných od pravěku až do teď. Přináší to přinejmenším dvě výhody: jednak není závislá na tom, ve kterém okamžiku se žebříček přepočítá, jednak odpadají potíže se stanovením síly hráčů, kteří ještě nesehráli žádnou partii. Nevýhodou však je, že každý hráč s sebou jako balvan táhne výsledky, kterých dosahoval před lety a které třeba byly mnohem horší než dnes, protože od té doby se ve scrabblu hodně zlepšil. Proto se u této metody do budoucna uvažuje o přiřazení nižší váhy starším partiím, případně o jejich úplném vyřazení po uplynutí nějaké doby.

Známe-li sílu hráče podle každé z těchto tří metod, jak určíme sílu pro žebříček ČAS? Před počítáním průměru je potřeba všechny tři síly normalizovat, protože jejich číselné vyjádření se pohybuje v rozdílných mezích (Paluba zhruba od 0 do 250, průměrný hráč má sílu 100; Dansa zhruba od 1000 do 2000, průměrný hráč má kolem 1500; Peklo má rovněž průměr kolem 1500, ale hodnoty nejsilnějších a nejslabších hráčů se od tohoto bodu vzdalují více).

Normalizace se provede takto: Pro každou metodu se najde hráč, který má nejnižší sílu podle této metody, a jeho normalizovaná síla se položí rovna nule. Obdobně normalizovaná síla nejsilnějšího hráče se nastaví na 1000. Síly ostatních hráčů se pak upraví tak, aby byly ve stejné vzdálenosti mezi 0 a 1000, jako byly před normalizací mezi sílou nejslabšího a nejsilnějšího hráče.

Z normalizovaných sil se udělá aritmetický průměr a výsledek se zaokrouhlí na celé číslo. To je síla hráče v žebříčku ČAS.

Paluba

Poznámka: V této kapitole se silou rozumí síla podle metody Paluba, nikoli celková síla v žebříčku ČAS.

Tato pravidla vycházejí z pravidel pro starší žebříčky ve Vrhcábech a v Abalone. Upravena byla zejména v zacházení s body získanými v započítávaných partiích. Zatímco v prvně jmenovaných hrách se počítá s bodovým ohodnocením jedné partie nepřesahujícím 10 bodů, ve Scrabble je obvyklý zisk řádově stovek bodů. Proto se do žebříčku počítá rozdíl bodů obou hráčů dělený deseti. Podrobněji je postup popsán níže.

Nový hráč začíná se silou 100. Ta se pak považuje za sílu průměrného hráče.

V okamžiku přepočítávání žebříčku se za každou partii zvlášť získá hodnota změny z, která může být kladná i záporná. Tato z se každému hráči sečtou a přičtou k síle, kterou měl před přepočítáváním žebříčku. Vstupem pro zjištění z z konkrétní partie je skóre daného hráče skóre₁, skóre jeho protivníka skóre₂, poslední síla hráče síla₁ a poslední síla jeho protivníka síla₂.

Změna z pro konkrétního hráče je opačným číslem změny jeho protivníka, tj. jeden hráč získá právě tolik bodů, kolik druhý ztratí. Změna je tím vyšší, čím nepravděpodobnější byl daný výsledek.

Funkce pro vypočítání z u partií scrabble je aproximací integrační funkce, která se počítá v ostatních žebříčcích a vychází z principu, že pravděpodobnost výhry nad průměrným hráčem má tzv. normální rozdělení. Funkce je následující: , tj. ve Visual Basiku:

  relativní_skóre = (skóre1 - skóre2 + Sgn(skóre1 - skóre2) * 9) / 10
  rozdíl_v_žebříčku = Sgn(relativní_skóre) * (síla1 - síla2)
  výsledek = relativní_skóre * (2 / (1 + 1.02 ^ rozdíl_v_žebříčku))
  z = zaokrouhlit(výsledek, 0.01)

Změny po jednotlivých partiích se zaokrouhlují na setiny bodu. Nová síla (po přičtení všech změn) se zaokrouhluje na celé body.

Síla nemůže klesnout pod nulu. Pokud by po započtení všech změn hráči vyšla záporná síla, přiřadí se mu síla = 0. Bez ohledu na to se hráčům, kteří nad ním vyhráli, zvýší ohčo o plnou výši z, která vyplývá ze vzájemného výsledku. (Poznámka: Omezení síly zdola je motivováno spíše esteticky a psychologicky. Z matematického hlediska není důvod, proč by zvláště špatný hráč nemohl klesat i hluboko pod nulu.)

Dansa

V této kapitole je popsán žebříček NSA v implementaci Daniela Zemana, ve které zatím chybí některé rysy. Zatím tedy nejsou počítány akcelerační body, zpětnovazební body ani performance rating (to uvádím jen pro znalce žebříčku NSA; pokud nevíte, co tyto pojmy znamenají, nevadí). Koeficient rozvoje hráče není interpolován mezi dva řádky tabulky tam, kde to pravidla vyžadují. Počáteční síla hráče není získávána iteračně jako performance rating, nýbrž je nastavena pevně na hodnotu 1500 bodů. Poznámka: v této kapitole se silou rozumí síla podle metody Dansa, nikoli celková síla v žebříčku ČAS.

Po každém turnaji se stanoví počet partií, které hráč měl podle očekávání vyhrát, a odečte od počtu partií, které skutečně vyhrál. Jeho síla se stanoví na základě tohoto rozdílu, hráčovy předturnajové síly a součinitele, který závisí na počtu partií hráčem dosud sehraných.

Poznámka: Takto určená síla není závislá ani na bodových ziscích v partiích, ani na výsledcích proti jednotlivým hráčům, ale pouze na celkovém počtu vítězství a na rozdílech mezi silou hráče a jeho soupeřů.

Systém vychází ze dvou předpokladů:

• Pravděpodobnost výhry v partii je funkcí rozdílu sil obou hráčů.
• Hustota této pravděpodobnosti má normální rozložení s průměrem 0 a směrodatnou odchylkou 200*odmocnina(2).

Po každém turnaji se spočítají pravděpodobné vyhlídky hráče, které závisí na rozdílech jeho síly a sil jeho soupeřů. Tento očekávaný zisk se odečte od skutečného zisku, čímž se dostane přínos. Tento přínos se podle dosavadní síly hráče a podle počtu dosud sehraných partií vynásobí patřičným součinitelem podle tabulky (viz níže) a přičte k dosavadní síle. Výsledek po zaokrouhlení na nejbližší celé číslo tvoří novou sílu hráče.

Platí následující matematické vztahy:

R_n ... nový osobní koeficient hráče

R_o ... starý osobní koeficient hráče

R_i ... osobní koeficient i-tého soupeře

D_i ... rozdíl OK hráče a i-tého soupeře

P_i ... předpokládaný bodový zisk s i-tým soupeřem

P ... předpokládaný bodový zisk hráče v hodnoceném období

W ... skutečný bodový zisk hráče v hodnoceném období

K ... koeficient rozvoje hráče

n ... počet sehraných partií

Koeficient rozvoje hráče se stanoví podle následující tabulky:

Předturnajová síla	Počet sehraných partií
	1 - 49	50+
1 - 1799	30	20
1800 - 1999	24	16
2000 +	15	10

Jestliže se hráčova síla po turnaji přesune na jiný řádek této tabulky (tj. překročí-li hranici 1800 nebo 2000 bodů), měla by se podle původní metody NSA změna síly přepočítat ve dvou krocích s odpovídajícími součiniteli (v prvním kroku by se použilo tolik výher, kolik je třeba k dosažení hraničního počtu bodů, ve druhém kroku výhry zbývající). V metodě Dansa však toto pravidlo zatím není zahrnuto.

Příklady:

Vaše očekávání by mělo být 0,6 vítězství při rozdílu sil 72 bodů 0,7 při 148 bodech, 0,8 při 239 a 0,9 při 362 bodech. Mnozí zkušení hráči věří, že větší vyhlídky jsou příliš vysoké.

Vstupujete-li do turnaje se silou 1850 a hrajete 7 partií proti hráčům se silami 1702, 1702, 1778, 1922, 1922, 1998 a 1998, vaše vyhlídky na vítězství jsou 0,7 + 0,7 + 0,6 + 0,4 + 0,4 + 0,3 + 0,3 = 3,4. Jestliže jste skutečně vyhráli 4 partie a jedenkrát remizovali, získali jste "přebytek" vítězství 4,5 - 3,4 = 1,1 partie. Sehráli-li jste před tímto turnajem 48 partií, činí váš koeficient rozvoje podle tabulky 24 a vaše síla by měla vzrůst o 24 * 1,1 = 26,4 na 1876 (zaokrouhleno na nejbližší celé číslo).

Peklo

Autorem této metody je Petr Kaňovský. Název vznikl smícháním iniciál PK a jména Elo. Na následujících řádcích uvedeme teoretické odvození metody, vlastní postup výpočtu je nejlépe vidět přímo ze zdrojového kódu programu, kterým je výpočet žebříčku realizován (odkaz najdete na konci této stránky).

Alespoň jednoho turnaje se zúčastnilo n hráčů. Sestrojíme tabulku velikosti n×n, přičemž do políčka b[i,j] (i-tý řádek a j-tý sloupec) zapíšeme počet všech bodů, které získal i-tý hráč při partiích s j-tým hráčem na všech turnajích.

Poté určujeme na základě této tabulky všem hráčům současně jejich ELO[i]. Základní myšlenkou je, že pravděpodobnost výhry hráče s elem E₁ nad hráčem s elem E₂ je

(1) 1/(1+2^((E2-E1)/200)),

tj. například pravděpodobnost, že hráč porazí hráče s elem o 200 nižším, než má sám, je 2/3. Dále předpokládáme, že průměrný hráč má elo = 1500.

Označíme-li x[i] pravděpodobnost, že i-tý hráč porazí hráče s elem 1500, získáme

(2) ELO[i]=1500+200*ln(x[i]/(1-x[i])).

Pravděpodobnost, že hráč i porazí hráče j, je po úpravě

(3) x[i]*(1-x[j])/((x[i]*(1-x[j])+x[j]*(1-x[i])).

Pokud je elo již stabilní (hráči sehráli dostatek partií), měl by hráč i získat při zápase s hráčem j v průměru 0 bodů, a proto je přirozené předpokládat, že za vítězství získá k*x[j]*(1-x[i]) bodů a za prohru ztratí k*x[i]*(1-x[j]) bodů, kde k je vhodná konstanta. Potom je splněn vztah (2). Je zde také vidět, že čím je soupeř silnější, tím více získá hráč bodů v případě vítězství a tím méně bodů ztratí v případě prohry.

Protože chceme nalézt stabilní elo, chceme, aby v případě, že všichni hráči sehrají opět všechny své partie se stejným výsledkem, se jejich elo nezměnilo. Spolu s výše uvedenými tvrzeními to dává rovnice

(4) 0 = (b[i,1]*x[1]*(1-x[i]) - b[1,i]*x[i]*(1-x[1])
+ (b[i,2]*x[2]*(1-x[i]) - b[2,i]*x[i]*(1-x[2])
+ ...
+ (b[i,n]*x[n]*(1-x[i]) - b[n,i]*x[i]*(1-x[n])

pro všechna i = 1, 2, ..., n.

To dává systém rovnic

(5) x[i]=suma(b[i,j]*x[j]) / suma(b[i,j]*x[j]+b[j,i]*(1-x[j]))

pro všechna i = 1, 2, ..., n, kde v sumě sčítáme přes všechna j = 1, 2, ..., n, j<>i.

Aby nebylo příliš zkresleno elo hráčů, kteří sehráli příliš málo partií, u hráče, který sehrál r partií (r<20) předpokládáme, že sehrál zbývajících r partií s fiktivním hráčem s konstantním elem 1500 a nerozhodným výsledkem. To vyrovnává elo hráčů, kteří sehráli málo partií, k hodnotě 1500, což je lepší, než v důsledku jedné prohrané partie jim dát příliš vysoké nebo nízké elo.

To nám dává systém

(6) x[i]=suma(b[i,j]*x[j]) / suma(b[i,j]*x[j]+b[j,i]*(1-x[j]))

pro všechna i = 1, 2, ..., n, kde v sumě sčítáme přes všechna j = 0, 1, ..., n, j<>i, kde

(7) b[0,i]=b[i,0]=min(0,(40-suma(b[i,j]+b[j,i]))/2)
x[0]=1/2.

Protože chceme, aby průměrný hráč měl elo = 1500, přidáme ještě podmínku

(8) x[1]+x[2]+...+x[n]=n/2.

Systém (6), (7), (8) můžeme řešit iteračně, jako nultou iteraci zvolíme například x[1]=x[2]=...=x[n]=1/2. Další iterace získáme ze vztahu

(9) x[i]=y[i]/{(y[1]+...+y[n])/(n/2)},

kde y[i]=suma(b[i,j]*x[j]) / suma(b[i,j]*x[j]+b[j,i]*(1-x[j])) pro všechna i = 1, 2, ..., n, kde v sumě sčítáme přes všechna j = 0, 1, ..., n, j<>i.

Dá se ukázat, že systém iterací velmi rychle konverguje, čímž získáme jediné řešení systému (6), (7), (8). Ela jednotlivých hráčů určíme pomocí vztahu (2).

Poznámka: Je-li b[0,i]=b[i,0]=0, první iterací získáme procentuální úspěšnost hráče, druhou iterací v podstatě procentuální úspěšnost opravenou o body Buchholze (součet bodů soupeřů), další iterace již výsledek jen trochu zpřesní. Podobný závěr získáme i za předpokladu, že hráči sehráli stejný malý počet partií. Provedeme-li výpočet ela jen izolovaně na výsledky některého turnaje, získáme výsledky, které odpovídají oficiálním výsledkům turnaje (tvořené pomocí počtu výher a bodů Buchholze), dochází zde jen k malým odchylkám (zejména pokud došlo k rovnosti a rozhodovalo skóre).

Autor: Tomáš Kuča
© 2008