朱良双　王静文　李媛

摘要：蒙特卡罗树搜索（MCTS）在许多完备的信息双人游戏中获得成功。本文给出了UCT（UpperConfidenceBoundApplytoTree）算法結合了UCB公式和蒙特卡洛树搜索算法，同时与局面评估相结合，根据点格棋长链和环的特点对算法进行了优化。有利于更快更准地找到当前局面的最优解。

关键词：UCT算法;估值函数;点格棋

【Abstract】MonteCarlotreesearch（MCTS）hasbeensuccessfulinmanyperfectinformationgames.Inthispaper，UCT（UpperConfidenceBoundApplytoTree）algorithmisproposed，whichcombinesUCBformulaandMonteCarlotreesearchalgorithm.Meanwhilecombinedwithsituationassessment，theselectionofnodesforevaluationbyUCBalgorithmisconducivetofindtheoptimalsolutionofthecurrentsituationfasterandmoreaccurately.

【Keywords】UCTalgorithm;evaluationfunction;DotsandBoxes

作者简介：朱良双（1999-），男，本科生，主要研究方向：计算机博弈;王静文（1965-），男，工程师，主要研究方向：人工智能和信息安全;李媛（1976-），女，博士后，教授，主要研究方向：人工智能和随机过程。

0引言

众所周知，点格棋是由数学家爱德华·卢卡斯提出的一种只需要在纸上就可以进行的游戏。与一般的传统游戏不同，点格棋的玩法是通过点与点之间的边来占领格子，再根据所占领区域大小来判定胜负，是一种将图论、数学等知识结合在一起的游戏。

在国内，自2011年起在全国大学生计算机博弈竞赛已将该项目作为竞赛项目之一，随着国内外各类机器博弈赛事的陆续举办，对于点格棋搜索算法的研究受到了越来越多的爱好者关注，在2020年的全国大学生计算机大赛中，点格棋的参赛队伍已达到27支，为历年最多。

1点格棋简介

点格棋的棋盘大小可以根据情况进行设置，典型的点格棋棋盘由6×6的点围成的5×5的格子，如图1所示。

图1中，棋盘中共60条边，格子数为25，由于比赛胜负是按照双方所占格子数来确定，格子数为奇数时可以避免出现平局情况。

点格棋的基本规则如下：

（1）双方轮流在水平或竖直方向的相邻两点之间下棋。……