Warum verwendet das Elo-Bewertungssystem eine falsche Aktualisierungsregel?

Das Elo-Bewertungssystem verwendet einen Gradientenabstiegsminimierungsalgorithmus der Kreuzentropieverlustfunktion zwischen der erwarteten und der beobachteten Wahrscheinlichkeit eines Ergebnisses in gepaarten Vergleichen. Wir können die allgemeinen Verlustfunktionen als schreiben

E = - \sum_{n, i} p_{i} L o g (q_{i})

$E=-\sum_{n,i} p_i Log (q_i)$

wobei die Summe über alle Ergebnisse und alle Gegner . ist die beobachtete Frequenz des Ereignisses und die erwartete Frequenz. $i$ $n$ $p_i$ $_i$ $q_i$

Bei nur zwei möglichen Ergebnissen (gewinnen oder verlieren) und einem Gegner haben wir

E = - p L o g (q) - (1 - p) L o g (1 - q)

$E=-p Log (q)-(1-p)Log(1-q)$

Wenn die Rangfolge des Spielers und die Rangfolge des Spielers , können wir die erwartete Wahrscheinlichkeit als Dann wird die Aktualisierungsregel für den Gradientenabstieg verwendet $\pi_i$ $i$ $\pi_j$ $j$

q_{i} = \frac{e^{π_{i}}}{e^{π_{i}} + e^{π_{j}}}

$q_i=\frac{e^{\pi_i}}{e^{\pi_i}+e^{\pi_j}}$

q_{j} = \frac{e^{π_{j}}}{e^{π_{i}} + e^{π_{j}}}

$q_j=\frac{e^{\pi_j}}{e^{\pi_i}+e^{\pi_j}}$

π_{i}^{'} = π_{i} - η (q_{i} - p_{i})

$\pi_i'=\pi_i-\eta (q_i-p_i)$

π_{j}^{'} = π_{j} - η (q_{j} - p_{j})

$\pi_j'=\pi_j-\eta (q_j-p_j)$

Dabei sind und die erwartete und beobachtete Gewinnwahrscheinlichkeit des Spielers gegen den Spieler . Dies sind die Aktualisierungsregeln. $q_i$ $p_i$ $i$ $j$ two outcomes

Bei Vorhandensein von Ziehungen können wir das obige Modell einschließlich und des dritten Ergebnisses mit Wahrscheinlichkeit verallgemeinern

q (d) = \frac{ν e^{\frac{π_{i} + π_{j}}{2}}}{e^{π_{i}} + e^{π_{j}} + ν e^{\frac{π_{i} + π_{j}}{2}}}

$q(d)=\frac{\nu e^{\frac{\pi_i+\pi_j}{2}}}{e^{\pi_i}+e^{\pi_j}+\nu e^{\frac{\pi_i+\pi_j}{2}}}$

q_{i} (w) = \frac{e^{π_{i}}}{e^{π_{i}} + e^{π_{j}} + ν e^{\frac{π_{i} + π_{j}}{2}}}

$q_i(w)=\frac{ e^{\pi_i}}{e^{\pi_i}+e^{\pi_j}+\nu e^{\frac{\pi_i+\pi_j}{2}}}$

q_{j} (w) = \frac{e^{π_{j}}}{e^{π_{i}} + e^{π_{j}} + ν e^{\frac{π_{i} + π_{j}}{2}}}

$q_j(w)=\frac{ e^{\pi_j}}{e^{\pi_i}+e^{\pi_j}+\nu e^{\frac{\pi_i+\pi_j}{2}}}$

Und wir können die Verlustfunktion als erstellen

E = - p (w) L o g (q (w)) - (1 - p (w) - p (d)) L o g (q (l)) - p (d) L o g (q (d))

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

wobei ist jeweils die beobachteten Wahrscheinlichkeit , und und erwartete Wahrscheinlichkeit , und . Im letzteren Fall wäre die Aktualisierungsregel $p(w),p(l),p(d)$ winloosedraw $q(w),q(l),q(d)$ winloosedraw

π_{i}^{'} = π_{i} - η (q_{i} (w) + \frac{q_{i} (d)}{2} - p_{i} (w) - \frac{p_{i} (d)}{2})

$\pi_i'=\pi_i-\eta (q_i(w)+\frac{q_i(d)}{2}-p_i(w)-\frac{p_i(d)}{2})$

π_{j}^{'} = π_{j} - η (q_{j} (w) + \frac{q_{j} (d)}{2} - p_{j} (w) - \frac{p_{j} (d)}{2})

$\pi_j'=\pi_j-\eta (q_j(w)+\frac{q_j(d)}{2}-p_j(w)-\frac{p_j(d)}{2})$

wobei und die erwartete Wahrscheinlichkeit sind, dass der Spieler gewinnt und gegen den Spieler zieht . Und wobei und die beobachtete Wahrscheinlichkeit sind, dass der Spieler gewinnt und gegen den Spieler zieht . Dies ist die Aktualisierungsregel. $q_j(w)$ $q_j(d)$ $i$ $j$ $p_i(w)$ $p_i(d)$ $i$ $j$ three outcome

Die Frage ist, warum das Elo-Bewertungssystem die two outcomesAktualisierungsregeln auch bei Unentschieden verwendet.

regression optimization rating emanuele
quelle

Antworten:

Die Wahrscheinlichkeit des Zeichnens im Gegensatz zu einem entscheidenden Ergebnis ist im Elo-System nicht angegeben . Stattdessen wird ein Unentschieden - sowohl bei der erwarteten Leistung als auch beim Spielergebnis - als halber Sieg und halber Verlust betrachtet.

Ein Beispiel von der Elo-Seite in Wikipedia : "Die erwartete Punktzahl eines Spielers ist seine Gewinnwahrscheinlichkeit plus die Hälfte seiner Unentschiedenwahrscheinlichkeit. Eine erwartete Punktzahl von 0,75 könnte also eine Gewinnchance von 75%, eine Verlustchance von 25% und eine Chance von 0% bedeuten Auf der anderen Seite könnte es eine 50% ige Gewinnchance, eine 0% ige Verlustchance und eine 50% ige Gewinnchance bedeuten. "

Die Wahrscheinlichkeit des Zeichnens ist, wie gesagt, nicht angegeben und führt zu einer einfachen two outcomeAktualisierungsregel, , in der , also nach einem einzelnen Spiel (Sieg) oder (Unentschieden, als halber Gewinn) oder (Verlust). $R_A^\prime = R_A + K(S_A - E_A)$ $S_A=1 \cdot (n_w + 0.5 \cdot n_d ) + 0 \cdot (0.5 \cdot n_d + n_l)$ $S_A=1$ $S_A=0.5$ $S_A=0$

Wie Elo modelliert das Glicko-System keine Draws, sondern führt ein Update als Durchschnitt aus Gewinn und Verlust (pro Spieler) durch. Stattdessen werden im TrueSkill- Rangsystem "Unentschieden modelliert, indem angenommen wird, dass der Leistungsunterschied in einem bestimmten Spiel gering ist. Daher hängt die Chance auf ein Unentschieden nur vom Unterschied der Spielstärke der beiden Spieler ab. Jedoch empirische Ergebnisse im Spiel von Schach zeigen, dass Unentschieden zwischen Profispielern wahrscheinlicher sind als Anfänger. Daher scheint die Chance auf ein Unentschieden auch von der Fähigkeitsstufe abzuhängen. "

Dieser Ansatz erfordert für jedes Spiel eine andere spezifische Modellierung (und TrueSkill wird auf einige Microsoft Xbox-Spiele angewendet), sodass er für Elo und Glicko (nur für Schach entwickelt) geeignet ist und nicht für Rankade , unser Mehrzweck-Ranking-System.

Tomaso Neri
quelle

"Die erwartete Punktzahl eines Spielers ist seine Gewinnwahrscheinlichkeit plus die Hälfte seiner Unentschiedenwahrscheinlichkeit." ist genau das, was ich in der obigen Formel gefunden habe. Wie auch immer, in der Elo-Aktualisierungsformel ist die Hälfte der Wahrscheinlichkeit des Zeichnens nicht angegeben, wie Sie hervorheben. Es bleibt die Frage, warum wir uns im Elo-Ranking-System nicht für Unentschieden interessieren.

Emanuele

Sie können immer (- siehe erstes Beispiel von Wikipedia und keine Chance Zeichnung) erwartet Punktzahl als die Chance zu gewinnen und die Chance zu verlieren auszudrücken. In diesem Fall ist "die erwartete Punktzahl eines Spielers seine Gewinnwahrscheinlichkeit" (und alles andere, da die halbe Wahrscheinlichkeit des Ziehens Null ist). Nach einem einzelnen Spiel ist das Ergebnis ein Sieg oder eine Niederlage oder ein halber Sieg. Selbst wenn Sie ein Spiel haben, in dem Unentschieden erlaubt sind, können Sie die Elo-Punktzahl mit nur einer Kombination aus Sieg und Niederlage aktualisieren, als hätten Unentschieden keine Chance.

Tomaso Neri