基于认知科学的计算机围棋博弈问题的研究

论文摘要

认知科学是20世纪世界科学标志性的新兴研究门类,它作为探究人脑工作机制的前沿性尖端学科,已经引起了全世界科学家的广泛关注。由于在视觉表现形式上具有抽象、复杂的特性,计算机围棋正在成为认知科学研究的重要方向和工具。近年来,研究者大多采用Monte Carlo （MC）、Upper Confidence bounds applied to Trees （UC）、All Moves As First （AMAF）等不包含任何围棋知识的统计算法解决围棋对弈问题。本文则以不同的角度,通过研究围棋棋手的知识结构、表述形式、思维模型等,提出了一系列基于模拟人类棋手思考方式,量化棋手模糊判断结果的计算机围棋解决方案,不但有助于围棋程序棋力的提高,更有助于提升对人类认知能力的理解,促进认知科学的研究、发展,具有重要的创新意义和实用价值。论文具体的创新内容如下：1.对棋块的气划分等级。根据分级结果,可以判断棋块的安全程度,确定捕获目标,产生候选着点并对其排序。通过Memory-enhanced Test Driver （MTD（f））算法对候选点依次进行搜索,寻找出正确的捕获棋步。实验结果表明其效果较好,可以应用于计算机围棋实战中。这也为第三章计算厚势价值时确定有效子数做了必要的准备。2.对厚势价值进行量化。与传统的计算完全控制点的数量不同,本文提出了厚势的影响有如控制概率在二维空间的弥散,所有空点被控制的概率总和即为此厚势价值的思想,并为此设计了一种棋子影响函数,建立了一种计算厚势价值的数学模型；尝试将厚势的价值分为基本值和附加值两部分,进而动态地调整不同棋力下对厚势价值的不同判断,模拟了人类棋手对厚势的感觉；利用简单遗传算法对模型参数进行分级优化,获得了各个棋力层次下的厚势价值量化模型。实验结果表明该模型达到了较高精度,可以应用于计算机围棋序盘、中盘、收官等模块中,为第四章量化棋局形势的程序设计提供了基础。3.提出了一种对棋局形势进行量化评价的方法,采用获胜概率表征量化结果。通过模拟人类棋手判断形势的思考方式,以领先目数和棋局进展程度作为获胜概率的计算依据,并结合多级种群竞争消亡算法对模型参数进行了优化。当围棋程序的棋力发生变化时,只需相应调整模型中的参数,因此模型可以适用于不同棋力层次,具有较强的移植性和较高的普适性,在实验中取得了较好的效果,为第五章程序选择、确定最佳棋步奠定了基础。这种根据围棋知识构建模型、利用遗传算法确定参数的方法也可以应用于其他计算机博弈问题的解决。4.提出了一种计算机围棋中盘着手策略,包括棋步产生、评估和确定的方法。通过计算实地价值、战略价值、棋形价值和后续价值,对候选棋步进行初始评估。根据目的性差异,将棋步分为进攻和防御两部分；并结合获胜概率,计算攻防力度调整权值,从而动态调整攻击和防御棋步的评估值,寻找出最佳棋步。此方法既模拟了人类棋手在落子前的思考过程,又发挥了计算机擅于运算的特长,将动态分析、静态搜索和知识库的应用相结合,体现出一定层次的智能。5.开发了一个计算机围棋博弈系统CognitiveGo,将上述内容整合实现。每当落子前,CognitiveGo先根据模式库寻找一些可能的着点,继而根据自身棋力,对双方的实地、厚势、棋块强弱进行判断,并结合判断结果调整下一步棋的目标方向。在此过程中,模式库影响候选棋步的推荐,形势判断则影响目标之间的转换。综上所述,本文主要采用模拟人类棋手思考过程,建立相应模型的方式对计算机围棋相关问题进行研究,其研究方法和成果对于提升计算博弈智能,促进认知科学发展具有现实的应用价值和理论意义。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 围棋简介
• 1.1.2 计算机围棋简介
• 1.1.3 计算机围棋的意义
• 1.2 计算机围棋的研究现状
• 1.3 论文的研究思路与内容安排
• 第二章 吃子问题求解模型的构造
• 2.1 前言
• 2.2 确定捕获对象和捕获方法
• 2.2.1 简单吃子法
• 2.2.2 捕获对象的确定
• 2.2.3 气的分级
• 2.2.4 候选点的产生
• 2.3 搜索算法与走法排序
• 2.3.1 MTD（f）搜索算法
• 2.3.2 Hash表的迭代与走法排序
• 2.3.3 考虑对手最强的反抗路径
• 2.4 实验结果与分析
• 2.5 小结
• 第三章 厚势价值量化模型的构造
• 3.1 前言
• 3.2 厚势价值量化的理论基础
• 3.3 厚势价值的量化
• 3.3.1 影响函数
• 3.3.2 厚势价值量化模型Ⅰ:Fence Winnable
• 3.3.3 厚势价值量化模型Ⅱ:Fence Cognitive
• 3.4 实验结果与分析
• 3.5 小结
• 第四章 获胜概率量化模型的构造
• 4.1 前言
• 4.2 获胜概率模型的意义
• 4.3 获胜概率计算模型Ⅰ:Laurel Midgame
• 4.3.1 棋局进展程度
• 4.3.2 领先目数
• 4.3.3 获胜概率模型
• 4.4 获胜概率计算模型Ⅱ:Laurel Cognitive
• 4.4.1 计算方法
• 4.4.2 参数优化
• 4.5 实验结果与分析
• 4.6 小结
• 第五章 CognitiveGo着手选择与系统集成
• 5.1 前言
• 5.2 系统界面和功能
• 5.3 着手选择
• 5.3.1 着手生成
• 5.3.2 着手评估
• 5.3.3 评估值修正
• 5.3.4 最佳棋步的确定
• 5.4 小结
• 第六章 总结和展望
• 6.1 总结
• 6.2 展望
• 附录1 围棋业余5段段位证
• 附录2 围棋业余5段段位证书
• 附录3 本文所涉及的各模型信息表
• 攻读博士学位期间发表和完成的论文
• 参考文献
• 致谢