论文部分内容阅读
人工智能是近年来很活跃的研究领域之一。计算机博弈是人工智能研究的一个重要分支,它的研究为人工智能带来了很多重要的方法和理论,产生了广泛的社会影响和学术影响。国内外对博弈的研究已经较为广泛,特别是IBM的国际象棋程序“深蓝”,已经达到了人类的世界冠军水平。“深蓝”的研究成果,特别是基于剪枝的极大极小树搜索技术为设计其它的计算机棋类博奕系统提供了良好的参照。但是不同的棋类博奕,其规则的千差万别赋予了每一种棋类博奕特殊的专业知识。这就必然要求设计一个具体的棋类博奕系统时应该深入研究它的基本原理和内在规律。本文以计算机五子棋博奕系统做为研究课题,在对大量的相关文献进行分析研究的基础上,首先按照人工智能和计算机博奕的一般原理设计了一个五子棋博奕系统的基本模型,所做的工作包括三个方面:第一研究了五子棋在计算机中的表示问题,讨论了计算机中存贮棋局和识别下棋次序,局势状态变化及局势特征、走法产生等方法。第二研究了博弈树的极小极大搜索技术及在此基础上的Alpha-Beta剪枝过程和剪枝优化问题。实现将候选的后继节点按位置邻近顺序排序,使剪枝过程得到优化。此外还研究了Alpha-Beta剪枝的改进算法NegaScout算法,此算法首先采用一小的有限Alpha-Beta窗口,以确定实际估计值的范围,再在这个较小的范围中搜索实际的估计值。由于在较小的范围中搜索,效率能得以提高。第三根据五子棋的特点,提取棋局局势的若干特征,对这些特征赋加权分,并对整个棋局进行特征统计,采用一个线性函数求得棋局的总估计分值。实践中,采用极小极大搜索加此静态估值技术的初版程序,达到了比初学者强的水平,一些比较熟练的业余人员时常也会负于此程序。在上述工作的基础上,本文的创新性研究主要包括以下两个方面:第一对五子棋博奕的专业知识进行了认真的整理,针对五子棋博奕规则简单、局势判断清楚的特点,对五子棋常见的开局、定式及其后的对局做了细致的统计分析,阐明了五子棋对奕中黑白双方优劣势并非均衡的规律,这一规律作为一个指导原则在设计五子棋博奕系统时起到重要作用。第二针对初版程序中存在的缺点和不足,通过查找原因,实现了算法的优化和加强。初版程序在运行时其搜索速度和对奕表现不能让人满意。其主要原因有两个:使用常规的Alpha-Beta搜索和NegaScout算法不能避免相同局面的重复节点的搜索,从而影响搜索速度;采用固定的估值法,估值的不准确使其“智力”较低,而且固定的赋值方式使其不能在对奕过程中提高棋力。解决的方法有两个:在执行常