ALGORITMO DI VALUTAZIONE ELO

IL Algoritmo di valutazione Elo è un algoritmo di valutazione ampiamente utilizzato per classificare i giocatori in molti giochi competitivi.

I giocatori con un punteggio ELO più alto hanno una probabilità maggiore di vincere una partita rispetto ai giocatori con un punteggio ELO più basso.
Dopo ogni partita viene aggiornata la valutazione ELO dei giocatori.
Se vince un giocatore con un punteggio ELO più alto, verranno trasferiti solo pochi punti dal giocatore con un punteggio più basso.
Tuttavia, se vince il giocatore con il punteggio più basso, i punti trasferiti da un giocatore con il punteggio più alto saranno molto maggiori.

Approccio: Per risolvere il problema seguire l'idea seguente:

P1: Probabilità di vincita del giocatore con rating2 P2: Probabilità di vincita del giocatore con rating1.
P1 = (1.0 / (1.0 + pow(10 ((voto1 - voto2) / 400))));
P2 = (1.0 / (1.0 + pow(10 ((voto2 - voto1) / 400))));

array.da Java
Ovviamente P1 + P2 = 1. La valutazione del giocatore viene aggiornata utilizzando la formula riportata di seguito: -
voto1 = voto1 + K*(punteggio effettivo - punteggio previsto);
Nella maggior parte dei giochi il "punteggio effettivo" è 0 o 1 e significa che il giocatore vince o perde. K è una costante. Se K ha un valore inferiore, il rating viene modificato di una piccola frazione, ma se K ha un valore superiore, i cambiamenti nel rating sono significativi. Diverse organizzazioni stabiliscono un valore diverso di K.

Esempio:

Supponiamo che ci sia una partita dal vivo su chess.com tra due giocatori
valutazione1 = 1200 valutazione2 = 1000;
P1 = (1,0 / (1,0 + potenza(10 ((1000-1200) / 400)))) = 0,76
P2 = (1,0 / (1,0 + potenza(10 ((1200-1000) / 400)))) = 0,24
E assumiamo la costante K=30;
un array di oggetti java
CASO-1:
Supponiamo che il giocatore 1 vinca: voto1 = voto1 + k*(effettivo - previsto) = 1200+30(1 - 0,76) = 1207,2;
valutazione2 = valutazione2 + k*(effettivo - previsto) = 1000+30(0 - 0,24) = 992,8;
operatore resto Python
Caso-2:
Supponiamo che il giocatore 2 vinca: voto1 = voto1 + k*(effettivo - previsto) = 1200+30(0 - 0,76) = 1177,2;
valutazione2 = valutazione2 + k*(effettivo - previsto) = 1000+30(1 - 0,24) = 1022,8;

Seguire i passaggi seguenti per risolvere il problema:

Calcola la probabilità di vincita dei giocatori A e B utilizzando la formula sopra riportata
Se vince il giocatore A o il giocatore B, le valutazioni vengono aggiornate di conseguenza utilizzando le formule:
- valutazione1 = valutazione1 + K*(punteggio effettivo - punteggio previsto)
- valutazione2 = valutazione2 + K*(punteggio effettivo - punteggio previsto)
- Dove il punteggio effettivo è 0 o 1
Stampa le valutazioni aggiornate

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

CPP

#include    using namespace std; // Function to calculate the Probability float Probability(int rating1 int rating2) {  // Calculate and return the expected score  return 1.0 / (1 + 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. void EloRating(float Ra float Rb int K float outcome) {  // Calculate the Winning Probability of Player B  float Pb = Probability(Ra Rb);  // Calculate the Winning Probability of Player A  float Pa = Probability(Rb Ra);  // Update the Elo Ratings  Ra = Ra + K * (outcome - Pa);  Rb = Rb + K * ((1 - outcome) - Pb);  // Print updated ratings  cout << 'Updated Ratings:-n';  cout << 'Ra = ' << Ra << ' Rb = ' << Rb << endl; } // Driver code int main() {  // Current ELO ratings  float 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  float outcome = 1;  // Function call  EloRating(Ra Rb K outcome);  return 0; }

Java

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);  } }

Python

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}');  } }

JavaScript

// 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);

Produzione

Updated Ratings:- Ra = 1207.21 Rb = 992.792

Complessità temporale: La complessità temporale dell'algoritmo dipende principalmente dalla complessità della funzione pow, la cui complessità dipende dall'architettura del computer. Su x86 questa è un'operazione a tempo costante:-O(1)
Spazio ausiliario: O(1)