App Store
Steam游戏设计左道，匹配机制Elo系统介绍与Trueskill系统原理研究
一、前言
温馨提示，万字长文，且需要一定数学基础，较为枯燥，建议睡前看助眠。
玩家技能评估系统是多人竞技游戏中不可或缺的一部分，通常有以下三部分组成：
真实技能评价
可以理解为玩家实际的实力，战斗力，技巧水平的度量。技能评价一致的玩家，就是势均力敌的玩家，理论上更希望他们匹配到一起，他们的胜负也应该趋于平局。
外显评价
真实技能评价不一定展示给玩家看，因为真实技能评价往往是一个波动上升的状态，并且经常会进入平台期，对于玩家来说，这并不是最好的体验，玩家想要的是随着战斗持续提升。
外显评价的意义就是跟真实评价解耦，我们可以对其进行各种操作，例如赢一把加一颗星，输一把掉一颗星，比一个算法算出来的复杂的分数更好理解。并且可以加上掉星保护，段位保护，连胜加星等等操作，让玩家整体始终是上升的状态，并且不会影响玩家的真实评价。
匹配系统
以真实技能评价为匹配的核心，辅助外显评价，最后综合考虑匹配时长，对局质量等等，将合适的玩家匹配到一起进行游玩。
这一块不在这里细说，但是微软有一个有趣的数据结论可做参考，对局质量影响远大于匹配时长。
技能评估系统有很多方法实现，例如Elo评分系统，Glicko和Glicko2，MMR，Trueskill等。
Elo和Elo的变种因其简单易用，应用最广，包括我们之前项目也是用的自己魔改的Elo。但是Elo有其局限，目前最强大的方法还是Trueskill，当然也最复杂。
Trueskill是一种基于贝叶斯在线学习的玩家评分系统，由微软研究院研发，最初用于Xbox的多人对战匹配系统。Halo系列，战争装备系列，Forza Motorsport系列，彩6等游戏都用了这个方法。
注意，适合项目的才是最好的，所有技能评估系统，都得根据项目具体情况进行魔改。因此，都先得理解这些系统背后的原理，才能为自己项目深度定制。在好理解这方面，可以说是Elo完胜，Trueskill用的人少不是没有原因的，为了理解和实现Trueskill，一共看了不下一百页英文论文（好几遍），被数学淹没，猪脑过大载。这些论文链接都附在文末，不能我一个人看。
因为Elo和Trueskill还是有一些共通之处，先介绍Elo方便理解。
二、Elo评分系统
Elo背景不多介绍，网上比较多自行搜索，直接说原理。
Elo的核心是用一个分数来衡量玩家水平，用分数差来计算胜率，再结合实际结果来反过来修正玩家的分数，来匹配玩家的真实水平。
首先，我们认为一个玩家实际游玩中的技能水平，符合正态分布N(μ,σ^2)，如下：
μ就是平均值，可以理解为该玩家的平均水平，在Elo里这个值可以直接用来作为玩家的战斗力评分，σ指的是标准差，也就是玩家水平的波动程度，σ越大，波动越大，越小说明玩家发挥越稳定。
表达成函数就是正态分布的概率密度函数probability density function（PDF），概率密度函数的意思就是给定x值，随机到该x值的概率。
正态分布的特性是，玩家实际发挥在 (μ−4σ,μ+4σ) 区间内的概率为99.9937%，而根据微软后台的数据，实际上玩家落在 (μ−3σ,μ+3σ) 区间内的概率为99.99%。
举个例子，玩家A，μ等于1000，σ等于200，则代表A的水平大概率就在400-1600(μ−3σ,μ+3σ) 之间波动，并且越靠近1000，概率越大。假如这时候，来了个玩家B，μ等于1200，σ等于200，两者的比较如下图：
我们可以理解为，正态分布描述的是一个一件事情发生不同结果的概率可能性分布，很直觉的，B玩家的胜利的可能性更高，但是当A发挥更好，B发挥更差时，A也有胜利的可能性。
根据正态分布的计算规则，当B玩家的正态分布减去A玩家的正态分布时，可以获得一个新的正态分布，新的正态分布的意义是两者实际表现的分数，相减后差值的所有可能性分布，相减的公式如下：
相减的结果如下图：
可以看到，是以200为平均值的一个正态分布，1200左右波动减去1000左右波动，差值的可能性当然是落到200左右。当差值大于0，也就是B发挥的比A好的所有可能性，其实就是B的胜率了，如下图：
这个胜率的具体多少，需要用累积分布函数Cumulative Distribution Function（CDF）来计算，CDF就是前面PDF的积分，意义是随机变量X小于等于某个值的概率。推导过程省略，直接给出结果公式：
D就是两者玩家μ的差值，实际实现中，这个积分实现比较麻烦，就会用一个表现接近的逻辑分布（logistics）来近似地拟合，公式简化为如下：
这时候我们知道了胜率，就可以进行新的玩家水平分数的更新，我们以玩家A为例，本场战斗结果G有三种：
胜利G=1；失败G=0；平局G=1/2。
接下来我们来计算玩家A的分数改变，Elo的计算公式如下：
玩家B的同理，不赘述，我们来分析一下这个公式的实际意义：
当D越大时，说明战斗前战斗力A比B高很多，P(D)也就预期胜率越大，越接近1，这时如果赢了，G=1，G-P(D)=1-预期胜率，也就越接近0，加的分就越少。
反之，如果A输了，则0-预期胜率，扣得分数就越多，但最多不会超过K，这就是K为什么决定了单场评分变化上下限。
同理，当A的战斗力比B低很多，结果就相反，A赢了就赢得多，输了就输的少。
这是合乎逻辑的，战斗前的战斗力，可以理解为我们预测的玩家的战力，当预测的强者战胜了弱者，是符合预期的，对战斗力的调整就应该更小，反之，以弱胜强，对两者的分数变化都会更大。
特别的，我们看当A跟B战斗力一样的时候（我们倾向这么匹配），这时候D为0，变化就是统一为1/2的K。若是这时候恰好是平局，G=1/2。则双方分数不增不减，也是符合预期的。
以上，就是最简单Elo版本，可以达成根据匹配双方的实力差距，进行战斗力评分的合理调整，而匹配的逻辑也很简单，战力μ尽量接近的匹配到一起就行。
Elo最大的优势就是简单好理解，实现起来也很简单。但是实战中，上述的简单版本是不够的，原版Elo有如下几个问题：
上述几个问题都有打补丁解决的方案，但是都会让Elo变得冗杂，也不是最优解，it just works（陶德脸）。这里不赘述，后面再写一篇专门的文章来讲更好的Elo。
三、Trueskill前置知识
实际上，Elo可以视作Trueskill的子集，一种特殊简化情况。
前面elo的过程中，其实有一个非常重要的简化，就是认为玩家水平的正态分布的不确定性σ是一样的，实际上当然是不一样的，真正的玩家应该如下：
其中红色的玩家，μ值更高，代表平均水平更高，并且σ更小，代表他发挥更稳定，蓝色玩家相反。经过一场战斗后，如果蓝色玩家赢了，变化大约如下：
重要的是，可以看到，和平均水平μ类似，σ也不是一成不变的，随着战斗或者时间等因素的变化，σ也在动态变化。Trueskill相对elo最大的变化也在这里，它不是依赖一个相对固定的K值来控制评分调整，而是利用贝叶斯推断，完整地对μ和σ进行预测和后验调整。
数学警告！Trueskill相对Elo会复杂很多，下面会用尽量通俗的语言，尽量少的数学推导来讲明白原理，但是仍需要一些前置知识才能看懂：
1、似然函数likelihood function
p(x|θ)是一个有着两个变量的函数。如果，你将θ设为常量，则你会得到一个概率函数（关于x的函数）；如果，你将x设为常量你将得到似然函数（关于θ的函数）。
举个人话版本例子，概率函数就是，有一枚材质均匀的硬币，理论上你知道它正面朝上的概率是50%，这个已知信息就是θ，现在需要你来求解抛100次硬币正面朝上的概率分布，这就是概率分布函数p(x)。
反过来，这时候有个人作弊了，把这个硬币灌了铅，正面或反面会重一点，重多少你不知道。但是刚刚你尝试投掷了100次，70次朝上，现在需要你通过这个已知信息，来反推硬币朝上的概率是多少，这就是似然函数p(θ)。
值得注意的是，这个结果也是一个概率分布函数，并不是70%，而是70%左右的概率最大，p(θ)的函数曲线大致如下图：
2、贝叶斯推断
那么刚刚那个硬币的例子，实际θ值是多少呢？这里来到了一个关键点，就是统计推断两大学派的不同：
1经典统计推断
经典统计推断会认为这个θ值是一个常数，是一个定值，比如就是68%，只是我们不知道，然后我们通过各种方法去估计它。
很合理，但是如果问题做个小改动，硬币里面没有灌铅，而是住了个小精灵，这个小精灵凭心情决定哪面朝上，我们知道它喜欢正面一些，但是它不会数数，所以只能凭感觉。
这是一个更接近真实情况的求解需求，现实中的问题可没有那么多定值的解，大多数情况充满了主观因素，复杂的不可控因素，因此这里经典统计推断就不好用了，这就需要用上贝叶斯统计推断。
2贝叶斯推断
贝叶斯推断认为，这个未知参数θ是一个随机变量，它有一个先验分布，例如刚刚我们知道小精灵喜欢正面一些，但不会数数，这些就是先验知识，我们可以利用这些先验知识，搞一个先验分布来缩小可能性的范围。这个先验知识可以是历史数据，经验，甚至是主观判断。
然后在已知观察数据X的基础上（刚刚抛的100次，70次朝上），利用贝叶斯定理来推导一个后验概率分布，这个后验概率体现了结合先验知识和观察数据后，参数的概率分布，如果我们拿这个后验概率来更新我们的先验知识，再次进行实验，就能使我们的推断越来越准确，这个就是贝叶斯推断常用在机器学习和实时数据分析的由来。
而Trueskill的基本原理，也是如此。
3、贝叶斯定理
贝叶斯定理的公式为：
P(E|F)的意思就是根据结果F来计算E的后验分布Posterior，还是刚刚的例子，F就相当于之前的“100次硬币70次朝上”这个结果，E就是真正硬币朝上的概率分布。可以理解为当F发生的前提下，E发生的概率分布。
了解一下推导过程，其实很好理解，条件概率公式如下：
可以理解为E和F都发生的概率=（F发生的前提下，E发生的概率）*F发生的总概率。举例人话版本：吃到一颗酸李子的概率=李子里面酸李子的概率*水果是李子的概率。
同理反过来也是，吃到一颗酸李子的概率=酸的东西是李子的概率*拿到酸的东西的概率。公式如下：
可得：
推出贝叶斯定理：
怎么来直观的理解贝叶斯定理？人话版本：假如我们想知道李子里酸李子的概率P(E|F)，等于：不管酸甜，拿到李子的概率P(F)中，随便拿一个，这个恰好是酸李子个概率P(F|E)*P(E)。
结合前面所说，我们将公式转换成更好理解的版本：
P(E|F)是后验结果Posterior，P(F|E)就是P(E|F)的似然函数likelihood，P(E)就是先验分布Prior，P(F)就是边缘分布Marginal，边缘分布解释看后文。
可以表达成这个公式：Posterior=Likelihood*Prior/Marginal
4、因子图Factor Graph
因子图（Factor Graph）是一种图形模型，用于表示变量之间的复杂依赖关系，可以将一个全局的概率分布或函数分解为多个局部因子的乘积形式。
因子图包含两种节点：变量节点（Variable Nodes），代表模型中的随机变量；因子节点（Factor Nodes），代表定义在变量子集上的函数，这些函数通常与概率分布相关联。也可以理解为变量之间的条件概率或逻辑关系。
因子图的边连接变量节点和因子节点，表示该变量参与了因子节点所代表的函数计算。因子节点的引入使得图模型能够显式地表示变量间的局部依赖关系。
最重要的是，可以利用因子图加上消息传递算法，计算出任意变量节点的边缘分布，用于我们的贝叶斯推断（前面公式中的分母）。
上面的黑方块就是因子节点，白圆圈就是变量节点。具体意义先不纠结，下面详述。
5、Sum-Product算法
再Trueskill里用的消息传递算法是Sum-Product算法，这是信念传播算法的一种，适合用于因子图。
可以想象成因子图里的节点们，可以跟相邻的节点说话，告诉他们自己当前的状态，来作为对方调整的依据。同理，其他相邻节点也可以跟它传递消息，帮助它来调整自身的值。
刚刚因子图的解释中又说，有两种节点，变量节点和因子节点，这两种节点消息传递方式不同：
当消息从因子节点传递到变量节点时，因子节点会将所有和它相连的变量节点，除了目标变量节点外，进行边缘化处理，也就是联合概率中不相关变量进行加总的操作，如果是连续的随机变量，则进行积分。这一步就是Sum。
当消息从变量节点传递到因子节点时，变量节点会取所有和它连接的除了目标因子节点外的因子节点，将它们产生的消息进行求积。求积本质上是算这些影响该变量节点的因子节点视作一个个独立事件，他们的联合概率就是他们的乘积，相当于将这些事件对该变量节点的影响综合起来，然后作为信息，传递给目标因子节点。这就是Product。
这就是Sum-Product这个名字的来源。
6、边缘概率
概率的边缘化也很好理解，假如有两个独立的随机变量A,B，有一个联合概率分布P(A,B)，当我们不关心B，想知道A的概率分布P（A）时，就对B进行边缘化操作。
假如B是一个离散随机变量，有三种可能1,2,3，A的概率分布就是：P(A)=P(A,B=1)+P(A,B=2)+P(A,B=3)，也就是B在各个可能性下，联合概率就只剩A作为变量的结果，将他们加起来，就是A总的可能性分布。
当B是连续随机变量时同理，只要把加法改成积分就行。
因此，结合因子图和Sum-Product算法的原理我们可以知道，当想要求一个因子图上任意变量节点的边缘概率，只需要将其作为根节点，然后将消息从叶子节点开始传递，传递到根节点后就是边缘概率。
四、Trueskill原理分析
好了，上面这些基础知识了解了之后，就可以上硬菜了。
Trueskill原理先用一句话来说，就是，一场比赛结束，我们的目标是根据玩家过去的技巧水平（先验知识），加上已知的比赛结果，推算出玩家最有可能的新技巧水平（后验推论）。这个后验推论的意义可以参考前文例子理解，换句话说，就是结合已知信息，加上刚刚的比赛结果，推测这几个玩家最有可能的技巧水平是怎么样的，这就是我们需要的新技巧水平预测了。
上述的这句话就是贝叶斯推断，可以用前文的公式表达：Posterior=Likelihood*Prior/Marginal。我们的目标就是求得Posterior。
Elo本质上也符合这句话，但是Trueskill更进一步，将整个过程视作一个非常通用的，受各种随机因素影响的过程，从玩家过去的水平，到玩家表现，到队伍表现，再到队伍间的表现差值，最后到比赛结果。
记得之前贝叶斯推断和经典统计推断的不同吗，在这里，想要更快理解Trueskill的贝叶斯推断过程，首先得把思维扭转过来，我们追求的结果，包括过程中的大部分变量，都是随机值，是一个随机分布，而不是定值。我们所求的，不是某个固定结果，而是一个最有可能性的随机范围。
如上所说，除了比赛结果是确定的值，其他每一步都是受各种影响的不确定的随机分布。我们需要通过几个已知的信息，求出玩家最有可能的水平分布。直接计算将会是一个非常复杂的包含多个参数的联合概率分布。
于是我们可以用因子图来将其拆分简化，方便分步计算，下面的因子图就是将这个过程抽象表现出来的结果，这是一个最简单的1v1的比赛：
从上往下看，首先我们还是认为玩家的水平是一个正态分布:
根据这个正态分布，可以活动玩家的真实水平S，这是第二层。真实水平S到实际的表现P，中间也会根据战斗随机性等因素β有波动，这个波动我们也认为是正态分布：
由这个函数我们可以得到玩家的实际表现P，两个玩家表现的差距，就是d=(Pa-Pb)，注意这里是指两个正态分布相减，得出的d也是一个正态分布。差距d根据一个指示函数，来推出战斗结果，简单来说就是d小于一个值，就是平局，否则就是胜利。
上述就是一个Trueskill计算过程的因子分解，下面我们直接以一个更加通用的多人对战Trueskill因子图来详细讲解：
红的圈圈就是代表一个变量节点，黑方块代表一个因子节点，箭头就代表消息传递。上述因子图描述的一场比赛，是由四位玩家，分成三队，将多人和组队的可能性都涵盖进去了，也体现了Trueskill相比Elo的强大之处，底层上支持任意人数任意组队方式的比赛，后续拓展原理都一样。
注意一点，这个因子图里的队伍表现是从高到低排好序的。
回忆一下之前讲的这个公式：Posterior=Likelihood*Prior/Marginal
接下来具体讲解一下因子图每一层的意义，来完成上述公式。
1、因子图第1层，先验的技巧水平S
第一步，由过往的先验数据来推断玩家的技巧，这个数据可以取自数据库中玩家过往的数据。参考前文，我们认为玩家的水平符合正态分布，由μ和σ控制，每个玩家这两个参数不同。
这里的τ是一个新引入的参数，用作每场比赛增加一个固定的不确定性，来保证玩家的不确定性不会收敛到0，因为后续所有计算的结果，都会将不确定性缩小。
这一步就代表我们基于过去数据加上一个调整参数，来作为我们先验的知识，所以用作我们的先验分布Prior
公式完成三分之一：posterior=likelihood*Prior/Marginal
2、因子图第2层，根据技巧来定表现
技巧水平是技巧水平，实际表现基于技巧水平，但不完全等于，所以这一步表达的是技巧水平如何转化为表现。
这里引入一个新参数β，代表的是多少技能评分差距，能保证高的玩家有80%的胜率。例如β等于4，就意味着20分的玩家和16分的玩家战斗有80%能赢。这个参数用于表达游戏本身的不确定性，不确定性越低的游戏例如围棋，β就低，斗地主就会更高。
3、因子图第3层，根据单人表现来定团队表现
这里可以看到，一队多个人的计算方法是直接相加，但实际比赛往往不完全是，两个人合作，一加一大于二和互相拖后腿都有可能。所以这一块是Trueskill值得优化的部分。但为了更简单，我们先近似地认为，队伍表现就是队员表现的和。
4、因子图第4层，队伍表现间的比较
比较简单，两个队伍表现都是正态分布，相减一下就是差距d的可能分布，和elo那边的计算一样，可参考上文。
5、因子图第5层，根据队伍间的比较，推出结果
这里引入新的参数ε，可以称其为平局临界值，当双方表现的差距小于这个值时，将其当做平局处理，大于这个值才分胜负。引入他的原因就是Trueskill只会在意两种状态，就是胜利和平局，这两个结果不同对于后面的计算方式和计算结果有很大的不同，因此，需要有一个ε值来作为缓冲区间，以免特别双方表现接近的时候，视作胜利，带来误差。从数学上来讲，d是两个随机数的差，理论上d=0的概率是0，所以也需要一个区间来让其有意义，类似我们写代码的时候判0都是小于一个很小的数。当然可以看出，这也是Trueskill值得优化的点，它没有考虑胜利的大小，大胜和小胜，以及险胜，体现的双方实力差距是完全不同的。
6、多人多队多次迭代
队伍差距这里，可以进行多次消息传递的迭代，来获得更精确的值，具体原理仍旧不变，只有一个要注意的是，最终结果到Team Diff的这一步，是一个指示函数，不是一个高斯分布，需要先用矩匹配Moment Matching，将其近似为高斯分布，在进行消息传递。
如此从上往下传递消息到战斗结果为止，就是技巧水平S到战斗结果R的似然函数了，也就是公式中的likelihood
然后同样用Sum-Product算法，从下往上传递消息，直到S，就如前文边缘概率所说，这个就是技巧水平S的边缘概率Marginal
到这一步，公式完整，求出S的后验概率 posterior=likelihood*Prior/Marginal
中间具体数学推导过程不在这赘述，感兴趣的可以看文末链接里的《The Math Behind Trueskill》。
这里为了方便理解，我再用一个更加白话的方式，描述一下整个推导过程，如果上述过程已经看懂，可以跳过：
我们现在有个玩家小美，她的技巧水平是一个波动的随机值，过往经验来看是在1200分左右波动，大多数情况下，在1000-1400之间，是一个正态分布。这时她参与了一场战斗，战斗结束后她赢了对手。我们预测，以她的水平SA，在游戏内的表现，也是一个正态分布的随机范围PA，同理她的对手是PB，她跟她的对手的表现差距，也是一个正态分布的随机范围d。这时候已知的结果r告诉d，在胜利的情况下，你的随机分布需要修改一下，这样更有可能获得胜利，d说ok。然后d又告诉PA和PB，如果我这么修改，你们俩最好也修改一下，这样你们俩算出我这个d的可能性会更大。PAPB说ok，那SA你也得修改一下，这样得到我这个PA的可能性更大，SA说ok，我改，我改了，得通知一下小美，小美你的技巧应该在1300分左右波动，波动也应该减少到1250-1350之间，才有更大可能打出SA这样的技巧。经过所有节点的窃窃私语，互相传递消息后，大家都进入一种状态，这种状态就是大家都是最有可能发生这个结果的状态，所以再去互相传递消息的时候，消息开始重复没有什么新变化，达成一种平衡。
五、Trueskill结果分析
由上述的过程，我们可以得到最终结果：
更新胜负双方μ的函数如上，归一化的c值如下：
从公式可以看出，双方自身的σ越大，更新越大，因为不确定性更大，但是对手的不确定性越大，更新会趋向更少。β越大更新越小，因为较大波动的战斗规则，对实力的确定帮助也较小。
v是指高斯截断函数，在非平局情况下，v的公式为：
V的分母Φ(x)是指累积密度分布CDF，用作求随机变量小于等于x时的概率分布。
上述公式的推导过程我们不纠结，重要的是公式代表的意义。t相当于胜者和负者间预计的平均实力差距，可以看一下V有关t的函数图像：
可以看到，当t越大，说明胜者和负者预计实力差距越大，因此更新就越少。反之t越小，甚至小于0时，意味着预计实力低的人反而赢了，因此超乎意料，应该更新更多。
ε越大，更新越大，因为平局临界越大，胜利更不容易发生，因此一旦发生，对实力的更新越大。
平局时，v的公式为：
同样的，我们看看关于v关于t的函数图像：
这里是t是越接近0，更新越小，因为符合平局的预期。正数越大，我们预期的胜者扣分越多，因为预期胜者和负者实力差距越大，结果是平局，那就意味着两者实力预估偏差很大，因此更新更大，反之负数分析类似。
ε越大，更新绝对值越小，因为平局临界越大，平局更容易发生，因此对实力的更新越小。
接下来是玩家的σ的更新公式：
和μ的更新公式不一样，σ的公式是在旧的方差上乘以一个0-1之间的数，这也很好理解，每场战斗获得新信息后，不确定性或多或少都应该下降。这也是前文每场比赛加入不确定性τ的原因。可以看到和μ公式一致的是，当自身原本的不确定性越大，更新趋向越大，同样由于c的存在，对方的不确定性越大，更新趋向更小，β越大，更新趋向也越小。
在非平局情况下，w的公式为：
同样的，我们来分析一下w关于t的函数图像：
可以看到，两者预测的实力差距越大，对不确定性的更新越小，因为结果更加符合预料，因此，对缩小双方水平的不确定性没什么帮助。ε越大，更新更大，因为平局临界越大，更不容易取胜，因此对不确定性的更新越大。
在平局情况下，w的公式为：
同样的，我们来分析一下w关于t的函数图像：
和之前类似，两者预期实力越接近，平局时的不确定性就更小，因为达成平局在预料之内。因为是平局，所以ε越大，更新越小。但是我们可以看到ε=4时，t在0附近对不确定性的更新基本为0，这意味着更容易平局的战斗，对双方更新战斗力价值不大，但是对于一般游戏，平局的概率一般较低。
到这一步，我们就可以得出玩家新的技巧水平的正态分布了，将新的参数μ和σ存起来，作为下一次战斗的先验知识，如此循环，越来越接近玩家的真实水平。
玩家的rank标识
假如说有些游戏不想用独立的外显段位，就想根据玩家水平的正态分布，直接展示一个玩家能理解的rank分数，微软那边的方法是rank=μ-k*σ。然后k取3，前文提到过，正态分布99.99%概率落在μ±3倍σ之间，所以这个rank的意思就是以这个作为玩家评分，则玩家的技巧绝大概率会大于这个rank，所以称作为保守rank。
实际上我认为，不一定要用这个公式或者这个k值，但是思路上，需要保证把μ和σ都考虑进去，因为玩家的水平不只包含平均值μ，稳定性σ本身也是水平的体现。例如k=0，其实就是elo的分数，没有考虑到σ，因此并不准确。
匹配算法
匹配算法就很简单了，elo是玩家elo分接近的匹配，Trueskill就是代表玩家水平的两个正态分布，重合度越高代表水平接近，适合匹配。这里没什么讲究，直接用正态分布重合度的公式即可：
六、Trueskill优化方向
以上是Trueskill的基本原理，在理解之后，就需要针对性的根据项目进行定制调整，实际上微软也18年也提出了Trueskill2，基本原理不变，但是加入了对组队，KDA，中途退出等额外因素的考虑，结果会更精确。后面我也会研究一下Trueskill2，下面是一些我目前想到的优化方向，先列出来，后续思考实践后，再进行深入分享：
1同组多人计算方式，目前是直接相加，实际不是
可以根据双方游玩时长（我们游戏可以是回合数）等来给权重。总体思路是双方的水平发挥的百分比相加才是更客观的。更进一步，1加1大于2的情况，双方化学反应的情况，如何表现？
2目前Trueskill不关心胜利是大胜还是小胜，有优化空间
大胜小胜险胜，理论上对结果的判断可以有一个加权。或者说若是有游戏，结果表达为不是简单的胜负，就应该根据胜负差距进行更精确的处理。
3部分更新
可以根据具体情况，部分更新结果，例如网络不好，那就少更新一点（本场战斗不代表真实水平）。
4根据局内表现调整
据我们游戏，增加合适的额外考虑，例如连击数，击杀数，优化Trueskill的结果。
5随时间变化的影响
玩家长期不玩回坑，这时候σ应要变大。
6机器人的考虑
机器人在Trueskill计算中应该以一个怎么样的技巧水平作为参数，不同机器人应该需要不同的参数。
7Trueskill的扩展应用
贝叶斯方法是机器学习的重要工具，做复杂的概率处理非常强大，类似于对玩家水平的模拟，所有模糊评价某个值的问题，都可以用上。例如对关卡难度的评价，平衡性处理等等。
七、引用
1、TrueSkill: A Bayesian Skill Rating System
https://www.microsoft.com/en-us/research/wp-content/uploads/2006/01/TR-2006-80.pdf
2、TrueSkill 2: An improved Bayesian skill rating system
https://www.microsoft.com/en-us/research/uploads/prod/2018/03/trueskill2.pdf
3、The Math Behind TrueSkill
https://www.moserware.com/assets/computing-your-skill/The%20Math%20Behind%20TrueSkill.pdf
4、On Gaussian Expectation Propagation
https://www.microsoft.com/en-us/research/wp-content/uploads/2005/07/EP.pdf
5、Understanding Belief Propagation and its Generalizations
https://people.csail.mit.edu/billf/publications/Understanding_Belief_Propogation.pdf
6、Computing Your Skill
https://www.moserware.com/2010/03/computing-your-skill.html
来源：鱼塘游戏制作工坊
原文：https://mp.weixin.qq.com/s/MhAJSimzZS8JpNSOJp36Ng
温馨提示，万字长文，且需要一定数学基础，较为枯燥，建议睡前看助眠。
玩家技能评估系统是多人竞技游戏中不可或缺的一部分，通常有以下三部分组成：
真实技能评价
可以理解为玩家实际的实力，战斗力，技巧水平的度量。技能评价一致的玩家，就是势均力敌的玩家，理论上更希望他们匹配到一起，他们的胜负也应该趋于平局。
外显评价
真实技能评价不一定展示给玩家看，因为真实技能评价往往是一个波动上升的状态，并且经常会进入平台期，对于玩家来说，这并不是最好的体验，玩家想要的是随着战斗持续提升。
外显评价的意义就是跟真实评价解耦，我们可以对其进行各种操作，例如赢一把加一颗星，输一把掉一颗星，比一个算法算出来的复杂的分数更好理解。并且可以加上掉星保护，段位保护，连胜加星等等操作，让玩家整体始终是上升的状态，并且不会影响玩家的真实评价。
匹配系统
以真实技能评价为匹配的核心，辅助外显评价，最后综合考虑匹配时长，对局质量等等，将合适的玩家匹配到一起进行游玩。
这一块不在这里细说，但是微软有一个有趣的数据结论可做参考，对局质量影响远大于匹配时长。
技能评估系统有很多方法实现，例如Elo评分系统，Glicko和Glicko2，MMR，Trueskill等。
Elo和Elo的变种因其简单易用，应用最广，包括我们之前项目也是用的自己魔改的Elo。但是Elo有其局限，目前最强大的方法还是Trueskill，当然也最复杂。
Trueskill是一种基于贝叶斯在线学习的玩家评分系统，由微软研究院研发，最初用于Xbox的多人对战匹配系统。Halo系列，战争装备系列，Forza Motorsport系列，彩6等游戏都用了这个方法。
注意，适合项目的才是最好的，所有技能评估系统，都得根据项目具体情况进行魔改。因此，都先得理解这些系统背后的原理，才能为自己项目深度定制。在好理解这方面，可以说是Elo完胜，Trueskill用的人少不是没有原因的，为了理解和实现Trueskill，一共看了不下一百页英文论文（好几遍），被数学淹没，猪脑过大载。这些论文链接都附在文末，不能我一个人看。
因为Elo和Trueskill还是有一些共通之处，先介绍Elo方便理解。
二、Elo评分系统
Elo背景不多介绍，网上比较多自行搜索，直接说原理。
Elo的核心是用一个分数来衡量玩家水平，用分数差来计算胜率，再结合实际结果来反过来修正玩家的分数，来匹配玩家的真实水平。
首先，我们认为一个玩家实际游玩中的技能水平，符合正态分布N(μ,σ^2)，如下：
μ就是平均值，可以理解为该玩家的平均水平，在Elo里这个值可以直接用来作为玩家的战斗力评分，σ指的是标准差，也就是玩家水平的波动程度，σ越大，波动越大，越小说明玩家发挥越稳定。
表达成函数就是正态分布的概率密度函数probability density function（PDF），概率密度函数的意思就是给定x值，随机到该x值的概率。
正态分布的特性是，玩家实际发挥在 (μ−4σ,μ+4σ) 区间内的概率为99.9937%，而根据微软后台的数据，实际上玩家落在 (μ−3σ,μ+3σ) 区间内的概率为99.99%。
举个例子，玩家A，μ等于1000，σ等于200，则代表A的水平大概率就在400-1600(μ−3σ,μ+3σ) 之间波动，并且越靠近1000，概率越大。假如这时候，来了个玩家B，μ等于1200，σ等于200，两者的比较如下图：
我们可以理解为，正态分布描述的是一个一件事情发生不同结果的概率可能性分布，很直觉的，B玩家的胜利的可能性更高，但是当A发挥更好，B发挥更差时，A也有胜利的可能性。
根据正态分布的计算规则，当B玩家的正态分布减去A玩家的正态分布时，可以获得一个新的正态分布，新的正态分布的意义是两者实际表现的分数，相减后差值的所有可能性分布，相减的公式如下：
相减的结果如下图：
可以看到，是以200为平均值的一个正态分布，1200左右波动减去1000左右波动，差值的可能性当然是落到200左右。当差值大于0，也就是B发挥的比A好的所有可能性，其实就是B的胜率了，如下图：
这个胜率的具体多少，需要用累积分布函数Cumulative Distribution Function（CDF）来计算，CDF就是前面PDF的积分，意义是随机变量X小于等于某个值的概率。推导过程省略，直接给出结果公式：
D就是两者玩家μ的差值，实际实现中，这个积分实现比较麻烦，就会用一个表现接近的逻辑分布（logistics）来近似地拟合，公式简化为如下：
这时候我们知道了胜率，就可以进行新的玩家水平分数的更新，我们以玩家A为例，本场战斗结果G有三种：
胜利G=1；失败G=0；平局G=1/2。
接下来我们来计算玩家A的分数改变，Elo的计算公式如下：
- Rn是新的玩家A的评分，R0是比赛前的评分，这里是1000。
- K是我们设计师定的值，决定了单场比赛的评分变化上限，可以根据情况灵活配置，例如随段位提升减小K值。
- Ge就是刚刚是胜率，等于P(D)。
- D是两者之间的平均分的差值=μA-μB，也等价于战斗前两者的分数差值
玩家B的同理，不赘述，我们来分析一下这个公式的实际意义：
当D越大时，说明战斗前战斗力A比B高很多，P(D)也就预期胜率越大，越接近1，这时如果赢了，G=1，G-P(D)=1-预期胜率，也就越接近0，加的分就越少。
反之，如果A输了，则0-预期胜率，扣得分数就越多，但最多不会超过K，这就是K为什么决定了单场评分变化上下限。
同理，当A的战斗力比B低很多，结果就相反，A赢了就赢得多，输了就输的少。
这是合乎逻辑的，战斗前的战斗力，可以理解为我们预测的玩家的战力，当预测的强者战胜了弱者，是符合预期的，对战斗力的调整就应该更小，反之，以弱胜强，对两者的分数变化都会更大。
特别的，我们看当A跟B战斗力一样的时候（我们倾向这么匹配），这时候D为0，变化就是统一为1/2的K。若是这时候恰好是平局，G=1/2。则双方分数不增不减，也是符合预期的。
以上，就是最简单Elo版本，可以达成根据匹配双方的实力差距，进行战斗力评分的合理调整，而匹配的逻辑也很简单，战力μ尽量接近的匹配到一起就行。
Elo最大的优势就是简单好理解，实现起来也很简单。但是实战中，上述的简单版本是不够的，原版Elo有如下几个问题：
- 收敛速度比较慢，需要大量对局，Elo分才能相对精确地代表玩家的真实水平。
- Elo是为双人设计的规则，并不底层支持多人，以及复杂的情况。
- 平局的处理比较粗糙，简单视作一半胜利一半失败。
- 理论上，Elo并不是最精确的战力表达方法，下面trueskill会细说。
上述几个问题都有打补丁解决的方案，但是都会让Elo变得冗杂，也不是最优解，it just works（陶德脸）。这里不赘述，后面再写一篇专门的文章来讲更好的Elo。
三、Trueskill前置知识
实际上，Elo可以视作Trueskill的子集，一种特殊简化情况。
前面elo的过程中，其实有一个非常重要的简化，就是认为玩家水平的正态分布的不确定性σ是一样的，实际上当然是不一样的，真正的玩家应该如下：
其中红色的玩家，μ值更高，代表平均水平更高，并且σ更小，代表他发挥更稳定，蓝色玩家相反。经过一场战斗后，如果蓝色玩家赢了，变化大约如下：
重要的是，可以看到，和平均水平μ类似，σ也不是一成不变的，随着战斗或者时间等因素的变化，σ也在动态变化。Trueskill相对elo最大的变化也在这里，它不是依赖一个相对固定的K值来控制评分调整，而是利用贝叶斯推断，完整地对μ和σ进行预测和后验调整。
数学警告！Trueskill相对Elo会复杂很多，下面会用尽量通俗的语言，尽量少的数学推导来讲明白原理，但是仍需要一些前置知识才能看懂：
1、似然函数likelihood function
p(x|θ)是一个有着两个变量的函数。如果，你将θ设为常量，则你会得到一个概率函数（关于x的函数）；如果，你将x设为常量你将得到似然函数（关于θ的函数）。
举个人话版本例子，概率函数就是，有一枚材质均匀的硬币，理论上你知道它正面朝上的概率是50%，这个已知信息就是θ，现在需要你来求解抛100次硬币正面朝上的概率分布，这就是概率分布函数p(x)。
反过来，这时候有个人作弊了，把这个硬币灌了铅，正面或反面会重一点，重多少你不知道。但是刚刚你尝试投掷了100次，70次朝上，现在需要你通过这个已知信息，来反推硬币朝上的概率是多少，这就是似然函数p(θ)。
值得注意的是，这个结果也是一个概率分布函数，并不是70%，而是70%左右的概率最大，p(θ)的函数曲线大致如下图：
2、贝叶斯推断
那么刚刚那个硬币的例子，实际θ值是多少呢？这里来到了一个关键点，就是统计推断两大学派的不同：
1经典统计推断
经典统计推断会认为这个θ值是一个常数，是一个定值，比如就是68%，只是我们不知道，然后我们通过各种方法去估计它。
很合理，但是如果问题做个小改动，硬币里面没有灌铅，而是住了个小精灵，这个小精灵凭心情决定哪面朝上，我们知道它喜欢正面一些，但是它不会数数，所以只能凭感觉。
这是一个更接近真实情况的求解需求，现实中的问题可没有那么多定值的解，大多数情况充满了主观因素，复杂的不可控因素，因此这里经典统计推断就不好用了，这就需要用上贝叶斯统计推断。
2贝叶斯推断
贝叶斯推断认为，这个未知参数θ是一个随机变量，它有一个先验分布，例如刚刚我们知道小精灵喜欢正面一些，但不会数数，这些就是先验知识，我们可以利用这些先验知识，搞一个先验分布来缩小可能性的范围。这个先验知识可以是历史数据，经验，甚至是主观判断。
然后在已知观察数据X的基础上（刚刚抛的100次，70次朝上），利用贝叶斯定理来推导一个后验概率分布，这个后验概率体现了结合先验知识和观察数据后，参数的概率分布，如果我们拿这个后验概率来更新我们的先验知识，再次进行实验，就能使我们的推断越来越准确，这个就是贝叶斯推断常用在机器学习和实时数据分析的由来。
而Trueskill的基本原理，也是如此。
3、贝叶斯定理
贝叶斯定理的公式为：
P(E|F)的意思就是根据结果F来计算E的后验分布Posterior，还是刚刚的例子，F就相当于之前的“100次硬币70次朝上”这个结果，E就是真正硬币朝上的概率分布。可以理解为当F发生的前提下，E发生的概率分布。
了解一下推导过程，其实很好理解，条件概率公式如下：
可以理解为E和F都发生的概率=（F发生的前提下，E发生的概率）*F发生的总概率。举例人话版本：吃到一颗酸李子的概率=李子里面酸李子的概率*水果是李子的概率。
同理反过来也是，吃到一颗酸李子的概率=酸的东西是李子的概率*拿到酸的东西的概率。公式如下：
可得：
推出贝叶斯定理：
怎么来直观的理解贝叶斯定理？人话版本：假如我们想知道李子里酸李子的概率P(E|F)，等于：不管酸甜，拿到李子的概率P(F)中，随便拿一个，这个恰好是酸李子个概率P(F|E)*P(E)。
结合前面所说，我们将公式转换成更好理解的版本：
P(E|F)是后验结果Posterior，P(F|E)就是P(E|F)的似然函数likelihood，P(E)就是先验分布Prior，P(F)就是边缘分布Marginal，边缘分布解释看后文。
可以表达成这个公式：Posterior=Likelihood*Prior/Marginal
4、因子图Factor Graph
因子图（Factor Graph）是一种图形模型，用于表示变量之间的复杂依赖关系，可以将一个全局的概率分布或函数分解为多个局部因子的乘积形式。
因子图包含两种节点：变量节点（Variable Nodes），代表模型中的随机变量；因子节点（Factor Nodes），代表定义在变量子集上的函数，这些函数通常与概率分布相关联。也可以理解为变量之间的条件概率或逻辑关系。
因子图的边连接变量节点和因子节点，表示该变量参与了因子节点所代表的函数计算。因子节点的引入使得图模型能够显式地表示变量间的局部依赖关系。
最重要的是，可以利用因子图加上消息传递算法，计算出任意变量节点的边缘分布，用于我们的贝叶斯推断（前面公式中的分母）。
上面的黑方块就是因子节点，白圆圈就是变量节点。具体意义先不纠结，下面详述。
5、Sum-Product算法
再Trueskill里用的消息传递算法是Sum-Product算法，这是信念传播算法的一种，适合用于因子图。
可以想象成因子图里的节点们，可以跟相邻的节点说话，告诉他们自己当前的状态，来作为对方调整的依据。同理，其他相邻节点也可以跟它传递消息，帮助它来调整自身的值。
刚刚因子图的解释中又说，有两种节点，变量节点和因子节点，这两种节点消息传递方式不同：
当消息从因子节点传递到变量节点时，因子节点会将所有和它相连的变量节点，除了目标变量节点外，进行边缘化处理，也就是联合概率中不相关变量进行加总的操作，如果是连续的随机变量，则进行积分。这一步就是Sum。
当消息从变量节点传递到因子节点时，变量节点会取所有和它连接的除了目标因子节点外的因子节点，将它们产生的消息进行求积。求积本质上是算这些影响该变量节点的因子节点视作一个个独立事件，他们的联合概率就是他们的乘积，相当于将这些事件对该变量节点的影响综合起来，然后作为信息，传递给目标因子节点。这就是Product。
这就是Sum-Product这个名字的来源。
6、边缘概率
概率的边缘化也很好理解，假如有两个独立的随机变量A,B，有一个联合概率分布P(A,B)，当我们不关心B，想知道A的概率分布P（A）时，就对B进行边缘化操作。
假如B是一个离散随机变量，有三种可能1,2,3，A的概率分布就是：P(A)=P(A,B=1)+P(A,B=2)+P(A,B=3)，也就是B在各个可能性下，联合概率就只剩A作为变量的结果，将他们加起来，就是A总的可能性分布。
当B是连续随机变量时同理，只要把加法改成积分就行。
因此，结合因子图和Sum-Product算法的原理我们可以知道，当想要求一个因子图上任意变量节点的边缘概率，只需要将其作为根节点，然后将消息从叶子节点开始传递，传递到根节点后就是边缘概率。
四、Trueskill原理分析
好了，上面这些基础知识了解了之后，就可以上硬菜了。
Trueskill原理先用一句话来说，就是，一场比赛结束，我们的目标是根据玩家过去的技巧水平（先验知识），加上已知的比赛结果，推算出玩家最有可能的新技巧水平（后验推论）。这个后验推论的意义可以参考前文例子理解，换句话说，就是结合已知信息，加上刚刚的比赛结果，推测这几个玩家最有可能的技巧水平是怎么样的，这就是我们需要的新技巧水平预测了。
上述的这句话就是贝叶斯推断，可以用前文的公式表达：Posterior=Likelihood*Prior/Marginal。我们的目标就是求得Posterior。
Elo本质上也符合这句话，但是Trueskill更进一步，将整个过程视作一个非常通用的，受各种随机因素影响的过程，从玩家过去的水平，到玩家表现，到队伍表现，再到队伍间的表现差值，最后到比赛结果。
记得之前贝叶斯推断和经典统计推断的不同吗，在这里，想要更快理解Trueskill的贝叶斯推断过程，首先得把思维扭转过来，我们追求的结果，包括过程中的大部分变量，都是随机值，是一个随机分布，而不是定值。我们所求的，不是某个固定结果，而是一个最有可能性的随机范围。
如上所说，除了比赛结果是确定的值，其他每一步都是受各种影响的不确定的随机分布。我们需要通过几个已知的信息，求出玩家最有可能的水平分布。直接计算将会是一个非常复杂的包含多个参数的联合概率分布。
于是我们可以用因子图来将其拆分简化，方便分步计算，下面的因子图就是将这个过程抽象表现出来的结果，这是一个最简单的1v1的比赛：
从上往下看，首先我们还是认为玩家的水平是一个正态分布:
根据这个正态分布，可以活动玩家的真实水平S，这是第二层。真实水平S到实际的表现P，中间也会根据战斗随机性等因素β有波动，这个波动我们也认为是正态分布：
由这个函数我们可以得到玩家的实际表现P，两个玩家表现的差距，就是d=(Pa-Pb)，注意这里是指两个正态分布相减，得出的d也是一个正态分布。差距d根据一个指示函数，来推出战斗结果，简单来说就是d小于一个值，就是平局，否则就是胜利。
上述就是一个Trueskill计算过程的因子分解，下面我们直接以一个更加通用的多人对战Trueskill因子图来详细讲解：
红的圈圈就是代表一个变量节点，黑方块代表一个因子节点，箭头就代表消息传递。上述因子图描述的一场比赛，是由四位玩家，分成三队，将多人和组队的可能性都涵盖进去了，也体现了Trueskill相比Elo的强大之处，底层上支持任意人数任意组队方式的比赛，后续拓展原理都一样。
注意一点，这个因子图里的队伍表现是从高到低排好序的。
回忆一下之前讲的这个公式：Posterior=Likelihood*Prior/Marginal
接下来具体讲解一下因子图每一层的意义，来完成上述公式。
1、因子图第1层，先验的技巧水平S
第一步，由过往的先验数据来推断玩家的技巧，这个数据可以取自数据库中玩家过往的数据。参考前文，我们认为玩家的水平符合正态分布，由μ和σ控制，每个玩家这两个参数不同。
这里的τ是一个新引入的参数，用作每场比赛增加一个固定的不确定性，来保证玩家的不确定性不会收敛到0，因为后续所有计算的结果，都会将不确定性缩小。
这一步就代表我们基于过去数据加上一个调整参数，来作为我们先验的知识，所以用作我们的先验分布Prior
公式完成三分之一：posterior=likelihood*Prior/Marginal
2、因子图第2层，根据技巧来定表现
技巧水平是技巧水平，实际表现基于技巧水平，但不完全等于，所以这一步表达的是技巧水平如何转化为表现。
这里引入一个新参数β，代表的是多少技能评分差距，能保证高的玩家有80%的胜率。例如β等于4，就意味着20分的玩家和16分的玩家战斗有80%能赢。这个参数用于表达游戏本身的不确定性，不确定性越低的游戏例如围棋，β就低，斗地主就会更高。
3、因子图第3层，根据单人表现来定团队表现
这里可以看到，一队多个人的计算方法是直接相加，但实际比赛往往不完全是，两个人合作，一加一大于二和互相拖后腿都有可能。所以这一块是Trueskill值得优化的部分。但为了更简单，我们先近似地认为，队伍表现就是队员表现的和。
4、因子图第4层，队伍表现间的比较
比较简单，两个队伍表现都是正态分布，相减一下就是差距d的可能分布，和elo那边的计算一样，可参考上文。
5、因子图第5层，根据队伍间的比较，推出结果
这里引入新的参数ε，可以称其为平局临界值，当双方表现的差距小于这个值时，将其当做平局处理，大于这个值才分胜负。引入他的原因就是Trueskill只会在意两种状态，就是胜利和平局，这两个结果不同对于后面的计算方式和计算结果有很大的不同，因此，需要有一个ε值来作为缓冲区间，以免特别双方表现接近的时候，视作胜利，带来误差。从数学上来讲，d是两个随机数的差，理论上d=0的概率是0，所以也需要一个区间来让其有意义，类似我们写代码的时候判0都是小于一个很小的数。当然可以看出，这也是Trueskill值得优化的点，它没有考虑胜利的大小，大胜和小胜，以及险胜，体现的双方实力差距是完全不同的。
6、多人多队多次迭代
队伍差距这里，可以进行多次消息传递的迭代，来获得更精确的值，具体原理仍旧不变，只有一个要注意的是，最终结果到Team Diff的这一步，是一个指示函数，不是一个高斯分布，需要先用矩匹配Moment Matching，将其近似为高斯分布，在进行消息传递。
如此从上往下传递消息到战斗结果为止，就是技巧水平S到战斗结果R的似然函数了，也就是公式中的likelihood
然后同样用Sum-Product算法，从下往上传递消息，直到S，就如前文边缘概率所说，这个就是技巧水平S的边缘概率Marginal
到这一步，公式完整，求出S的后验概率 posterior=likelihood*Prior/Marginal
中间具体数学推导过程不在这赘述，感兴趣的可以看文末链接里的《The Math Behind Trueskill》。
这里为了方便理解，我再用一个更加白话的方式，描述一下整个推导过程，如果上述过程已经看懂，可以跳过：
我们现在有个玩家小美，她的技巧水平是一个波动的随机值，过往经验来看是在1200分左右波动，大多数情况下，在1000-1400之间，是一个正态分布。这时她参与了一场战斗，战斗结束后她赢了对手。我们预测，以她的水平SA，在游戏内的表现，也是一个正态分布的随机范围PA，同理她的对手是PB，她跟她的对手的表现差距，也是一个正态分布的随机范围d。这时候已知的结果r告诉d，在胜利的情况下，你的随机分布需要修改一下，这样更有可能获得胜利，d说ok。然后d又告诉PA和PB，如果我这么修改，你们俩最好也修改一下，这样你们俩算出我这个d的可能性会更大。PAPB说ok，那SA你也得修改一下，这样得到我这个PA的可能性更大，SA说ok，我改，我改了，得通知一下小美，小美你的技巧应该在1300分左右波动，波动也应该减少到1250-1350之间，才有更大可能打出SA这样的技巧。经过所有节点的窃窃私语，互相传递消息后，大家都进入一种状态，这种状态就是大家都是最有可能发生这个结果的状态，所以再去互相传递消息的时候，消息开始重复没有什么新变化，达成一种平衡。
五、Trueskill结果分析
由上述的过程，我们可以得到最终结果：
更新胜负双方μ的函数如上，归一化的c值如下：
从公式可以看出，双方自身的σ越大，更新越大，因为不确定性更大，但是对手的不确定性越大，更新会趋向更少。β越大更新越小，因为较大波动的战斗规则，对实力的确定帮助也较小。
v是指高斯截断函数，在非平局情况下，v的公式为：
V的分母Φ(x)是指累积密度分布CDF，用作求随机变量小于等于x时的概率分布。
上述公式的推导过程我们不纠结，重要的是公式代表的意义。t相当于胜者和负者间预计的平均实力差距，可以看一下V有关t的函数图像：
可以看到，当t越大，说明胜者和负者预计实力差距越大，因此更新就越少。反之t越小，甚至小于0时，意味着预计实力低的人反而赢了，因此超乎意料，应该更新更多。
ε越大，更新越大，因为平局临界越大，胜利更不容易发生，因此一旦发生，对实力的更新越大。
平局时，v的公式为：
同样的，我们看看关于v关于t的函数图像：
这里是t是越接近0，更新越小，因为符合平局的预期。正数越大，我们预期的胜者扣分越多，因为预期胜者和负者实力差距越大，结果是平局，那就意味着两者实力预估偏差很大，因此更新更大，反之负数分析类似。
ε越大，更新绝对值越小，因为平局临界越大，平局更容易发生，因此对实力的更新越小。
接下来是玩家的σ的更新公式：
和μ的更新公式不一样，σ的公式是在旧的方差上乘以一个0-1之间的数，这也很好理解，每场战斗获得新信息后，不确定性或多或少都应该下降。这也是前文每场比赛加入不确定性τ的原因。可以看到和μ公式一致的是，当自身原本的不确定性越大，更新趋向越大，同样由于c的存在，对方的不确定性越大，更新趋向更小，β越大，更新趋向也越小。
在非平局情况下，w的公式为：
同样的，我们来分析一下w关于t的函数图像：
可以看到，两者预测的实力差距越大，对不确定性的更新越小，因为结果更加符合预料，因此，对缩小双方水平的不确定性没什么帮助。ε越大，更新更大，因为平局临界越大，更不容易取胜，因此对不确定性的更新越大。
在平局情况下，w的公式为：
同样的，我们来分析一下w关于t的函数图像：
和之前类似，两者预期实力越接近，平局时的不确定性就更小，因为达成平局在预料之内。因为是平局，所以ε越大，更新越小。但是我们可以看到ε=4时，t在0附近对不确定性的更新基本为0，这意味着更容易平局的战斗，对双方更新战斗力价值不大，但是对于一般游戏，平局的概率一般较低。
到这一步，我们就可以得出玩家新的技巧水平的正态分布了，将新的参数μ和σ存起来，作为下一次战斗的先验知识，如此循环，越来越接近玩家的真实水平。
玩家的rank标识
假如说有些游戏不想用独立的外显段位，就想根据玩家水平的正态分布，直接展示一个玩家能理解的rank分数，微软那边的方法是rank=μ-k*σ。然后k取3，前文提到过，正态分布99.99%概率落在μ±3倍σ之间，所以这个rank的意思就是以这个作为玩家评分，则玩家的技巧绝大概率会大于这个rank，所以称作为保守rank。
实际上我认为，不一定要用这个公式或者这个k值，但是思路上，需要保证把μ和σ都考虑进去，因为玩家的水平不只包含平均值μ，稳定性σ本身也是水平的体现。例如k=0，其实就是elo的分数，没有考虑到σ，因此并不准确。
匹配算法
匹配算法就很简单了，elo是玩家elo分接近的匹配，Trueskill就是代表玩家水平的两个正态分布，重合度越高代表水平接近，适合匹配。这里没什么讲究，直接用正态分布重合度的公式即可：
六、Trueskill优化方向
以上是Trueskill的基本原理，在理解之后，就需要针对性的根据项目进行定制调整，实际上微软也18年也提出了Trueskill2，基本原理不变，但是加入了对组队，KDA，中途退出等额外因素的考虑，结果会更精确。后面我也会研究一下Trueskill2，下面是一些我目前想到的优化方向，先列出来，后续思考实践后，再进行深入分享：
1同组多人计算方式，目前是直接相加，实际不是
可以根据双方游玩时长（我们游戏可以是回合数）等来给权重。总体思路是双方的水平发挥的百分比相加才是更客观的。更进一步，1加1大于2的情况，双方化学反应的情况，如何表现？
2目前Trueskill不关心胜利是大胜还是小胜，有优化空间
大胜小胜险胜，理论上对结果的判断可以有一个加权。或者说若是有游戏，结果表达为不是简单的胜负，就应该根据胜负差距进行更精确的处理。
3部分更新
可以根据具体情况，部分更新结果，例如网络不好，那就少更新一点（本场战斗不代表真实水平）。
4根据局内表现调整
据我们游戏，增加合适的额外考虑，例如连击数，击杀数，优化Trueskill的结果。
5随时间变化的影响
玩家长期不玩回坑，这时候σ应要变大。
6机器人的考虑
机器人在Trueskill计算中应该以一个怎么样的技巧水平作为参数，不同机器人应该需要不同的参数。
7Trueskill的扩展应用
贝叶斯方法是机器学习的重要工具，做复杂的概率处理非常强大，类似于对玩家水平的模拟，所有模糊评价某个值的问题，都可以用上。例如对关卡难度的评价，平衡性处理等等。
七、引用
1、TrueSkill: A Bayesian Skill Rating System
https://www.microsoft.com/en-us/research/wp-content/uploads/2006/01/TR-2006-80.pdf
2、TrueSkill 2: An improved Bayesian skill rating system
https://www.microsoft.com/en-us/research/uploads/prod/2018/03/trueskill2.pdf
3、The Math Behind TrueSkill
https://www.moserware.com/assets/computing-your-skill/The%20Math%20Behind%20TrueSkill.pdf
4、On Gaussian Expectation Propagation
https://www.microsoft.com/en-us/research/wp-content/uploads/2005/07/EP.pdf
5、Understanding Belief Propagation and its Generalizations
https://people.csail.mit.edu/billf/publications/Understanding_Belief_Propogation.pdf
6、Computing Your Skill
https://www.moserware.com/2010/03/computing-your-skill.html
来源：鱼塘游戏制作工坊
原文：https://mp.weixin.qq.com/s/MhAJSimzZS8JpNSOJp36Ng
评论
登录 后参与讨论
暂无评论，来抢沙发
闽公网安备 35020302034348号