并行思想的六子棋博弈搜索算法设计

安徽财经大学计算机科学与技术系 邓银莹 常 郝

搜索算法是计算机博弈的核心问题，其好坏对整个系统产生直接影响。通过对计算机六子棋博弈中搜索算法的研究，将Alpha-Beta剪枝、深度优先搜索、极大极小值、深度学习四种算法并行结合，使计算机在对抗过程中综合选取最佳落子点，借此提高机器博弈水平，使计算机博弈更加灵活高效。

1 六子棋搜索策略发展现状及研究意义

计算机博弈是人工智能领域一个重要且具有挑战性的研究分支，包括五子棋、军旗等棋牌游戏。六子棋以规则简单、局面复杂的特点吸引玩家前来研究与挑战，其设计包含数据结构、搜索算法、估值函数、着法生成四部分。六子棋落子需综合评估两步棋的状态，而如何让这两步棋发挥最大作用，是研究的难点所在。

1.1 六子棋搜索策略发展现状

2005年六子棋出现至今，虽与五子棋略有相似，但由于六子棋每轮每方可落两子，最后的局面由两子统一评定，所以它的计算复杂度相当于五子棋的两倍，利用研究五子棋的方法无法完全解决六子棋博弈问题。因此许多研究者开始寻找其它策略，应对六子棋出现后的新挑战。

目前已研究的六子棋搜索策略包括极大极小搜索、Alpha-Beta剪枝、深度优先搜索、蒙特卡洛搜索、深度学习等。这些方法或多或少在提高程序搜索效率，提升博弈研究水平方面做出贡献，也为后来者进一步研究与优化提供理论支持与方向。

1.2 当前研究存在不足

目前六子棋的搜索算法多样，但存在以下缺点：1）算法在计算机中串行执行，无法充分利用CPU并行计算优势。2）部分算法因搜索时间长，无法在既定时间内完成最佳落子的查找与判定。3）部分算法虽耗时短，但因搜索不充分导致落子策略存在缺陷。

1.3 研究意义

对六子棋博弈搜索技术的研究，一方面是为找出更佳的搜索策略，能够在更短的时间进行更深、更广的搜索，从而提高六子棋博弈水平，更好地解决计算机博弈中的问题。另一方面通过学习并行计算相关知识，研究计算机博弈算法并行可行性，借此加深对机器博弈的理解与应用，推动未来人类智能领域发展。

2 搜索技术分析

搜索算法能从当前局面找出合适落子点进行棋局。当局面逐渐复杂时，简单的搜索并不能有效找到最佳落子点，针对不同位置还应考虑落子后的发展情况。因此，为了更加有效地利用搜索算法，在提高落子质量的同时，对搜索深度与存储空间进行合理分配，从而达到优化程序的目的，下面介绍几种博弈搜索算法。搜索算法优缺点对比表1所示。

表1 搜索算法优缺点对比

2.1 深度优先搜索

深度优先搜索与树的先序遍历类似，对每一个可能的分支进行深入查找。访问后更改当前结点状态，保证每个结点只访问一次。当某个分支访问至叶子结点，则进行回溯，查找相邻结点进行访问。

2.2 极大极小值搜索

假设双方每次落子为最佳走法，而落子后双方都需通过估值函数评价各自棋局好坏。对于己方必是选取最优落子点，同时认为对方选取的也是最优落子，因此选择估值最低的局面开展博弈树。

2.3 Alpha-Beta剪枝搜索

Alpha-Beta剪枝以极大极小值搜索为基础，通过排除搜索后的无用结点节省搜索空间，提高算法效率。对于极大值情况，保留最大分支；对于极小值情况，保留最小分支。

2.4 深度学习搜素

深度学习旨在建立一个模拟人脑的神经网络，设定当前局面为输入层，下一步落棋点为输出层，在隐藏层中利用六子棋规则筛选落子点，给不同棋子位置设定不同概率，经过训练得到最优解。

3 算法设计

3.1 并行处理

并行计算将任务分为多个小对象，使计算机能同时处理多个程序，从而加快计算机整体运行速度，提高完成效率。其难点在于，找到程序中可以并行运算的部分。

图1表示同时执行四种搜索算法，综合得到的落子并选取最佳落子点，使各算法得到充分利用，避免单个算法带来的局限性。

图1 并行算法流程图

3.2 估值函数

博弈程序的落子点判断，主要由搜索策略和估值函数配合完成。对于棋局的判断，以基于“路”的搜索为基础，在搜索中无需考虑棋形分布，只需查找某条路上是否存在六子，即可判断胜负。每条路由某个点位以及与之相连的5个点组成，统计该条路上棋子个数，并用二进制将信息存储。接着调用估值函数，给不同路赋予不同分值，最后综合分值选出最优落子策略。相比基于“棋形”的搜索，该方法节省大量匹配时间，便于对当前棋局的评估。连子估值如表2所示。

表2 连子估值表

估值函数的判定需参考固定子力值、棋子位置值、棋子灵活度值、威胁与保护值、动态调整值五要素。上表为最初参数设定，还需通过不断测试找到更合适的权值，从而完善程序，提高棋力。

3.3 走法生成与选择

走法生成是指将当前局面所有合理走法罗列出的模块，也是用以告知计算机下一步走法的部分。通过并行计算得到每种搜索方式提供的最佳走法，再进行模拟比较，选择分值最高的落子点作为之后的博弈策略。

图2代表一副棋局，接下来由计算机执行程序确定两颗白子下落位置。表3列出计算机并行处理四种搜索算法得到的两颗落子坐标，以及利用估值函数得到的棋子分值。由表可知，深度学习算法得到的落子分值最高，为最佳落子。

最佳落子的选择利用贪心思想，选取分值最高者为最终结果，但可能存在一定误差。因此还需考虑不同搜索算法所消耗时间、对之后棋局的影响等因素，综合判断后再做定夺。

图2 某时刻棋局图

表3 落子分值表

总结：随着计算机博弈不断发展，单一算法不足以适应复杂多变的棋局状况。本文通过对计算机博弈中六子棋搜索技术的研究，结合并行算法，为计算机博弈搜索策略提供新思路与研究方向。