五子棋AI教程第二版九：性能优化
lihongxun945 opened this issue · 1 comments
性能优化的重要性
前面讲到的置换表其实就是最常见的一种性能优化方式。他不不会对棋力有负面影响（不会剪掉不该剪掉的分支），但是能提升运算速度从而达到提升棋力的作用。如果你把前面几章讲的技术都运用了，那么大约能实现 8 层深度的搜索，对战业余玩家会有很高的胜率。不过如果你想挑战一些对五子棋比较有研究的高级玩家，那么仅仅8层搜索是不够的。
我们知道，棋力 = 搜索深度，我们要提升电脑的棋力，最直接方式就是加大搜索深度。但是搜索深度每加深一层，时间会提升大约 20 倍，如果8层深度需要20秒，那么10层将会需要 20*20*20 = 8000秒 超过了一个小时，这显然是不能接受的。因此我们需要尽可能优化搜索的性能，提升速度，以达到更大的搜索深度。
这里介绍几种我使用的优化算法，供大家参考，另外一些比较知名的优化算法但是我没有实现的，会在文章末尾也给出链接。
评估函数的局部刷新
还记得我们开始的时候讲到的局势评估函数吗，每当棋盘上有棋子的变动，我们就会对每个位置进行一次评分，这样就会获得一个全新的评分。而事实上，如果一个棋子变动，比如棋盘上增加了一个棋子，如图，假设我们走了25，那么只会在它的米子方向上的几个位置的分数会发生变化，其余的大部分棋子分数不会有任何变化。因此当我们更新分数的时候，只需要更新这7个点即可，而不是更新24个点的分数。这样能大幅降低计算量。
另外，我还实现了一个更进一步的优化。还是上图，我们只需要更新 4, 16, 14, 15, 11, 17, 5 七个点。其中每个点的分数，都是他的四个方向的分数的和。但是这个时候，这些点其实只有一个方向上的分数发生了变化，其余三个方向的分数不会变。比如 11，其实只有纵向分数发生了变化，其余方向的分数不变。因此我们可以缓存不同方向的分数，在计算分数和的时候直接使用不变的分数。
在我的代码中有上面两种方法的实现，请参阅 board.js 中的 evaluate 函数。
米子进攻路径优化
现在我们每一层搜索，都会遍历所有的可能的点，但事实上，任何一方的进攻，其实并不是杂乱的，一般情况下，它的连续进攻路线都可以用一条折线链接起来，其中每一个节点都在上一个节点的米子方向上。比如下图：
黑棋连续进行了 19, 21, 23, 25 四步进攻，形成活四，如果我们把这四步连接起来，会发现他们形成了一条折线：
按照这个思路，我们可以在生成节点的时候，参考它的上一步，只有在上一步的米子方向上的点我们才考虑，比如 19 之后，我们就不考虑 14 右边的冲四棋，因为它无法和我们的 19 有米子方向的联系。
当然，事实上这样很容易产生误判的，比如有两种情况。
第一种情况，己方的进攻路径不一定是每一步都是上一步的米子方向。上例中其实电脑进行了一个很长的 VCT， 11, 13, 17, 19, 21, 23, 25，加上防守的棋，总共是 14 步，而其中 17 和 19 并不在对方的米子方向上。
第二种情况，在乙方VCT进攻的时候，对方在其他地方进行了一步冲四，由于必须防守，因此打乱了进攻路径，使得下一次的点很可能不在这个防守点的米子方向上。
对于第一种情况，我没有想到太好的解决方式，一种比较可行的做法是在前几步的时候可以不做米子的限制，只在后几步限制。
对于第二种情况，我的做法是标记标记进攻点，每次生成的棋是上一次进攻点的米子方向，如果被迫进行了防守，则防守的一步并不算进攻点，因而不会打乱之前的进攻路线。至于如何判断进攻点，可以参考我的代码中的实现。
进攻的时候要在米子方向，同理，防守对面的时候也肯定是在对面的进攻点的米子方向。这样做可以大幅减少需要计算的点。不过，由于对上述两种例外情况我都没有找到完美解决方式，因此电脑现在依然有一定几率出现误判。不过大部分时候，即使误判了，电脑依然走的是正确的线路。所以综合来看，由于误判而走了错棋的概率是比较小的。
冲四延伸
这是一个比较好实现的技巧。即如果发现某一方进行了冲四，则在这个节点的下增加两层搜索深度（以抵消冲四和防守这两步棋的消耗）。这样有两个好处：
- 因为冲四延伸，自己冲四可以多搜索两层，更容易发现自己的好棋
- 因为冲四延伸，可以防止对方试图通过冲四来增大深度，干扰电脑的搜索（把结果推向更深的层次）
其他一些技巧
还有其他一些我没有实现的技巧，因为篇幅限制，这里我只贴出一些链接，有兴趣的话可以自行参阅：
- 主要变例搜索 PVS
- 开局库 https://www.xqbase.com/computer/book.htm
图片失效了