论文部分内容阅读
计算机博弈是人工智能领域最具挑战性的研究方向之一。计算机国际象棋博弈已经发展的比较成熟,计算机中国象棋博弈的难度比国际象棋有过之而无不及,但计算机中国象棋博弈的研究却十分滞后。本文借鉴计算机国际象棋博弈的成功经验,对计算机中国象棋博弈中所包含的开局库和博弈树搜索两个部分进行了深入的研究。中国象棋人机对弈的研究,具有理论和实际意义。首先,为解决开局库中由于“异途同归”现象而引发的存储空间浪费问题,提出“棋局状态”方法。针对传统中国象棋软件开局库存在着布局呆板、缺乏战略性和灵活性的问题,结合“棋局状态”的思想,设计并实现基于SQL Server数据库技术的开局库,并从时间复杂度和空间复杂度两方面论述基于数据库技术的开局库的优越性。其次,为加快中国象棋计算机博弈速度,对国际象棋中的Alpha-Beta剪枝搜索、渴望搜索和主要变例搜索等经典算法进行深入研究,提出优化着法顺序的方法,解决剪枝算法着法生成顺序造成的搜索效率低的问题;在此基础上,利用迭代深化方法可避免因“水平效应”而带来的战略性错误的优势,提出一种着法排序、迭代深化和主要变例搜索三者相结合的混合博弈树搜索算法。最后,在基于VC++ 6.0+SQL 2000的平台下实现中国象棋软件,并利用计算机所思考时间的平均值、最大值和最小值三个评定指标,将本文的方法与各种博弈树搜索算法的效率进行分析和比较。实验结果表明,当计算机使用本文提出的混合博弈树搜索算法时的博弈速度最快、棋力最高。