面向人工智能专业课程的棋类博弈教学辅助平台
2020-12-31赵才荣傅佳悦卫志华丁志军苗夺谦
赵才荣，傅佳悦，卫志华，丁志军，苗夺谦
(同济大学电子与信息工程学院计算机科学与技术系，上海 201804)
0 引 言
随着计算机科学领域的发展，人工智能成为了迅速发展的最新兴的科学与工程领域之一。2016年3月15日，Google旗下Deep Mind团队开发出的围棋程序AlphaGo[1]以4∶1击败了韩国顶尖棋手李世乭，这一事件拉开了人工智能热潮的序幕[2]。次年5月，同样由英国的Deep Mind团队开发的升级版人工智能围棋程序AlphaGo Master[3]击败了当时的人类顶尖棋手柯洁，从此人工智能在棋类领域显露出了无与伦比的威力。这种包含计算机程序的博弈称为计算机博弈，也可称为机器博弈。在博弈中，计算机程序能够像人一样进行判断和推理，以此做出理性的决策。
棋类游戏是计算机博弈的一个标准性问题，人们对棋类人工智能博弈原理与决策机理的研究，可应用于其他诸多领域中，例如军事演练中的最佳作战策略、形式化数学证明问题、物流问题等。棋类对弈过程中展现出来的逻辑思维、形象思维和灵感思维完美地覆盖了计算思维能力涉及的各个方面[4]。学生通过对棋类计算机博弈的学习和研究，可以提高计算机程序设计能力、动手实践能力，同时可以提高计算思维能力和自主创新能力。
为促进学生对人工智能博弈算法的学习、实现棋类博弈程序间的对弈，设计一个通过统一的交互协议进行通讯的棋类博弈平台是有必要的。在该平台上，博弈程序间可以通过比赛的形式比较程序的优劣。
为此，很多文献探讨了棋类人工智能博弈平台的设计。文献[5]设计并实现了五子棋机器博弈教学实验平台，支持学生将独立开发的算法策略载入平台，实现在线博弈与交流；文献[6]设计开发了一种能够与人进行五子棋实时对弈的程序，但主要集中在博弈程序的设计，且不支持博弈程序间的对弈。文献[7-8]实现了网页围棋游戏的开发，但不支持博弈程序间的对弈，且界面不够美观；象棋巫师网站[9]提供了支持象棋博弈程序对弈的软件，但其通信协议较为复杂，加大了学生设计博弈程序的实践难度；孔德帅等人[10]实现了一种基于机器视觉的中国象棋人机博弈系统设计，主要通过摄像头采集棋盘图像，调用系统内置博弈算法计算走法，再采用机械臂实现棋子移动。
可以看到，现有博弈平台一般只针对某种特定的棋类，例如五子棋或围棋，且基本上不具备博弈程序间对弈的功能。主要原因在于这些平台没有提供确定的通信协议以及博弈程序对战入口，因此博弈程序设计者无法成功地将人工智能博弈程序接入平台中。
针对上述工作的问题和不足，本文提出并设计了一种新的教学辅助平台：面向棋类博弈智能体设计的教学辅助平台。该平台可以支持多种棋类智能体的博弈，达到教学辅助作用，便于学生自主、创新学习，提高教学效率。本文的主要工作包括：
1)规定了不同棋类的通信协议，遵循简单性、开放性和可扩展性原则。能够有效辅助学生实现博弈程序与平台的交互。
2)设计实现了棋类博弈平台，该平台可以支持五子棋、中国象棋、国际象棋、围棋这4类棋的人人对弈、博弈程序间对弈以及人与博弈程序间的博弈。
1 博弈智能体的设计
本研究的目的是辅助人工智能博弈类算法的学习，即促进学生自主、创新地开发棋类博弈程序。棋类博弈程序的设计和开发旨在让学生将所学人工智能理论知识应用于实践中，以提高解决实际问题的能力。为保证学生所编程序能够在本教学辅助平台上成功运行，并进行博弈比赛，需要统一规定明确的引擎(即博弈程序)与平台通信协议。确定引擎通信协议后，引擎和平台之间的交互即可通过标准的指令和反馈进行。下文给出中国象棋的引擎协议。其他棋类的协议也可在本平台中查阅。
1.1 通信协议制定
为了降低学生处理博弈程序交互的难度，更多地关注于博弈算法本身和相关人工智能算法的优化改进，本平台的中国象棋引擎协议是基于中国象棋通用引擎协议[11]的简化版本。采用FEN格式串来表示象棋局面的记录规范。
引擎和界面通信的指令和反馈如下：
(1)ucci。
引导状态的指令。引擎启动后，平台给引擎发送的第一条指令，通知引擎现在使用的协议是UCCI。
(2)ucciok。
引导状态的反馈，此后引擎进入空闲状态。
(3)isready。
空闲状态和思考状态的指令。检测引擎是否处于就绪状态，其反馈总是readyok，该指令仅仅用来检测引擎是否能够正常接收指令。
(4)readyok。
空闲状态和思考状态的反馈。表明引擎处于就绪状态(可正常接收指令)。
(5)position {fen
空闲状态的指令。设置“内置棋盘”的局面，用fen来指定FEN格式串，moves后面跟的是随后走过的着法，例如：“position fen rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR r--01 moves h2e2 h9g7 startpos”表示开始局面，它等价于“fen rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/ 1C5C1/9/RNBAKABNR r--01”。
(6)go time
空闲状态的指令，此后引擎进入思考状态。让引擎根据position指令设定的棋盘来思考，milliseconds为限定时间。若超出限定时间，引擎未给出反馈，则判定失败。
(7)bestmove<最佳着法>。
思考状态的反馈，此后引擎返回空闲状态。显示思考结果，即引擎认为在当前局面下的最佳着法。
(8)nobestmove。
思考状态的反馈，引擎主动认输。
(9)quit。
空闲状态的指令。让引擎退出运转。
(10)bye。
接收到quit指令后的反馈。引擎完成了退出运转前的准备工作，通知界面，引擎将在瞬间正常退出运转。界面收到该指令后，即可关闭输入输出通道。
1.2 博弈算法
计算机博弈包括博弈过程建模、搜索算法、棋局评估等过程[12]。在实践过程中，博弈程序从平台处获取当前局面的状态(例如FEN格式串)，随后博弈程序启动搜索算法，并给出其认定的最优走子方案返回给平台，平台根据走子方案实现前端棋子的移动。在设计博弈程序时，搜索算法作为关键技术，直接决定了程序的性能。
常用的博弈算法是极小极大搜索算法。对弈双方都非常理智，但所要达到的目的相反，所以在考虑着法的时候都尽量想让棋局朝着自己的方面转化。在同一棵博弈树的不同的层面上就要有不同的选择标准，即一方总是希望下一步是儿子节点中取值最大者，而另一方恰恰相反，希望在下一步是儿子节点中取值最小者。Alpha-Beta剪枝算法用于裁剪博弈树中对搜索结果不影响的树枝，以提高运算速度。
此外，在设计博弈程序时，可以针对不同的棋类特性对基础算法进行改进优化。文献[13]针对五子棋模型提出了一系列的改进着棋方法，即利用局部搜索、多线程技术、浅层最优算法优化剪枝算法等。文献[14]通过知识库的构建和专家开局走法的引入有效解决了中国象棋重复局面导致的时间、硬件资源浪费的问题。文献[15]在传统Alpha-Beta剪枝的基础上，通过引入迭代深化和历史表等辅助剪枝手段，有效减少了搜索节点数目，提高了剪枝效率。文献[16]对围棋博弈进行深入研究，提出了结合深度学习与蒙特卡洛树搜索算法的快速走子网络。文献[17]结合时间差分算法和反向传播神经网络，设计了一种局面估值算法，可以实现估值函数参数的自动调整，提升程序的博弈水平。
本平台支持用户上传智能体程序与平台内置棋类智能体程序对弈。在此，介绍本平台中中国象棋内置智能体程序采用的相关博弈算法。首先是开局库[18]的设置，由于开局局面落子情况较为简单，单纯的搜索效果不如利用人类一直以来的下棋经验所总结出的好。核心搜索算法为基于Alpha-Beta剪枝的极小极大搜索算法[19]，为了产生更多的Alpha-Beta截断，采用多种启发搜索算法[20-22]优化走法搜索顺序，包含置换表启发、静态评估启发、杀手启发、历史表启发。在对吃子着法进行排序时，根据MVV/LVA的原则进行：优先搜索“最有价值的受害者和最没价值的攻击者”。在搜索博弈树的过程中，由于对战时间的不确定性，程序采用迭代加深搜索算法。算法中采用了置换表技术[23]，其原理是采用哈希表将已搜索的节点的局面特征、估值和其他相关信息记录下来，如果待搜索的节点的局面特征在哈希表中已经有记录，在满足相关条件时，就可以直接利用置换表中的结果。
棋类博弈程序的设计和开发可以结合人工智能多方面的知识，内容丰富，变化无穷。学生在程序设计过程中不仅可以提高编程能力、实践能力，还能有丰富的空间自主探索，提高科研创新能力。
2 博弈平台的设计
本平台提供了对多种棋类(五子棋、国际象棋、围棋、中国象棋)进行对弈的支持，用户注册后可使用该平台实现不同棋类的人人对弈、人机对弈和机机对弈。平台的总体架构如图1所示，包含3个主要模块：主页模块、用户模块、博弈模块。
图1 平台总体架构
2.1 主页模块
主页模块分为：首页、联系、通信协议。通信协议中包含4类棋采用的具体通信方式，以辅助用户顺利实现博弈程序与平台的交互。主页提供了各个棋类比赛的入口，用户可进一步创建对局并设置对局参数，例如棋手可设置为计算机棋手、人类棋手或系统预置AI(计算机棋手为博弈智能体，需用户自行上传)。在主页中也可进入用户模块进行相关操作。
2.2 用户模块
用户模块包含的功能：用户注册、用户登录、密码修改、个人信息修改以及历史对局查看。在用户注册与登录过程中，加入了用户名和密码的表单验证，使得注册用户仅能拥有合法用户名，用户邮箱必须惟一。用户登录后，平台可以记录其用户行为，包括胜负记录、积分详情、对局信息，在个人信息中可以一一查看。通过设置用户身份来管理用户，如普通用户和管理员用户，管理员能够加入任意棋局，实时查看比赛进程。
2.3 博弈模块
作为本平台的重点，博弈模块包含3个部分：查看对局、创建对局和积分排名。
1)查看对局。
针对每种棋类，查看对局页面将从数据库的数据表中，根据对应棋种的标志号，读取棋局的比赛记录，加载于网页表单之中。用户可浏览所有的对局房间，对于未开始棋局，可加入房间参与对局。
2)创建对局。
创建对局前，用户可以设置棋局采用的引擎协议、棋手模式、比赛步时、比赛局时。进入棋局对弈界面后，通过记录用户发送的请求号，系统将同一对弈棋局中的用户捆绑在同一个房间内(包括被设置为实时观战的管理员用户)，后端应用引擎通信协议，对接用户与博弈智能体的着子操作，前后端通过SocketIO服务，在同一个房间内，进行异步数据通信，并在页面端应用JS作出动画响应。
在进行棋局对弈时，系统根据有无棋类博弈智能体程序的参与，选择不同的运作方式，对弈流程如图2所示。
图2 棋局对弈流程图
若无博弈智能体程序参与对弈，即无需处理上传文件有效性的验证，也无需启动后台线程。系统仅需要利用SocketIO异步通信机制，根据引擎通信协议，同步用户双方的棋盘着子进程。有棋类博弈智能体程序参与的情况下，需要启动博弈智能体程序作为后台线程，当轮到博弈智能体程序着子的时候，需要将一方的棋盘状态以引擎通信协议规定的格式，标准输入输出到博弈智能体程序中，待其运行搜索算法，在有限时间内做出决策，并以规定格式返回决策结果，系统再将结果广播给同一棋局中的所有用户，并在前端界面利用JS棋盘脚本予以呈现。
3)积分排名。
积分排名页面直接从数据库的用户表中读取用户的积分信息，对其进行排名并加载。在每次对局结束后，平台根据棋局种类、胜负情况，计算用户积分变化并更新数据库中积分值。
3 博弈平台实现
3.1 数据库的设计与实现
在平台的实现中，数据库是支撑平台运作的关键。由于平台支持用户注册、用户比赛数据记录、用户比赛数据查阅等功能，所以需要为此设计不同的数据库表，并降低数据之间的冗余，具体的数据库表结构如图3所示。
图3 数据库类图
Chess类为平台所支持的棋的种类；Game类是每个棋局所具有的属性；Role类是用户所在的类别，管理着其所拥有的权限；User类是每个用户所具有的属性。在平台不断改进完善中，根据具体需求，可以更新数据库类结构，添加新的属性。
数据库软件选用SQLite，系统与数据库软件的交互主要依赖于Python平台下的ORM框架SQLAlchemy，即能够以Python语言面向对象的编程方式，等价执行SQL语句对数据库的操作。
3.2 平台实现
本平台采用客户服务器结构，服务器端基于Python语言Flask框架、SQLite数据库进行开发，客户端采用基于Html、CSS、JavaScript的Bootstrap框架。表1给出了平台开发过程中所依赖的Python库及其相关功能。
表1 Python后端依赖
棋类博弈程序间的自动对弈是本平台的核心内容之一。根据通信协议，棋类博弈程序采用标准的输入输出流，因此系统采用Python标准库中subprocess模块实现与子程序之间进行交互的功能。
4 平台使用评估
4.1 平台展示
本系统运行环境为Apache服务器。浏览器访问平台网址，首先进入的是平台主页。主页上摆放着通往各个页面的链接，通过点击导航栏右上角进行用户登录或注册，已登录用户可以查看到4大棋种创建对局的按钮。首页的整体布局如图4所示。
点击任意棋类创建对局，进入设置对局参数的中间页面，用户设置好引擎协议、棋手模式、单方步时、局时等参数以后，进入棋局页面，处于待准备状态。
图5为用户上传棋类程序参与对局的操作步骤。首先从主页开始创建对局，然后设置棋局为计算机棋手对决人类棋手，进入等待页面。被设定为计算机棋手的一方，需要点击“点击上传文件”按钮，进行智能体程序路径的查找并确认，确认以后点击“上传”按钮，棋类程序会自动在系统后台加载完成。
图4 平台首页
图5 用户上传棋类程序
图6为智能体双方准备就绪以后，轮流着子的过程。与此同时，管理员用户也可以加入二人对局观战。
图6 智能体间对局
4.2 教学使用情况
本棋类博弈教学辅助平台已于2018年起应用于本科课程《人工智能原理与应用》的实践教学中。
在算法学习过程中，学生可自主登录平台，上传编写好的智能体程序，并与其他用户进行对弈，促进对博弈算法的理解改进。实践环节成绩评定采用瑞士制分组对抗，由云蛇比赛编排软件给出对局名单以及先后手，学生根据初始编排结果进入平台创建对局，上传智能体程序实现对弈。平台具有积分计算功能，每局比赛获胜方可获得2个积分，平局双方获得1个积分，败北队伍获得0个积分。首轮比赛结束后，将积分结果输入编排软件中，得到下一轮对局名单，重复操作直至完成预定轮数。图7给出了中国象棋用户积分排名情况，用户积分记录中包含得分棋局编号，总积分为用户所有棋局得分之和。通过比赛最终积分值，可获取实践智能体程序得分。
图7 棋类积分排名
最终实践成绩由实验报告和智能体程序得分组成，分别占40%和60%。实践成绩占课程总成绩的比例为40%。实践内容的安排，旨在让学生能够灵活掌握并运用博弈算法，棋类博弈教学辅助平台能够有效促进该过程的实施。
4.3 实践效果
以往学生在博弈算法相关实验中，能够掌握基础的极小极大搜索算法、Alpha-Beta剪枝算法。对于复杂场景下的博弈算法设计，例如不完美的实时决策，仅限于理解，未实际动手实践。
在本博弈平台开发前，人工智能专业课程博弈算法实验一般基于井字棋或五子棋设计博弈智能体。智能体与人对弈进行测试，或是在离线软件上与智能体对弈测试。学生无法随时开展线上对局博弈。由于井字棋、五子棋的博弈树复杂度不是非常高，影响学生对博弈算法的深入探索及自主创新。
开发本棋类博弈辅助平台后，人工智能课程博弈算法实验可设计五子棋、中国象棋、国际象棋以及围棋的智能体程序，内容丰富有趣。针对更复杂的博弈场景和博弈树，研究不限于极小极大搜索算法和Alpha-Beta剪枝，需要对博弈算法进行优化改进。例如，针对中国象棋等更复杂的走子情况和更大规模的博弈树，程序如何优化着法顺序、提高剪枝效率；针对平台给定任意行棋步时，程序如何判断搜索深度、设计评估函数。更复杂的博弈场景给予学生更多的空间探索新的博弈算法并优化改进。棋类博弈辅助平台的设计，允许学生在线上开展对局，通过竞争的方式提高学生学习的主动性，鼓励学生在竞争中不断创新以提高智能体程序的性能。因此，棋类博弈辅助平台的开发具有实用创新性。
本文以2019学年《人工智能原理与应用》课程的一个教学班为例介绍具体的实践教学成果。班级共有85名学生，分为21组(小组成员为4人)，以小组为单位开展智能体程序的设计。不同小组所设计的智能体性能有区别的原因主要在于所设计的博弈算法不同，程序应对不同局面的落子反馈不同。
通过2个学期的改革方案实施尝试，选修了本门课程的本科生基本都具备了问题抽象化、解决实际问题的能力，95%以上的学生表示对课堂教授的博弈算法有了更深刻的理解和更熟练的运用，80%以上的学生表示通过实验过程掌握了许多新知识，例如开局库和残局库的使用、评估函数的设计、置换表技术等。
5 结束语
本文满足面向人工智能博弈领域算法辅助教学的需求，在定义了严格的通信协议的基础上，设计并实现了教学辅助平台，该平台能够支持五子棋、中国象棋、国际象棋和围棋的3种博弈模式：人人对弈、人与博弈智能体对弈、以及博弈智能体之间的对弈。目前，该平台已经用于同济大学课程教学中，平台的设计有效增加了学生的学习兴趣，提升了课程的教学效果，起到了很好的教学辅助作用，更有利地促进了对学生自主创新能力的培养，提升了理论与实践结合的动手能力。
