| 标题 | 计算机围棋相关问题研究 |
| 范文 | 摘要：在对计算机围棋存在的问题进行分析的基础上，描述了相关的数据结构，提出了块、气、评估函数等的算法思路。 关键词：计算机围棋；棋子；搜索 1 引言 围棋是二人零和有限确定完全信息游戏的一种。二人，指游戏有两个参与者；零和，一方胜则另一方负；有限，游戏不会无限进行下去；确定，不存在类似骰子游戏中那样不确定的因素；全信息，双方都知道对局的局面。 围棋的规则非常简单： ①棋盘为19×19道； ②黑先、白后，轮流在空白交叉点上下子； ③气尽提取（没有“气”的棋子要从棋盘上拿走）； ④禁止全局同形再现； ⑤最后占据交叉点多的一方为胜。 计算机围棋是研究如何让计算机下围棋的问题，它是人工智能领域中的一个重要研究课题。目前，计算机围棋的发展还很缓慢，棋力最高仅约二级（相当于初学者水平）。1997年，计算机“深蓝”就已经击败了国际象棋世界冠军卡斯帕罗夫，其它棋类计算机也可以达到很高的水平，只有围棋例外，这主要是由围棋的独特之处造成的。 2 围棋的特点 2.1 围棋搜索空间大 围棋棋盘为19×19，大于国际象棋的8×8；围棋棋局的平均手数约240步，大于国际象棋的约80步；围棋每步棋的选择（分支因子）平均约200个，大于国际象棋的约40个。开局的时候，国际象棋有38种选择，而围棋有361种选择（考虑到对称的问题，实际有55种选择；但从第二步开始，很多情况下又有360种选择……）。全部可能的局面数国际象棋数量级约10120，围棋约10300。 2.2 围棋需判断死活 对国际象棋来说，棋子基本不存在死活问题，而围棋的棋子就有死活之分。对死活的判断牵涉到很多复杂的问题。另外，围棋棋子的价值在不同状态下是不断变化的，前后差距有时非常巨大（所谓的“要子”与“废子”）。 2.3 围棋的系统性 围棋中棋子的价值不是孤立存在的，而是与所处的棋块密切相关，“块”是一组有关联的同色棋子，它构成了围棋对局中的战术单元。若把整个棋局看成一场战争，则块可看成是一支部队。 2.4 围棋的模糊性 围棋中充满模糊信息，有很多术语如“棋形”、“急所”、“大场”、“模样”等，很容易产生对棋局的不同理解。下围棋是一种融抽象思维和形象思维为一体的决策过程，除了对计算能力的要求以外，也需要凭借一定的“感觉”来行棋。 3 计算机围棋需解决的问题 3.1 数据结构 3.1.1 棋盘 棋局状态用一个19×19的二维数组表示： byte Board[19][19] 其中，0表示没有棋子，1表示有黑子，-1表示有白子。 3.1.2 棋子位置 棋子位置用一个结构表示： struct Position { byte x;//棋子的列号 byte y;//棋子的行号 int value;//下此位置时局面的评估函数值 } 3.1.3 下棋顺序 下棋顺序用栈表示，以便于悔棋及复盘研究。 3.2 算法 3.2.1 块的划分 块是围棋对局中的战术单元，计算机围棋的一个基本任务就是块的划分。好的分块算法能使计算机对当前的局面有比较正确的评估。它可用于判断棋子的安危，确定战术搜索的范围，从而产生相应的攻防着点。 块的划分主要依据棋子之间的位置关系来确定。 首先，判断棋子是否连接，连接指的是对方不可切断棋子之间的联络，如双关、尖、虎口等。 其次，棋盘上每个棋子都会对整个盘面发生影响，其中对相邻的棋子影响最大，随着距离的增加相应衰减。为此，可以给棋子周围的空位赋一个影响值，并且不同棋子对同一个空位的影响值可以叠加。若某个空位的影响值不小于一个给定的值，则认为该空位被相应颜色的棋子控制。 相连的棋子、连接的棋子及与本方控制的空位相连的棋子都被认为属于同一块。 3.2.2 气的计算 可以用递归算法，分别计算棋串中每个棋子上、下、左、右气的数目，累加得到整个棋串的气数[1]。 3.2.3 评估函数 首先，可以通过死活搜索来判断块的死活；其次，计算双方明确的地域；最后，考虑棋子对周围的辐射，也就是“势”的影响。综合以上三个要素，可以对棋局给出一个比较准确的评估值。 3.2.4 搜索算法 3.2.4.1 极大极小搜索 二人完全信息博弈中典型的人工智能方法是利用搜索博弈树以决定下一步，在国际象棋中已取得了非常好的效果。但在围棋中，由于围棋的复杂性，全宽度搜索不切实际。在此，把目标定位为如何寻找一步相对好的着法，这种情况下，搜索深度和广度可根据情况进行调整，搜索范围限制在局部搜索树中。这种搜索策略可通过极大极小（MINIMAX）搜索来实现。 极大极小搜索具体算法描述如下。 ①从起始局面出发，生成规定深度的博弈树（每个结点对应一个局面）。 ②用静态评估函数给出每个叶结点的估值。 ③对该博弈树，自底向上逐级计算每个结点的值。具体方法为：根据下一层结点的值得到博弈树上一层结点的值，若轮己方下子，结点值取下一层的最大值；若轮对方下子，则取下一层的最小值。 ④根结点选择分枝值最大的着法。 3.2.4.2 α-β剪枝 MINIMAX过程是把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树，然后再进行结点静态估值和倒推计算。如果把生成搜索树和倒推估值结合起来进行，再根据一定的条件判定，就有可能尽早修剪掉一些无用的分枝，这就是α-β过程的基本思想。 α-β过程的剪枝规则描述如下。 ①α剪枝：若任一极小值层结点的β值小于或等于它任一先辈极大值层结点的α值，即α（先辈层）≥β（后继层），则可中止该极小值层中这个MIN结点以下的搜索过程。这个MIN结点最终的倒推值就确定为这个β值。 ②β剪枝：若任一极大值层结点的α值大于或等于它任一先辈极小值层结点的β值，即α（后继层）≥β（先辈层），则可中止该极大值层中这个MAX结点以下的搜索过程。这个MAX结点最终的倒推值就确定为这个α值[2]。 α-β剪枝方法搜索得到的最佳着法与极大极小方法得到的结果是一致的，α-β剪枝并没有因为提高效率，而降低搜索的效果。在实际搜索时，并不是先生成指定深度的搜索树，再在搜索树上进行剪枝。如果这样，就失去了α-β剪枝方法的意义。在实际实现时，首先规定一个搜索深度，然后按照类似于深度优先搜索的方式，生成结点。在结点的生成过程中，如果在某一个结点处发生了剪枝，则其余未生成的结点就不再生成了。 α-β剪枝过程是二人博弈问题的一般搜索方法，实践证明，该方法可以有效地减少在搜索过程中生成的结点数，提高搜索效率。 4 结束语 围棋充满了无穷的奥妙和永恒的魅力，将人工智能技术应用于计算机围棋实践中，对围棋本身的理论研究以及人工智能科学的发展都有着重要的意义。 参考文献 [1]曹永忠. 基于互联网的围棋对弈及着手搜索系统的研究[DB/OL]. 万方数据, 2009. [2]林尧瑞，马少平．人工智能导论[M]．北京：清华大学出版社，1989：120. 作者简介：张全中，1969年生，男，硕士，工程师，围棋业余5段，研究方向为计算机应用。 |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。