基于UCT算法的点格棋游戏系统

摘要

本发明公开了一种基于UCT算法的点格棋游戏系统，包括：外部显示装置、输入装置和内部处理单元；外部显示装置，用于与内部处理单元建立通讯，显示棋盘信息和对弈过程；输入装置，用于用户设置参数和策略选择，并与内部处理单元建立通讯，进行点格棋游戏，或者选择进行自动测试；内部处理单元，采用智能的博弈技术实现游戏系统的智能化，实现智能博弈技术之间自动对弈以及人与智能博弈技术之间的对弈。本发明采用UCT算法作为点格棋游戏系统的博弈技术，解决了原有算法的估值问题，在对所有的可能下棋选择进行全局搜索的基础上根据搜索结果选择好的节点进行更多次的局部搜索，可以搜索结果向着好的方向发展。并且可以同时利用多线程进行多次的模拟，充分利用了电脑的硬件资源。

说明书

技术领域

本发明属于电子棋类游戏技术领域，特别涉及一种基于UCT算法的点格棋游戏系统。

背景技术

点格棋是一种二人纸笔游戏，可以帮助人类提升逻辑推理能力，锻炼数学思维，开发更深层次的智力。棋盘是由36个点60条边组成的5×5格子，规则是：对弈双方轮流棋盘上着边，边由棋盘上相邻的两点连接而成，边只能是水平或者是竖直的；边不属于任何一方，只会对格子的归属进行判断；当每个格子的四条边都被占满时格子由最后一个着边者占领，占领格子后可继续着边直至不能占领格子或游戏结束，最后根据双方所捕获的格子数多少判断胜负。棋类游戏博弈问题是人工智能的典型问题，研究博弈技术同时也可以推动人工智能的发展。

当前的点格棋博弈系统所采用的搜索方法多为Alpha-Beta算法。棋类游戏系统通常是根据当前局面对存在的所有可能情况向下搜索，构造出一颗模拟的树状图，称之为博弈树。由于Alpha-Beta算法中的α值和β值就是当前棋盘节点的估值，所以针对点格棋，必须有一个棋盘的估值函数。利用估值函数将不同的棋盘量化，通过量化后的数字来比较不同棋盘对于博弈一方的优劣情况。点格棋属于添子类游戏，在开局阶段棋盘中可下边较多、随机性强，但是开局阶段对棋盘的划分将直接决定最终的胜负，所以估值函数设计相对较难。

蒙特卡罗方法也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。使用概率统计的方法解决点格棋估值设计随机性强的问题，为实现采用概率估值的搜索方法使用信心上限算法又称UCT算法，它是蒙特卡洛算法的一种延伸。

综合上述分析，目前点格棋游戏系统常用的博弈技术是Alpha-Beta剪枝算法，但是该算法必须要设计一个估值函数对局面优劣进行分析，而点格棋的估值函数设计目前的方法存在判断依据少，随机性较强的较难。

发明内容

本发明目的是针对现有点格棋算法的缺陷，提供一种基于UCT算法的点格棋游戏系统。

为了实现上述目的，本发明采用以下技术方案：一种基于UCT算法的点格棋游戏系统，包括：外部显示装置、输入装置和内部处理单元；

外部显示装置，系统的外部接口，用于与内部处理单元建立通讯，显示棋盘信息和对弈过程，控制游戏的开始与终止；

输入装置，用于用户设置参数和策略选择，并与内部处理单元建立通讯，进行点格棋游戏，或者选择进行自动测试；

内部处理单元，采用智能的博弈技术实现游戏系统的智能化，实现智能博弈技术之间自动对弈以及人与智能博弈技术之间的对弈。

所述内部处理单元包括：

搜索模块，采用基于UCT算法的概率估值搜索方法，根据当前棋盘的状态通过对博弈搜索算法的应用，模拟各种下棋选择将会获得的结果，不断地对博弈树进行搜索，最后根据搜索的情况找到当前的最优的下棋选择；

储存模块，通过使用大小为11×11的字符型数组实现对棋盘信息的存储，当下棋过程中棋局状态产生变化时，通过改变数组中的数据值实现对棋盘信息的存储；信息交互模块，实现外部装置、输入装置与处理单元之间的数据传输，信息交互，对游戏系统的状态进行控制；包括实现开始、暂停、悔棋、加载下棋策略等功能的控制；

互动模块，通过加载人工下棋和智能下棋两个接口实现人与人、人与电脑、电脑与电脑之间的下棋，两个接口通过调用人工策略类和智能下棋策略类实现。

所述基于UCT算法的概率估值搜索方法包括：

(1)选择结点：根据各分支的胜负概率在博弈树中进行节点选择，获取胜率值最大的节点；

(2)展开节点：当一个结点被选中，如果该结点没有子结点，并且达到设定的模拟棋局的次数，为该结点拓展子结点，在拓展节点时对等价边进行裁剪；

(3)模拟棋局：对所拓展的节点按照固定的方法进行模拟下棋，不区分博弈的双方，直到棋局结束为止；模拟结束后统计模拟次数和胜负结果，为下一步估值提供数据；

(4)回馈更新：根据模拟棋局得到的胜负概率值对整个博弈树进行估值，将模拟棋局的胜负结果沿着父节点反馈更新整个搜索树。

所述步骤1中胜负概率用信心上限值反映，信心上限值计算公式如公式(1)所示：

>

式中：为博弈树中第j个分支的平均回报，n是所有角子机总访问次数，n_j是博弈树分支j的访问次数。

所述步骤2中等价边为点格棋棋盘确定的链、环中，每个棋型剩余不止一条边，选择其中任意一条产生的相同结果的边。

所述步骤4中更新是把从代表当前局面的父节点到第2步中所找到的子节点所形成的路径上的所有点，依照模拟棋局的结果来更新胜场数和访问次数，亦即若此点为先手，且模拟棋局之结果为先手胜，则此节点的胜利次数加一，反之亦然；访问次数则是此路径上的所有节点都加一，根据博弈树每个分支的访问次数和收益值对每个分支进行改了概率估值。

所述概率估值采用收益值反映，所述收益值的计算方式为：

式中k对修正值所占收益值的比重进行控制，score表示本方所捕获的格子数，n表示棋盘的大小。

点格棋游戏系统的界面层提供强制下棋、悔棋、测试、设置棋盘参数等功能。在主界面中点击菜单栏设置按钮可以，设置界面中可以设置的参数如棋盘大小、对弈双方等。下棋的双方可以选择为人人对弈、人机对弈、机机对弈，在设置完双方和对弈参数后，点击开始可以进行下棋。在过程中可以强制某一方走确定的棋步；当某一方玩家出现错误时，可以向对方提出悔棋请求，当对方同意后，棋盘上会自动消除玩家刚下的一步棋。

系统的搜索层主要是通过加载系统搜索方法，根据当前棋盘的状态通过对博弈搜索算法的应用，模拟各种下棋选择将会获得的结果，不断地对博弈树进行搜索，最后根据搜索的情况找到当前对我方的最优的下棋选择。在获得当前最优的下棋选择后，根据棋盘数据结构返回所下边的坐标，界面模块根据坐标在棋盘上进行显示。

蒙特卡洛法的一种延伸算法--UCT算法能对当前棋局存在的所有可能情况进行多次模拟，通过概率值预估节点的好坏，优先选择表现好的节点。在选择进行模拟的节点时采用以信心上限值为依据，在超大规模博弈树的搜索过程中相对于传统的搜索算法有着时间和空间方面的优势。在与风险评估模型相结合的基础上，可以在可控的时间内得到当前局势下的相对较优的解决方案。这种方法可以很好的解决了点格棋目前存在的盘面评估问题。

采用UCT算法作为点格棋游戏系统的博弈技术还具有以下优势：首先，它解决了原有算法的估值问题，其次UCT算法在对所有的可能下棋选择进行全局搜索的基础上根据搜索结果选择好的节点进行更多次的局部搜索，可以搜索结果向着好的方向发展。最后，在UCT算法进行模拟棋局的时候可以同时利用多线程进行多次的模拟，充分利用了电脑的硬件资源。

附图说明

图1是实施例点格棋游戏系统主界面。

图2是实施例UCT算法的搜索过程。

图3是实施例等价边示意图。

具体实施方式

为了更好地理解本发明的技术方案，以下结合附图对本方案进行更加详细的描述。

1、点格棋博弈系统

(1)系统设计

点格棋游戏系统分为界面层和处理层两大部分，界面层主要负责与用户的交互操作，如显示对弈过程、设置参数。界面层主要的功能就是对系统的界面进行实现同时具有对策略进行自动化测试的功能以及具有人性化的悔棋功能。处理层主要是采用智能的博弈技术实现游戏系统的智能化，实现智能博弈技术之间自动对弈以及人与智能博弈技术之间的对弈。

(2)系统实现

本发明系统采用MicrosoftVisualStudio2010作为开发环境，以C++为开发语言，实现了点格棋游戏系统各项功能。本系统在实现时使用了多线程技术，是为了同步完成多项任务，通过提高资源使用率来提高系统的效率。根据系统设计要求，点格棋游戏弈系统的初始化界面如图1所示。

点格棋游戏系统，包括：外部显示装置、输入装置和内部处理单元；

外部显示装置，用于与内部处理单元建立通讯，显示棋盘信息和对弈过程；本发明设计的点格棋系统界面是基于MFC单文档应用类型设计的。微软基础类库(MicrosoftFoundationClasses，简称MFC)是以C++类的形式封装了WindowsAPI，包含一个应用程序框架的类库。引入MFC的目的是为了减少应用程序开发人员的工作量。

输入装置，用于用户设置参数和策略选择，并与内部处理单元建立通讯，进行点格棋游戏，或者选择进行自动测试；MFC中的消息响应机制正好符合本设计中界面上对各个菜单按钮事件处理的需求，通过对界面上的菜单按钮分别进行消息映射，从而可以执行相应的函数进行单击事件处理。

内部处理单元，采用智能的博弈技术实现游戏系统的智能化，实现智能博弈技术之间自动对弈以及人与智能博弈技术之间的对弈。

内部处理单元包括：搜索模块，采用基于UCT算法的概率估值搜索方法，根据当前棋盘的状态通过对博弈搜索算法的应用，模拟各种下棋选择将会获得的结果，不断地对博弈树进行搜索，最后根据搜索的情况找到当前的最优的下棋选择；

储存模块，整个棋盘的所有数据全部存储在一个字符型的11x11的数组如公式(3)所示。其中每一个元素都与真实棋盘中的点，格子，边一一对应。其中，若坐标是格子，则0代表未被捕获，1代表被玩家1捕获，2代表被玩家2捕获；若坐标是边，则0表示该边可以下棋，1代表该边不可下棋。

信息交互模块，系统的信息交互模块实现了外部显示装置、输入装置与内部处理单元中搜索模块之间的信息交互。当外部输入装置的开始开关处于开启状态后，搜索模块进行初始化操作，准备接受来自输入装置的控制信号。若控制信号显示机器走棋则调用搜索模块的策略接口；若显示需要人工下棋则在棋盘界面上对鼠标位置进行捕获，当棋盘上的下棋位置被触发，则将下棋位置的坐标作为信号发送给处理单元，更新存储数组。若信号显示准备获取输入信息下棋过程中一方完成走棋后，交互模块中的计时单元完成本轮下棋的计时操作，同时给出切换信号。当某些原因需要暂停比赛，可以通过外部装置的暂停按钮向内部处理单元发送暂停比赛计时、停止搜索操作、锁定棋盘界信号，内部出路单位根据信号完成相应的操作。下棋过程中因为若下棋某方出现失误，走棋犯规等情况，外部装置发个违规指令给内部处理单元，内部处理给出报警提示，若下棋方需要进行悔棋，则内部处理单元根据存储模块的下棋记录对最新的下棋记录进行撤销，同时将本轮计时从比赛时间中减去。

互动模块，互动模块主要实现人工下棋和智能下棋之间的互动，主要包括人人对弈、人机对弈、机机对弈三种模式。在内部处理单元获得外部装置和输入装置传来的信号后，根据选择的下棋方加载不同下棋接口，接口通过加载策略类实现下棋程序。人工下棋策略类：计算机处于捕捉鼠标事件状态，若检测到鼠标点击事件，则开始检测鼠标位置是否合法，合法分为两类：a是否处于两点之间一定范围内，可指定某条直线。b指定直线是否为空。不合法则操作无效，继续准备捕捉鼠标事件。合法则在该位置显示直线。智能下棋策略类则是调用搜索算法进行搜索，本发明后面部分会详细介绍。

2、基于概率估值的搜索方法

搜索模块采用基于概率估值的搜索算法，并在原有的基础上根据点格棋的特点对算法进行优化。搜索算法的过程如图2所示，具体实施如下：

(1)选择结点

UCT算法是将信心上限值算法思想用于博弈树搜索的一种算法,信心上限值算法是一类解决多臂匪徒问题算法的总称。算法中的信心上限值就是每个分支的胜负概率情况的一个反映，信心上限值是每个分支的概率估值。信心上限值的大小代表这个节点优劣，值越大说明这个节点较优，在进行搜索和模拟时将会选择更多次的次数，信心上限值计算公式如下：

>

说明：式中:式为博弈树中第j个分支的平均回报,n是所有角子机总访问次数,n_j是博弈树分支j的访问次数。I_j的前半部分表示利用已有的回报,后半部分表示探索未知的回报。

公式要这样设定的好处主要体现在搜索深度上。一般搜索算法的博弈树的高度是相同的。而UCT算法与别的算法最大的不同就是不同的分支完全可以拓展到不同的搜索深度。对于双方最有可能落子的分支，UCT算法可以达到一个非常高的深度；而对于双方不太可能落子的分支，UCT算法的深度这时候就变得很浅。这样做将计算机资源有效的利用到有效分支，大大提高搜索树的局部深度，提高算法的智能水平。

(2)拓展结点

在UCT算法中拓展结点的这一步骤中，需要为结点拓展子结点。那么，拓展子结点的多寡将直接影响整个算法的效率。如果每次拓展子结点的数量比较少的话，算法的效率无疑是比子结点数量多的情况是要高上许多的。经研究发现，在给定一个棋局状态的情况下，下棋选择是有许多重复的，具体表现为在一个可下边下棋和在另一个可下边下棋结果是相同的，本发明称这些和别的边重复的边为等价边。

等价边定义：点格棋棋盘确定的链、环中，每个棋型剩余不止一条边，选择其中任意一条产生的相同结果，就称每个棋型中的边互为等价边。本发明定义的等价边具体包含以五种边。

①有一格短链中余下的两条边互为等价边，如图3(a)中两条实线表示一个一格短链，两条虚线表示的边，选择任意一条都会使短链形成一个C型格，使短链被对手捕获。所以图3(a)中虚线表示的两条边互为等价边。

②有二格短链中短链边界的两条边互为等价边。如图3(b)中四条实线表示一个二格短链，两条虚线表示的边无论选择在哪一条边下棋，对手下一步棋则一定会在捕获这个短链或者形成双交交换奇偶性中先择一个，产生的结果也是相同的。所以图3(b)中虚线表示的两条边互为等价边。

③经确定的长链中存在的所有边互为等价边。如图3(c)中八条实线形成一个长链，五条虚线表示的边无无论选择其中的哪一条可下边下棋，对手下一步棋则一定会在捕获这个长链或者形成双交交换奇偶性中先择一个，下一步棋后的结果是相同的。所以图3(c)中虚线表示的五条边互为等价边。

④经确定环的中剩余的所有边互为等价边。如图3(d)中八条实线形成一个环，四条虚线表示的边无无论选择其中的哪一条可下边下棋，对手下一步棋则一定会在捕获这个环链或者形成双交交换奇偶性中先择一个，下一步棋后的结果是相同的。所以图3(d)中虚线表示的四条边互为等价边。

⑤盘的四个边角格子如果四条边都未被下过，可以认为棋盘边角上的两条边是一种特殊的等价边。如图3(e)中的①、②、③、④四个边角上的两条虚线表示的边，因为棋盘是对称的所以两条边具有相同的价值。所以每个边角的两条边互为等价边。

在拓展节点时对等价边进行裁剪，减小节点数目，使得博弈树的规模不会过于庞大从而提高算法效率。

(3)模拟棋局

当一个结点被选择函数所选中，那么将从该结点的棋局状态开始随机落子直至游戏结束。利用蒙特卡洛法的思想，进行大量的随机试验，根据试验样本反映的情况，进行下一步的估值。要使大量随机的模拟更具意义，重点在于棋局要有意义，而不是随机落子。本发明在模拟棋局中加入了模拟算法。具体算法所下：

输入：当前棋盘界面

输出：棋盘中的一条边

模拟算法仅通过对棋盘中的安全边和C型格进行判断，若存在安全边且存在C型格的情况下直接捕获C型格，若无C型格则选择一条安全边，若无安全边则随机选择一条边。模拟算法要保证在短时间内进行大量的模拟，不能设计太过复杂，本发明设计的算法可以保证时间的前提下尽可能的提高了模拟的准确性。减少了在现实情况下根本不存在的无效模拟，节省时间用于更多次有意义的模拟，让模拟更加的接近真实情况，模拟获得结果更具准确性。

(4)回溯更新

根据模拟棋局得到的胜负概率值对整个博弈树进行估值，将模拟棋局的胜负结果沿着父结点反馈更新整个搜索树。回溯更新的是模拟棋局产生的收益值。收益值是单节点的概率估值。原有的收益值v的计算方式为：

考虑到点格棋的特点，每次赢格子数目的不同所产生的效果也不相同，赢得格子越多说明本次模拟的价值更高。所以设计含有修正值的收益值计算公式，对收益进行修正之后进行返值。改进收益值v的计算方式为：

说明：式中k对修正值所占收益值的比重进行控制，score表示本方所捕获的格子数,n表示棋盘的大小。

在计算了收益值之后，对博弈过程中构建的博弈树，按照选择节点的路径进行回溯更新，更新的是每个节点的访问次数和收益值两个属性，将博弈树中所有访问过的节点的访问次数加一，该节点的收益值加上所有字节点的收益值之和，作为新的收益值。

(5)获得最佳棋步

每一步下棋都分配有固定的时间，下棋之初，以当前棋局作为根节点构建博弈树，博弈树第一层列举所有的可能下棋，然后对博弈树上的节点随机设定信心上限初始值，进行UCT算法搜索不断地进行选择、拓展、模拟、更新四个步骤，直至时间若用完，结束UCT算法，挑出收益值最高的子结点，作为本次最优下棋。