【开源视界】从四色问题到玩家能力评估
| 导语 Max-Sum算法在解决多智能体系统相关的分布式约束优化问题中已经成为一个比较成熟的方案，在很多场景比如智能电网的能源优化，突发灾难AI无人机协同搜救，智能交通系统控制等都得到了实际应用。所以这里以它为主线，写了一篇小短文，也算为推广多智能体系统这个学科领域做点微不足道的贡献。
1852年，南非有位数学家叫法兰西斯·古德里(Francis Guthrie)，他提出了一个问题“能否只用四种颜色就可以给所有的地图染色？”这个如今广为人知的问题，却在当时持续困扰了数学家们120多年，直到1976年，才被两位数学家凯尼斯·阿佩尔(Kenneth Appel)和沃夫冈·哈肯(Wolfgang Haken)借助计算机证明。
Francis Guthrie (图片来源: Wikipedia)
对于大多数人来讲，这个定理是怎么证明的，其实无所谓。只是既然证明了，以后解决类似问题自然也更加理直气壮了些。比如说要写个地图着色程序，那么如果第一层for循环是遍历地图上的国家，那第二层for循环很可能就是for color=1 to 4。反正背后有数学家撑腰，也不用担心代码死循环出不来了。
再也不用担心代码死循环出不来了
不过今天这里我们来换个思路：
假如现在地图上，每个区域都有一个小机器人，每个小机器人只负责自己所在区域使用什么颜色，同时每个小机器人也可以跟邻居区域的机器人互相通信，但每个小机器人不能修改其它区域的颜色，也不能直接与非相邻区域的机器人通信(可以委托传话)。
现在请给这些机器人设计一套AI算法，让它们能够完成整张地图的四色填充。
如果去网上搜一下Four-color problem，能搜到像这样各种奇怪的填色地图
或许大家已经注意到了，这里我们引入了“给每个区域的小机器人写AI”这样的设定，使得这个问题不再是上帝视角，而是要从每个机器人个体的视角来解决问题。
或许这个问题大家可能会有千奇百怪的解法，不过这里，我们来讲一种叫做max-sum的算法。
Max-sum的方法是基于一种叫factor graph(因子图)的理论。简单讲一下这个理论是这样的：
(下面会有较长公式，可以粗略看一下或者跳到后面例子)
对于函数 ，
这里
或者我们干脆举个例子：
这样就是把函数g因子分解为f1, f2, f3, f4，这里我们还可以把它画成图：
这里可以很直观地看出每个f函数和与其相关的x变量。
另外还有一个边际函数：
这个函数是什么意思呢？我们可以简单地把函数g想象成概率密度函数p(x)，那么gk(Xk)就变成了随机变量Xk的概率密度函数，这个公式是不是顿时就变成概率论的基础公式了？
那么这样做有什么用呢？
首先，如果是对每个X计算g(X)，那么正常来讲每次都要计算g(X1, X2, ..., Xn)。但从上面的图可以看出，不是所有的X互相之间都是相关的。而如果做了因子分解之后，每次只需要计算跟当前X相关的f函数，其它无关的f函数的结果是可以复用的，这样就减少了计算量；
同时，将函数g因子化之后，我们可以同时计算不同的函数f，这样也提高了运算的并行程度。
另外我们注意到：把函数g因子分解那一步，得到的函数f是相乘的，而下面求边际函数那一步则是相加求和。
所以，这个算法就叫做sum-product。
那么，实际计算的时候，通常是用一种message passing的方法。我们还是看这个图
传递的message分为两种，一种是从变量结点传给函数结点，记做q；另一种是从函数结点传给变量结点，记做r。
从变量n传给函数m:
M(n)表示与变量结点n相连的所有函数结点的集合
从函数m传给变量n:
N(m)表示与函数结点m相连的所有变量结点的集合
这里简单解释一下：比如变量X2拿到了函数f2和f3的消息，那么X2计算f2乘以f3，再传给f4，这样f4就可以通过X2得到f2和f3的结果；之后f4把结果跟自己相乘，再传给X3，这样X3就拿到了从X2传来的结果。
另外消息传播是并行的，也就是说f4在把X2的结果传给X3的时候，也可以把来自X3的结果传给X2，这样经过足够多次消息传播之后，所有的结点都能够拿到整个图的结果。
接下来我们把目标再稍做修改，假设我们想计算使gk(Xk)最大的Xk的值，那么我们需要把上面两个式子修改一下：
然后之前对于求边际函数的计算就变成求最大值的计算:
这个就叫做Max-Product
最后，如果我们把q和r都取log，log后的函数记做Q和R，就变成了:
那么边际函数就是：
而最大值为：
这就到了我们今天的主题: max-sum算法。
那么回到我们的四色问题，我们用一个简单的例子来解释max-sum算法
假设现在是一张很简单的地图，只有左中右三块区域，左中、中右相邻，但左右不相邻，同时我们限定只能用两种颜色01填充。
如果抽象成图就是这样：
把它画成因子图，就变成：
对于每个区域，它与相邻的区域如果颜色相同，则会被扣分，写作效益(Utility)公式就是：
这里γm (xm ) << 1表示该区域的颜色偏好，如γ1 (x1)=[0.1, -0.1]就表示x1对颜色0的偏好为0.1，对颜色1的偏好为-0.1，这个主要是为了避免当两种颜色都可选时，不知道应该选那个的纠结情况。
整个max-sum的消息传递过程用一个流程表示就是：
首先步骤0先是初始化颜色偏好；
步骤1时，函数结点1拿到从变量结点1和2发送的消息Q1->1和Q2->1，然后计算出发给变量节点1和2的消息R1->2和R1->1，这里消息的内容就是对两种颜色的收益(比如R1->2的消息就是[-0.1, 0.1])
当变量节点收到所有相邻的函数节点发来的消息时，就能算出自己最优的解了，比如步骤2时x1得到[0.1, -0.1]，因此选择颜色0
这里有个max-sum的python实现，里面就有上面的地图上色的例子，可以结合代码看一下
https://github.com/andry91/Max_Sum_Python
(他的代码运行的时候有个小bug，要手动创建reportG/FactorGraph和reportC/Charts这两个文件夹)
Max-sum在四色问题中的应用，其实是一种用分布式去中心化的算法做优化的思想，这类优化问题我们称为DCOP(distributed constraint optimization problems)，而max-sum由于可以把优化目标分解为多个子目标相加的形式，并且非常适合分布式优化计算，所以目前是这类问题的一种主流解决方法。
这里我们从factor-graph介绍了因子图的思想，再到sum-product求边际值和message passing的消息传递方法，最后引申到max-sum做分布式求最优解。大家应该开始对这种思路稍微熟悉了，那么这与游戏能力评估有什么关系呢？
当前很多游戏会用Elo算法给玩家能力打分，因为Elo计算相对简单方便，但Elo往往只能用来衡量玩家之间相对实力的平均水平，但对玩家发挥的稳定性描述不足，因此每当用来比较估计双方对战胜率时，结果很难估计准确。
而TrueSkill算法则包含了玩家能力均值和方差，从而直接描述玩家能力的近似概率分布，这样在比较两名玩家实力时，能够相对Elo更准确地给出胜率的估计。
而TrueSkill恰恰也用到了factor-graph模型和sum-product的来计算玩家能力的分布(当然还用到了一些其它的理论，比如Expectation Propagation算法)，这一点可以在TrueSkill的开源项目中看到：
https://github.com/sublee/trueskill
该项目的主要代码，就是trueskill目录下的factorgraph.py文件，可以结合TrueSkill论文中的这张图来看
这里和max-sum不同，它并没有用到去中心化的思想，算法重点也不是放在分布式上。它的计算过程可以分为两个message update阶段：从上往下和从下往上，从上往下(浅色箭头)计算出每个team的能力分布，然后比较每个队伍之间的表现(图中圆圈数字顺序依次计算)，最后根据后验从下往上更新能力的均值和方差。这两个过程可以参考factorgraph.py中每个factor的up和down方法。
更多关于TrueSkill的介绍，还可以参考https://trueskill.org/。
文章中部分公式及截图来源:
Farinelli, A., Rogers, A., Petcu, A. and Jennings, N.R., 2008. Decentralised coordination of low-power embedded devices using the max-sum algorithm.
以及Google Image搜索和Wikipedia
走近鹅厂专家 | Ta们靠什么成为专家？
