论文部分内容阅读
机器博弈是人工智能学科的一个重要课题,是人工智能的“果蝇”,是检验利用智能方法解决复杂问题效果的试金石,其研究内容与人工智能和人类智慧都具有紧密的相关性。早在上世纪60年代,Semual采用自学习方法编写的西洋跳棋程序就战胜了人类高手,一度引发了空前的轰动。在2005年,吴毅成教授首先提出了六子棋,其难度远远超过五子棋。由于Go-Moku和Renju这两种常见的五子棋博弈问题已经被成功地破解,六子棋便成为k子棋机器博弈研究中的新的挑战性问题。必须指出,已有的五子棋和六子棋机器博弈研究对相应棋类的复杂度均有着不同程度的高估,这反映了k子棋机器博弈的相关研究存在着重大的缺陷。以六子棋的机器博弈问题为对象,针对其研究现状,本文提出了基于连珠模式的六子棋机器博弈模型——CPBIM,旨在纠正现存研究成果之中的误区,进而提高k子棋机器博弈的研究水平。在CPBIM的基础上,围绕着机器博弈的关键性技术,对包括数据和知识的表示、搜索算法、估值方法、着法生成和排序等各个方面,分别展开了深入的研究。本文的创新性研究成果主要包括:(1)提出了一种基于“连珠”模式的六子棋机器博弈模型—CPBIM (Connection-Pattern Based Incremental Model),并将该模型推广到一族k子棋中。首先,提出了一种不同于传统模式的新模式——连珠,从而在局面的表示及分析方面,直接改善了程序的效率。接着,为了让连珠更好地表达领域的高级知识,提出了从低级的具体知识自动地推导出高级的抽象知识的方法,得到了一个严格且完善的连珠分类体系。然后,为了有效地解决k子棋博弈复杂度被严重高估的问题,提出了一种交叉点类型体系,从而保证程序有能力从众多候选点中过滤掉那些对博弈结果毫无影响的候选着法,还为实现高效的着法排序提供了关键性的支持。最后,为了加强博弈程序对高级知识的利用和提高程序的执行效率,结合连珠的非负整数表示法,提出了基于连珠来构建知识库的方法。(2)将迭代加深(Iterative Deepening)思想应用于威胁空间搜索(Threat SpaceSearch)中,提出了DFID-TSS (Depth First Iterative Deepening Treat Space Search)搜索。新的搜索算法找到的解的路径总是最短的;在求解能力不变的条件下,新算法的平均执行时间也大为缩短。(3)为利用CPBIM所提供的领域知识来改进搜索效率,在PN(Proof Number)搜索算法的基础上,提出了PN#搜索算法。PN#在PN总是倾向于搜索一棵稀疏的博弈树的基础上,还鼓励算法更优先地和更深入地搜索较好的分枝。PN#不但提高了搜索速度,降低了内存需求,而且在算法的实现上与PN同样简洁。(4)将神经元网络与TD(λ)算法相结合,引入到估值函数的设计当中,提出了一种以先验知识引导的估值函数自学习方法。该方法不仅避免了单纯采用自学习方法时出现的收敛速度慢等问题,还易于实现。此外,为降低无用样例对学习结果的负面影响,提出用有选择的可学习序列代替完整的棋谱作为学习样例。(5)针对连珠棋候选着法多、着法排序代价高的特点,提出了分类且逐步着法排序的方法,借此来降低着法排序的高昂代价。其中,对于同类着法的排序问题,还提出了新的排序机制,在不影响区分度的情况下,将评估值的取值范围尽可能地缩小,从而能够以高效的桶排序替代常用的选择排序。(6)在开局库设计、时间控制等方面,结合六子棋或机器博弈问题的特点,在充分考虑到性能与代价之间的平衡之后,均提出了相应的优化方法。上述模型、方法及算法均已被成功地运用于六子棋机器博弈软件NEUConn6之中。在国际和国内的一系列机器博弈竞赛当中,NEUConn6都取得了良好的成绩,从实践上有力地说明了本文研究工作的正确性、有效性和实用性。