UCT算法在不围棋博弈中的实现

《UCT算法在不围棋博弈中的实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2015年8月韶关学院学报·自然科学Aug.2015第36卷第8期JournalofShaoguanUniversity·NaturalScienceVol.36No.8UCT算法在不围棋博弈中的实现*梁国军，谢垂益，胡伶俐，林昊，李景炤（韶关学院数学与统计学院，广东韶关5120051）摘要：计算机博弈是人工智能领域的挑战性课题，它利用计算机进行分析、判断和推理，从而得到理性的决策.不围棋是近年来计算机博弈竞赛的一个棋种，属于围棋的变体，其规则是先吃子或棋子自杀的一方为负.通过分析不围棋博弈模型的特点，提出了对上限信

2、心界树搜索(UCT)算法的一个优化方法，在算法的启动过程优先选择评分较高的盘面进行模拟博弈，以便得到更好的落子选择.在与著名的OASE-NoGo软件的试验对弈中，以该算法为核心设计的不围棋软件取得了90%以上的胜率，证明是可行、有效的.关键词：人工智能；计算机博弈；不围棋；UCT算法中图分类号：TP312文献标识码：A文章编号：1007-5348（2015）08-0017-04棋类游戏是计算机博弈领域的重要研究课题，这些研究工作有助于加深对人工智能与计算机科学的认识，促进对人类认知过程的理解.不围棋是十多年前开始出现

3、的一种双人博弈游戏，属于围棋的变体，如［1］果一方落子后吃掉了对方的棋子、或者令已方棋子自杀，则落子一方判负.2011年起，由国际计算机博弈协会（InternationalComputerGamesAssociation，ICGA）组织的计算机奥林匹克（ComputerOlynpiad）大赛增加了不围棋项目.2012年起，由中国人工智能学会举办的中国机器博弈锦标赛也将不围棋列入比赛项目.在这些高级别赛事的推动下，不围棋正在为人们认识并开始进行研究.笔者总结了不围棋的研究现状，分析了不围棋的博弈模型，给出上限信心界树搜

4、索（UCT，UCBforTreeSearch）中的UCB1子算法的一个修正，使其能更早地选择优势盘面，并据此设计了一个不围棋博弈软件，通过与对照软件的对弈实验来验证算法的有效性.1研究现状早些年，计算机博弈对于棋类游戏的研究集中在基于模式识别和专家系统的方法上（最典型的是基于静态评估函数的α-β博弈树方法），并在国际象棋、中国象棋等项目中获得了成功.但是对于围棋类的项目，由于搜索空间巨大只能访问博弈树的一小部分、无法进行准确的静态盘面评估，因此传统的方法一直无法取得满意的结果，在2000年前后，世界上最高水平的计算机

5、围棋软件的棋力还比不上人类的业余初段.2006年，LeventeKocsis和CsabaSzepesvári将蒙特卡洛树搜索（Monte-CarloTreeSearch，MCTS）方法［2］［3］与UCB公式结合，提出上限信心界树搜索（UCT，UCBforTreeSearch）算法，显著地提高了搜索效率.UCT算法的出现开创了计算机博弈研究的新局面.此后人们围绕MCTS方法进行研究和改进，推动围棋软件的棋力不断提高.2013年3月，围棋软件CrazyStone在受让四子的情况下，战胜日本棋手石田芳夫九段，其棋力已达到

6、业余五、六段的水平.首次对不围棋的研究报道出现在2011年，文献［4］介绍了MCTS算法在不围棋中的实现.通过对比测试发现，在围棋中常用的快速动作值估计（RapidAction-ValueEstimates，RAVE）、节点慢速创建、布局模板、UCT等方法和算法，在不围棋中同样有效；文献［5］提出一个结合本体、进化计算、模糊逻辑、模糊标记语言的遗传算法，根据收集的棋局模式和预构建的不围棋模糊本体，用基于模糊推理机制的遗传模糊标记语言分析当前棋局，得到下一个最好的棋步，并应用了遗传学习机制，可在与参照棋局的对垒中不断提

7、高［收稿日期］2015-05-15［基金项目］国家级大学生创新创业训练计划项目(201410576018)；广东省大学生创新创业训练计划项目(201410576060)；韶关学院科研项目(2012-16).［作者简介］梁国军(1992-)，男，广东清远人，韶关学院数学与统计学院本科生；研究方向：计算机算法.*通讯作者.·18·韶关学院学报·自然科学2015年棋力；文献［6-7］分析了棋局模板的分类和格式定义，在对弈过程中优先使用模板进行棋步的选择，当出现模板中没有的棋局时再使用MCTS算法；文献［8］提出在对弈过程中

8、进行UCT树的重用，可以增加5%～30%的搜索深度；文献［9］通过启发式、暴力搜索、参数调整等方式，提高UCT算法的搜索成功率；文献［10］提出在MCTS算法中增加静态估计方法，根据周围棋子的类型标记出允许自由落子的点和禁止落子的点，加快博弈树搜索速度.由于不围棋是新的棋类，相关的研究成果较少.目前对不围棋的主要研究方法是参考棋类尤其是围棋的相