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

贺天琦

摘 要：随着科技的发展，人工智能的开发很受追捧，博弈已经成为人工智能研究的重点目标。他们是相互促进的关系，因为人工智能的发展在很大程度上依靠博弈的发展。虽然棋类博弈的结果令人满意，但是在围棋领域却依旧不理想，没有较大的突破。因此，近年來才有众多的人力和物力投入到计算机围棋研究上。

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

观察人工智能并不长但起起落落的发展史可以发现，凡是人工智能技术的跃升，都是在棋类运动上与人类较量，进而通过机器完胜人类来证明人工智能的发展程度。但是围棋技术的发展却面临了很多难题。虽然现在的科技很发达，但是通过分析可以看出，现有的围棋程序还有待提高。对于计算机来说，在围棋方面，比较难以处理的是其中的模糊概念，因为这些是很难用算法设计的。围棋本身就是考验人智力与思维的一种博弈方式，也是因为如此，开发计算机围棋程序不仅是为了满足人类的娱乐需求，也是在考验设计者的思维是否活跃。所以，设计开发计算机围棋是很有意义的一项工程。

一、计算机围棋中的算法种类

目前的国内外市场对于围棋的研究主要有三种方法，分别是基础算法、搜索算法以及学习算法，每类算法里面包含的小型算法都是很多的。笔者着重研究的是搜索算法，所以简单地介绍一下搜索算法中小的算法种类。搜索算法中包括minmax算法、negmax算法、mtdf算法等，因为搜索算法是与人竞技的一种围棋程序，需要有完整的计算和精确的时间对峙。当然，在搜索算法中，不免会包含数学形态学、遗传算法、模糊学习法等算法来完善这道程序。

二、计算机围棋研究

这是一个不断追求超越的年代，不仅经济在发展，科技也在不断地进步。因此，对于围棋搜索算法方面的研究也没有滞后，有很多的创新点。

第一，不断地提出新的思维模式，而且在不断地完善完棋手的思维，计算机的程序在不停地探讨新的思维空间。在一盘围棋的棋局中，应该先对整盘棋局进行评估分析，经过仔细推敲来判断出棋局的死活。当然对于棋局死活的判断并非简单的事情，而且对于有些棋局也不一定能够判断出死活。虽然如此，这种思想和入手的方式是不可缺少的，从而在棋手对决时，就给棋手造成困难，让其在完胜的情况下由程序判断出的时间指数。

第二，在程序的设计中，经常会有出其不意的设计。在死活搜索中，它是通过这种搜索方式，通过直接的算法方式直接地面向目标，在棋局进行过程中，计算这颗旗子是救还是舍。但是实验发现，这种搜索方式有不足之处，就是浪费时间，不能直接地、快速地传递出正确的指令和判断。这也就需要在程序中不断改进，从而达到人性化运用，提高它的利用价值。

第三，在上面的介绍中，我们可以看到，搜索算法中还涉及数学形态学，引用了数学中的函数和计算。在程序设计算法的过程中，运用数学的函数型模式来有效计算每个旗子出现在某一位置的概率，以及棋子在落下后出现在哪一范围内的比例比较大，这是与人类棋手对决的关键一项，是不可缺少的。通过直观的函数图像反应，然后做出正确的判断，再根据数字明确地计算在对方落子后下一步该如何走，才能置对方于死地或者吃掉对方的棋子。由此可以看出，在计算机围棋设计中，程序师对围棋程序的设计考虑得很周到，这也是在不断的尝试和改进中的发光点。

第四，在数字算法的不断发掘之后，又出现了复合目标搜索算法。这种算法贵在复合的方式。这种算法主要运用简单的基本函数，通过单一的目标，对当时棋局的形式建立二维的向量，从而分析和决定棋子的下一步走向。这种算法简单，其可用率也是比较大的。

第五，在不断的开发和设计中，围棋程序搜索算法的设计师也没有让我们失望，陆续地设计出了pemis模拟库与定式库学习算法。这种算法是一种对称的棋局方式，能够在棋局中建立黑白的不同模式，可进行旋转和移动等，而且在使用的过程中所占的空间较小，对于围棋程序来说是一个很好的算法设计，在有利的情况下又不浪费所占的空间。

总之，在计算机围棋研究的过程中，不同的算法得出来的效果是不同的，在不断地探究搜索算法和完善算法时，就会发现，棋类博弈中的围棋的研究领域是很大的，而且具有很高的研究价值，促进了人类设计思维的创新。

参考文献：

[1]姜启源.数学模型[M].北京：高等教育出版社，1987.

[2]曹文君.知识库系统原理及其应用[M].上海：复旦大学出版社，1995.endprint