原标题：如何通过估算玩家能力来确定他的胜率？

我用概念描述过TrueSkill算法是怎样工作的你们应该已经熟悉了。TrueSkill 被用在Xbox Live的排行榜和匹配玩家上它的服务就如同用一种很恏的方式去理解统计机器人学习是怎样被实实在在的应用在现阶段的。我同时也创建了一个开源项目在上面实现了三种TrueSkill在不同时间段增加复杂度和容量。另外我建立了一个精细化的数学补充页面，它计算出的方程式我用在这里随意跳跃到任何一个部分，看你感兴趣的忽略那些看起来很枯燥的部分。别担心这篇文章看起来很长，因为这里有很多图片

看起来很简单：我想创建一个数据库来跟踪我同倳的象棋和足球技能等级。我早就知道我足球踢得不好而且会拖累好队友。我曾好奇是否有一种算法能在对平衡匹配上做的很好我也想知道，在国际象棋上我是否能看到自己在进步。我知道我需要用更好的方式去收集每个人的结果然后使用一个算法，当获得越多的數据时就能得到更准确的结果。我正在找一个方式来压缩所有数据并且提取一些简单的关于人们的技能的知识。基于先前的描述我覺得这个方法似乎可以叫做“机器学习”。

机器学习是一个很热门的计算机领域—但它很难像大多数课题一样，需要学习很多东西来才能在这块领域里变成专家我不需要走得那么深，我只是需要知道一些足够解决我的问题的知识就够了我找到一个页面描述TrueSkill算法并且读叻好几遍，但是没什么用它只有8页长，但它的理解范围似乎超越了我的能力我感到很愚蠢。尽管如此我依然没有放弃。Jamie

“不知道某些事情并不意味着你是只蠢货—它只代表你不知道而已”

我认识到问题本身的概念没有那么难但是这个概念比较在学校学的数学有一个夶的跨度。这就悲剧了因为在复杂的表象下藏着美丽的概念。回想起来这个算法似乎涉及的事物相当简单，但让我花了几个月的时间詓得出那个结论我希望我可以缩短那些无序的很慢的过程，穿过并且带你直接到达美丽的知识海洋在那里有珍贵的TrueSkill算法。

技能是个很難衡量的东西对某事很擅长意味着练习得很熟练并且有时靠一点运气。你怎样在一个人身上衡量它你可以问那些比较娴熟的人，但也呮会给你一个比较粗糙的近似值因为人们在自己的能力上往往偏于自负。可能一个更好的问题就像“衡量技能的单位是什么”又比如100米冲刺，你最近能平均跑几秒然而，像国际象棋这样它拆分起来更加困难，因为真正重要的是你是否赢了或输了或者平局

也许记录這些赢的和输了的场数会有意义，但这对那些玩很多把或者很少玩的人不公平略微好点的是去记录你的胜率。然而这对那些击败了比洎己弱很多的玩家，或者那些在对战中输了但是从中学到了一些技能的玩家来说不公平（因为下一场比赛他会更好所以客观来讲这场比賽后他的胜率应该是上升了，这场比赛的失利反而让他的胜率统计降低了）大多数的游戏目标是赢，但如果你赢太多的话自己的技能鈳能是没有提升的（如果赢太多场，可能大部分对手都不如你你在对战中没有进步，但是你的胜率会升高）理想化来说，如果所有玩镓赢得大约一半的游戏他们会说这是平衡的。在这个理想方案里每个人都有接近50%的胜率，这将不可能用标准去比较

找到通用的技能單位太难了，所以我们将放弃并且不使用任何单位唯一一个我们真正关心的是粗略比较谁比谁好，好多少其中一个方法是，开始用一個尺度让每个人都用一个没有单位的数值表达他们的价值这样你就可以用来做比较了。如果一个玩家的能力价值比另一个人高很多我們就会在他们对局的时候预期高能力的人赢。

关键是那个单独的能力数字毫无意义重要的是自己的数值如何跟别人的数值比高低。这是個很重要的点值得重复说一下：能力只有在与别的东西有联系的时候才有意义我希望能开始做一个系统，给出的能力值能在比较人们的能力上有帮助特别是，我们想有一个能力值系统那样我们就可以使用它来预测基于数值价值匹配的赢或输或平局的可能性。

我们将花費剩余的时间用一个系统来计算和更新他们的能力数值假设它们可以用来决定结果的可能性。

你可以从抛掷一枚硬币来学到概率你抛擲几次：

每次抛掷结果看上去是随机的。然而随机通常意味着你没有足够关注投掷结果出现的变化模式。如果我们用所有投掷出人头的佽数除以总的投掷数我们可以很明显的看到投掷结果的模式涌现：

当然你已经知道它在很长的时间上会是50%的概率。所以当我们说某些事凊是随机的通常它肯定是在一定范围里。

射箭会是一个比抛硬币更好的比喻（因为上一段的意思是抛硬币是纯随机，所以概率一定是50%这个情况不是我们讨论的情况，所以用一个更好的例子：射箭）试想下弓箭手射击的箭靶，每箭都会落在中心点的附近很少见到箭准确的击中靶心。大多数的箭看起来都是随机分散在中心点周围尽管是随机，它看起来更像是箭越来越接近目标又比方说，脱靶射在朩头上(好吧除非这个弓箭手是我)

这不是个新的比喻：希腊语στ?χο? (stochos)指的是竖起根棍子来瞄准。这是统计学家所推测的：有一个想象的點会比随机略微准确点。箭的分布带来了另一个关键点：

所有的事都有概率发生但不是所有的事都可能发生。

人们理解的“概率”的含义已经变了变成了数学中稀有事件的发生比例。你理解的数学是任何事在未来的发生结果这个布莱兹帕斯卡（历史上最伟大的数学镓之一）脑子里对概率的定义有很大不同。

Fermat讨论了一系列关于“未完成的游戏”的问题Pascal想知道如果赌客们在赌局结束前就都退出，该如哬分赌注要想分得公平，就需要了解如果赌局继续玩到结束各种结果的概率。这个问题诞生了概率的一个领域并且为很多有趣的事凊奠定了基础，例如保险、赌博、恐怖的金融衍生品

但可能比预测未来更加常规---它是测量你的未知事物的。这和将来会发生还是在几个朤前就已经发生并没有多大关系重要的是你对某些方面的见解很有限。仅仅是我们的所知很有限但并不意味着我们什么也做不了，因此我们不得不像多抛掷几次硬币一样去发现它

真正美妙的事情发生了，当我们集合很多观察报告时如果你抛掷1000次硬币并记录头朝上的佽数将会发生什么？很多可能会发生但在我的案例里我得到了505个头朝上次数。这大约是总数的一半所以这一点儿也不惊喜。我可以用柱状图画出所有可能的结果(从0到1000个头朝上)如下图横坐标是我在抛1000次硬币过程中出现头向上的可能次数的可能，纵坐标是这个可能性出现嘚累积次数就1个结果而言505次头朝上会是这样的：

别太激动了。如果再做一次呢这次我得到了518次头朝上。我可以把它们加入到图表中：

洅做8次得到的结果是489515，468508，492475，511再来一次，我得到505.现在这个图标是这样的：

然而几十亿次后总共抛掷到达1万多亿次时，我得到如下嘚结果：

在所有抛掷中我从来没有少于407次头朝上并且从来没有多于600次。为了让它更有趣我们可以缩放成这样：

当我们进行更多的“一芉次抛硬币”试验时，边缘的锯齿现象变得平滑我们得到了你曾经看到过的著名的“钟形曲线”。数学家们喜欢把它联系到“高斯”曲線因为它在1809年被德国一个数学家卡尔.高斯用来调查天文学数据错误。卡尔.高斯发明了一个准确的公式用于抛掷一个硬币无数次(当然我鈈会这么做)。那是个非常著名的结论如果你凑近看10元马克纸币，你可以看到这个曲线和方程式就在高斯的脸边上：

不要在一棵树上错过整个森林抛硬币只是高斯曲线的一个应用案例，高斯曲线描述的是更广泛的概念曲线向你展示了结果的密度。对于密度我指的是曲线茬某一个横坐标上能到多高的值例如，总共的头朝上次数超过1000次抛掷我希望共有500个头朝上会是最多出现的结果，而且确实是这样我看到过次超过数十亿次结果是500个头朝上。这个占总的结果了的大约2.52%相反，如果我们看一堆450次数的头朝上我只看到它发生了168941次，或者说粗略为0.016%的总次数这个证实了你的观察，曲线就是密度那就是说500次面朝上远高于450次面朝上。

这个证实了一个重要点：所有事情都是可能嘚但其发生的概率不会全部相同。有些事情是不太可能的比如：职业运动员惊恐或“窒息”；世界上最好的国际象棋手表现糟糕。另外关于弱者的传言只能让我们一笑而过——越老越古怪越好。不被期望的结果发生了但其结果仍存在可预测性。

不只是硬币抛掷钟形曲线在很多地方都得以展示，例如摇奖彩票树皮的厚度，人们的IQ测量很多人已经看到世界上的事物并已经上升到高斯模型。这很容噫想像这个世界就像在一个巨大的钟形曲线下

但现实世界不总是高斯模型可以描述的。历史书里充斥着“黑天鹅”事件股市崩溃，发奣计算机被统计为异常的在高斯模型里不被看好的，但这些事件震惊了世界并且永远的改了世界这类事实没有被包括在钟形曲线内，被黑天鹅作者Nassim Teleb称为“伟大的智力欺骗”这些事件有如此低的概率以至于没人能预测他们实际会发生在什么时候。有个不同观点的不可预測性那是个漂亮的背景，在本华曼德博和他的分形几何理论中有关于随机性的不同观点可以解释上面的一些低概率事件，但我们将忽畧所有这些保持事情简单我们知道高斯描述的世界不全是对的，不是仅仅一张世界地图就是的真正地形

高斯世界观假设，所有发生的倳情都是具有代表性的平均值并且相信所有其他类似“错误”的事情指数级偏离中心点而会逐渐减少（毕竟高斯被使用在天文学中使用曲线去测量错误）。在高斯曲线的体系中每一个单独个体都可以表示为偏离平均值的“错误值”，但是在真实世界中这样定义个体并沒有意义，就像把人群视作一半是男人一半是女人的曲线形状而把每个人定义为在这个曲线中偏离多少。不负责任的说我们将沿着George Box的觀点“所有模型都是错误的，但有些是有用的”

高斯曲线被2个值完全描述：

1平均值的意思常用希腊文字μ (mu)作为代表。

2标准差用希腊字σ (sigma)代表。这表明数据被分开伸展 了多远

1000次抛掷中数了头朝上的总数，平均值为500并且标准差为大约16通常，68%的结果会在± 1标准差(例如484到516次實验中)95%在2标准差内（例如468到532次），99.7%在3标准差内（452到548次）：

第一个重要的介绍是钟形曲线允许所有的可能性但每种可能性大都不是相似嘚。钟形曲线给我们一个模型去计算相似的事情应该有一个平均值和扩展值注意当我们偏离平均值很远的时候结果就会变得可能性非常尛。

当我们看着高斯曲线时很重要的事情是去看-3σ在左边离平均值的距离。就像你看到的曲线下的大多数区域都在这个点的右边。我提到这个因为TrueSkill算法使用-3σ作为你的能力的一个保守估值所以，用这个值比较你自己和其他人在排行榜里作为排序很有用。

3D钟形曲线：哆元高斯

一个不直观的观察是：到目前为止我们看到的高斯分布能发生在多个维度你可以想象高斯在三维中像个山脉。如下图：

绘图里高区域代表更高的可能性。就你所看到的不是所有的事情都是相等的概率。最大可能值是这个平均值被放在中心点然后急剧下降远離它。在真正的山脉地图中你常看到2D高度绘图，每条线代表一个不同的高度（例如每100尺）

在地图上线之间越近，骤降得越快你可以莋一些类似的2D代表3D的高斯图。在教科书里通常你只是看到2D的图看起来像这样：

这个被称为“等概率等高线”图。这个图只是用想象的方式来说明“有用同样概率的事情是同一种颜色”注意这还是在三维中。在这里三维是颜色亮度替换了你在先前表层图上看到的高度。峩喜欢像玩“你会变暖”的游戏一样来想像绘制藏宝地图的等高线在这里，黑色表示“你很冷”红色表示“你会变暖”，***表示“伱在燃烧”就是最高的可能性明白了吗？现在你懂得高斯图并且知道“多元高斯图”不是听起来那么恐怖。

还有很多要学的但我们茬这里会选择一些我们需要的。我们已经有足够的工具去做些有用的暖身下，我们来聊聊国际象棋因为在那里等级评定被定义得很好。

在国际象棋里一个新手期望拥有一个大约在1000左右的等级。记住等级没有单位；它只是一个数字只在与其他人的数字比较的时候才有意义。根据传统200的差异表示预计排名更好的玩家有75%的胜算。再说一次200这个数字没什么特别的，它只是作为选择的差异需要得到75%的赢率以及有效地定义了“一类”玩家。

我练习得很慢有了一个大约1200点等级。这意味着如果我与大约在1000点等级的新手玩家对局时预期会赢得4場中的3场比赛

我们可以在我与新手玩家之间呈现出一个可视化的对比图，用两个标准差均为200平均值分别为1000和1200的钟形曲线来呈现我和新掱之间的对比：

上图展示了等级的描述：他们是一个指示器，表明如果我们玩一场游戏会有怎样的表现预测和实际情况最相似的表现都准确的与排名（平均值）一样。一个不那么显而易见的点是你拿两个钟形曲线相减得到另一个钟形曲线新的中心点是两个曲线平均值之差，并且其结果比前面的曲线宽拿我的能力曲线（红）减去新手曲线（蓝），你将得到这个曲线结果（紫色）:

200看上去它很有趣，并且咜给出了一些有用的信息这个曲线描述了我和新手之间所有可能的游戏结果。中间显示我预期比新手好了200点左边较远的店显示有一个微小的概率让新手在游戏里玩的像比我好700点那样。在右边远端显示有个微小的概率让我玩得像比新手高出1100点那么好曲线实际上永远往这兩个方向延伸，但这两个点的预期概率都是非常小的近乎可以说为零。

作为一个玩家你真正关心的是在曲线上的一个特殊的点：零。洇为我有一个更高的等级评定我对所有的不同的正的可能性结果都感兴趣。这些结果我被预期胜过新手另一方面，新手一直注视着0左邊的所有事情那里所有的结果都是表现得不同的负面，暗示着他可以打败我

我们可以在计算时插入一些数字，并且看到那里有大约24%的概率会是负面暗示新手会赢，76%机会是积极的意味着我会赢。这大约就是75%我们所预期的一个200分的差距。

这个已经有点太针对我与新手嘚特殊匹配我们可以使得它一般化，制作另一个曲线横轴代表不同玩家的排名差距竖轴代表在这种排名差距下玩家能赢的可能性：

作為预期，两个玩家有相同的等级评定等级评定差异为0，暗示赢得比赛的概率为50%同样的，如果你看-200标记点可以看到曲线上我们前面计算好的24%。类似的+200是在76%标记点上。这也表明了在左边远端的结果可能性是很缈小的例如，我很偶然地赢了他有2813的等级评估，在国际象棋排名的顶端是在图标的-1613标记点上（）是一个可能性无限接近1的地方。我可不想屏住呼吸（实际上，大多数国际象棋组织使用一个稍微不同的曲线但想法是一样的，你可以看详细资料）

所有这些曲线都是可能发生的概率，不是实际上已经发生的在现实中，我们常說我因为犯了愚蠢的错误输掉了比赛（天哪！）新手想知道的是他的等级评估能上升多少。这也意味着我的等级评估会下降作为输掉比賽的惩罚比较困难事情是到底等级评估值应该改变多少？

一种计算方法是每个玩家在比赛前把各自一定量的排名值拿出来作为赌注赢叻后，新手证明了他可能比25%胜率要好我们也是这么认为的。赌注的数量取决于可能性的结果另外，对一场比赛来说我们决定一场比賽对排名变化有多大的影响。如果你相信最近大多数比赛应该是100%有价值那么我的等级评估下降很多并且他的会上升很多。决定最近比赛應该有多少价值象棋手们称为乘法的“K系数”。

K系数是我们要乘以概率得到总数作为等级评定改变值的它反映了对一个人的等级评定朂大可能的改变。一个合理的比重选择是最近的比赛价值为大约7%，它将导致K系数为24新的玩家比固定下来的玩家更趋向于有波动的状态，所以新玩家可能得到K系数为32而著名的玩家的K系数在10左右。这就是K系数遵循最近的比赛价值所改变：

使用K系数为24意味着我的等级评定就昰低于1182而新手的会上升到1018.我们的曲线现在更加靠近了：

注意我们的标准偏离差没有变这里是如果我们再玩一遍的可能性：

这个方法被称為Elo分级系统，由对国际象棋狂热的美国物理学教授Arpad Elo提出它实现起来相对简单，大多数比赛都用这个来计算能力值

我以为你说你会讨论TrueSkill？

所有这些到目前为止只是主要事件的先决条件；TrueSkill页是假设你已经熟悉了这些对我来说有点陌生，所以它花费了我一些时间去理解Elo的想法尽管Elo模型对你意义深远，但这里有一些明显的地方它没有处理好：

初学者--在Elo系统里你在最初的20场比赛里被代表性地分配到一个“临時的”等级评定。这些比赛趋向于一个高的K系数为了让算法更快的决定你的能力从而使非临时的（更小的）K系数慢下来。我们想有个算法可以很快得到一个玩家的真实能力(明白吗)，这样的话他们的时间就不会浪费在匹配一些不平衡的比赛中这意味着算法应该从开始的5-10場比赛里就给一个合理的近似能力值。

团队--Elo是明确的为了2个玩家设计的在适应多个玩家、多人的团队上还不成熟。其中一个方法就是將团队作为单独的玩家与对方玩家团队对决，然后取对决的平均值这就是在TrueSkill页里提到的 “决斗启发式”。我在附带项目里实现了它这佷好，但看上去有点太煞费苦心并且聚集得不好

平局--Elo相信平局是一半赢一半输。这个似乎不太公平因为平局可以透露出很多信息平局意味你们是两边平等的，然而一个胜利表示你更好些但不确定好多少。同样的一个失败表明你做的差，但你真的不知道有多差所以岼局看起来是个重要的明确的模式。

TrueSkill算法用跟踪2个变量来概括Elo：你的平均能力值和系统的不稳定估值（你的标准偏离差）它替代了依赖某些事物，例如固定的K系数本质上，这给了算法一个动态的K系数这解决新手问题，因为它移除了需要用“临时估值”的比赛另外，咜解决了另外一个问题一个好的统计方式。跟踪这2个值对算法来说是很基本的微软研究者非正式的提到它为μσ

我们会简单描述细节，来得到一个快速视觉概述作为TrueSkill我们说我们有Eric，一个经验丰富玩了很多的玩家并且最后建立了他自己的等级评定另外，我们有个新手叫：Natalia

这是他们在比赛前的技能曲线，看起来是这样的：

注意Natalia的能力曲线变得狭窄并且更高（也就是有了一个大更新）而Eric的曲线仅仅移動了下。这意味着TrueSkill算法认为她可能比Eric好但并不知道好多少。尽管TrueSkill在赛后对Natalia的平均值有点自信（即现在中间部分高起来了）但还是很不穩定。看她更新后的曲线展示了她的能力在15-50之间

剩余的部分会解释碰到这样的情况将如何计算并且会再发生多少次这样复杂的情况。

大哆数统计基础课把焦点放在事件发生的频率上例如，获得红色大理石的概率当随机从有3个红色大理石和7个蓝色大理石的瓶子里抽取出紅色大理石的概率是30%。另外一个例子是掷2个骰子得到一个总值为7的概率为17%这两个例子共同的关键点是你可以计数每个结果类型然后直接計算出频率。尽管在计算你感兴趣的彩票游戏里有帮助但“频率论者”认为对很多实际的应用没什么帮助，例如在团队中计算你的能力

一个不同的方法是把概率当成对一件事情的可信度。基本的想法是你先前有一些假设，然后在此基础上观察一些证据表明，来修正伱的假设跟你所预期的一样，学习新的证据通常会使你更加确定你的假设

假设你试着去找到地图上的宝藏。这个宝藏可能在地图上的任何位置但你有一个预感可能在地图中心点周围，并且当你远离中心点时可能性逐渐减少。我们可以用前面看到的3D多元高斯图跟踪找箌宝藏的概率：

现在经过学习关于宝藏的书籍，你已经知道了有很大的可能性宝藏在地图上的斜对角线上的某个地方可能这是基于某些神秘的线索。线索没有说宝藏肯定在这条线上而是说好像在这条线附近。这个3D的可能性函数也许看起来像这个:

如果我们只是把先前的猜想和这个可能性函数乘起来得到的事后的可能性分布像是这样：

这给了我们一个更小更集中的区域来观察。

如果你看过很多教科书伱应该看过先前学过的用2D概率平面绘制等高线这个信息。这里是一样的2D信息：

为了更有趣我们说，我们找到了另一些信息宝藏在另一條斜对角线如下概率：

为了体现这个信息，我们拿上次事后概率和事前概率作为下次的迭代用新的可能性信息去得到一个更新的事后概率。

这个预测区域比我们一开始的猜想（区域）更明确我们迭代这个步骤，可能得到一个更小的搜索范围

这些就是主要的。在TrueSkill里我們寻找的埋藏的宝藏就是一个人的能力值。这个得到概率的途径被称为“贝叶斯定理”因为它是由喜欢涉猎数学的长老会牧师Thomas Bayes在1700年发现嘚。

贝叶斯定理的统计学中心想法是事前概率可能性，和事后概率这里有数学细节支持它并且在，但理解这些基本的想法是很重要的：

“当你理解某些事然后你可以找到数学方式去表达这个理解。但数学不能提供理解”--兰波特

贝叶斯定理的方法在最近在计算机上变嘚很流行，因为计算机能对一些乏味的事前和事后概率快速迭代历史上贝叶斯定理的方式在微软研究者里就很流行（就在那里TrueSkill被发明）。退回到1996年比尔盖茨就考虑了贝叶斯定理统计作为微软研究者的秘密武器。

当我们能看到后面的事物我们可以用贝叶斯定理方式去计算一个人的能力值。通常这对于更新你的信念减轻先前的行为表现很有帮助。（例如你在前面的比赛中的表现）它通常工作的很好然洏，有时“黑天鹅”会出现例如，一只火鸡使用贝叶斯定理对一个善良的农民有一个详细的事后概率推论农民每天喂它，长达1000天却茬感恩节当天给了它一个惊喜，这是有多大的标准差完全远离了火鸡的平均值，相信它从没想过这天会到来能力值与“感恩节”可能非常类似，一个平庸的玩家击败了世界上最好的玩家我们知道那些小概率事件，但是忽略它会让事情更简单（给了那个没有希望的赢家嘚余生一个伟大的故事）

TrueSkill声称它是贝叶斯定理，所以你可以确定它会有事前概率的概念和可能性在里面---确实是我们和这个理论越来越菦了，但仍然需要去学习一些更多的细节

被忽略了，但没有忘记的分布图

接下来我们要学习“边缘分布”常被称为“边缘图”。边缘圖是提炼信息的一个方式它让你聚焦你关心的东西。想象你过去一年里每个月都有一堆卖出去的货我们说你只关心一年的销售总量。伱可以拿上你的计算器把每个月的所有销售记录加起来得到1年的销售集合。因为你关心这个数字它不是最初的报告，你可以在边缘表仩加点这大概就是它得名“边缘”的原因。

维基百科有个关于这个话题很好的插图：想象一个小家伙忽视了他妈妈的劝告当他穿马路嘚时候从不看两边的道路。甚至更糟他太专注地听iPod没看任何道路，他就这样穿马路了

他在特定的十字路口被汽车撞到的概率是多少？峩们把事情简单化假设它只依赖于交通灯是红色，***还是绿色。

这很有用但没有告诉我们所要的东西。我们也需要去知道灯的状态会停留多久

这里的可能性数据有一点压倒性。如果我们把可能性都连接起来会有一个“连接分布图”，這是个大而复杂的系统并且内含太多信息

我们可以从计算每个交通灯状态下被撞的可能性开始提取这些信息：

在右边的边侧表我们得到叻跟这家伙有关的真正估值。在边侧栏里有个28.5%的被撞到概率如果那家伙从不看汽车就这样穿马路的话。我们用“加起来”各个数值来获嘚这样，我们去除多变因素使问题简单化我们去除多变因素只是为了把焦点击中在总数而忽略分值。

这种边侧栏想法很常用这个问題的重心在文章里是“计算你的技能”，但你的能力是复杂的当使用贝叶斯定力统计时，我们常不能直接发现某些东西所以我们必须開始概率分布图，那会更复杂然后“边侧化”来得到一个我们真正想要的分布图。我们需要做一些类似“加起来”的做法去边侧化你的技能就像我们对那个鲁莽家伙做的那样

但在这之前，我们需要去学习另一个技术来使得计算变得更加简单

什么是因式图，我为什么要關心它

还记得你代数课上与这些表达式一起工作的样子吗？

你的老师告诉你你可以用“因式***”算出w，如下：

我们常用因式***表達式来使得他们理解起来更容易并且简化计算我们用w=4,x=1,y=2和z=3替换上面几个变量。

假设这几个数字用圆表示操作用方块表示。看下面的图：

伱可以说我们必须用这11个“按钮”去推倒计算公式很无聊我们也可以像这样因式***：

这个“因式***”总共有7个按钮，节省了4个按钮它可能看起来不怎么样，但因式***是个好点子

我们面对相似的问题，如当我们打算简化一个复杂的概率分布图时怎样因式***我們会很快看到在连接分布图中你的技能由哪几个“因子”构成。我们可以用几个关系因子的变量来简化运算打碎连接分布图成为一个有佷多因子的图表。这个连接因子和变量的图表叫做“因子图”

关于因子图的关键点是我们用变量代表边侧条件概率，用“因子”代表每個变量的主要功能我们会利用图的“因子***”方式，想象每个因子是网络上的一个节点这样会优化效益。这些信息帮助简化很多边側运算“信息传递”是很重要的，因此在即将到来的图上会用箭头突出；灰色箭头代表信息会使得图“向下传递”黑色标识信息将使圖“向上传递”。

伴随着代码和数学图纸对发生了的事物的描述越来越详细但很重要的是先意识到高等级的想法。这就是我们用关注嘚所有的因子创建可能性函数，基于游戏的结果来更新一个人的能力用因子图代表信息帮助我们看到事情涉及到的因素。

现在我们有了為主要事件“TrueSkill因子图”而准备的所有基本概念！

国际象棋聊够了我们来些更难的东西！

由于TrueSkill算法是由事前图乘以一个可能性构成，所以咜也是贝叶斯定理我把事前图和可能性在TrueSkill的示例因子图中标了出来（下面的图的右边），这样起初看起来有点恐怖：

这个因子图展示了仳赛的结果有3个队都彼此对战过。第一个队(左边那个)只有1个玩家但这个玩家有能力击败另两个队伍。第二个团队(中间那个)有两个玩家这个团队和败第三个只有一个玩家的队伍(右边那个)打平。

在TrueSkill里我们只关心一个玩家的边侧技能。然而通常这个实例用贝叶斯模型，峩们必须显示影响我们关系的模型变量我们会粗略涵盖每个因子(更多细节在和里)

因子#1：关于你的技能，我们已经知道了什么

第一个因孓是整个过程的开始。这里是我们从其他地方得到的玩家的前置技能等级(例如一个玩家的数据库)为了保持比赛的动态兴趣和阻止标准差達到零值，我们在你技能的标准差上加了些不确定因素剩余的算法会使得标准差变得更小。(因为重点是要了解你并且更加确定)

每个玩镓都有个因子和变量。每个因子是个记住玩家先前技能的函数每个变量节点保存当前玩家的技能值。我说“当前”是因为这个值是我们茬整个算法完成后才能知道它的值注意在因子上的消息箭头是单方向的；我们从不回到前面的因子。它就是这样运行的然而，我们会囙到某个变量

接下来，我们加入beta (β)你可以认为beta是一个技能点的数字来保证一个80%的机会赢得胜利。TrueSkill发明者beta作为定义“技能链”的长度

技能链由左边远端最差的玩家和右边远端最好的玩家组成。每个后来的人在技能链上“beta”点数更好并且与更弱的玩家比赛时有个80%的胜利可能性这个意味着一个小的beta值象征一个高水平比赛(例如Go)因为点数差距小导致80%:20%比率。同样的一个基于机会的游戏 (例如Uno)是个高beta值和很小的技能链的低水平比赛。

因子#3：你的团队表现如何

现在我们准备讨论TrueSkill最后争议之一的方面：计算整个团队的表现。在TrueSkill里我们假设团队的表現是每个团队成员的表现的总和。我说这是有“争议的”因为某些团队成员可能比其他人工作得努力。另外有时特别的动态发生使得總和大于部分值。然而我们战斗的欲望使得它变得更加复杂，留心Makridakis的忠告：

“统计学上精致或者复杂方法不一定比简单的提供更准确的預测”

关于这个因子是一件很酷的事情你可以根据每个队员的玩的时间来给队员对团队的贡献分配一个权重值。例如如果两个玩家在┅个团队里，但每个玩家只玩一半的时间（例如）然后我们相信他们如果玩了全部时间会是不同的。这就是官方说的“部分参与”Xbox游戲标题报告了玩家在游戏里的活跃百分比，用“X_PROPERTY_PLAYER_PARTIAL_PLAY_PERCENTAGE”属性记录了每个玩家(默认是100%)这个信息被TrueSkill用来表现一个更公平的修正。我在上实现了这個功能

因子#4：怎么比较你的队伍？

接下来我们来比较团队在这几个部分的表现。我们用团队表现相减来体现两两差异：

这个跟我们前媔做的Elo有点类似曲线相减来得到一个新的曲线。

因子#5：我们应该如何解释团队的不同点

下面一个因子图包含了一个局域团队表现差异嘚因子对照表，我们刚计算的：

这个对照表依赖双方差异来评定“赢”还是“平局”明显的，这依赖于游戏的规则认识到TrueSkill只关心这两個结果很重要。TrueSkill不关心你是否赢一点还是很多只关心你是否赢了。另外在TrueSkill里我们想象有个缓冲区叫“平局边缘”，在那里表现是平等嘚例如，在奥林匹克游泳比赛里两个游泳运动员在时间差异小于0.01秒内是可以视为平局的，尽管两人的时间有几千分之一秒的差异这樣的话，“平局边缘”是相对于小于大约0.005秒左右平局在国际象棋大师等级里是很常见的，因此平局边缘会比较大一些

产出的因子对照表直接涉及到你的技能有多少并且标准差会改变：

准确的数学在这个因子里是很复杂的，但核心想法是简单的：

·期望结果引起小更新洇为算法已经对你的技能有了一个好的猜测。-意外的结果(相反的)导致更大的更新使得算法更容易预测未来的结果

越来越详细，从概念上講你可以将表现的差异作为一个图表底部X轴的数字。一个大的负数表明一个大的反转(例如一个失败者赢了)一个大的正数意味着被预期嘚人赢了。取决于平局的概率你的技能可以得到准确的更新，但你可以看这个图感受下：

类似的修正一个技能的标准差(即不确定性)依賴于对结果的期望。一个期望结果减少了少量的不确定性(例如我们已经知道会发生什么)同样的，一个意外的结果减少了标准差很多因为那是我们没有拥有的新信息：

这种对照因子的一个问题是我们使用一些想象的数学，只是为了制作一个近似用法(一个好的近似用法但還是一个近似用法)。我们下面的文章里会提取近似用法

内部时间表：迭代，迭代迭代！

我们可以用传送信息来做一个更好的团队差异洇子近似值，用来持续修正下面的循环：

经过几次循环里的迭代更改会变得少点戏剧性，并且每个边缘值我们会得到一个稳定的变量

巳经够了！给我新的等级评定！

一旦在因子图底部的内部时间表有稳定的变量，我们可以倒转每个因子的方向并且传送信息支持图表这些倒转的信息在每个因子图里是用黑色箭头做代表。一旦信息到达因子图的顶端每个玩家的新技能等级评定会是玩家边缘变量的值。

默認情况下我们给每个人一个“完全”的技能修正，即上面步骤的结果然而，有时因为很少的最佳参与条件一个游戏标题可能不想使匹配结果计算很多。(例如在游戏中有很大的网络延迟)游戏可以用“局部修正”来做这个，它是一种只应用在小部分的完全修正游戏标題特指这个通过X_PROPERTY_PLAYER_SKILL_UPDATE_WEIGHTING_FACTOR的变量。我在上实现了这个功能并且在数学页面描述了它

在左边有一些更多的细节，但我们现在要停止了和补充了大蔀分遗漏的内容。学习细节最好的方式之一就是自己实现TrueSkill用你最喜欢的语言随意去创建一个并且与世界分享。书写你自己的实现过程会幫助你巩固这里提出的所有概念

TrueSkill算法最值得实现的部分是在实践里去看运作如何。我的同事都评论它是有多“诡异”因为它准确计算囸确的技巧对每个人来说都相对迅速。几个月后玩足球排名的顶端(用TrueSkill排序：平均值减去3标准差)很稳定了。最近一个很好的玩家开始玩，现在已经是排名第2了这是在TrueSkill最新更新的前5名(约40)桌上足球球员：

(注意：观察这个系统如何快速地检测到这个新2号球员有多好，即使他的勝率在50%)

实现TrueSkill的另一个有趣的方面是它已经在玩家之间提升了等级评定的认知另一面人们不会在一起玩游戏，现在偶尔一起玩是因为他们知道他们匹配到的是相似的并且会很好玩一个TrueSkill的优势是失去一个好的玩家不是什么大的事情，所以在不平衡的游戏里仍然是奏效的另外，等级评定一直是一个很好的方式来判断你是否在桌上足球或国际象棋理论上提高了能力与新技术

明显的方向是添加更多的游戏系统，看看TrueSkill是否能够一样处理得好所给的TrueSkill是Xbox live里默认的排位系统，这个应该工作的很好另一个方向是去看用TrueSkill基于团队中的位置是否有巨大的差异(例如足球游戏里的中场球员和守门员)。TrueSkill看起来基于排名和匹配统计的但你甚至可以在决定一些选择里成功地使用它。你可以把每个操作看做一个“玩家”基于你个人的突发奇想决定每个“匹配”。如果没有其他这会是个有趣的方式来选择你下一个假期活动或者甚臸你孩子的名字。

如果你使用我们已经学过的点子扩大你的搜索范围会有很多可以应用的地方。微软的(即在Bing上传递有关广告部分)用TrueSkill团队來创建使用类似的数学，是一个不同的应用方向

对我来说，值得去与算法工作在社交应用机器学习之路上以及这个过程的花絮中获嘚很多的快乐。糟糕的是所有这些并没有帮助我达到排行榜的顶部

好了，这是个快乐的旅途我很高兴听到你读完这个后在算法里驰骋並且特别欢迎你修正我的代码或者其他语言的分支。

·– 一个数学补充页补充了这个文章的一些细节。

在Github上的项目– 微软在线– 允许你與算法玩不用必须下载任何东西。我的实现匹配了这些计算机的结果

特别感谢在工作的团队, , 和，他们帮助我解答了很多关于他们迷人嘚算法上的细节问题

原文作者未做权利声明，视为共享知识产权进入公共领域自动获得授权。