Dlaczego system oceny Elo używa niewłaściwej reguły aktualizacji?

10

System oceny Elo wykorzystuje algorytm minimalizacji spadku gradientu funkcji utraty entropii krzyżowej między spodziewanym i obserwowanym prawdopodobieństwem wyniku w porównaniach w parach. Możemy zapisać funkcje strat ogólnych jako

E=n,ipiLog(qi)

gdzie suma jest wykonywana dla wszystkich wyników i wszystkich przeciwników n . p i to obserwowana częstotliwość zdarzenia iinpii oraz qi oczekiwaną częstotliwość.

W przypadku tylko dwóch możliwych wyników (wygrana lub przegrana) i jednego przeciwnika mamy

E=pLog(q)(1p)Log(1q)

Jeśli jest rankingiem gracza i iπii jest rankingiem gracza j , możemy zbudować oczekiwane prawdopodobieństwo jako q i = e π iπjj qj=eπj

qi=eπieπi+eπj
a następnie reguła aktualizacji opadania gradientu mówi użycie
qj=eπjeπi+eπj

πi=πiη(qipi)

πj=πjη(qjpj)

gdzie a p i są oczekiwane i obserwowane prawdopodobieństwo wygranej gracza I wobec gracza j . To sązasady aktualizacji.qipiijtwo outcomes

W przypadku losowań możemy uogólnić powyższy model z prawdopodobieństwem trzeciego wyniku

q(d)=νeπi+πj2eπi+eπj+νeπi+πj2
qi(w)=eπieπi+eπj+νeπi+πj2
qj(w)=eπjeπi+eπj+νeπi+πj2

I możemy zbudować funkcję Loss jako

E=p(w)Log(q(w))(1p(w)p(d))Log(q(l))p(d)Log(q(d))

gdzie p(w),p(l),p(d)winloosedrawq(w),q(l),q(d)win , loosei draw. W tym drugim przypadku reguła aktualizacji byłaby

πi=πiη(qi(w)+qi(d)2pi(w)pi(d)2)

πj=πjη(qj(w)+qj(d)2pj(w)pj(d)2)

qj(w)qj(d)ijpi(w)pja(re)jajotthree outcome

Pytanie brzmi, dlaczego system oceny Elo korzysta z two outcomes reguły aktualizacji nawet w przypadku losowań?

emanuele
źródło

Odpowiedzi:

3

Prawdopodobieństwo losowania, w przeciwieństwie do uzyskania decydującego wyniku, nie jest określone w systemie Elo. Zamiast tego rozważa się remis - zarówno pod względem oczekiwanego wyniku, jak i wyniku meczu - pół zwycięstwa i pół przegranej.

Przykład ze strony Elo w Wikipedii : „Oczekiwany wynik gracza to jego prawdopodobieństwo wygranej plus połowa jego prawdopodobieństwa losowania. Zatem oczekiwany wynik 0,75 może oznaczać 75% szans na wygraną, 25% szans na przegraną i 0% szans na z drugiej strony może oznaczać 50% szansy na wygraną, 0% szansy na przegraną i 50% szansy na remis. ”

Prawdopodobieństwo rysowania, jak już powiedziałem, nie jest określone i prowadzi do prostej two outcomereguły aktualizacji,RZA=RZA+K.(S.ZA-miZA), w którym S.ZA=1(nw+0,5nre)+0(0,5nre+nl), więc po jednym meczu S.ZA=1 (wygrana) lub S.ZA=0,5 (remis, jako połowa wygranej), lub S.ZA=0 (utrata).

Podobnie jak Elo, system Glicko nie modeluje losowań, ale dokonuje aktualizacji jako średniej wygranej i przegranej (na gracza). Zamiast tego w systemie rankingowym TrueSkill „losowania są modelowane przy założeniu, że różnica w wydajności w danej grze jest niewielka. Stąd szansa na losowanie zależy tylko od różnicy siły gry dwóch graczy. Jednak ustalenia empiryczne w grze pokazu szachowego, że losowanie jest bardziej prawdopodobne między zawodowymi graczami niż początkującymi. Dlatego szansa na losowanie wydaje się również zależeć od poziomu umiejętności. ”

To podejście wymaga innego specyficznego modelowania dla każdej gry (a TrueSkill jest stosowany do kilku gier Microsoft Xbox), więc jest odpowiedni dla Elo i Glicko (zaprojektowanych tylko dla szachów) i nie jest przeznaczony do rankingowej , naszego uniwersalnego systemu rankingowego.

Tomaso Neri
źródło
„Oczekiwanym wynikiem gracza jest prawdopodobieństwo wygranej plus połowa prawdopodobieństwa losowania”. jest dokładnie tym, co znalazłem w powyższym wzorze. W każdym razie we wzorze aktualizacji Elo połowa prawdopodobieństwa losowania nie jest określona, ​​jak wskazujesz. Pozostaje pytanie, dlaczego w systemie rankingowym Elo nie dbamy o losowania?
emanuele
1
Można zawsze wyrazić oczekiwany wynik jako szansę na wygraną i możliwość utraty (i zerową szansę na rysunku - patrz pierwszy przykład z Wikipedii). W tym przypadku „oczekiwanym wynikiem gracza jest jego prawdopodobieństwo wygranej” (i cokolwiek więcej, ponieważ połowa prawdopodobieństwa losowania wynosi zero). Po pojedynczym meczu wynikiem jest wygrana, przegrana lub połowa wygranej. Nawet jeśli masz grę, w której dozwolone są losowania, możesz zaktualizować wynik Elo, używając kombinacji wygranej i przegranej, tak jakby remisy nie miały szans.
Tomaso Neri