1、摘要棋类博弈是人工智能的重要研究主题之一。而在围棋方面，由于围棋的搜索空间太大、计算机难于处理模糊概念且难于设计学习算法，目前最优秀的围棋程序的水平还处于业余低段水平。计算机围棋被认为是在继国际象棋之后人工智能领域中最困难的新挑战之一。围棋是检验人工智能发展水平的良好环境，如何提高围棋程序的棋力是人工智能领域的一大难题。所以计算机围棋研究具有重要的理论意义和实用价值。本论文将介绍如何基于UCT算法设计和实现围棋引擎。第一部分介绍了计算机围棋研究背景及意义、研究状况和关键技术，包括MONTECARLO方法和UCT算法的理论。第二部分在围棋引擎总体概述的基础上说明其总体功能模块，并对各个子功能模块
2、进行描述，重点讲解了交替下子的流程以及棋步产生模块。第三部分阐明了基于UCT算法的围棋引擎的设计，先设计围棋引擎的总体流程，再依次说明UCT算法流程、棋步合法性的判断等模块的具体设计流程。第四部分探讨了基于UCT算法的围棋引擎的实现，在分析围棋引擎核心模块UCT算法实现的基础上，详细说明了候选步的产生及管理机制，节点的UCT选择，展开节点和棋局模拟，分析指出不同的因素和策略对计算机围棋引擎的影响，其中棋局模拟的着手库模式匹配和其它围棋知识对加强程序棋力有至关重要的作用。最后对主要工作做了总结，提出进一步的发展目标。基于上述内容，实现了一个基于UCT算法的围棋引擎TAOGO，支持GMP、GTP围
3、棋协议，SGF文件调试输出和统计UCT模拟棋局的数据，目前能正常与围棋客户端进行通信，实现人机和机机对弈。关键词人工智能计算机围棋UCT算法模式匹配目录1绪论111研究背景及意义112研究状况113关键技术2131MONTECARLO方法2132UCT算法22基于UCT的围棋引擎的概述521围棋引擎的总体概述522围棋引擎的总体功能模块523交替下子流程模块724棋步产生UCT模块825棋步合法性判断模块926算气模块927更新棋盘提子模块1028胜负计算模块103基于UCT的围棋引擎的设计1131围棋引擎总体流程设计1132UCT算法具体流程设计1233棋步合法性判断模块设计1434算气模块
4、设计1635更新棋盘提子模块设计1736胜负计算模块设计184基于UCT的围棋引擎的实现2041软硬件开发环境2042围棋引擎的数据结构20421棋局数据20422UCTTREE数据2143围棋引擎的UCT算法实现21431UCT算法的核心实现21432候选步的产生方式及管理机制23433选择节点UCT选择25434展开节点27435棋局模拟2944围棋引擎运行效果36441围棋协议对弈测试36442调试模式的SGF文件37443UCT模拟棋局数据统计385工作总结及未来展望3951工作总结3952未来展望39致谢40参考文献41英文摘要4311绪论11研究背景及意义博弈是人工智能的重要研究主
5、题，人工智能的发展在很大程度上得益于博弈研究的发展。1997年著名的深蓝计算机战胜国际象棋世界冠军卡斯帕罗夫成为轰动一时的新闻事件L。可以说，作为博弈研究的主要内容之一，棋类博弈得到了满意的解决，唯一的例外的是围棋，目前最优秀的围棋程序还处于业余低段水平。围棋是博弈的一种，属双人零和博弈2。它起源于3000多年前的中国，充分体现了东方人的智慧，盛行于中日韩，逐渐在欧美流行。它比国际象棋复杂得多，正因为如此，很多人工智能学家、心理学家和数学家也投入到了计算机围棋研究领域。计算机围棋这个名称来自于COMPUTERGO的直译，略显生硬。简单地说，计算机围棋就是结合人工智能技术教计算机下围棋，以达到与
6、人类棋手相抗衡的目的。由于围棋的搜索空间太大、计算机难于处理模糊概念且难于设计学习算法，造成了计算机围棋程序的棋力难于提高。围棋是检验人工智能发展水平的良好环境，如何提高围棋程序的棋力是人工智能领域的一大难题。同时，开发出与人类棋手水平相当的围棋程序也有助于对人类认知能力的理解。所以计算机围棋研究具有重要的理论意义和实用价值。12研究状况计算机围棋自ZOBRIST在1970年设计出第一个可与人对弈的程序以来3，至今已有约四十年的历史。由于围棋本身的特质，使得计算机围棋在继西洋棋、象棋之后，成为人工智能中一个相当引人注目的新挑战。然而计算机围棋的难点之一，便在于缺乏良好的局面评估函数4，使其不能
7、跟国际象棋一样，运用设计良好的局面评估函数、搜寻树以及优秀的剪枝法，即可获得不错的棋力；计算机围棋大多借鉴一些经验法则，以静态的评估为主，而动态的搜寻则仅用于局部的、目标明确的棋串攻杀，较少的全局搜寻。因此，人类的经验如何应运用于计算机围棋，就成了设计的重点。自2003年起，BOUZY试图打破这种情况5。他运用蒙特卡罗MONTECARLO方法作为评估函数，并且试图运用这一评估函数，作全局性的搜索，然而在棋力上始终没有大的突破。直到2006年，同样使用蒙特卡罗方法的程序CRAZYSTONE67，才在杜林举行的第211届计算机奥林匹克的九路围棋项目中夺得金牌。虽然如此，CRAZYSTONE仅在19
8、路围棋项目中夺得第五名，仍未撼动以人类思维为主的围棋程序GNUGO在19路围棋的地位。然而，随着基于蒙特卡罗的UCTUPPERCONFIDENCEBOUNDSAPPLIEDTOTREES搜索方法的出现，以UCT为基础的围棋程序MOGO810也逐渐在一些较非正式的比赛中崭露头角。2007年6月，第12届计算机奥林匹克于阿姆斯特丹举行，上届冠军GNUGO、亚军GOINTELLECT以及前文介绍过的CRAZYSTONE等程序均有参赛，MOGO在强敌环伺之下，以全胜战绩夺得了19路围棋项目的金牌，CRAZYSTONE也拿到了第二名，GNUGO退居第三。这象征UCT的成功，也代表一个崭新的局面的到来。1
9、3关键技术131MONTECARLO方法MONTECARLO1112方法主要理论基础是依据大数定理，在随机取样的情况下，可以获得有误差的评估值，取样的数量越多，误差将越小，评估值将越准确。将MONTECARLO方法应用于围棋13，其核心的思想是，在于通过统计许多模拟棋局的结果，进行局面的优劣判断。亦即将蒙特卡罗方法作为局面评估函数，以决定着手的好坏。其中，所谓的模拟棋局，指的是对某一目标盘面，由电脑随机落子，直到终盘而可以判定胜负为止。在随机落子时，除了基本的围棋规则外，只有一个限制不得自填眼位，这个限制是为了防止棋局无法结束而设定的。模拟棋局的结果，与目前常见的只判断黑胜或白胜不同，而是会判
10、断输赢的目数，在决定着手优劣时，则是统计此着手下所有模拟棋局平均的输赢目数来决定的。132UCT算法UCT又名UCBFORTREESEARCH，是UCBUPPERCONFIDENCEBOUND在TREESEARCH上的应用。而UCB本来是为了解决吃角子老虎机问题BANDITPROBLEM而产生的。所谓的吃角子老虎机问题，简述如下目前有若干台吃角子老虎机，每台机器可以投钱并拉动操纵杆，此时会得到收益REWARD，投钱、拉杆、得到收益的过程，称之为一个PLAY。每台吃角子老虎机有不同的收益率，倘若玩家想要在若干次的PLAY里获得最大总收益，那么该怎么做一般来说，玩家会开始动手玩，并且依照目前积累的
11、经验来决定下一次的PLAY要选择哪一台机器，这称之为开发EXPLOITATION。相对地，如果玩家不断地依照目前所获得的经验来决定，而不试图尝试其它的其他的机器，则可能会忽略收益率更高的机器，因此3适度地尝试其他机器是必须的，这称之为探险EXPLORATION。如何在开发与探险之间保持平衡，就是UCB试图解决的EXEEXPLOITATIONVSEXPLORATION问题。UCB根据目前获得的信息，配合上一个调整值，试图在开发与探险间保持平衡。大致上来说，每一次PLAY时，UCB会根据每一台机器目前的平均收益值亦即其到目前为止的表现，加上一个额外的参数，得出本次PLAY此台机器的UCB值，然后根
12、据此值，挑选出拥有最大UCB值的机器，作为本次PLAY所要选择的机器。其中，所谓额外参数，会随每一台机器被选择的次数增加而相对减少，其目的在于让选择机器时，不过分拘泥于旧有的表现，而可以适度地探索其他机器。UCB公式表示如下也称为UCB114错误未找到引用源。3错误未找到引用源。是第J台机器到目前为止的平均收益，错误未找到引用源。是第J台机器被测试的次数，N是所有机器目前被测试的总次数。让公式3的值最大的机器将是下一个被选择的机器。前项即为此台机器的过去表现，后项则是调整参数。而UCB1TUNED是相对于UCB1实验较佳的配置策略14。UCB1TUNED的公式如下错误未找到引用源。4错误未找到
13、引用源。5让公式5的值最大的机器将是下一个被告选择来测试的机器。UCTUCBFORTREESEARCH其实就是把UCB1或UCB1TUNED统称为UCB等公式运用于TREESEARCH上的一个方法14。以概念而言，UCT把每一个节点都当作是一个吃角子老虎机问题，而此节点的每一个分支，都是一台吃角子老虎的机器。选择分支，就会获得相应的收益。TREESEARCH开始时，UCT会建立一棵TREE，然后1从根节点开始2利用UCB公式计算每个子节点的UCB值，选择UCB值最高的子节点3若此子节点并非叶节点从未拜访过的节点，则由此节点开始，重复24直到遇到叶节点，则计算叶节点的收益值，并依此更新根节点到此
14、一节点路径上所有节点的收益值5由1开始重复，直到时间结束，或达到某一预设次数6由根节点的所有子节点中，选择平均收益值最高者，作为最佳节点此一节点，就是UCT的结果。42基于UCT的围棋引擎的概述21围棋引擎的总体概述计算机围棋程序通常也可称为计算机围棋引擎，具体表现为引擎本身没有也不需要实现图形围棋界面这通常是交由围棋客户端来做的，而是通过特定的围棋协议与引擎外部进行通信，如图21所示。这样的好处是逻辑简单，功能明确，只需要关注围棋引擎的核心部分，即围棋引擎是如何去思考的，并尝试产生最优棋步。如果不去考虑围棋引擎具体的思考过程，它表现出来的仅仅是它思考的最终结果，一个棋步而已。除此之外，围棋引
15、擎所做的工作就是实现对弈双方交替落子的过程，同时根据棋规进行相应的更新棋盘处理，并在棋局结束时计算胜负。事实上，围棋引擎与围棋客户端的关系可以拿IDE和编译器的关系来类比。在编译源文件的时候，首先需要设置使用哪个编译器和相应的编译参数，然后IDE会调用编译器去编译源文件，接着编译器执行编译过程，最后编译器返回编译结果给IDE，IDE则显示编译结果给用户查看。而在围棋对弈的时候，首先需要设置使用哪个围棋引擎和围棋协议参数，然后围棋客户端会通过围棋协议告诉围棋引擎为黑棋或白棋产生一个棋步，接着围棋引擎进行思考，最后围棋引擎返回思考得到的棋步给围棋客户端，围棋客户端则在棋盘上显示该棋步给围棋用户查看
16、。围棋客户端围棋协议GMP、GTP围棋引擎图21围棋引擎与围棋客户端的通信22围棋引擎的总体功能模块围棋引擎TAOGO的总体功能模块图如图22所示。其中交替下子流程功能模块是围棋引擎的总体流程。如何基于UCT产生棋步是围棋引擎的核心功能模块，在棋步产生UCT功能模块下面的五个子功能模块中除了候选步产生及管理子模块是起辅助作用以外，其它四个子功能模块实际上是一个有机联系的整体，构成围棋引擎的UCT算法流程。棋步合法性判断模块是根据围棋规则来判断一个棋步是否合法。更新棋盘提子模块是检查是否有吃子，有则提掉，并记录可能的打劫位置。胜负计算模块是在棋局结束时根据围棋规则来计算胜负。算气模块是计算一个棋
17、串的气数。5围棋引擎总体功能棋步合法性判断算气模块更新棋盘提子棋步产生UCT交替下子流程选择节点展开节点棋局模拟回馈更新候选步产生及管理胜负计算图22围棋引擎总体功能模块如图23，是围棋引擎各个模块之间的关系。可以看到，围棋引擎交替下子流程模块对外负责与围棋客户端进行通信，然后调用引擎内部其它模块进行处理。例如围棋客户端输入了对手棋步，围棋引擎交替下子流程模块会调用棋步合法性判断模块对棋步进行判断，如果合法则更新棋盘，然后调用棋步产生UCT模块产生棋步，最后输出棋步返回给围棋客户端。围棋引擎交替下子流程模块在棋局开始时，还会进行一些初始化工作，主要是商定围棋规则，在棋局结束时则计算对弈双方的胜
18、负。棋步产生UCT模块在产生棋步过程中会执行多次模拟棋局，正式对局中所需要用到的功能模块同样会被调用，包括棋步合法性判断模块、更新棋盘提子模块和胜负计算模块。算气模块作为最基础的模块，为各个模块提供依据，服务的上层的模块包括棋步产生UCT模块、棋步合法性判断模块和更新棋盘提子模块。围棋客户端围棋协议GMP、GTP围棋引擎交替下子流程棋步产生UCT输入对手棋步输出棋步棋步胜负计算更新棋盘提子棋步合法性判断算气图23围棋引擎模块间的关系623交替下子流程模块交替下子流程模块展示了围棋引擎的基本流程活动，如图24是交替下子流程模块的活动图。活动一开始是进行初始化引擎，主要是商定围棋规则和初始化围棋引
19、擎内部的一些参数和数据。然后进入对弈双方交替下子的过程，直到棋局结束。交替下子时，如果是对手下子，则从围棋引擎外部得到对手棋步，否则轮到引擎下子，此时引擎的棋步产生模块会产生合法棋步，然后输出产生的棋步到围棋引擎外部。每当有下子的动作发生，则进行更新棋盘，对棋局改变的状态进行相应的处理。当棋局结束时，根据围棋规则计算双方的胜负，如果对弈双方对计算胜负的结果没有争议，棋局正式结束，否则继续对弈。有一点需要指出的是，在这里没有明显指出得到对手棋步是否要考虑该棋步的合法性。棋步的合法性通常围棋引擎外部的围棋客户端也会判断保证，不过在设计时应该考虑加入对对手棋步的合法性判断和相应的错误处理，以保证逻辑
20、的完整性，使得棋局能够顺利进行。图24交替下子流程的活动图724棋步产生UCT模块棋步产生UCT模块使用UCT算法来产生棋步，是整个围棋引擎的核心功能模块。前面132小节已经介绍了UCT算法的理论，下面来说明UCT算法究竟是如何应用在围棋上的。UCT使用在围棋上，主要的概念，就是每个节点代表一个盘面，此节点的分支代表此盘面下的合法着手，每个分支联结到的子节点，就是原盘面加上分支代表的着手后，所产生的新盘面。一般而言，目前盘面为根节点，根节点的分支代表目前盘面下的合法着手，根节点的子节点代表根节点的盘面加上分支代表的着手后所形成的新盘面，如图25所示。ROOTABCDE图25UCTTREE的概念
21、表示，其中每个节点均记录访问次数，胜利次数，形成此节点的着手，着手颜色等信息此外，UCB公式的收益值，如前131小节所述，就是依照MONTECARLO方法的概念，用模拟棋局的结果来决定。上面132小节中UCT算法第4个步骤中，计算机收益值，在此应该改为执行模拟棋局。所谓的模拟棋局，就是给定一个盘面在此给的是叶节点所代表的盘面，由计算机接手落子，直到终局，然后判定并回传胜负结果黑胜或白胜。在此要注意的是，UCT会据此结果，更新叶节点到根节点上所有节点的收益值，也就是说，一个节点会概括承受所有子节点模拟棋局的结果。对于任一节点，其收益值为此一节点的模拟棋局胜利数/此节点被访问的次数，亦即其胜率。上
22、式中所谓的胜利数，指的是指向此节点的分支所代表的颜色黑棋或白棋在模拟时的胜利次数。8UCTTREE搜索流程总结如下UCT算法使用极小极大游戏树MINIMAXGAMETREE，搭配节点选择公式UCB公式，选择树节点，展开要测试的节点，然后使用MONTECARLO方法执行模拟棋局，最后将模拟棋局的结果回馈更新。流程示意图如图26所示。模拟棋局结果被更新到路径上所有节点中模拟一次棋局一个或多个节点被创建递归选择节点直到遇到一个叶节点为根节点选择节点展开节点回馈更新棋局模拟重复N次图26UCTTREE搜索流程示意图25棋步合法性判断模块一个棋步是否合法，是根据围棋规则来确定的，规则如下1PASS也称虚
23、着是合法的棋步，允许任何一方放弃下子权而使用虚着。黑白双方轮流在空点上落子，即不能在非空棋点上落子。2禁着点。棋盘上的任何一点，如某方下子后，该子立即呈无气状态，同时又不能提取对方的棋子。这个点叫做禁着点。3禁止全局同形。着子后不得使对方重复面临曾出现过的局面。其中打劫是全局同形最基本的情况。26算气模块当任何一方落子后，除了虚着以外，都有可能把对方的棋子提掉，这个时候就要计算与所落子相邻的所有对方棋串的气数。事实上，在判断棋步的合法性时也往往需要计算双方棋串的气数。计算棋串的气数主要采用标记法，从棋串的某一个棋子开始，先标记该棋子已访问过，然后对于该棋子四个相邻的棋点，如果相邻棋点是空点，则
24、棋串气数加1；如果相邻棋点上是对方的棋子，则无需对该方向上的相邻棋点继续进行探索；9如果相邻棋点上是己方棋子，则对该相邻棋点上的己方棋子进行同样的操作，直至计算完整个棋串的气数。27更新棋盘提子模块更新棋盘时，主要是利用计算棋串气数的功能检查是否有提子，有提子时将对方的棋串提掉，即清空对应棋串位置，并记录可能导致劫争的位置。28胜负计算模块着子完毕的棋局，采用数子法计算胜负。将双方死子清理出盘外后，对任意一方的活棋和活棋围住的点以子为单位进行计数。双方活棋之间的空点各得一半。棋盘总点数的一半点为归本数。一方总得点数超过此数为胜，等于此数为和，小于此数为负。如果有贴子，则要按照相关的规定进行计算
25、。103基于UCT的围棋引擎的设计31围棋引擎总体流程设计初始化引擎PASSXYNY/返回节点着手/FREE_TREEROOT/释放UCTTREE/22在PLAY_SIMULATION函数中变量NUM_VISITS控制节点被扩展时的次数，能降低UCTTREE节点在内存的增长速率，在相同模拟次数的情况下，增加对节点搜索模拟的次数，在一定程度上增加程序搜索的有效程度，负面影响是会减少棋步搜索的深度。在PLAY_SIMULATION函数中PLAY_RANDOM_GAME函数包含了模拟棋局的功能棋形模式匹配、长气逃子和吃子。UCT_SELECT函数中要优先选择未被访问过的子节点，这也是一个策略问题。关
26、于PLAY_RANDOM_GAME和UCT_SELECT函数的功能分别在435小节和434小节会有详细说明。至于MAKE_MOVE函数则是根据围棋规则对落子进行更新棋盘处理，关于基本围棋规则会在讨论PLAY_RANDOM_GRAME函数模拟棋局功能时进行介绍。而UPDATE_NODE函数是当模拟棋局胜利时将胜率加1，被访问次数不管胜利与否都加1。注意UPDATE_NODE更新节点信息时，模拟棋局胜负的结果对于不同深度的节点是相反的。某一深度的节点的父节点和子节点代表对方着手的节点，如果模拟棋局结果对该节点来说是胜利着手，则模拟棋局对于对方而言就是失败的，所以更新到该节点的父节点和子节点的胜负结
27、果是相反的。实际上也就是说，UCT树本质是一棵极小极大MINIMAX树，对于己方有利的棋步对对方则是不利的，反之亦然。432候选步的产生方式及管理机制/返回0代表输，1代表赢/INTPLAY_SIMULATIONNODENINTRANDOMRESULT0/NUM_VISITS次模拟直到子节点被扩展节省内存/IFNCHILDNULL/展开子节点/NODENEXTUCT_SELECTN/选择UCT值最大子节点/IFNEXTNULL/ERROR/MAKE_MOVENEXTX,NEXTY/落子/INTRESPLAY_SIMULATIONNEXT/递归选择节点/RANDOMRESULT1RESUPDAT
28、E_NODE1RANDOMRESULT,N/更新节点信息/RETURNRANDOMRESULT/返回模拟结果/23棋局一开始时，虽然棋盘上有八十一个空点，黑棋可以任意选择其一，也就是说有八十一个候选步。如此一来，游戏树的树支将缓慢递减，但是，并不时每个候选步都是合适的，根据围棋知识，选择如图41中的二十五个候选步为棋局开始的候选步。图41二十五个候选步如果一开始只有十五个空战成为候选步，必须要在适当时机，把其它空点也加入候选步中，否则，有些空点将就永远不会被选择，而造成错误。因此，需要一个候选步的产生方式及管理机制。由于每下一子称为着手，就会让周围附近的空点成为下一步合适的候选步。因此，产生候
29、选步的方式就是对于每一个空点，检查其周围是否有下子，看是否将其纳入候选步。而检查的方式是根据空点所在线，周围棋子与空点之间的距离和已下棋子的步数来判断的。其中两个棋子的距离是指两个棋子横坐标差的绝对值和纵坐标差的绝对值之和，即有P1X1,Y1和P2X2,Y2，则两个棋子距离为|P1P2|X1X2|Y1Y2|1一线空点已下棋子的步数不超过预定的步数如10时，不考虑一线空点作为候选步。达到预定的步数后，对于一线的空点，当周围有棋子在一线或二线上而且和该空点的距离小于3时，将该空点纳入候选步。如图42中，交叉点代表空点，其阴影部分代表如果这些地方有棋子，则说明该空点适合作为候选步。图42一线空点候选
30、步范围242二线空点已下棋子的步数不超过预定的步数如5时，不考虑一线空点作为候选步。达到预定的步数后，对于二线的空点，当周围纵横坐标都不超过两线所构成的矩形范围内，如果有棋子距离该空点小于4时，即类似于中国象眼的位置不考虑，则将空点纳入候选步。如图43所示，用三角形标记的地方即为象眼位置，不考虑该位置是否有棋子。图43二线空点候选步范围3三线及三线以上空点三线及三线以上空点，考虑到九路棋盘的特殊性，无条件纳入候选步。由于围棋棋盘上的空点数目是固定的，九路棋盘只有八十一个棋点，可以成为候选步的空点最多也只有八十一个，所有使用CANDIDATE_MOVE数组来保存是适合的。根据敌之要点即我之要点的
31、指导思想，这里不考虑空点是由于黑棋或白棋而纳入候选步的，简化了产生候选步操作，同时也避免错失好点。当然有时某些空点并非是要点或好点，将其纳入候选步，在展开子节点时不仅浪费了游戏树内存空间，而且增加了搜索空间，减少有效搜索次数，搜索到不好的着手的几率也会增大。这就体现了计算机围棋中不同的策略对围棋程序的影响。候选步的产生与管理是在每次落子时执行，也就是在程序的流程中只要有下子的动作，不论是展开节点还是棋局模拟时随机下子，都会使用候选步的产生与管理。433选择节点UCT选择上文中提到过的UCT_SELECT函数是从父节点中选择UCT值最大的节点进行搜索，其中UCT值的计算如下简略代码所示251可变
32、参数对UCT值的影响首先来关注子节点被访问过的情况时，UCT值的计算用以下公式计算UCTVALUEWINRATEUCTKSQRTLOGPARENTVISITS/CHILDVISITS要注意到UCTK的值是可变的，不同的值对程序的影响也不同。在CGOS上运行许多实现了基础UCT算法，使用不同参数值的围棋机器人找到最优参数值。它们使用如下方法UCB1AVGSCORECSQRTLOGN/M其中上一行的公式和UCT_SELECT函数中的计算公式实际上等价的。要注意K和C都是在根号SQRT外面的。不同参数对围棋机器人的影响如图44所示。图中NICK代表围棋机器人的名称。ELO代表等级分排行，PLTS代表
33、围棋机器人的实力，10K表示10级。C为可变参数。IFCHILDVISITS0/胜率,UCB公式的过去表现/WINRATEGET_WINRATECHILD/UCB公式过去表现调整参数/UCTVALUEWINRATEUCTKSQRTLOGPARENTVISITS/CHILDVISITSELSE/总是优先随机选择一个未访问过的子节点/UCTVALUE100001000RAND26图44可变参数对围棋机器人的影响2FPUFIRSTPLAYURGENCY当子节点从未被访问过时，使用下面的公式计算UCT值UCTVALUE100001000RAND1子节点被创建时，其被访问数和胜利数都为0。而更新节点信息
34、时，即便模拟棋局返回胜利结果，胜利数仅加1，被访问数加1。也就是说当节点被访问的次数很少时，用公式UCTVALUEWINRATEUCTKSQRTLOGPARENTVISITS/CHILDVISITS2计算出来的UCT值实际很小，远远小于用公式1计算出来的UCT值，这就确保了能够优先随机未被访问过的子节点。用公式1计算出来的UCT值，称为FPU8。将FPU值赋给未被访问过的节点。任意节点，至少被访问过一次之后，它的UCT值是根据公式2来计算。选择最高UCT值的节点来落子。因此FPU很大时能保证在开发已访问过的子节点之前探索未被访问过的节点一次。如果总是至少访问一次所有的子节点，有时这样会导致搜索
35、的低效，尤其是搜索的次数的次数相对于游戏树的节点数目不大的时候。例如一个节点如果持续返回胜利的结果，没有好的理由需要去探索其它的节点。从另一方面来说，取较小的FPU值同样可以使得不去搜索其它一些未被访问过的节点。434展开节点当节点要展开时，并不是每个候选步都是合适的。如421小节提到的，九路棋局一开始虽然有八十一个空点可以选择，但是依据围棋知识，并非八十一个空点都是合适的。因此，对于候选步有筛选的必要。将不合理的候选步予以去除，筛选的作用可以树的分支，在相同的时间或相同的模拟棋局次数，可以增加搜索的深度。每一个节点代表一个盘面，对于一个特定的盘面其候选步也是固定的。当一个节点要展开产生子节点
36、时，先对所有候选步进行筛选，将筛选后的候选步分别记录在子节点中，子节点之间以伙伴关系链接形式链接起来，将该节点的子节点指针指向链头子关点。棋局开始时，节点只有根节点，盘面上有八十一个空点可供选择，但是只有二十五个空点为合适的候选步图41，此为第一步粗略的筛选。再更进一步，由于对称的点可以视为同一个，所以，仅六个候选步需要测试。如此一来，树分支由原来的八十一缩减成六。27图45六个需要测试的候选步同样地，对于开局时，棋局可能会对称，筛选候选步时还可以进行简单的筛选，直到发现棋局不对称为止。例如图46所示，只需要考虑阴影部分即可。图46对称棋局候选步对于任何树节点，在展开子节点之前，都执行候选步筛
37、选，去除不合理的候选步，能减少树分支，增加搜索深度，进而提高搜索结果的准确性。但是，筛选的进行需要围棋知识的辅助，而且，不当的筛选有可能把合适的甚至是最佳的候选步予以去除，造成无法挽救的错误。因此，对于候选步的筛选必须谨慎地进行，不仅筛选的条件必须严谨，更需要经过测试验证以确认不会造成不必要的副作用。目前TAOGO中所使用的候选步筛选仅依据围棋基本规则，将不合法及不适合的候选步予以去除。目前归纳共有三种棋步，第一种如图47的A1，A9等棋点对黑棋而言是自杀的着手，由于使用中国围棋规则，因此自杀着手是禁着的一种。第二种是劫，如图47的H1，由于上一步黑棋下G2吃掉H2，白棋不能下，这称为打劫立即
38、反提着手，也是禁着的一种，打劫立即反提着手是围棋规则中避免棋局无法结束的一项规定，如果没有这项规定，黑白双方将会因为互相吃掉对方的子而不断地循环而让棋局无法结束。第三种是真眼，如图47中的A6，C9，D8等为白棋的真眼，是棋串死活重要的部分，白棋没有理由把自己的真眼填掉，对白棋而言是不合适的着手，对黑棋而言则是禁着。28图47禁着与打劫435棋局模拟模拟棋局的好坏是决定节点着手好坏的一个重要依据，因此，模拟棋局的合理性与正确性是相当重要的，虽然在大量的随机取样下，可以得到误差小到忽略的结果，但是，一盘棋局的比赛时间是有限的，每一个着手更需要在更短的时间内获得结果，所以，执行合理而正确的模拟棋局
39、是有其必要性的。另外，对于一些常见的棋形，人类棋手总结出其特定的比较好的着手，虽然在某些盘面下可能不是最佳的着手，但通常来说都不会太坏，对于这部分的加强就需要围棋的知识。当愈多的检查与处理被加入，模拟棋局的合理性与正确性也随之增加，但是模拟棋局的所需时间也随之增加，在相同时间内可以执行的模拟棋局的数量也就相对减少。因此，如何让模拟棋局足够合理与正确，同时不会让一盘模拟棋局的所需时间太长，将是一项困难的挑战。对此，采取的策略是先确认在相同的模拟棋局次数情况下，棋力是否有提升，再确认能在限定内时间内完成棋局比赛。在此对模拟棋局的加强方法分别说明如下1棋局结束的判断无论一盘棋局下得好坏，总得知道如何
40、判断棋局是否结束。前文中曾提到过在蒙特卡罗方法中模拟棋局用不自填眼位来确保棋局正常结束。自填眼位通常是指如图48中第一行最左边图所示，E5位置的空点相邻的四个棋点都是是同色图中为黑棋的棋子，而不考虑其周围四个对角点用交叉标记的颜色。29图48中央自填眼位的判断在中央一个空点如果周围四个对角点至少有两个被敌方棋子占据时，而不能将对方棋子杀死，该空点将成为假眼，最终会被对方打吃而自己自填眼位。即如图48第一行中，如果图中交叉点被白棋占据，E5点将成为假眼而最终自填眼位。而图48第二行则是真眼。如图49，在边、角一个空点周围的对角点如果有一个被敌方棋子占据，则该空点也会自填眼位。图49边、角自填眼位
41、的判断从上面的分析中要明确的是不自填眼位确切来说应该是不自填真眼。注意，这里的真假眼是从形状上来简单判断的，并不考虑棋串的气数和死活，因此有一些比较少见的棋形是假眼成真眼活棋的，如果把假眼填掉，会导致棋子被杀，模拟棋局失真。如图410，黑棋两个都是假眼，都因为不入气而活棋。图410双假眼成活棋30除了不自填眼位外，还涉及到公气黑棋和白棋共同拥有的气点的填充，在中国围棋规则数子法里要求填公气。围棋顾名思义就是围地，当棋子占据的地盘比较大时，难以判断一个空点是否是公气。在棋局结束时，如果有不能活棋的又没有马上被提掉的棋子，称为俘虏，也是要提掉的。另外，一块地被围起来，也很难检查是属于哪方棋子的地盘
42、。当然，还有更多的情况，可以说棋局的结束情况是相当复杂的。对此，TAOGO采取以实战为最高原则，基本的围棋规则和不自填眼位，一直下到将棋盘上所有的公气填完，提尽俘虏，活棋下成两个或两个以上真眼的棋形。这样做的好处是在结束棋局时只要黑白双方都发现没有地方可下，双方都PASS棋局即可宣告结束，而且在计算胜负时也是和中国围棋规则的数子法的精神是一致的，计算简单。不过这样下也会对模拟棋局效率有一定的影响，因为填充公气，提取俘虏，作真眼等并不会对胜负的结果有影响，如果这类棋步步数太多会浪费时间。如图411，是棋局结束时的盘面图。图411棋局结束盘面还有一个会对判断棋局结束有影响的是双活的情形。双活时如果
43、强制要求填公气，将导致被吃，对棋局的胜负可能会造成影响。如图412，E9，E8为黑白两个棋串共有，谁都不能下，强制要求填公气时填公气的一方会被吃。由于双活的情形比较少见，而判断是否双活又非常困难，简单忽略双活是可行的。31图412双活2围棋基本规则处理在模拟棋局中，有可能会选择到非法或不合理的棋步，非法的棋步因为地摊围棋的基本规则，是一定要去除的，但是不合理的棋步，如果不去除，则会造成不合理的模拟棋局。这部分使用候选步筛选方式处理，不再赘述，但是对于假眼，则是必须确认是否能成为真眼，也就是检查其斜角四个相邻的棋点是否为空点，如果是空点，表示有机会形成真眼，此时就以斜角的相邻空点任选其一为棋步，
44、如果无空点，表示此假眼已成为劫，填此假眼只是粘劫，不属于眼位。如果选择到的是对方的假眼，则要检查是否此棋步会吃掉对方棋串，也就是对方的棋串只剩一气，且其最后一气就是此假眼。如果不是，则此对方的假眼是己方的禁着。3模式匹配对于常见的棋形，人类棋士通过长期经验积累，总结出一些着手比较合理，得失大致均等，双方都能接受的定型，就是在围棋上称为定式。由于定式的数量很多，棋步较复杂，要想在快速的模拟棋局中构建一个高效的定式库，实现起来非常复杂，对于模拟次数很大的模拟棋局来说开销也太大。事实上，由于人类棋士对弈时通常采用十九路棋盘，其中许多定式也不一定适合于九路棋盘，而且九路棋盘比较小，往往开局、中盘、收官
45、等阶段的界线难以分清，可以采用的的着手相对比较少且简单。在这里，TAOGO创建了一个简单的着手库，并进行模式匹配。下面进行详细说明。围棋中有一句有名的格言“金角银边草肚皮”25，里面包含了最基本的围棋布局着子原理。角部因为具有两条边线，在这里基本可以不着子或少着子，而于外部围住即可，因此围取同样的地域，子力花费最少。边部次之，因为只有一条边线，围取同样地域，着子就得稍多一些。中央空阔，要围中央，效率就最差。32在棋局开始时，对于九路棋盘来说，只要能占据两个角，基本上在以后的对局中盘面不一定会有优势，至少能均衡双方的实力，不会落后太多。如图413，TAOGO在开局时会检查四个角是否有棋子，如果没
46、有棋子占角，则在图413中阴影部分的四个点随机选择一个位置占角。图413开局占角当四个角被全部占完之后，开始进行其它着手的模式匹配。着手库数据结构如下着手库所有的模式保存为PATTERN数组，目前共有26个。在每个着手模式中，PATN数组保存了每个着手模式的棋形中的每个棋点的位置和属性，PATLEN是着手模式棋形中棋点的数目，TRFNO是该棋形可能的变换形状的数目，PATWT是模式的值，值越大，优先选择模式值越高的着手。/模式着手位置和属性/STRUCTPATVALINTX,Y,ATT/ATT0该位置为空点（非一线）,1被对方棋子占据（非一线）,2被己方棋子占据（非一线）,3模式匹配成功，己方
47、棋子要下的位置4该位置为空（一线）,5被对方棋子占据（一线）,6被己方棋子占据（一线）/STRUCTPATTERNSTRUCTPATVALPATNMAXPC/存储模式/INTPATLEN/模式中着手棋点的数目，最大为MAXPC/INTTRFNO/匹配棋形的变换数目，通常为4或8/INTPATWT/模式的值，值越大，优先下/33着手库棋形的变换是采用转换表的方式进行，如下所示每一种棋形转换，有棋点M,N，用如下公式计算转换后棋点位置NX,MY其含义是对于模式R中棋点K进行T转换得到的棋点坐标。根据棋形的不同变换的可能数目是4或8，4对应于转换表的前四种，8代表整个转换表。模式匹配的方式是，对于棋
48、盘上所有己方所下的棋子，以该棋子为中心，检查其周围棋子的分布是否匹配着手库中的棋形，如果有多个棋形匹配成功，则根据匹配模式的值选择最高的落子。下面各举4和8种变换的着手库匹配各一例。如图414和415分别是4和8种变换的棋形，各种变换由左到时右排列。用黑棋代表己方棋子，白棋代表对方棋子，方块代表以该个己方棋子为中心进行变换和检查，交叉代表模式匹配成功时己方落子的位置，阴影部分代表匹配棋形中的空点。在图414中最左边图中E5和F5由于是对称的，故其变换只有4种。在图415中，因为棋形不规则，其变换有8种。图4144种变换棋形NXNTRFT00PATRPATNKXTRFT01PATRPATNKYM
49、YMTRFT10PATRPATNKXTRFT11PATRPATNKYSTATICINTTRF8221,0,0,1,/线性转换/1,0,0,1,/反转/0,1,1,0,/旋转90度/0,1,1,0,/旋转90度同时反转/1,0,0,1,/向左翻转/1,0,0,1,/向左翻转同时反转/0,1,1,0,/旋转90度同时向左翻转/0,1,1,0/旋转90度，向左翻转同时反转/34图4158种变换棋形4长气和叫吃对方棋子如果在前面的着手库匹配中没有找到任何合适的棋步，则检查已方少于四气的棋串，对其所有的气点尝试落子长气，并计算长气前后的气数差，如果小于0，即紧自己的气，则放弃落子，大于0时则计算长气前后气数差占长气前气数的比重，选择比重最大的地方落子。如果没有检查到已方有少于四气的棋串，则检查对方少于四气的棋串，对其所有的气点尝试落子叫吃，并计算对方长气的可能性，选取使对方气数最小的地方落子。如果对方没有少于四气的棋串，则在候选步中随机一个合法的棋步落子。如果没有合法的候选棋步，则表明棋盘上没有可下的着手，此时PASS一步轮到对方落子。长气检查先于叫吃对方棋子，是由于在模拟对局过程中发现叫吃对方棋子优先时，有可能会出现如图416的循环着手。图416
