ELO等级分制度

Twcat_tree

发布于 2022-11-22 09:15:20

1.4K0

发布于 2022-11-22 09:15:20

文章被收录于专栏：二猫の家

前言

近段重温了经典电影《社交网络》，在电影中，Facebook创始人马克·扎克伯格在和女友分手后，受到好友爱德华多对核心算法的指引写下了哈佛女生“选美”网站Facemash，并一气之下黑了学校教务系统，将所有女生的照片放在Facemash上供人评比，网站大获成功，在上线两小时（周末凌晨两点到四点）内点击量达到了2万2千次，挤爆了哈佛的网络。Facemash也被喻为Facebook的原型，而这个网站中所用到的算法就是 ELO等级分制度

ELO等级分制度

ELO等级分制度是美国物理学家 Arpad Elo 创建的一个衡量各类对弈活动选手水平的评分方法，是当今对弈水平评估的公认的权威方法。被广泛应用于国际象棋、围棋、足球等运动，以及很多网游与电子竞技产业。

游戏界比较著名的应用有： FIFA online,、炉石传说、星际争霸天梯排行、魔兽世界竞技场、Dota天梯系统、LOL匹配等游戏的竞技比赛系统中，都是采用ELO等级分

ELO是一套较为完善的评分规则和机制，比较适合对竞技类游戏的选手的技术等级进行评估，用以计量个体在对决类比赛中相对技能的算法系统，对于游戏而言，需要让每场游戏尽可能的接近公平，创造双方势均力敌的竞赛环境。

下面就来对算法进行解读，Arpad Elo认为：

假设每个玩家每盘游戏中的表现是一个正态分布的随机变量，ELO系统用随机变量的平均值来代表选手的真正水平。（后来普遍认为 Logistic逻辑斯蒂分布更为合理）。 ELO系统用胜平负来评价选手在某一场游戏中的表现，赢就代表这场发挥比对手好，反之就是不好，因此会用赢加分，输扣分，平不得分来进行评分。

ELO计算方法：

Ra：A玩家当前的积分

Rb：B玩家当前的积分

Sa：实际胜负值，胜=1，平=0.5，负=0

Ea：预期A选手的胜负值，Ea=1/(1+101)

Eb：预期B选手的胜负值，Eb=1/(1+102)

因为E值也为预估，则Ea+ Eb=1

如果选手的表现比期望要好，那么此选手的排名应该上升。相反，若表现不如期望，则排名会下降。

Sa为选手A本局的得分（1或0），K为常数，数值越大比分变动越快，在大师级象棋赛中通常取16。用这个公式来计算出选手A本局比赛后的等级分排名。

例如，棋手A等级分为1613，与等级分为1573的棋手B战平。若K取32，则A的胜率期望值为，约为0.5573，因而A的新等级分为1613 + 32 · (0.5 − 0.5573) = 1611.166

代码实现：代码分析：

Facemash中ELO等级分用来对进行女生的分数进行评比，从而确定哪些是最优质女生。

首先，每个女生都有一个基础分，这个基础分在一开始都是一样的1400分，可称作“旧等级分”，在供人评比之后，将会通过公式计算出“新等级分”。

新等级分=旧等级分+K值(胜负值-期望胜率) 
      K值是一个定值，不过电影里没说明K值为多少，于是自己假定一个10 
      胜负值很简单，对于胜者胜负值为1，对于负者胜负值为0（这里没有平手，所以忽略平手时的0.5） 
      期望胜率待会儿再说，先告诉大家，当比较的2个女生旧等级分相同时，期望胜率对双方都为0.5

现在假定某人在A，B两位女生中选择了A，那么A的新等级分为1400+10(1-0.5)=1405，B的新等级分为1400+10(0-0.5)=1395

在经过一阵评选之后，就会产生2位女生等级分不同的情况，这时候就需要用第二个公式重新计算期望胜率。

现在假定第2个人在A，B两位女生中选择了A，那么对A来说新的期望胜率为1/(1+10(1395-1405/400))≈51.4%，对B来说新的期望胜率为1/(1+10(1405-1395/400))≈48.5%，A的新等级分为1405+10(1-0.514)=1410.14，B的新等级分为1395+10(0-0.485)=1389.86

源码：

#include <bits/stdc++.h>
using namespace std;
 
#define win	    1;
#define loss 	0;
#define tie  	0.5;
 
class OBJ{ 
    public:
    	double Score; 
    	string Name;
		OBJ(string name){// 这是构造函数
		    this->Score = 1400 ;
		    this->Name = name;
		}
};
 
double getmean(OBJ obj1,OBJ obj2){//计算期望 
	return 1 / (1+pow(10,(obj1.Score - obj2.Score)/400));
}
 
void computeScore(OBJ &obj1,OBJ &obj2,double result){
	double mean1 =  getmean(obj1,obj2);
	double mean2 =  getmean(obj2,obj1);
	obj1.Score = obj1.Score + 10*(result - mean1);
	obj2.Score = obj2.Score + 10*(abs(result-1) - mean2);
} 
 
int main(){
	OBJ obj1("xiaoA");
	OBJ obj2("xiaoB");
	double result;
	while(1){
		cout << "输入比赛结果（1为A赢，0.5为平局，0为B赢，-1结束）：  ";
		cin >> result;
		if(result == -1)break; 
		computeScore(obj1,obj2,result) ;
		cout << "比赛结束后A的分数为：" << obj1.Score<<endl; 
		cout << "比赛结束后B的分数为：" << obj2.Score<<endl;
	}
	cout << "game over，thanks"; 
    return 0;
}

运算结果：