浅谈计算机围棋中的搜索算法

袁溪

摘要：围棋讲究的是下棋者之间的博弈，这种博弈人工智能的开发也成为相关人员研究开发的的重点课题。可以说，发展人工智能，和棋类博弈有着密不可分的关系，研究发现，大部分棋类博弈人工智能的结果是不错的， 但是围棋的成效和突破却不太有明显，本文主要对计算机围棋中的搜索算法进行了简要分析，希望对计算机围棋研究有所帮助。

关键词：计算机围棋；搜索算法

随着高科技和人工智能的快速发展，但凡人工智能技术的有所突破，都是在棋类运动人工智能的研究上有所突破，通俗说，就是人类与机器人在棋类博弈之间的较量，如果机器人战胜了人类的棋艺，那么就说明人工智能的发展进了一步。纵观在众多的棋类运动中，围棋技术的发展一直不尽如人意，困难重重。从现阶段围棋程序中，研究人员发现还有很多可以提高的空间。

一、计算机围棋的概念

在计算机围棋运行的过程中，有四方面最主要的内容，分别是全盘评价、战略评价、着法选择以及搜索策略。一个优秀的全盘评价器的编写程序难度是非常高的，目前就算是程序写出来，但要是将其运行起来其速度还是相对较为缓慢的。所以要想在此条件下对着法选择器进行编写，并达到人让人们满意的程度还是既重要又有一定难度的。通常情况下，人类在博弈时，一般不会只算眼前的一步，相反则是会进行全面的思考，以便为下一步棋子的落脚奠定基础，所以当我们与计算机进行博弈的过程中，计算机中的程序就会对对战做出相应的判断，并依据棋子的走向来计算出以下几十步的走法，而在休战时，也需要利用着法选择器，从战略大局的角度，将下一步的有利落脚点预测出来。但计算机计算出的评价结果时高时低，并不是太可靠，这时，就需要程序从不同的评价结果之间选择一个可靠的结果。在对棋子的落法进行选择时，需要依据相应的选择程序从宏观角度全方位的进行计算和预测，以保障棋子着法正确，但有时候，其选择就会与全盘器计算的落子点大致相同，此时就需要计算机来针对其战略目标进行思考。也就是说对于计算机围棋，其首要任务就是要明确战略方向，其次是棋子落脚点的选择，最后需要搜索全盘。并依据搜索结果来对其着法进行评价，选择出最为恰当和价值最高的落脚点。

二、计算机围棋的搜索算法

在计算机围棋发展的过程中，其在计算方面一共所涉及到了以下几种方法：基础、搜索以及学习算法等。其中不同的算法内也涵盖了诸多小比例算法。以下主要以搜索算法为例来予以探讨。

在博弈树上，我们能够清楚的了解到在其选择结点若为最大值时必定实在max的方向，而最小值也通常在min方向，也就说明两者之间是相互交换的，也是很典范的双人对战过程。完成这个过程的算法有很多，比如minmax算法、negmax算法、mtdf算法、alphabeta算法、failsoft算法等，这些都属于搜索算法中的小算法， 这几年，又出现了抽象证据搜索、证据数搜索，分解搜索等等。不管哪种算法，都是与人竞技的一种围棋程序，搜索算法也不例外，运行时，一定要有完整的计算和精确的时间对峙。同时，决定计算机围棋搜索算法的快慢因素主要有：状态表示、候選走法产生、确定目标状态、确定相对优势状态的静态评估函数等，因此，在使用搜索算法的同时，还需各种类的学科来完善程序，比如包含数学形态学、遗传算法、模糊学习法等算法。

我们对经典的搜索算法的性能，通过模拟数据进行了比较，可以了解到，博弈树不论是在最大结点数、最大分支数方面还是在最大深度、结点值方面其数量都是相对较大的。我们对每次搜索后记录实际搜索结点数和搜索时间（毫秒）的结果进行经典搜索算法的性能进行对比，如表所示：

从比较中可以发现，alphabeta算法和failsofta虽然所用的时间不一样，但剪枝效率最好，所用时间不同主要是因为它们的内在逻辑结构不一样。Negascout算法由于子结点的排序完全没有规律，是随机的，所以剪枝效率就稍微差了些。而minmax算法和negamax算法对所有的结点都搜索了一次，而mtdf算法因为没有采用置换表，所以造成了大量重复的搜索。

三、计算机围棋搜索算法的发展创新

计算机围棋搜索算法必须要紧跟时代步伐，不断创新。

一方面要创新计算机程序的思维模式， 探讨新的思维空间。例如，输赢搜索时，可采用直接算法来对走向目标进行确定，在棋局开始时，来对棋子的价值进行分析，明确棋子舍得。以往的搜索方式大多不能又快又准的进行判断，给出正确的指令。这就需要在程序的设计中要有常人想不到的设计，提高它的利用价值。

另一方面， 程序师对围棋程序设计的方方面面都要考虑到。比如，在程序设计算法的过程中， 机器人与人类棋手对决的关键步骤，是依据走向来对棋子每一位置落点概率进行计算，并对其落点范围加以计算，然后通过函数图像， 做出正确的判断。

参考文献：

[1]张玉琪.基于静态评估的计算机围棋UCT算法改进研究[D].导师：熊邦书；余磊.南昌航空大学，2015.

[2]岳鹏.计算机围棋中的算法研究[D].导师：邱玉辉.西南大学，2015.