论文部分内容阅读
人工智能是计算机科学的一个重要分支,与能源技术、生物工程、空间技术等并称为当今世界的尖端科技。计算机博弈是人工智能研究的一个重要方面,人类对计算机博弈的研究衍生了大量的研究成果,这些成果对更广泛的领域产生了重要影响。随着计算机博弈在Othello、Checker和国际象棋等棋类上的成功,全世界的学者又把目光投到了中国象棋、日本将棋、围棋等更为复杂的棋类上面。六子棋(Connect6)作为一种二人零和完备信息博弈,与围棋有着相近的复杂度,成为学者们研究的焦点之一。六子棋计算机博弈的关键技术包括状态表示、走法生成、状态评估、搜索引擎、开局库建立、参数优化等,本文的主要工作是围绕走法生成、状态评估、搜索引擎、开局库建立等进行研究和改进,具体的工作内容和成果如下:1.比较研究常用的棋盘状态表示法的优缺点后,借鉴比特棋盘的思想,提出了一种适用于六子棋的改进后的比特棋盘。使用该数据结构,可通过位运算快速判断各种棋型。2.深入地研究了各种Alpha-Beta搜索及改进技术后,通过编程实现了这些算法,并比较了六子棋博弈程序中这些算法间的性能差异,发现其中MTD(f)算法的性能最好。3.通过分析搜索算法的工作过程,并结合六子棋走法生成的特殊性,提出了将走法生成模块中的预置表与搜索引擎中的置换表融合在一起的改进措施,极大地避免了在搜索过程中频繁地生成走法。同时还比较了改进前后的MTD(f)算法的性能差异,证明了改进措施的有效性。4.认真研究六子棋的特点后,提出了对六子棋棋型的新定义。使用该定义可极大地降低棋形的分类难度,从而提高估值函数的运行速度。5.针对新的棋型定义,设计了一种简单可行的棋型识别方法。同时还结合改进后的比特棋盘技术实现了基于该方法的快速而有效的估值算法。6.利用哈希技术设计了一个简单的开局库,搜集并录入了31种常见开局及其对称形式,同时还录入了4个开局的关键走法及其变化。本文的创新之处有以下几点:1.在状态表示中,改进比特棋盘,使之适用于六子棋博弈程序。2.在搜索引擎中,融合预置表与置换表,降低生成走法的时间耗费,提高了搜索算法的效率。3.在六子棋理论方面,提出了新的六子棋棋型定义,简化了棋型分类。4.在棋局评估中,提出了6-8窗口法,该方法可快速有效的判断各种棋型。该方法同时也利用在走法生成中,评估各空点的价值。