朱伊波 梁楠楠

【摘 要】针对点格棋博弈系统，传统搜索算法由于采用了等深度搜索，存在时间资源分配不合理，且评估函数只能依靠人工调参的问题，严重影响了算法执行效率。本课题拟采用基于α-β搜索算法的变长搜索方案，尽可能地减少在节点较多时的搜索时间，以提升搜索算法的效率;同时引入遗传算法、神经网络等算法，根据棋局状态动态调整评估函数参数，以达到提升棋力的目的。

【关键词】点格棋;α-β搜索算法;神经网络

一、引言

点格棋由于其棋型种类繁杂多变，没有定式，以及在安全边存在的情况下，估值会由于其安全边占有顺序的不同而有误差，目前，点格棋博弈系统所采用的招法确定优化方法大多都是阿尔法-贝塔（Alpha-Beta）算法，Alpha-Beta算法是对极大极小算法的优化，同时，也是一种对博弈树的剪枝策略。本项目便是针对Alpha-Beta算法进行研究。

二、基于Alpha-Beta搜索算法的变长搜索算法的操作原理

以点格棋博弈树为例，如图所示

变长搜索方案示例图

其中□代表己方拓展的节点，○代表对方拓展的节点，点格棋博弈树就是通过博弈双方轮流拓展节点来构建的。在d=4的一层节点被分成了4组，以第一组为例，节点n1的离散度为0.3小于n2，同样n3的离散度也小于n2，则只需要对n2进一步搜索。

三、变长搜索方案实现的框架构建

选取UCT搜索算法作为框架来实现该改进方案。UCT算法（上限置信区间算法）是蒙特卡洛算法的一种延伸算法，同時又将UCB算法应用到博弈树搜索上，通过UCB值的大小来选择进行评估的节点而不再是随机选择，通过UCB算法引导博弈树向更好的方向生长，有利于更快的获得最优解。……