围棋算法图
来源公众号：量子位
晓查 发自 凹非寺 量子位 报道 | 公众号 QbitAI
9102年，人类依然不断回想起围棋技艺被AlphaGo所碾压的恐怖。
却也有不以为然的声音：只会下棋的AI，再厉害也还是个运动员啊！
百度说：你们错了，它还是一位数学家。
百度硅谷AI实验室的同学们，就在用这个出自谷歌DeepMind的围棋算法，解决一个比围棋复杂得多的数学问题。
为了重新训练这个算法，百度用了300张1080Ti和2080Ti显卡。
他们解决的问题，叫做“图着色问题”，又叫着色问题，属于前些天让中国奥数队全军覆没的图论。它是最著名的NP-完全问题之一。
简单来说，就是用尽可能少的颜色，给一张图的顶点上色，保证相邻顶点的颜色不重复。
10个顶点的简单版是这样的：
而复杂版……只要顶点足够多，分分钟让人类数学家无从下手，如果有512个顶点，这个问题的复杂度会比围棋高出几百个数量级。
在这个数学问题上，运动员AlphaGo表现优秀，最高能将一张图所用的颜色减少10%。
从四色定理谈起
就算你对“图论”、“着色问题”这些词有点陌生，应该也听说过“四色定理”。这是第一个由计算辅助证明的数学定理。
四色定理告诉我们，只需4种颜色我们就可以让地图上所有相邻国家的颜色互不相同。
这其实就是一个平面上的着色问题，国家可以简化为顶点，国与国之间的相邻关系可以简化为连接顶点之间的线。对于平面图而言，颜色数k最小等于几？
历史上数学家已经手工证明了五色定理（k=5），但是因为运算量太大，在将颜色数量进一步减少到四种（k=4）时却迟迟无法解决，最终在70年代靠计算机才完成证明。
一般来说，我们可以用贪心算法解决这个问题，其基本思路是：先尝试用一种颜色给尽可能多的点上色，当上一步完成后，再用第二种尽可能多地给其他点上色，然后再加入第三种、第四种等等，直到把整张图填满。
或者是用深度优先搜索算法，先一步步给图像着色，若遇到相邻点颜色相同就回溯，再换一种着色方法，直到问题解决为止。
比围棋世界更复杂
如果图的顶点数比较少，以上两种方法还可行，但随着顶点数的增加，以上两种算法的局限性就暴露了出来。
△ 用贪心算法着色和最优解的对比
贪心算法会陷入局部最优解，而深度优先搜索算法的运算量会越来越大，以至于完全不可行。
图着色问题的复杂度随着顶点数增加而急剧增长。当顶点数达到512时，其可能得状态数就达到达到了10^790，远超围棋的10^460，当然更是比全宇宙的粒子数10^80多得多。
即使中等大小图的状态数也远超围棋，如果顶点数量达到1000万，复杂度会大得惊人，相当于在1后面有4583万个0。
另外着色问题还有另一个复杂维度，围棋算法可以反复在同一张相同棋盘上进行测试，而图即使顶点相同，因为连接各点的边不相同，结构也不完全相同。
从围棋中获得启发
这些更复杂的问题对算法的训练和推理提出了极大的挑战。而AlphaGo曾在解决这类复杂问题上取得了很大的成功，研究人员也很自然的想到了用它来解决图的着色问题。
对于这类问题，我们一般采用启发式搜索算法（heuristic search），就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到达到目标。
AlphaGo使用的蒙特卡洛树搜索（MCTS）用的就是一种启发式搜索算法。
△ 蒙特卡洛树搜索算法示意图：选择路径；扩展树；由神经网络执行模拟；将最终结果反向传播，更新路径节点。
AlphaGo下棋通过正是这种方法，计算当前棋盘上获胜概率最大的点，直到赢棋为止。
图着色问题与围棋也有类似之处，它的每一步棋就是给接下来的点填上颜色。它和围棋和象棋一样都可以用强化学习来解决问题，差别则是奖励。
在图着色问题中，最明显的奖励选择是颜色种类，使用的种类越少越好。而在围棋和象棋中，奖励是游戏的胜负结果。
在棋类游戏中，让算法在自我对弈中进化是很一件很自然的事，让表现最好的学习算法与自己对抗，这就是AlphaGo的升级版本AlphaGo Zero。
AlphaGo Zero没有学习人类棋谱，它只是懂得围棋规则，在不断的对弈中获得提高，谷歌只用了21天，就让这个0基础的升级版打败了5-0战胜柯洁的AlphaGo Master版。
当AlphaGo进化到自学版本AlphaGo Zero后，它就更适合做图着色问题了，因为着色问题是没有所谓“人类棋谱”可以学习的。
在图着色问题种，研究人员让AlphaGo Zero与其他算法比赛，看谁用的颜色种类少，这就是算法的奖励机制。
原理
和AlphaGo一样，图着色算法也有策略网络（p-network）和价值网络（v-network），p是顶点涂某种颜色的概率，v是最终颜色数量少于之前最佳算法结果的概率。
而在围棋游戏中，p代表落子位置的概率，v代表最终获胜的概率。
为此，研究人员设计了一个快速着色网络（FastColorNet）。
对于这个网络，有如下要求：
1、可扩展性（Scalability）：线性O（V）或线性对数O（E+VlogV）时间复杂度，保证它在更大的图形（比如1000万顶点）上也能使用。
2、完整图形上下文（Full Graph Context）：不同的图有不同的着色策略，因此网络需要有图形结构的信息。
我们将该网络的损失定义为：
π代表当前行走步数，z代表当前使用的颜色数。
上图就是FastColorNet的架构。它的输入包含两个部分：问题上下文（problem context）和可能颜色上下文（possible color context）。
问题上下文（problem context）是根据刚刚着色的顶点，来安排接下来对哪些顶点进行着色。它在任务开始和结束的时候都是零。问题上下文中包含的顶点数是一个超参数，在实验中设置为8。
可能颜色上下文（possible color context）是以上顶点集合每种可能用到的颜色。它也是一个超参数，在实验中设置为4。
以上两个上下文都输入当策略网络和价值网络中。
策略网络使用全局图形上下文（global graph context），它负责计算将每个颜色选择分配给当前顶点的概率。
随着填充过程的进行，颜色数量会逐渐增加。为了支持颜色数量的变化，它会首先独立处理每种颜色，产生一个非标准化分数，然后通过seq2seq模型对该分数进行处理，该模型还会考虑与其他颜色的依赖性。最终通过softmax操作得出归一化的填充颜色概率。
策略网络利用了具有相同颜色的节点之间的局部关系，提高了准确性，同时还降低了大图计算的时间复杂度。
价值网络负责从输入数据预测着色问题最终的结果。 问题上下文（problem context）中的顶点与着色顺序存储在对应的序列中。使用seq2seq模型处理此序列，然后将这个序列与图形上下文（graph context）组合起来，并将它们馈送到完全连接的reLU层中，最终结果输入softmax，计算出胜利、失败或平局的概率。
结果
研究人员用FastColorNet的强化学习过程来训练图着色问题，图形大小从32个顶点到1000万个顶点不等。
上图显示了图所需颜色的数量如何随顶点数量的增长而增长。
在32K到16M个顶点的图上进行测试，FastColor在训练集中使用的颜色比以往的启发式搜索算法提高了5%-10%。 尽管在测试集有所逊色，但性能也比先前的算法高出1%-2%。
虽然提升比例看起来不高，但这种算法显示出解决此类问题的潜力。Twitter上一位网友这样评价：这篇文章以线性复杂度O（n）解决了一个NP完全问题。
论文地址：https：//arxiv.org/abs/1902.10162
— 完 —
订阅AI内参，获取AI行业资讯
购买AI书籍
诚挚招聘
量子位正在招募编辑/记者，工作地点在北京中关村。期待有才气、有热情的同学加入我们！相关细节，请在量子位公众号（QbitAI）对话界面，回复“招聘”两个字。
量子位 QbitAI · 头条号签约作者
