Der Elo-Bewertungsalgorithmus ist ein weit verbreiteter Bewertungsalgorithmus, mit dem Spieler in vielen Wettbewerbsspielen bewertet werden.
- Spieler mit höheren ELO-Werten haben eine höhere Wahrscheinlichkeit, ein Spiel zu gewinnen als Spieler mit niedrigeren ELO-Werten.
- Nach jedem Spiel wird die ELO-Bewertung der Spieler aktualisiert.
- Wenn ein Spieler mit einem höheren ELO-Wert gewinnt, werden nur wenige Punkte vom Spieler mit dem niedrigeren Wert übertragen.
- Wenn jedoch der Spieler mit der niedrigeren Bewertung gewinnt, sind die übertragenen Punkte eines Spielers mit der höheren Bewertung weitaus höher.
Ansatz: Um das Problem zu lösen, befolgen Sie die folgende Idee:
P1: Gewinnwahrscheinlichkeit des Spielers mit der Bewertung 2. P2: Gewinnwahrscheinlichkeit des Spielers mit der Bewertung 1.
P1 = (1,0 / (1,0 + pow(10 ((Bewertung1 - Bewertung2) / 400))));
P2 = (1,0 / (1,0 + pow(10 ((Bewertung2 - Bewertung1) / 400))));Offensichtlich ist P1 + P2 = 1. Die Bewertung des Spielers wird mithilfe der unten angegebenen Formel aktualisiert:
Bewertung1 = Bewertung1 + K*(Tatsächliche Punktzahl – Erwartete Punktzahl);In den meisten Spielen ist der tatsächliche Punktestand entweder 0 oder 1, was bedeutet, dass der Spieler entweder gewinnt oder verliert. K ist eine Konstante. Wenn K einen niedrigeren Wert hat, ändert sich die Bewertung um einen kleinen Bruchteil, wenn K jedoch einen höheren Wert hat, sind die Änderungen in der Bewertung erheblich. Verschiedene Organisationen legen einen unterschiedlichen Wert für K fest.
Beispiel:
Angenommen, auf chess.com findet ein Live-Spiel zwischen zwei Spielern statt
Bewertung1 = 1200 Bewertung2 = 1000;P1 = (1,0 / (1,0 + pow(10 ((1000-1200) / 400)))) = 0,76
P2 = (1,0 / (1,0 + pow(10 ((1200-1000) / 400)))) = 0,24
Und nehmen Sie die Konstante K=30 an;FALL-1:
Angenommen, Spieler 1 gewinnt: Bewertung1 = Bewertung1 + k*(tatsächlich – erwartet) = 1200+30(1 – 0,76) = 1207,2;
Bewertung2 = Bewertung2 + k*(tatsächlich – erwartet) = 1000+30(0 – 0,24) = 992,8;Fall 2:
Angenommen, Spieler 2 gewinnt: Bewertung1 = Bewertung1 + k*(tatsächlich – erwartet) = 1200+30(0 – 0,76) = 1177,2;
Bewertung2 = Bewertung2 + k*(tatsächlich – erwartet) = 1000+30(1 – 0,24) = 1022,8;
Befolgen Sie die folgenden Schritte, um das Problem zu lösen:
- Berechnen Sie die Gewinnwahrscheinlichkeit der Spieler A und B anhand der oben angegebenen Formel
- Wenn Spieler A gewinnt oder Spieler B gewinnt, werden die Bewertungen entsprechend anhand der Formeln aktualisiert:
- Bewertung1 = Bewertung1 + K*(Tatsächliche Punktzahl – Erwartete Punktzahl)
- Bewertung2 = Bewertung2 + K*(Tatsächliche Punktzahl – Erwartete Punktzahl)
- Wobei die tatsächliche Punktzahl 0 oder 1 ist
- Drucken Sie die aktualisierten Bewertungen aus
Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:
CPP#include
import java.lang.Math; public class EloRating { // Function to calculate the Probability public static double Probability(int rating1 int rating2) { // Calculate and return the expected score return 1.0 / (1 + Math.pow(10 (rating1 - rating2) / 400.0)); } // Function to calculate Elo rating // K is a constant. // outcome determines the outcome: 1 for Player A win 0 for Player B win 0.5 for draw. public static void EloRating(double Ra double Rb int K double outcome) { // Calculate the Winning Probability of Player B double Pb = Probability(Ra Rb); // Calculate the Winning Probability of Player A double Pa = Probability(Rb Ra); // Update the Elo Ratings Ra = Ra + K * (outcome - Pa); Rb = Rb + K * ((1 - outcome) - Pb); // Print updated ratings System.out.println('Updated Ratings:-'); System.out.println('Ra = ' + Ra + ' Rb = ' + Rb); } public static void main(String[] args) { // Current ELO ratings double Ra = 1200 Rb = 1000; // K is a constant int K = 30; // Outcome: 1 for Player A win 0 for Player B win 0.5 for draw double outcome = 1; // Function call EloRating(Ra Rb K outcome); } }
import math # Function to calculate the Probability def probability(rating1 rating2): # Calculate and return the expected score return 1.0 / (1 + math.pow(10 (rating1 - rating2) / 400.0)) # Function to calculate Elo rating # K is a constant. # outcome determines the outcome: 1 for Player A win 0 for Player B win 0.5 for draw. def elo_rating(Ra Rb K outcome): # Calculate the Winning Probability of Player B Pb = probability(Ra Rb) # Calculate the Winning Probability of Player A Pa = probability(Rb Ra) # Update the Elo Ratings Ra = Ra + K * (outcome - Pa) Rb = Rb + K * ((1 - outcome) - Pb) # Print updated ratings print('Updated Ratings:-') print(f'Ra = {Ra} Rb = {Rb}') # Current ELO ratings Ra = 1200 Rb = 1000 # K is a constant K = 30 # Outcome: 1 for Player A win 0 for Player B win 0.5 for draw outcome = 1 # Function call elo_rating(Ra Rb K outcome)
using System; class EloRating { // Function to calculate the Probability public static double Probability(int rating1 int rating2) { // Calculate and return the expected score return 1.0 / (1 + Math.Pow(10 (rating1 - rating2) / 400.0)); } // Function to calculate Elo rating // K is a constant. // outcome determines the outcome: 1 for Player A win 0 for Player B win 0.5 for draw. public static void CalculateEloRating(ref double Ra ref double Rb int K double outcome) { // Calculate the Winning Probability of Player B double Pb = Probability((int)Ra (int)Rb); // Calculate the Winning Probability of Player A double Pa = Probability((int)Rb (int)Ra); // Update the Elo Ratings Ra = Ra + K * (outcome - Pa); Rb = Rb + K * ((1 - outcome) - Pb); } static void Main() { // Current ELO ratings double Ra = 1200 Rb = 1000; // K is a constant int K = 30; // Outcome: 1 for Player A win 0 for Player B win 0.5 for draw double outcome = 1; // Function call CalculateEloRating(ref Ra ref Rb K outcome); // Print updated ratings Console.WriteLine('Updated Ratings:-'); Console.WriteLine($'Ra = {Ra} Rb = {Rb}'); } }
// Function to calculate the Probability function probability(rating1 rating2) { // Calculate and return the expected score return 1 / (1 + Math.pow(10 (rating1 - rating2) / 400)); } // Function to calculate Elo rating // K is a constant. // outcome determines the outcome: 1 for Player A win 0 for Player B win 0.5 for draw. function eloRating(Ra Rb K outcome) { // Calculate the Winning Probability of Player B let Pb = probability(Ra Rb); // Calculate the Winning Probability of Player A let Pa = probability(Rb Ra); // Update the Elo Ratings Ra = Ra + K * (outcome - Pa); Rb = Rb + K * ((1 - outcome) - Pb); // Print updated ratings console.log('Updated Ratings:-'); console.log(`Ra = ${Ra} Rb = ${Rb}`); } // Current ELO ratings let Ra = 1200 Rb = 1000; // K is a constant let K = 30; // Outcome: 1 for Player A win 0 for Player B win 0.5 for draw let outcome = 1; // Function call eloRating(Ra Rb K outcome);
Ausgabe
Updated Ratings:- Ra = 1207.21 Rb = 992.792
Zeitkomplexität: Die zeitliche Komplexität des Algorithmus hängt hauptsächlich von der Komplexität der pow-Funktion ab, deren Komplexität von der Computerarchitektur abhängt. Auf x86 ist dies ein Konstantzeitbetrieb:-O(1)
Hilfsraum: O(1)