Add AI to Gobang Game

[paperplane110]

Alpha-Beta pruning: https://www.jiqizhixin.com/graph/technologies/56dbb21e-c3f9-4e06-b16a-2e28f25b26c8

[paperplane110]

Todo:

• [x] Evaluation function
• [ ] mini-max search
• [ ] alpha-beta pruning
• [ ] ...

[paperplane110]

评估函数

links：https://github.com/lihongxun945/myblog/issues/13

按照教程，评估函数返回的是整个棋盘的分数，而非某一位置的分数。

若一个一个点的遍历，对于每个点进行九个方向延伸，数棋型，会出现重复数同一个棋型的情况，这也是我想了很久没想通的地方。

今天想到了另一种方法来评估，

1. 从四个方向（横，纵，撇，捺）来遍历棋盘，每次取一行
2. 使用滑动窗口的方法来评估这一行这个方向上的分数
3. 最后汇总即为总分数

首先列出棋型，简化了对称的情况：1（黑，ai），2（白，玩家，棋盘边界）

• 连五：11111
• 活四：011110
• 死四：211110，11101，11011
• 活三：011100，011010
• 死三：211100，2011102，211010，210110，11001，10101
• 活二：001100，001010，001001
• 死二：211000，210100，210010，2011002，2010102
• 活一：0001000

注意：

• 在取每一行的时候，~认为棋盘的边界为对方的棋子~（评估对手分数会有问题），棋盘边界为-1。
• 已经对称的pattern，不要重复计分
• 活型至少有6格空间

[paperplane110]

可能有bug

[paperplane110]

问题在于由于滑动窗口，活三匹配上两次： 011100, 001110

需要添加校验逻辑，在一次 evalLine 中，同一棋子不能被两个 pattern 匹配上

或者扩展pattern为：0011100, 2011100，0011102

同理：

• 活二：001010, 010100 -> 0010100, 0010102, 2010100
• 活二：100100, 001001 -> 010010（因为 010010 可形成活三 011010、010110）

[paperplane110]

Alpha-Beta 剪枝

[paperplane110]

实现ab剪枝后，目前ai可以搜索四层，每次搜索125w节点左右，搜索时长1分钟以上。

局限：局面评估函数是一个O(n^2)复杂度的一个函数，需要优化

[paperplane110]

加速方法：

1. 判断没有棋子的情况直接返回0分
2. 使用变量，记录出现过的整行的pattern，相当于使用”记忆“的方法来加速

昨晚想到，其实每下一步棋子，只会影响其所在的四个方向的pattern的变化，因此整个棋盘的评估可以改成递推式的

• 一开始棋盘双方为0分，
• 每下一步棋，只重新计算它所影响的四行，对这四行的分值进行更新

需要考虑：是否保存每一步的历史分数

[paperplane110]

isWin function has bug