基于UCT的围棋引擎的研究与实现.doc

摘 要 棋类博弈是人工智能的重要研究主题之一。而在围棋方面，由于围棋的有哪些信誉好的足球投注网站空间太大、计算机难于处理模糊概念且难于设计学习算法，目前最优秀的围棋程序的水平还处于业余低段水平。计算机围棋被认为是在继国际象棋之后人工智能领域中最困难的新挑战之一。围棋是检验人工智能发展水平的良好环境，如何提高围棋程序的棋力是人工智能领域的一大难题。所以计算机围棋研究具有重要的理论意义和实用价值。 本论文将介绍如何基于UCT算法设计和实现围棋引擎。第一部分介绍了计算机围棋研究背景及意义、研究状况和关键技术，包括Monte Carlo方法和UCT算法的理论。第二部分在围棋引擎总体概述的基础上说明其总体功能模块，并对各个子功能模块进行描述，重点讲解了交替下子的流程以及棋步产生模块。第三部分阐明了基于UCT算法的围棋引擎的设计，先设计围棋引擎的总体流程，再依次说明UCT算法流程、棋步合法性的判断等模块的具体设计流程。第四部分探讨了基于UCT算法的围棋引擎的实现，在分析围棋引擎核心模块UCT算法实现的基础上，详细说明了候选步的产生及管理机制，节点的UCT选择，展开节点和棋局模拟，分析指出不同的因素和策略对计算机围棋引擎的影响，其中棋局模拟的着手库模式匹配和其它围棋知识对加强程序棋力有至关重要的作用。最后对主要工作做了总结，提出进一步的发展目标。 基于上述内容，实现了一个基于UCT算法的围棋引擎Tao Go，支持GMP、GTP围棋协议，SGF文件调试输出和统计UCT模拟棋局的数据，目前能正常与围棋客户端进行通信，实现人机和机机对弈。 关键词：人工智能 计算机围棋 UCT算法 模式匹配 目 录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc260254443 1 绪论 PAGEREF _Toc260254443 \h 1 HYPERLINK \l _Toc260254444 1.1 研究背景及意义 PAGEREF _Toc260254444 \h 1 HYPERLINK \l _Toc260254445 1.2 研究状况 PAGEREF _Toc260254445 \h 1 HYPERLINK \l _Toc260254446 1.3 关键技术 PAGEREF _Toc260254446 \h 2 HYPERLINK \l _Toc260254447 1.3.1 Monte Carlo方法 PAGEREF _Toc260254447 \h 2 HYPERLINK \l _Toc260254448 1.3.2 UCT算法 PAGEREF _Toc260254448 \h 2 HYPERLINK \l _Toc260254449 2 基于UCT的围棋引擎的概述 PAGEREF _Toc260254449 \h 5 HYPERLINK \l _Toc260254450 2.1 围棋引擎的总体概述 PAGEREF _Toc260254450 \h 5 HYPERLINK \l _Toc260254451 2.2 围棋引擎的总体功能模块 PAGEREF _Toc260254451 \h 5 HYPERLINK \l _Toc260254452 2.3 交替下子流程模块 PAGEREF _Toc260254452 \h 7 HYPERLINK \l _Toc260254453 2.4 棋步产生(UCT)模块 PAGEREF _Toc260254453 \h 8 HYPERLINK \l _Toc260254454 2.5 棋步合法性判断模块 PAGEREF _Toc260254454 \h 9 HYPERLINK \l _Toc260254455 2.6 算气模块 PAGEREF _Toc260254455 \h 9 HYPERLINK \l _Toc260254456 2.7 更新棋盘(提子)模块 PAGEREF _Toc260254456 \h 10 HYPERLINK \l _Toc260254457 2.8 胜负计算模块 PAGEREF _Toc260254457 \h 10 HYPERLINK \l _Toc260254458 3 基于UCT的围棋引擎的设计 PAGEREF _Toc260254458 \h 11 HYPERLINK \l _Toc260254459 3.1 围棋引擎总体流程设计 PAGEREF _Toc260254459 \h 11 HYPERLINK \l _Toc260254460 3.2 UCT算法具体流程设计 PAGEREF _Toc260254460 \h 12 HYPERLINK \l _Toc260254461