贯穿式案例教学法在机器博弈课程中的实践

刘 成，李 飞，孙玉霞，尹 航，邱虹坤，王亚杰

（沈阳航空航天大学 工程训练中心，辽宁 沈阳 110136）

0 引 言

AlphaGo战胜李世石之后，机器博弈技术实现飞速发展，人工智能再次成为业界热点，成为时代标签[1]。在新形势下，国务院在2017年7月制定了《新一代人工智能发展规划》，提出高校应该“拓宽人工智能专业教育内容，形成人工智能+X复合专业培养新模式”，鼓励以“寓教于乐”的形式普及与推广人工智能[2]；教育部在2018年4月印发了《高等学校人工智能创新行动计划》的通知，要求高校落实新一代人工智能发展规划，“进一步提升高校人工智能领域科技创新、人才培养和服务国家需求的能力”[3]。

机器博弈是人工智能研究的理想载体，是人工智能学科的“果蝇”[4]。在高校开设关于机器博弈的基础课程，是培养大学生人工智能科学素养、提高大学生大数据专业技能的重要途径，符合我国《新一代人工智能发展规划》的战略要求。因此，在高校的本科教学中开设有关机器博弈的课程意义重大，无论是课程内容的设计，还是教学方法的选取，都值得广泛深入的探讨。

1 计算机博弈基础课程简介

计算机博弈基础课程是沈阳航空航天大学于2015年开设的校级选修课，其目的是为了拓宽学生视野、激发学生创新潜能、夯实学生参与机器博弈等课外科技活动的技术储备。该课程面向全校各专业各年级的学生，总学时为16，其中理论学时为10，上机实验学时为6。

在授课时发现，选课的学生绝大多数是理工科的低年级学生，其中大一学生的人数比例有时高达85%。较多的零基础学生以及较短的学时，给授课工作带来一定的难度。如果通过提高选课条件的方式来限制选课学生的数量，则学生的受益面变窄，对机器博弈课外活动感兴趣的学生不能及时得到技术支持，背离了课程的目标。可见，采用传统的授课方式很难解决实际的教学条件和教学目标之间的矛盾。

贯穿式案例教学法的核心思想就是选取最具代表性和完整性的教学案例，用以贯穿整个教学过程的一种教学方法，是案例教学法[5-6]的一个变种。贯穿式案例教学法具有知识点衔接性强、理论联系实际和任务驱动等特征，被一些学者应用到教学中[7-8]。在计算机博弈基础课程中，作者选取“井字棋博弈程序”作为教学案例贯穿整个教学过程。

2 井字棋简介

井字棋（英文名称Tic-Tac-Toe）是与五子棋游戏规则类似的一种棋类游戏，棋盘是3×3的格子；在行棋过程中，首先形成“连三”的一方获胜。如图1所示，图1中黑方获胜。可见，井字棋也可以称为“三子棋”。源于人们对五子棋的认知，棋盘很小且规则简单的井字棋会给学生一种熟悉而亲近的感觉，能激发学生的热情和好奇心，也能树立学生深入学习的自信心，为教学活动创造了良好的开端。“牛角棋”是另外一种规则简单的中国民间游戏[9]，有不少学者使用牛角棋作为博弈程序的学术研究载体[10-11]。

井字棋和牛角棋都属于规则简单的游戏，一些学者选择后者作为学术研究载体可能有其独特的考量，不过从教学的角度看，选取井字棋作为教学素材更有优势。井字棋的棋盘相对更显规则，用于绘制界面的程序开发工作量较小，而且井字棋的棋盘较小，为概念的图形化表示提供了更加便利的条件，这些是笔者选择井字棋而不是牛角棋作为教学案例的一个重要原因。

事实上，井字棋与五子棋、六子棋等棋类游戏一样，都属于连珠棋（英文名叫k-in-a-row），文献[12]对连珠棋进行了统一的描述和游戏公平性的证明。可见，这些棋种存在很大的共性，井字棋博弈程序在多个方面（如程序的框架、界面的绘制、搜索算法等）可以为其他规则更复杂的连珠棋种所借用。这样，学生可以根据个人的兴趣能够较容易地扩展到其他棋种，教师的教学投入则容易体现事半功倍的效果，较好地符合了“从个别到一般，再到个别”的认知规律，这是笔者选择井字棋作为贯穿式教学案例的主要原因。

3 井字棋案例的实施

图1 井字棋的例子：机器执黑胜

井字棋案例是基于VC++6.0和MFC开发的完整源程序，其可执行程序的运行界面如图1所示。案例的实施过程是整个教学过程的主线，将授课内容分层次、分模块地和源程序对应起来，学生随时可以看到理论和概念在源程序中的具体实现。授课内容主要划分为以下6个模块。

3.1 VC++面向对象的主要特征简介

介绍类的封装和继承特性以及基于事件驱动的程序设计理念在VC++6.0中实现，教学目的是填补学生“面向对象程序设计”有关概念的空白。

案例中定义CGame类，用以封装着法搜索模块的数据和函数。在数据方面，CGame类定义常量、棋盘等；在函数方面，定义局面评估函数、展开博弈树的递归函数等。

CGame类定义的主体内容如下：

通过对比分析，引导学生能够理解CGame类在应用程序中的作用和地位以及与应用程序向导所生成的其他MFC类之间的关系；要求学生掌握添加事件处理（信息响应）函数OnLButtonDown的方法。

3.2 井字棋源程序的框架分析

框架分析能够使学生从宏观上把握博弈程序的逻辑，防止陷入局部的不易理解的细节，影响学生的兴趣和信心。

框架分析以“事件驱动”为主线，沿着从“人方点击鼠标左键落下棋子”到“机器给出着法更新棋盘”这个线路，理顺关键函数之间的调用关系。

表1列出了案例中关键函数的名称、功能和来源，这些函数构造了博弈程序的框架。

在表1中，前4个函数按照顺序构成了主调和被调关系，即OnLButtonDown→GetBestPoi nt→MinSearch ⇌ MaxSearch。其中的MinSearch和MaxSearch是核心函数，因为这两个函数是博弈树的主要构造者（参见3.4），采用“⇌”符号表示二者特殊的互相调用的关系，即递归调用关系。

在关键函数之间的调用关系理顺之后，教师重点讲解OnLButtonDown函数和OnDraw函数，因为前者处理了输入问题，后者处理了输出问题，都直观地对应于用户的界面操作，易于理解。

表1 案例中程序框架的关键函数

3.3 局面的评估

局面的评估，就是站在机方的角度，依据计分标准对双方盘面分别进行量化的评价，由GameState成员函数完成。原则上，局面的评估要以线型的评估为基础，即只有确定了线型估值，才能够进行局面估值[13]。为了简化局面估值，突出教学重点，案例直接依据局面的特性进行局面估值。局面特性共有4个方面（7种取值）：①如果当前局面存在连三，则给出胜负的判定，此时局面的估值为极值±100；当机方拥有连三时为+100，当人方拥有连三时为-100；②当不存在上述的情况时，如果当前局面某方拥有2个连二，则局面的估值为±50；③在不存在上述的情况时，如果棋盘存在空位（可以落子的地方），则局面的估值为±1；④如果棋盘不存在可以落子的空位，则局面的估值为0。

由于局面估值的取值范围也是博弈树结点的取值范围，所以，博弈树结点的取值v也是此7种值之一，即v∈{±100，±50，±1，0}。

3.4 博弈树的展开

博弈树是依据极大极小值算法展开的。这部分内容是课程的核心内容，但比较抽象，因此在授课方法和内容设计都遵循变抽象为形象、变复杂为简单的原则。按照这样的原则，对搜索算法的讲解进行了两方面的设计。

（1）将构造博弈树的递归函数由1个“负极大值”函数分解为2个函数，MaxSearch和MinSearch。虽然采用负极大值算法具有源码简洁等优点，但学生很难理解；将该函数分解为2个函数，极大值和极小值的求解步骤更加明显；在对博弈树进行剪枝操作时，对剪枝的具体实现以及剪枝的效果也易于观察和理解（剪枝的实现参见3.5的内容）。事实上，对“负极大值”函数的拆分，并不影响程序的执行效率[14]。

（2）博弈树结点的图像化表示。在绘制极大极小值算法的博弈树结点时，大多数的参考资料采用数值的形式来表示博弈树结点，学生很难将这样的一个数值和一个实际局面对应起来，为理解该算法的原理增加了难度，但以图像作为结点来描绘博弈树，则形象很多。图3用图像表示博弈树的例子，展示在当前局面下，机器如何依据极大极小值算法从ABC三种着法中判断出最佳着法。在图2中，每个图像代表博弈树的一个结点，也代表一个局面。有向线段表示结点的父子关系（即主调函数和被调函数的关系）；图像下面是局面的名称和局面估值；除了根结点之外，局面的名称以英文字母（D～P）命名，这样的字母顺序表达了博弈树结点动态构造和释放的顺序，也表达了算法深度优先的特征。

图2 基于极大极小值的博弈树示意图

在案例中，形如图2的博弈树的最大深度不会超过8，原因是当机方执黑先行时，第1手棋不必搜索，直接在棋盘中央落子即可；在第3手时，最多需要在7个空位中搜索，即最大深度为7；当人方执黑先行时，机方的第1手棋最多需要在8个空位中搜索，即最大深度为8。

3.5 博弈树的剪枝

剪枝，就是将最佳着法保留在博弈树中的前提下，忽略掉没有意义的博弈树结点，缩小博弈树的规模，以提高程序执行效率的搜索算法。应用于极大极小值的剪枝算法被称为Alpha-Beta剪枝。

图2共有4层结点，即第1、2、3、4层，父结点从子结点中获取值的大小遵循如下的规则：当父结点为奇数层时，应获取所有子结点中的极大值（即局部最大值）；当父结点为偶数层时，应获取所有子结点中的极小值（即局部最小值）。

根据上述规则，图2中的F和G两个结点是应该被剪掉的：D处于偶数层，应该获取E和F中的最小值；在D的所有子结点中，E是首先被构造和求解的；由于E的值为-100（即负无穷大），为全局最小值，则F的值不可能小于E的值，所以，F这个结点就没有构造的必要；不构造F，结点G就不存在了。

图2表达的剪枝效率较低，实际授课时可以挑选像图3那样剪枝效率较高的局面展示给学生。图3的A图表示，当把程序设置为“人方先手”且“不实施剪枝操作”时，机方搜索了一棵具有18 512个结点的博弈树，最终选取棋盘中心点作为最佳着法；图3的B图表示，当把程序设置为“人方先手”且“实施剪枝操作”时，机方搜索了一棵只有5 457个结点的博弈树，仍然选取棋盘中心点作为最佳着法。对比图3（A）和图4（B）图可见，实施Alpha-Beta剪枝后，博弈树的结点数量大约减少了2/3。

图3 是否实施Alpha-Beta剪枝的效果对比

另外，Alpha-Beta算法的剪枝效率与结点的排列顺序有关。例如，对于图3中的E和F两个结点，如果F先于E构造，则F和G两个结点不会被剪掉，剪枝效率变低。这样的问题可以引导学生加以关注和讨论。

3.6 案例的扩展

案例的扩展，就是在井字棋框架的基础之上，增加其他新技术实现新功能，目的是让学生不要把视野仅仅局限到案例源程序上，而是从具有一定高度的视角看待案例，理解案例潜在的可扩展性。由于扩展的内容有较多选择，所以应根据课时的长度做适当选择。例如，可以介绍哈希散列表技术，用以实现对局面的比较以及已知棋谱的使用；可以介绍挑战性更强的六子棋的行棋规则以及六子棋中常用的局面评估方法；可以修改GetBestPoint函数，用蒙特卡洛算法取代极大极小值算法来进行着法的评价，等。

3.7 教学实践效果

从学生评价以及完成的作业（包括当堂作业和大作业）质量看，教学效果良好。选修该课程的一部分学生参加了机器博弈校级比赛并取得了良好的成绩。表2为近3年校内机器博弈比赛获奖并且选修了该课程的学生人数统计。

表2 选修计算机博弈基础的部分学生在校赛中获奖人数统计

4 结 语

沈阳航空航天大学从2011年开始，以机器博弈为基点，以课程改革为手段，在培养大学生人工智能素养方面做了一些实际工作并取得了一定的成绩[15]，为新工科的建设提供了支撑，其中开设的计算机博弈基础课程是教学改革的一个重要方面。笔者在最近几次的计算机博弈基础课程的授课中，选择井字棋博弈程序作为贯穿式教学案例，收到了较好的教学效果，为学生参加机器博弈类课外科技活动提供了一定的技术支持。