计算机博弈教学中的计算思维能力培养

　　文章编号：1672-5913（2017）05-0022-03

　　中图分类号：G642

　　1 背 景

　　计算思维是运用计算机科学的思想与方法进行问题求解、系统设计、人类行为理解等涵盖计算机科学之广度的一系列思维活动[1]。在信息化时代，计算思维是一种和逻辑思维一样的基本能力。美国卡内基?梅隆大学周以真教授认为，与“读写算”一样，计算思维应该是21世纪每个人都必须具备的基本技能[1]。蒋宗礼教授认为：一个人若不具备计算思维能力，将在从业竞争中处于劣势；一个国家若不能使广大受教育者得到计算思维能力的培养，在激烈竞争的国际环境中将处于落后地位[2]。教育部高等学校大学计算机课程教学指导委员会于2010年7月发表了《九校联盟（C9）计算机基础教学发展战略联合声明》，正式提出计算思维教学改革宣言[3]。宣言明确指出：要旗帜鲜明地把计算思维能力的培养作为计算机基础教学的核心任务，加强以计算思维能力培养为核心的计算机基础教学课程体系和教学内容的研究。

　　近几年来，为了在计算机基础教学中加强对计算思维能力的培养，笔者尝试以计算机博弈为落脚点，通过计算机博弈教学提升学生的计算思维能力。计算思维能力主要包括以形式化和模型化为基础的形式化描述、抽象思维与逻辑思维能力[2]，棋类对弈过程集中展现出来的逻辑思维、形象思维和灵感思维完美地覆盖了计算思维能力涉及的各个方面，而计算机博弈恰好是棋类对弈这种人类高级思维活动的直接模拟。一个计算机博弈项目的实施涵盖了下棋规则问题的描述：棋盘、棋子障碍、空格、棋局、走棋表示等形式化数据描述；存储方式的选取；搜索算法、评估函数模型的计算机描述；并行程序设计思想和问题求解的效率。

　　2 计算机博弈中的计算思维能力培养

　　2.1 通过递进式教学，学生建立起计算思维概念

　　人类博弈的棋种很多，全国大学生计算机博弈大赛暨全国计算机博弈锦标赛2016年的比赛共设置了17个项目，大学生项目包括五子棋、六子棋、不围棋、点格棋、苏拉卡尔塔棋、亚马逊棋、幻影围棋、爱恩斯坦棋、军棋、海克斯棋10种棋类；锦标赛项目包括中国象棋、围棋、13围棋、9路围棋、国际跳棋（100格）、国际跳棋（64格）、二打一扑克牌（斗地主）7种棋牌类。教学中笔者发现学生根据兴趣选定一个棋种后，常常不知如何下手。此时，笔者给学生引入计算思维的概念，即遇到具体问题时，首先考虑人类与计算机各自解决该问题的优势以及问题的可计算性。

　　人类在处理复杂的决策与对策问题时，主要依靠思考，而思考过程就是在脑海中搜索的过程，即根据脑中存储的数据、知识、经验、方法、关系等，力图在可能的着法中找到最佳的着法（“解”）。人类下棋具有全局观或审局观，缺点是人类思考的深度有限。计算机下棋就是模仿人类下棋的思考过程，主要方法是在庞大的状态空间和博弈树中搜索。计算机的优势在于强劲的计算力，每秒可以计算上万亿个节点，但缺点是审局观差，很有可能一招不慎满盘皆输。

　　博弈树是一种形式化描述方法，通过介绍博弈树，让学生对形式化描述棋类博弈的过程有一个直观的认识，进而引导学生深刻理解对实际问题进行形式化描述的含义。

　　计算机并不能解决生活中所有的实际问题，因此学生在编写程序前需要了解要解决问题的复杂度，即问题的可计算性。笔者通过描述博弈树广度和宽度的含义，以具体棋种的博弈树为例，让学生理解复杂度的概念。表1展示了几种不同棋种的近似棋局状态数目。

　　由此，引导学生从计算机资源的角度分析解决问题的时间复杂度（要通过多少步才能解决问题）和空间复杂度（在解决问题时需要多少内存）。

　　当学生认识到完全展开常见棋类的博弈树是不可能完成的任务后，介绍如何将博弈树规模降低到计算机可解?Q的范围内，即评估函数和剪枝搜索算法。

　　至此，学生明白了一个计算机博弈系统程序至少包括棋局表示、走法生成、搜索引擎以及局面评估函数4个部分。棋局表示是对比赛过程中形成的棋局的描述。走法产生是将一个局面的所有可能走法罗列出来的程序。不同棋类由于规则不同，走法产生的复杂程度也有很大区别。搜索是如何找到最优着法，这是计算机博弈的核心部分。局面评估就是对棋局进行评估，是搜索算法的前提，要编写局面评估函数向人类学习如何审局。

　　2.2 以经典方法剖析为基础，培养学生的抽象和逻辑思维能力

　　对于博弈树的搜索，经典的搜索方法是极大极小搜索算法。通过对极大极小搜索算法的剖析，使学生深刻理解该算法背后的原理以及该算法可以选出最优结果的核心逻辑，训练学生的分析能力和逻辑思维能力，通过该算法递归实现的实例演示，强化学生的抽象空间思维能力。通过具体特例，向学生展示该算法可以被进一步优化的原因，然后介绍Alpha-Beta剪枝算法，通过具体实例演示，学生先对AB剪枝算法产生直观的认识，而后对其算法进行剖析，强化训练学生的逻辑思维能力，即对于某些满足特定条件的局面，为什么不用继续进行极大极小搜索。

　　再如，对于某些很难给出评价函数的棋类（如围棋），研究人员提出使用蒙特卡洛方法，通过大量随机模拟对弈的结果得到着法。这种方法的底层有一个坚实的数学基础，上层使用并行计算，通过计算、模拟、采样、优化等一系列数学方法获得评估结果。AlphaGo采用蒙特卡洛树加深度学习的方法使计算机围棋技术有了明显的提高。

　　2.3 由简到难，培养学生的综合分析与探索研究能力 　　站在巨人肩膀上学习，是人类在探索世界的过程中不断进步的根本原因。对于博弈的4个主要部分，应指导学生学会查阅资料，应了解解决目前问题已有的技术和方法及其优缺点。例如，为了让计算机下棋，要将所有棋局元素，包括棋盘、棋子、棋局、着法、规则、知识等，通过数字化方法（编码）转变为数据元素，各种数据元素再以特定关系构成相应的数据结构进行存储和处理。设计一种数据结构表示一种棋类游戏的状态往往要考虑几个方面的问题：占用的空间大小、操作数据的速度、使用方便与否。

　　以往，博弈棋盘的实现有两种：一是数组棋盘，二是位棋盘。数组棋盘就是定义一个数组，并利用数组的每个元素标示棋盘中每个位置的棋子情况。位棋盘亦称比特棋盘，用棋子状态条件的布尔值表示。棋局的存储也可采用Zobrist哈希技术实现，哈希数的最大优点在于它计算的是64位数的异或和，当棋局发生了变化，只要将相应变化棋子的哈希数再异或一次，便可以转变成新局面对应的哈希数。

　　2.4 具体问题具体分析，拿出可行方案

　　了解了现有技术，就需要针对具体的项目给出可行方案。例如，“深蓝”凭借强大的计算能力，借助穷举法穷尽了国际象棋对弈的所有变化，取得了?倮?，但对于围棋，计算机如果仍借助穷举推算，是不可能获得所有变化的。蒙特卡洛算法并不是全新算法，AlphaGo除了使用蒙特卡洛树进行搜索外，还采用了基于机器学习的神经网络。神经网络有很大的作用：第一是通过学习高水平棋手的棋谱，获得如何在盘面落子的棋感；第二是通过机器的增强型学习，获得形势判断的棋感。这两个棋感通过蒙特卡洛树搜索技术进行验证，使AlphaGo实现了技术突破。

　　3 结 语

　　培养学生具备计算思维能力，就是培养学生像计算机科学家那样思维，处理问题时学会从考虑人类与计算机的优势与局限性、要解决问题的复杂度、该类问题目前已有的解决方法及技术等方面着手，最后针对当前问题提出具体的算法、数据结构、程序语言等解决方案。计算机博弈是一种既简单方便、经济实用，又内涵丰富、变化无穷的思维逻辑研究载体，以学生喜闻乐见的、高对抗性的棋牌游戏作为教育和研究载体，将计算思维能力培养贯穿于计算机博弈系统实现的教学中，大大调动了学生的学习与研究热情。近6年来，笔者所在单位的学生在全国大学生计算机博弈比赛中，获得冠、亚、季军10余次，累计奖项50余项，这表明计算机博弈确实是提升学生计算思维能力的有效途径。

本文链接：http://www.qk112.com/lwfw/jiaoyulunwen/xueqianjiaoyu/217840.html