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

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

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

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

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

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

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

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

1.2 当前研究存在不足

目前六子棋的搜索算法多样，但存在以下缺点：1）算法在计算机中串行执行，无法充分利用CPU并行计算优势。……