用分享的方式成长,用有趣的眼光看世界。
欢迎来到22 26 25的博客!
热爱编码、算法、知识总结,不定期更新有趣、有料、有营养内容。 让我们共同学习,共同进步。
好文推荐: 从B站(哔哩哔哩)泄露的源码里发现了B站视频推荐的秘密
值得学习17个C/C++ 超经典开源项目,面试加分
400+条实用C/C++框架、库、工具整理 ,你能想到的都在这里了
目录
前言
ELO等级分制度
代码实现
前言
近段重温了经典电影《社交网络》,在电影中 ,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+10^[(Rb-Ra)/400])
Eb:预期B选手的胜负值,Eb=1/(1+10^[(Ra-Rb)/400])
因为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;}
运算结果:
如果有什么要补充的,欢迎下方👇评论区留言。
1份赞许= 100分的认可,如果感觉还不错,点个赞👍 支持一下吧 ~
不定期分享 有趣、有料、有营养内容,欢迎 订阅关注 👌 我的博客 ,期待在这里与你相遇 ~
上一篇:从B站 (哔哩哔哩) 泄露的源码里发现了B站视频推荐的秘密
下一篇:值得学习17个C/C++ 超经典开源项目,面试必备
如果觉得《Facebook前身 哈佛大学“选美“网站核心算法 -- ELO等级分制度(附源码)》对你有帮助,请点赞、收藏,并留下你的观点哦!