АЛГОРИТМ РЕЙТИНГУ ELO - МАТЕМАТИЧНИЙ

The Алгоритм рейтингу Elo це широко використовуваний рейтинговий алгоритм, який використовується для ранжирування гравців у багатьох змагальних іграх.

Гравці з вищим рейтингом ELO мають вищу ймовірність виграти гру, ніж гравці з нижчим рейтингом ELO.
Після кожної гри рейтинг ELO гравців оновлюється.
Якщо гравець з вищим рейтингом ELO виграє, лише кілька очок передаються від гравця з нижчим рейтингом.
Однак якщо виграє гравець з нижчим рейтингом, то передані очки від гравця з вищим рейтингом будуть набагато більшими.

Підхід: Щоб вирішити проблему, дотримуйтеся наведеної нижче ідеї:

P1: Ймовірність виграшу гравця з рейтингом 2 P2: Імовірність виграшу гравця з рейтингом 1.
P1 = (1,0 / (1,0 + pow(10 ((рейтинг1 - рейтинг2) / 400))));
P2 = (1,0 / (1,0 + pow(10 ((рейтинг2 - рейтинг1) / 400))));

рядок як масив
Очевидно, P1 + P2 = 1. Рейтинг гравця оновлюється за формулою, наведеною нижче:-
рейтинг1 = рейтинг1 + К*(Фактичний бал - Очікуваний бал);
У більшості ігор «Фактичний рахунок» дорівнює 0 або 1, що означає, що гравець виграє або програє. К — константа. Якщо K має нижче значення, то рейтинг змінюється на невелику частку, але якщо K має вище значення, то зміни в рейтингу є значними. Різні організації встановлюють різне значення K.

приклад:

Припустімо, що на сайті chess.com відбувається живий матч між двома гравцями
рейтинг1 = 1200 рейтинг2 = 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
І припустимо постійну K=30;
з'єднання та типи з'єднань
ВИПАДОК-1:
Припустимо, гравець 1 перемагає: рейтинг1 = рейтинг1 + k*(фактичний - очікуваний) = 1200+30(1 - 0,76) = 1207,2;
рейтинг2 = рейтинг2 + k*(фактичний - очікуваний) = 1000+30(0 - 0,24) = 992,8;
алгоритм сортування купи
Випадок-2:
Припустимо, гравець 2 перемагає: рейтинг1 = рейтинг1 + k*(фактичний - очікуваний) = 1200+30(0 - 0,76) = 1177,2;
рейтинг2 = рейтинг2 + k*(фактичний - очікуваний) = 1000+30(1 - 0,24) = 1022,8;

Щоб вирішити проблему, виконайте наведені нижче дії.

Обчисліть ймовірність виграшу гравців A і B за наведеною вище формулою
Якщо виграє гравець А або виграє гравець Б, рейтинги оновлюються відповідно за формулами:
- рейтинг1 = рейтинг1 + K*(Фактичний бал - Очікуваний бал)
- рейтинг2 = рейтинг2 + K*(Фактичний бал - Очікуваний бал)
- Де фактичний бал дорівнює 0 або 1
Роздрукуйте оновлені рейтинги

Нижче наведено реалізацію вищезазначеного підходу:

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

Вихід

Updated Ratings:- Ra = 1207.21 Rb = 992.792

Часова складність: Часова складність алгоритму здебільшого залежить від складності функції pow, складність якої залежить від архітектури комп’ютера. На x86 це операція з постійним часом: -O(1)
Допоміжний простір: O(1)