游戏背后的数学 Vol. 0.6 醉汉与围棋

本文力图以最通俗易懂的语言，讲清游戏背后的数学。如果你没有看懂，说明我讲得不够好，欢迎一起探讨问题。

不好意思，最通俗的语言也就这样了。

Vol. 2写了三分之二就鸽置了。本文只是一时心血来潮写的，不是本系列的正篇，内容也不怎么充实，各位权当小品看了。最近对AlphaGo和AlphaZero的算法感兴趣，看了些文章，我发现蒙特卡洛树搜索（Monte-Carlo tree search，MCTS）起到了举足轻重的作用。许多文章通俗易懂地解释了MCTS的工作原理，但都没有阐述其背后的数学直观，于是我就来大言不惭几句。

刚接触到MCTS时，我的第一反应是，这与位势论、偏微分方程边值问题的思想是共通的。打个比方，一只蚂蚁在一根木棍上行走，每次往前走一步、往后一步的概率都是1/2，走到木棍某一端点后停止，求蚂蚁先走到端点A的概率。用p(s)表示蚂蚁起点为s时先走到端点A的概率，则p(端点A) = 1，p(端点B) = 0，而p(s)等于p(s + ε)与p(s – ε)的算术平均。当步伐ε趋于0时，蚂蚁的行动模式趋于一维布朗运动。（这在数学上是不严格的。严格讲，ε趋于0的同时步频h还得趋于无穷，而且ε的平方与h始终成反比）此外，ε趋于0时再利用Schwarz定理可得：此时p为线段AB上的调和函数（一维调和函数即为线性函数），在端点A和B分别取值1和0，这便是线段上的狄利克雷问题。“p(s)等于p(s + ε)与p(s – ε)的算术平均”，意味着p具备某种“连续性”，p在s处的值由它在s附近状态的值决定。

再考虑一个滑稽的例子，一个醉汉在大楼楼顶漫步，每次行走以相同概率往前后左右走。消防队员在楼下铺满了救生气垫，令他们不安的是，3楼某住户有一个巨大的露天阳台。醉汉落到阳台上便会死亡，落到气垫上则得救，求醉汉从s出发时得救的概率。当醉汉的步伐ε趋于0时，和之前一样，其行动模式趋于二维布朗运动，p是调和函数；而且当s在楼顶边界时，若s下方有气垫则p(s) = 1，下方有阳台时p(s) = 0。位势论有以下经典的结论：其中B是标准布朗运动，τ是布朗运动关于边界的首中时。上述命题告诉我们，可以通过模拟布朗运动去求狄利克雷问题的近似解。特别地，当f为关于气垫的示性函数时，φ便是我们所求的“生还概率”。

回到围棋。 对于一个局面s，围棋相比国际象棋更需要大局观，无法精打细算地找到一个线性的局面估值函数f(s)。但是，我们可以考虑我方对局面s的胜率p(s)，这个p与前面的p有很多相似之处：p在s处的值由p在s附近状态的值决定；在棋局结束时能判定胜负，换言之，s在边界时p(s)能求出来并且等于0或1。因此，何不用随机模拟来求p的近似解呢？

但是，前面的问题中，蚂蚁与醉汉的移动规律我们是清楚的，围棋中各位置的落子概率我们却不知道，这便是蒙特卡洛树搜索要解决的内容了。

补充：p(s) = Σp(s')q(s'), 对s的全体后续局面s‘求和，q为转移概率。蚂蚁与醉汉的例子中，q是确定的，而MCTS里要根据随机模拟的结果更新权重。