그만큼 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입니다. 플레이어의 등급은 아래 공식을 사용하여 업데이트됩니다.
rating1 = rating1 + K*(실제 점수 - 기대 점수);대부분의 게임에서 '실제 점수'는 0 또는 1로, 플레이어가 승리하거나 패배한다는 의미입니다. K는 상수입니다. 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이 승리했다고 가정합니다. rating1 = rating1 + k*(실제 - 예상) = 1200+30(1 - 0.76) = 1207.2;
등급2 = 등급2 + k*(실제 - 예상) = 1000+30(0 - 0.24) = 992.8;사례-2:
플레이어 2가 승리했다고 가정합니다. rating1 = rating1 + k*(실제 - 예상) = 1200+30(0 - 0.76) = 1177.2;
등급2 = 등급2 + k*(실제 - 예상) = 1000+30(1 - 0.24) = 1022.8;
문제를 해결하려면 아래 단계를 따르십시오.
- 위에 주어진 공식을 사용하여 플레이어 A와 B의 승리 확률을 계산합니다.
- 플레이어 A가 이기거나 플레이어 B가 이기면 등급은 다음 공식을 사용하여 그에 따라 업데이트됩니다.
- rating1 = rating1 + K*(실제점수 - 기대점수)
- rating2 = rating2 + K*(실제점수 - 기대점수)
- 실제 점수가 0 또는 1인 경우
- 업데이트된 평점을 인쇄하세요.
다음은 위의 접근 방식을 구현한 것입니다.
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);
산출
Updated Ratings:- Ra = 1207.21 Rb = 992.792
시간 복잡도: 알고리즘의 시간 복잡도는 대부분 컴퓨터 아키텍처에 따라 복잡도가 달라지는 pow 함수의 복잡도에 따라 달라집니다. x86에서는 이것은 일정한 시간 작업입니다:-O(1)
보조 공간: 오(1)