ELO rating system(埃洛等級分系統(tǒng))

今天了解了一下游戲中的PVP模塊的實現(xiàn)，大多數(shù)的游戲都使用到了ELO算法，剛開始的時候并不清楚這個算法是做什么的，對此開始大量查找有關(guān)于ELO算法的資源，功夫不負有心人，總算找到一些有用的資源了。
先來簡單介紹一下埃洛等級分系統(tǒng)，根據(jù)百度百科是這樣描述的：

該系統(tǒng)基于統(tǒng)計學的一個評估棋手水平的方法。美國國際象棋協(xié)會在1960年首先使用這種計分方法。由于它比先前的方法更公平客觀，這種方法很快流行開來。1970年國際棋聯(lián)正式開始使用這個系統(tǒng)。
系統(tǒng)模型原先采用正態(tài)分布。但是實踐顯明棋手的表現(xiàn)并非呈正態(tài)分布，所以改進后的埃洛排名系統(tǒng)通常使用的是邏輯斯諦分布。

其實在此之前有看過一部電影<社交網(wǎng)絡(luò)>中也有提及到這個公式，電影中里的Mark Zackburg被女朋友甩后，在舍友的啟發(fā)下，充分發(fā)揮了技術(shù)宅男自娛自樂的惡搞天分，做出了Facemash網(wǎng)站，對學校女生的相貌進行排名打分，結(jié)果網(wǎng)站訪問流量過大，直接把學校網(wǎng)絡(luò)搞癱瘓了。Facemask大受歡迎的關(guān)鍵就在于Zackburg基友Eduardo寫在窗戶上的排名公式，看電影之時就對這個排名公式非常感興趣，上網(wǎng)了解下，才發(fā)現(xiàn)這條公式就是大名鼎鼎的ELO等級分制度。ELO的應(yīng)用非常廣泛，大部分棋類比賽，現(xiàn)在流行的MODB游戲，像11平臺的DOTA天梯系統(tǒng)，都是采用ELO等級分。

facemash.png

c4c7311488fe318a.jpg

ELO Rating System 是當今對弈水平評估的公認權(quán)威規(guī)則，已被廣泛應(yīng)于國際象棋、圍棋、足球和籃球等體育運動以及游戲中。例如星際爭霸天梯排行，魔獸世界競技場，Dota天梯系統(tǒng)，LOL匹配等游戲的競技比賽系統(tǒng)中。ELO是一套較為完善的評分規(guī)則和機制，比較適合對競技類游戲的選手的技術(shù)等級進行評估，用以計量個體在對決類比賽中相對技能的算法系統(tǒng)，對于游戲而言，需要讓每場游戲盡可能的接近公平，創(chuàng)造雙方勢均力敵的競賽環(huán)境。它最初由美國物理學教授 Arpad Elo 創(chuàng)立，故命名為埃羅排名。

一、ELO Rating System模型思路
1.假設(shè)每個玩家每盤游戲中的表現(xiàn)是一個正態(tài)分布的隨機變量，盡管選手在不同的游戲中發(fā)揮可能差異很大，但每位選手在一段時間內(nèi)表現(xiàn)的平均值變化很小，ELO系統(tǒng)用隨機變量的平均值來代表選手的真正水平。
2.ELO系統(tǒng)用勝平負來評價選手在某一場游戲中的表現(xiàn)，贏就代表這場發(fā)揮比對手好，反之就是不好，因此會用贏加分，輸扣分，平不得分來進行評分。

二、積分計算公式
Ra：A玩家當前的Rating
Rb：B玩家當前的Rating
Sa：實際勝負值，勝=1，平=0.5，負=0
Ea：預(yù)期A選手的勝負值，Ea=1/(1+10^[(Rb-Ra)/400])
Eb：預(yù)期B選手的勝負值，Eb=1/(1+10^[(Ra-Rb)/400])
因為E值也為預(yù)估，則Ea+ Eb=1

R’a=Ra+K（Sa-Ea）
R’a：A玩家進行了一場比賽之后的Rating

K：K值是一個極限值，代表理論上最多可以贏一個玩家的得分和失分，K/2就是相同rating的玩家其中一方勝利后所得的分數(shù)。
國際象棋大師賽中，K=16；在大部分的游戲規(guī)則中，K=32。通常水平越高的比賽中其K值越小，這樣做是為了避免少數(shù)的幾場比賽就能改變高端頂尖玩家的排名。

三、實例說明
若當前A玩家rating為1500，B玩家rating為1600
預(yù)估A玩家的勝負值Ea = 1/(1+10^[（1600-1500）/400]）≈0.36
預(yù)估B玩家的勝負值Eb = 1-Ea = 1-0.36 = 0.64

假設(shè)A玩家獲勝，實際勝負值為Sa = 1
A玩家最終得分為 R'a = 1500 + 32*(1-0.36) = 1500+20.5 = 1520，A玩家贏20分，B玩家輸20分。

假設(shè)B玩家獲勝，實際勝負值為Sa = 1
B隊最終得分為 R'b = 1600 + 32*(1-0.64) = 1600 + 11.52 = 1612，B玩家贏12分，A玩家輸12分。
PS：^符號代表次方運算。

四、天梯系統(tǒng)目的
1.保護新手不被有經(jīng)驗的玩家虐，讓高手局中沒有新手。
2.創(chuàng)造競技和公平的游戲?qū)郑雇婕业挠螒驑啡ぷ畲蠡?br>3.無需等待太久就能找到對手進入游戲。

五、具體實例
11對戰(zhàn)平臺的天梯實例。
下面的公式很好的說明了天梯積分的計算方法，而Si的計算則是取的ELO算法，雖然11的天梯還是存在Bug，但是不得不承認確實是很棒的設(shè)計。

從天梯積分曲線圖可以看出，雖然曲線有波動，但是基本上能夠代表這一段時間，玩家的技術(shù)水平區(qū)間，進而匹配戰(zhàn)力接近的玩家，讓玩家享受競技的樂趣，而不是一味的虐菜，最后獨孤求敗進而流失。