五子棋人机对战系统的设计文献综述

文献综述

五子棋是一种两人对弈的纯策略型棋类游戏，通常双方分别使用黑白两色的棋子，轮流下在棋盘直线与横线的交叉点上，先在横线、直线或斜对角线上形成五子连线者获胜。

早期棋类人机博弈程序主要基于专家系统，这是一种使用大量的“如果-就”规则定义的、自上而下的系统。专家系统需要找专家花大量的时间寻找并制定相关规则，并据此赋予不同的落子位置一定权重，从而得到机器下一步的落子位置。随着博弈算法的发展，诞生了“极大极小搜索算法”，该算法通过棋局局面状态以及不同的落子策略可生成一棵极大极小搜索树，树根结点即当前局面，对应孩子结点为不同落子策略。遍历搜索树意味着寻找落子的最佳路径，每多遍历一层，相当于多考虑一步落子情况，即“下一步看三步”，遍历的树深度越深，意味着考虑的情况越多。但是由于五子棋的标准棋盘为15times;15，树的叶节点数目将会成指数增长，这将使得搜索树无比巨大，导致计算机无法遍历到更深层次。而Alpha-Beta剪枝算法则解决了这部分问题，它利用递归，并结合Alpha和Beta的关系，在搜索的同时若是遍历到了比Beta更坏的策略则停止搜索直接返回，这有效减少了对搜索树无用部分的搜索导致的资源浪费，使得在搜索结点一致的情况下，搜索深度达到了极大极小搜索的两倍。曾经比较优秀的黑石五子棋程序就是基于Alpha-Beta剪枝算法，虽然它的棋力还是远远不能达到战胜最强人类棋手的级别，不过同样基于该算法的当今最强的五子棋引擎“奕心”多次获得了“世界连珠锦标赛”冠军，其水平可见一斑，然而在以绝对优势战胜最强人类棋手的层面上还有一段路要走。

计算机围棋程序AlphaGo的横空出世给我们带来了新的展望。AlphaGo的巨大成功，来源于DeepMind团队打破了传统学术界设计类人智能学习算法的桎梏，将具有感知能力的深度学习和具有决策能力的强化学习紧密结合在一起，构成深度强化学习算法。AlphaGo主要基于深度学习、蒙特卡洛树搜索以及神经网络等算法，它的核心在于通过深度学习生成估值网络减小搜索深度，通过强化学习生成并优化策略网络来减小搜索宽度，使得搜索效率大幅提升，从而提高了胜率。强化学习模拟人类学习过程，从零开始进行自我学习，通过大量自我对弈，形成蒙特卡洛树，选择成功数量多的策略进行自我学习。

如果将深度学习算法和蒙特卡洛算法应用到五子棋程序中，让程序进行“自学”式地调整估值网络和策略网络，也许能大幅提高当前五子棋程序的棋力。深度学习作为人工智能算法之一，能够使机器更加聪明，提高计算机处理复杂事务的能力，并已经在语音识别、图像处理等诸多领域有了重大突破。不过技术的发展最终还是为人类服务的，希望这次尝试能激发更多人对人工智能的思考，并为该类人工智能算法在不同领域的应用提供更多参考。

参考文献

[1] 王长飞, 蔡强, 李海生. 智能五子棋算法的设计实现[J]. 系统仿真学报, 2009, 21(4): 1051-1051.

[2] 朱全民, 陈松乔. 五子棋算法的研究与思考[J]. 计算技术与自动化, 2006, 25(2): 71-74.