基于python的棋类教学系统设计实现

2018-01-31宋向飞米思琦

科技视界 2018年30期

宋向飞米思琦

【摘要】本文主要研究和讨论了国际象棋比赛的发展趋势，UCT算法的特点以及tkinter的设计和实现。从而详细介绍在基于Python的五子棋教学系统的设計与实现过程中，所依赖的开发环境和语言、系统需求、设计思路和相关算法支持等等，最终实现了实现人机游戏的单机五子棋教学系统。

【关键词】五子棋；UCT；Python；Tkinter

中图分类号： TP311.1-4；G642 文献标识码： A 文章编号： 2095-2457（2018）30-0194-003

DOI：10.19694/j.cnki.issn2095-2457.2018.30.085

Design and implementation of Chess Teaching System Based on Python

SONG Xiang-fei MI Si-qi

（Hunan Normal University， Hunan Changsha 410006， China）

【Abstract】In this paper， the development trend of chess games， the characteristics of UCT algorithm and the design and implementation of Tkinter are deeply studied and discussed，and then the development environment， language， system requirements， design ideas and correlations that I relyon in the design and implementation of the Gobang teaching system based on Python are introduced in detail.Algorithm support and so on， and ultimately achieve the human-machine chess single player Gobang teaching system.

【Key words】Gobang； UCT； Python； Tkinter

1 人工智能的概念

《Machine Learning》中指出，机器学习就是指“计算机利用经验自动改善系统自身性能的行为”。人工智能的研究和实现是逻辑科学和思维科学的应用的结合，是一个被广泛应用和深入研究的分支。从思维的角度来看，人工智能是逻辑思维与灵感思维相互作用的综合设计结果。

2 系统分析

2.1 五子棋围棋教学系统对用户体验有影响，主要集中在以下几个方面：

（1）友好便捷的人机交互系统

（2）登录界面，提供账号密码的输入框，忘记密码的按钮以及注册界面的入口；

（3）注册界面，提供注册信息（账号、密码）的输入框；

系统主界面，左侧放置15×15大小的棋盘，以棕色为底色，右侧设置菜单栏，包括开始、重置、悔棋、保存＼查看棋谱、玩家先后手选择、电脑算法选择。

2.2 五子棋教学系统的主要功能模块

如上图1所示。

3 算法分析

3.1 UCT算法

UCT算法（Upper Confidence Bound Apply to Tree），上限置信区间算法，UCT算法是一种特殊的蒙特卡罗搜索算法，它有三个部分：树选择策略，默认模拟策略和模拟结果。

（1）树内选择策略

如图所示，在传统的搜索树技术中，当搜索深度参数为d且搜索深度达到d时，评估值通过评估函数获得，并且搜索算法基于所有评估值找到具有最大值的分支。在搜索深度相同的情况下获得评估值的模式中，设置搜索深度[1]度数为d，分支系数为b，搜索树中叶子节点的数量为N，关系式由式（1）表示。

N=bd（1）

与传统的搜索算法相比，UCT算法在不同搜索分支中的不同搜索深度上存在最大差异。

UCT 算法在不同的深度获取评估值。根据算法具体设计逻辑，在执行过程中，先评估分支的“希望”值，值越高，然后UCT算法的搜索深度越深（远大于d），结果能较大限度的拟合最优解[2]；相反，值越低，丢弃的可能性越大。

从根节点开始进行搜索并由其算法得到评估值，您可以知道叶节点的到达，在每个非叶节点n子ni∈ch（n）的过程中，树选择策略计算评估值ri，并且评估值可以用作选择标准，并且选择子节点以进行下一选择。ri 的计算公式见式（2）：

（2）缺省仿真策略

当搜索进行到叶节点时，UCT算法执行扩展操作（扩展）：使用此节点作为根节点，可以找到所有允许的和合法的子节点，并将这些子节点作为新叶节点添加到当前搜索树。对其V值和T值进行正确的初始化。应当注意，UCT算法使用默认模拟策略进行搜索直到结束，并且不使用其他评估函数来获得新叶节点的评估值。

此时，棋盘中棋子状态明确，有严格对应的位置坐标、次序和对应棋手，可以容易算出获胜方。当叶子节点的评估值为1时，黑色获胜，而当它为0时，白色获胜[3]。

（3）仿真结果回传

通过仿真算法，所有叶节点得到相应的V和T值，UCT算法通过结果返回将V和T值更新到路径上的所有内部节点。

3.2 主算法设计

由绪论部分分析可知，传统五子棋算法过于僵硬、套路死板，计算机端下棋套路固定，无法根据棋盘局势对下棋策略做出优化，UCT算法用于Go使其发光，因此本设计采用UCT算法作为五子棋的主要算法。在不同的棋局下，使用算法将棋盘上的空子进行大量的模拟，再由评估函数评估出胜率最高的若干落子点[4]，保存作为备选项。

在上图4中，是否存在可连五落子点指的是，己方或对手方在下一步棋可完成连五局势，即必胜。

UCT算法实现设当前棋盘棋局状态（落子位置和对应棋手）为A，根据棋局状态A以及相关规则，确定备选落子点，并将这些落子点组成列表B。假设列表B中的每个点都是下一步，并以此继续模拟下去直到一方获胜为止。在进行模拟时，由树内选择策略获取“期望”，这一“期望”应用于搜索深度d的确定，是指当算法模拟棋子次数达到d时，UCT算法从评价函数中得到相应的权重值，由不同的搜索深度d，U并且在不同的深度获取评估值，“期望”越高，搜索深度越大，求解结果更加符合最优解。根据评价函数统计每个点的胜率，选取胜率最高的那个点作为落子点[5]。

模拟国际象棋和执行统计赢率的流程图如图5所示。A点的最终总比赛达到6场比赛，胜利4胜，胜率为66.6%。

备选落子点的选取规则：考虑到Gomoku和Go之间的区别，在模拟Gobang游戏时你不需要全范围的布局。搜索范围和深度均可适度减小，选取备选落子点的范围限制在棋盘中棋子一定的半径范围内，超出这一范围的落子点不予以考虑。

备选落子点所具备的特点：

（1）所选落子点为空子，状态为-1；

（2）所选落子点临近交叉点有棋子已经布下（不论对方己方）；

（3）所选落子点三个范围内有棋子已经布下（不论对方己方）。

4 结果分析

（1）整个系统运行流畅，子菜单和主菜单之间相互连通，可返回；

（2）菜单栏的功能运行正常，可以实现开始、重置、悔棋、保存/查看棋谱功能，个性化选择功能；

（3）算法中在运用 UCT 时，可与系统其他部分，如棋谱文件，棋盘文件交互良好，同时在设定搜索时间时，可以返回搜索深度和模拟次数；

（4）进行多次人机对弈实验，系统运行流畅，用户体验感绝佳，对弈完成后棋盘数据也正确保存进棋盘文件，pickle文件同步保存用户信息。

本文设计并实现了五子棋象棋教学系统，与传统算法相关。