El Algoritmo de calificación Elo es un algoritmo de clasificación ampliamente utilizado para clasificar a los jugadores en muchos juegos competitivos.
- Los jugadores con calificaciones ELO más altas tienen una mayor probabilidad de ganar un juego que los jugadores con calificaciones ELO más bajas.
- Después de cada juego se actualiza la calificación ELO de los jugadores.
- Si un jugador con una calificación ELO más alta gana, solo se transfieren unos pocos puntos del jugador con una calificación más baja.
- Sin embargo, si gana el jugador con la puntuación más baja, los puntos transferidos por un jugador con la puntuación más alta serán mucho mayores.
Acercarse: Para resolver el problema, siga la siguiente idea:
P1: Probabilidad de ganar del jugador con rating2 P2: Probabilidad de ganar del jugador con rating1.
P1 = (1,0 / (1,0 + pow(10 ((calificación1 - calificación2) / 400))));
P2 = (1,0 / (1,0 + pow(10 ((calificación2 - calificación1) / 400))));Obviamente P1 + P2 = 1. La calificación del jugador se actualiza utilizando la fórmula que se proporciona a continuación: -
calificación1 = calificación1 + K*(Puntuación real - Puntuación esperada);En la mayoría de los juegos, la 'Puntuación real' es 0 o 1, lo que significa que el jugador gana o pierde. K es una constante. Si K es de un valor más bajo, entonces la calificación cambia en una pequeña fracción, pero si K es de un valor más alto, entonces los cambios en la calificación son significativos. Diferentes organizaciones establecen un valor diferente de K.
Ejemplo:
Supongamos que hay una partida en vivo en chess.com entre dos jugadores.
calificación1 = 1200 calificación2 = 1000;P1 = (1,0 / (1,0 + potencia(10 ((1000-1200) / 400)))) = 0,76
P2 = (1,0 / (1,0 + pow(10 ((1200-1000) / 400)))) = 0,24
Y supongamos constante K=30;CASO-1:
Supongamos que gana el jugador 1: calificación1 = calificación1 + k*(real - esperado) = 1200+30(1 - 0,76) = 1207,2;
calificación2 = calificación2 + k*(real - esperado) = 1000+30(0 - 0,24) = 992,8;Caso-2:
Supongamos que gana el jugador 2: calificación1 = calificación1 + k*(real - esperado) = 1200+30(0 - 0,76) = 1177,2;
calificación2 = calificación2 + k*(real - esperado) = 1000+30(1 - 0,24) = 1022,8;
Siga los pasos a continuación para resolver el problema:
- Calcule la probabilidad de ganar de los jugadores A y B usando la fórmula anterior
- Si el jugador A gana o el jugador B gana, las calificaciones se actualizan en consecuencia utilizando las fórmulas:
- calificación1 = calificación1 + K*(Puntuación real - Puntuación esperada)
- calificación2 = calificación2 + K*(Puntuación real - Puntuación esperada)
- Donde la puntuación real es 0 o 1
- Imprimir las calificaciones actualizadas
A continuación se muestra la implementación del enfoque anterior:
si por rudyard kipling resumenCPP
#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);
Producción
Updated Ratings:- Ra = 1207.21 Rb = 992.792
Complejidad del tiempo: La complejidad temporal del algoritmo depende principalmente de la complejidad de la función pow, cuya complejidad depende de la arquitectura de la computadora. En x86 esta es una operación de tiempo constante:-O(1)
Espacio Auxiliar: O(1)