强化学习 五子棋算法
- 蒙特卡洛树搜索 MCTS
-
- 蒙特卡洛树搜索算法
- 上限置信区间算法 UCT
- Minimax算法与纳什均衡
- alpha beta剪枝
- 估值函数
- 优化与总结
本文会以AI五子棋展开，讲解一些强化学习中博弈方向的算法。
全文只涉及算法讲解，不会展现代码。
蒙特卡洛树搜索 MCTS
随着计算机算力的发展，利用随机采样的样本值来估计真实值的蒙特卡洛方法 (Monte Carlo method) 得到了充分的发挥与利用。
如上图用蒙特卡洛方法以模拟面积比例，达到求出π的近似值的目的。
以五子棋举例，在不考虑任何其他算法与规则的情况下，我们在一个棋局的空位黑白交替随机落子，直至其中一方获胜或满棋盘。在这样的随机尝试中我们会记录双方胜负并在有足够大量的数据时依据胜率评价其中的每一步。这样的算法好处巨大，它可以在理想情况下求出每一步的理论最大胜率解。
蒙特卡洛树搜索 (The monte carlo search tree) 又称随机抽样或统计试验方法，属于计算数学的一个分支。在蒙特卡洛方法的基础上，我们利用树结构来更加高效的进行结点值的更新和选择。
蒙特卡洛树搜索算法
一般来说，蒙特卡洛树搜索会有一个根结点。像这样的根结点会有模拟后续选择的子结点若干个。
以五子棋为例，若以正中的H8位为根结点，棋盘大小为15 * 15，那么根结点的后续子结点就会有15 * 15 - 1个。
若是随机落子，那么这15 * 15 - 1中的某一个子结点会继续被分配15 * 15 - 2个子结点。在棋局结束时，我们会利用反向传播将结果返回各个参与结点，并以胜率评价该结点。随着数据量的增加，每一步棋（每个结点）的胜率会被更加完善。
看起来已经大功告成，不过，这样下来，我们的空间和时间复杂度会随着回合数n变得越来越高，节点个数会达到接近 22 5 n 225^n 225n. 这样的算法明显需要耗费极大的计算空间。所以，我们将要用到UCT算法及基于minimax算法的alpha beta剪枝来减少结点的个数，同时，我们还可以用到一些小窍门，比如用估值函数来省去不必要的尝试。
上限置信区间算法 UCT
UCT算法(Upper Confidence Bound Apply to Tree)是UCB算法(Upper Confidence Bound)在蒙特卡洛树搜索中的算法。UCB算法的背景起源于一种多臂老虎机(Multi-Armed Bandit)，可以追溯到上世纪三十年代。
多臂老虎机问题描述如下：
- 老虎机有K个摇臂，每个摇臂以一定的概率吐出金币，且概率是未知的
- 玩家每次只能从K个摇臂中选择其中一个，且相邻两次选择或奖励没有任何关系
- 玩家的目的是通过一定的策略使自己的奖励最大，即得到更多的金币
要是你是一个手持筹码的赌徒，如何才能在付出最少的情况下找出回报概率最大的老虎机摇臂？UCB算法很好地解决了这个问题。想象一下，要是我们想要找出高回报的老虎机摇臂，就必须先把所有的老虎机摇臂尝试到一定次数，再根据回报率将回报率高的摇臂的尝试机会加大一些，直到数据足以确定出最高回报率的摇臂。UCB算法公式也就类似于以上的思考方法。
UCB算法公式：
A = V i + C ∗ l n ( n ) N i A = Vi + C*\sqrt \frac{ln(n)}{Ni} A=Vi+C∗Niln(n)
其中Vi表示第i个摇臂回报的次数，n表示所有摇臂的按压次数，Ni表示按压第i个摇臂的次数。C是常数，能调节高回报与高尝试次数之间的权重。
回到我们五子棋中的例子来，要是上一次落子是父结点，那么作为所有落子可能的子结点就相当于之前的k个摇臂。我们给每个子结点一个置信度A，那么Vi就是第i个子结点获胜的次数，n为所有子结点的尝试次数，也就是父结点的尝试次数，Ni为第i个子结点的尝试次数，在这里我们的C一般取 2 \sqrt2 2 。
我们每次尝试都会选择置信度最高的子结点。在一开始时，置信度高的结点一般是被选择次数少的结点，这样能够达到多次尝试所有子结点的目的。在尝试一定次数后，胜率高的结点会更有机会被再次尝试，达到筛选高胜率子结点的目的。这就是应用于MCST中的UCT算法。
Minimax算法与纳什均衡
我们在得到每一步的胜率后，就可以让AI根据当前每一步的胜率来和我们对战。不过，以当前胜率最大的结点为下一步就一定是最优的选择吗？假如你是AI，与你对弈的是能力不输于你的人类，你通过算法计算出了如图的三步所有结点中AI的胜率，图中的root为人类落子，你恪守最高胜率的信条进行选择，最后胜率会有多大？
很明显，AI在第一次做出选择时，会选择胜率为60%的结点，而棋艺高超的人类则会选择看似吃亏的65%（此处是AI胜率）结点，给AI留下60%胜率和70%胜率的两个选择。所以，最后AI的胜率只有70%。
要是AI能够看得更加长远，只盯着第三步的90%胜率的结点落子，AI能做到90%胜率的最终结果吗？不能。因为人类会在AI选择40%胜率的结点后着70%胜率的棋，AI最高只会有80%的最终胜率。
五子棋属于一种完备信息零和博弈。如果我们的对手足够聪明，依靠所有已知信息，每次都会做出最优判断，像上面有限步数的棋局预测中，我们能够做到纳什均衡 (Nash equilibrium)。
对此也诞生了Minimax算法。不妨假设图中正三角为自己，倒三角为对手，三角的子结点是可供选择的方案。
我们自己想要选到结果最大的方案，对手想尽可能阻止我们选择结果大的方案，那么从下往上看，对手的每一步一定选择结果最小的方案，即B走b1选3，C走c1选2，D走d3选2——对手步对应MIN，选择结果最小的方案。而我们自己只能走a1选3，对应MAX，选择可选结果中的最大方案。
Minimax算法一般是局部的，因为算力的限制我们无法考虑到全局情形。正如同棋类大师能推算棋局的后几步，我们可以通过后三步或后五步的预测来找到目前最适合我们的选择。不过，像后五步预测（六层思考）这样对算力的要求还是太高，我们还能不能再减少一些不必要的结点？
alpha beta剪枝
在培养果树时，我们会剪掉重叠多余的树枝来减少果树对能量的消耗，使总光合作用效率最大化。在蒙特卡洛树中同样如此。
以Minimax算法为基础，alpha beta剪枝 (Alpha Beta Pruning) 能在理想情况下上将结点复杂度n减少至 n \sqrt n n ，在随机情况下减少至 n 3 4 n^ \frac{3}{4} n43.
alpha beta剪枝算法是怎么减去结点的呢？
我们给每一个非叶子结点一个alpha值与一个beta值，图中以[alpha, beta]表示，初始alpha beta为[-∞, +∞]。整体为先左子树，返回父结点，再右子树（多叉树时为先第一个子树到父结点，再从到第二个子树，从第二个子树到父结点……以此类推）。其中从子到父时，父结点中MIN层选自己的beta、子结点中alpha或beta最小，赋给beta；MAX层选自己的alpha、子结点中alpha或beta最大，赋给alpha。从父到子时，父结点中的alpha与beta传递给子结点。当alpha大于等于beta时剪枝。
从最左下角3开始。B属MIN层，选择最小值3向上赋给beta（注意，此时只有3，12和8的叶子结点未知），B[-∞, 3]. 向下到值为12和8的结点，不变。
A属MAX层，选择最大值3赋给alpha，A[3, +∞]. C的alpha与beta传递于A，C[3, +∞].
由于C的子结点中2最小，C属MIN层，将2传递给beta，C[3, 2]. 由于3大于2，其后值为4的子结点和值为6的子结点被剪枝。C向上到A，A属MAX层，A[3, +∞]不变。
A向下到D，D[3, +∞]. D属MIN层，先看14，取最小14赋给D的beta，D[3, 14]. 再看5，5不改变D。最后看2，取最小2赋给D的beta，D[3,2]. 由于3大于2，理应剪枝，但由于后面无兄弟结点，不剪枝。返回A，A属于MAX层，A[3, +∞]不变。到此，alpha beta剪枝完毕。
估值函数
虽有UCT算法与alpha beta算法减少大量计算，但是蒙特卡洛树搜索的随机取样仍然会耗费大量不必要的算力。如果我们能够提前对子结点进行下子价值的估计，多尝试高价值结点，少尝试或不尝试低价值结点，那么我们的算力会倾向于更值得尝试的方向。
- 首先遍历每一个子结点，进行估值计算
- 该点向左遍历，出现连续同色的棋子，进行加1，cnt++
- 返回该点向右遍历，出现连续同色的棋子，进行加1，cnt++
- 若两边无封堵，则权重为cnt * cnt颜色的值（白 1，黑 -1）
- 若一边出现封堵，则权重cnt * cnt颜色的值 / 4
- 若两边封堵，则权重为0
- 若 cnt 大于等于5，权重为最大值 * 颜色的值（白 1，黑 -1）
- 其他方向同样计算一遍，总权重是每个点四个方向（行、列、左右对角线）的权重之和
优化与总结
要判断多连子与有无封堵需要四个方向简单的遍历，这里不再赘述。
估值函数可以结合改良UCT算法，让AI尽可能多地尝试高价值结点，少尝试低价值结点，不尝试无价值结点。估值函数同样可以应用于alpha beta剪枝，一般比基于胜率的alpha beta剪枝耗时更短。
本篇博客借用到了很多其他人的经验与思想，在此表示感谢。要是有更好的意见和建议，还请批评指正。
