《计算机博弈-讲义》ppt课件

《《计算机博弈-讲义》ppt课件》由会员分享，可在线阅读，更多相关《《计算机博弈-讲义》ppt课件（77页珍藏版）》请在金锄头文库上搜索。

1、计算机博弈游戏设计,课程简介,计算机博弈游戏设计与开发课程是科技素质教育公共选修课程。计算机博弈游戏设计与开发是以博弈算法研究工作为逻辑起点，以全校各专业二年级以上本科学生为讲授对象，是集理论性与应用性为一体的学科。,课程简介,设置本课程的目的是： 1.普及计算机博弈的基础知识 2.掌握计算机博弈算法的理论、方法、技术 3.具备编程实现计算机博弈算法的实际技能 4.通过比赛选拔出优秀学生参加国内及国际大赛,课程简介,学习本课程的要求是 学习者应在熟练掌握一门编程语言的基础上，掌握计算机博弈（机器博弈）的相关概念， 了解计算机博弈的历程及已经取得的成果，掌握计算机博弈的技术构成与内涵， 熟悉博弈

2、平台的接口设计，并能按照软件工程的要求编写程序实现一个五子棋博弈策略算法 最终在博弈平台上进行比赛决出胜负。,先修课程要求 必须系统学习过至少一门程序设计语言课程，最好学习过数据结构、数据库原理、算法分析与设计等相关课程。,教材与参考资料,教材 PC游戏编程（人机博弈） 王小春 编著 重庆大学出版社 2002 参考书 人工智能及其应用（第4版） ，蔡自兴，清华大学出版社，2010 网络资源 东北大学机器博弈研究室，http:/ 中国人工智能网，http:/www.chinaai.org/ 象棋百科全书，http:/ 五子棋资料，http:/ 棋盘表示 走法产生 基本搜索技术 博弈评估 五子棋博

3、弈实例 高级搜索技术 实训平台：计算机博弈竞赛平台,1、计算机博弈概述,1.1 机器博弈简介 1.2 机器博弈的历史 1.3 中国象棋人机大战,1、计算机博弈概述,博弈的特征： 智力竞技,博弈是智力竞技。,机器博弈，意味着机器参与博弈，参与智力竞技。机器博弈可以是机器与机器之间的博弈，也可以是机器与人类之间的博弈。,我们这里的博弈只涉及双方博弈，即双方对垒的智力游戏，常见的是棋类游戏，如：中国象棋，军旗，围棋，以及国际象棋等。,1、计算机博弈概述,博弈的目标： 击败对手,博弈的目标是取胜，取胜的棋局如同状态空间法中的目标状态。,与华容道游戏一样，游戏者需要对棋局进行操作，以改变棋局，使其向目标

4、棋局转移。,然而，华容道游戏只涉及一个主体，不是博弈。,博弈涉及多个主体，他们按规则，依次对棋局进行操作，并且，他们的目标是击败对手。,1、计算机博弈概述,双方博弈实例 围棋,01 计算机博弈概述,计算机博弈（Computer Games，亦称：机器博弈）就是让计算机能够像人类一样思维，能够下棋。下棋是超越各种专业领域知识局限的智力游戏，并且成为一种智力体育项目，深受广大青少年的喜爱。 计算机博弈竞赛是将计算机技术、人工智能技术与体育比赛相结合，以计算机为研究平台，以青年学生耳闻乐见的、娱乐性强的、高对抗性的棋牌为研究载体，借此调动广大青年学生的学习热情与研究兴趣。目前，它已发展成为国内外流行

5、的标准竞赛平台。显然开展计算机博弈竞赛活动，便能充分发挥其推动教学与研究进展的能动作用。,01 关于计算机博弈,早在上世纪50年代，计算机和信息论的先驱者阿兰图灵（Alan Turing）、克劳德香浓（Claude Shannon）等老前辈就都非常重视计算机博弈的研究，指出计算机博弈具有理论的重要性，它的圆满解决，可以帮助解决类似并且重要的其它问题；而且有着很好的应用前景。半个多世纪的实践也证实了他们的预言。,01 关于计算机博弈,下棋本来是孩童就会玩的事情，但是让计算机实现这种思维过程，便成为计算机与人工智能领域的颇具挑战性的研究课题。 因为在计算机博弈程序的设计与开发当中，不仅涉及到程序语

6、言、程序设计方法学、图形人机界面、数据结构、软件工程、数据库、知识库、优化与学习算法等等， 而且必然面对规模庞大（天文数字）的博弈树的各种搜索算法，如：极大极小、-剪枝、迭代深化、蒙特卡洛、基于威胁、证据计数算法等等，内容丰富，变化无穷，可以让年轻人的聪明才智得到充分的发挥。,01 关于计算机博弈,计算机博弈进入门槛并不高，其中的项目特别适合于团队协作，团队成员通过分工合作，完成项目的分析、策略、算法、建模、编程、测试等各项任务， 因此，只要会计算机、懂计算机的青年学生都能进入计算机博弈项目小组，都能发现适合自己特点和能力的工作任务。,1.2 机器博弈的历史,中国象棋人机大战-2006,中国象

7、棋人机大战-2006,中国象棋人机大战-2006,中国象棋人机大战-2006,1.3、人机博弈系统,1.3.1 人机博弈系统的构成 1.3.2 棋盘表示 1.3.3 走法产生 1.3.4 搜索技术 1.3.5 估值,1.3.1 人机博弈系统的构成,人机对弈的程序，至少能具备如下几个部分： 某种在机器中表示棋局的方法，能够让程序知道博弈的状态。 产生合法走法的规则，以使博弈公正的进行，并可判断人类对手是否乱走。 从所有合法的走法中选择最佳的走法的技术。 一种评估局面优劣的方法，用以同上面的技术配合做出智能的选择。 一个界面，有了它，这个程序才能用。,1.3.2 棋盘表示,棋盘表示就是使用一种数据

8、结构来描述棋盘及棋盘上的棋子，通常是使用一个二维数组。一个典型的中国象棋棋盘是使用9X10的二维数组表示。每一个元素代表棋盘上的一个交点。一个没有棋子的交点所对应的元素是0，一个黑帅对应的元素是1，黑士则用2表示等等，依此类推。 棋盘的数据表示直接影响到程序的时间及空间复杂度。为了追求更高效率，研究人员针对不同棋类提出了多种不同的表示方法。,1.3.3 走法产生,博弈的规则决定了哪些走法是合法的。对有的游戏来说，这很简单，比如五子棋，任何空白的位置都是合法的落子点。但对于象棋来说，就有马走日、象走田等一系列复杂的规则。 走法产生是博弈程序中一个相当复杂而且耗费运算时间的方面。不过，通过良好的数

9、据结构，可以显著地提高生成的速度。,1.3.4 搜索技术,对于计算机来说，直接通过棋盘信息判别走法的好坏并不精确。除了输赢这样的局面可以可靠地判别外，其他的判断都只能做到大致估计。判别两种走法孰优孰劣的一个好方法就是察看棋局走下去的结果，也就是向下搜索若干步，然后比较发展下去的结果，为了避免差错，我们假定对手的思考也和我们一样，也就是，我们想到的内容，对手也想到了，这就是极大极小搜索算法的基本原则。极大极小搜索算法是本书中所有搜索算法的基础。 极大极小搜索算法的时间复杂度是O(bn)。这里b是分枝因子(branching factor），指棋局在各种情况下的合法走步的平均值：n是搜索的最大深度

10、，也就是向下搜索的博弈双方的走步。,1.3.5 估值,然而，现有的计算机的运算能力仍然十分有限。不可能一直搜索到分出输赢的那一步，在有限搜索深度的末端，我们用一些静态的方法，来估计局面的优势。这些方法在很大程度上依赖于具体的游戏规则和我们对于该游戏的经验知识，其中相当一部分不完全可靠。例如：中国象棋的程序通常将一个炮赋予远高于一个兵的价值，但一个兵在高手的运用之下往往可以产生不次于炮的作用。 写出一个好的估值函数并不是一件轻松的事，它需要你对所评估的棋类相当了解，最好是一个经验丰富的高手。然后还要进行无数次的试验，经历几番失败后才可能得到一个令人满意的估值函数。,2、棋盘表示,2.1 一般表示

11、法 2.2 比特棋盘,2.1 一般表示法,棋盘表示主要探讨的是使用什么数据结构来表示棋盘上的信息。一般说来，这与具体的棋类知识密切相关。通常，用来描述棋盘及其上棋子信息的是一个二维数组。 例如，可以用一个9X10个字节的二维数组来表示中国象棋的棋盘，数组中每一个字节代表棋盘上的一个交点，其值表明这个交点上放置的是一个什么棋子或是没有棋子，如图2.1所示：也可以用19X19个字节的二维数组来表示围棋的棋盘，在其上用值为0的字节表示该点空白，1表示该点有一个黑棋，2表示该点有一个白棋。,2.1 一般表示法,2.1 一般表示法,设计一种数据结构来表示一种棋类游戏的状态往往要考虑3个方面的问题： 占用

12、的空间数量 操作速度 使用方便与否,2.1 一般表示法,在早期的博弈编程中，由于内存极其有限，一些程序采用了极为紧凑的数据结构来表示棋盘上的信息。例如：中国象棋共有14种不同的棋子，红黑各7种，所以棋盘上1个交点的状态最多只能有15种，停放某种棋子或者空白。 基于这种思想，显然可以用4位来表示一个交点。也就是说，可以用一个字节来表示两个交点。这样表示整个棋盘的信息就只需要一个9X5个字节的二维数组了。可以让每个字节的高4位代表奇数行的交点，让低4位代表偶数行的交点。一个棋盘状态总共需要45个字节来表示。,如果从棋子的观点出发，将棋盘看作是一个平面坐标系，可以看出每一个棋子的位置信息，包含一个小

13、于10的横坐标和一个小于11的纵坐标。 显然，我们使用一个有32个字节的一维数组就可以表示所有32个棋子的位置，每个字节的高4位表示该棋子的横坐标，低4位表示该棋子的纵坐标。已被吃掉的棋子用一个坐标范围以外的数表示。这样整个棋盘上的信息就被装进了这32个字节当中。,2.1 一般表示法,紧凑的数据表示会赢得空间上的优势，这往往也伴随着时间上的优势。复制32个字节的棋盘信息无疑会快于90个字节的棋盘，但并不意味着所有的运算和操作都会更快。 使用32个字节的数据表示，程序员在确定一个棋子的位置时往往需要增加额外的移位操作以取出一个字节中含有的两个坐标信息。,2.2 比特棋盘,随着计算机存储能力的大幅

14、度提高，棋盘表示的空间需求往往已不是设计人员最为关注的问题。而考虑更多的问题是性能。 不太直观的紧凑结构往往不那么容易被理解和使用，这意味这更多的潜在错误和更长的调试时间。当然如果能够使内存需求量降低并且无损性能，设计人员（尤其是为硬件能力较低的掌上电脑或手机编程的人员）仍会倾向于使用紧凑的结构。,2.2 比特棋盘,在高性能的博弈程序里，往往有一些特别的数据表示。例如在国际象棋的棋盘表示中，很多情况下会采用8X8的数组来表示棋盘。但是有一种更精巧的结构，比特棋盘（Bit Boards），也获得了广泛使用。 20世纪60年代末，前苏联的KAISSA项目组提出了比特棋盘的技术。此技术后来应用于64

15、位主机，用一个64位数表示一种棋子的位置。这样一个国际象棋棋盘上的全部信息就可用12个比特棋盘表示，也就是12个64位数。使用比特棋盘可以极大程度地提高某些运算的速度。例如在一个国际象棋的局面里，你要检查黑王是否被白后将军了。如果采用8*8的数组表示，你需要完成如下步骤：,2.2 比特棋盘,先扫描数组找到白后的位置。往往要多次载入比较操作。 找出白后可到达的位置，检查黑王是否在其中一个位置上；如果是，就可以断定将军了。这往往也要多次比较操作。 而使用比特棋盘表示，你只需执行如下操作： 载入代表白后的比特棋盘，一个64位数。 利用这个比特棋盘，在预先建立的数据库中索引到代表白后可攻击到的位置的比特棋盘。 将这个比特棋盘和代表黑王的比特棋盘执行按位与操作，如果结果是0，则没有将军；否则，黑王就被白后将军了。,2.2 比特棋盘,两种方法在运算量上的差异是巨大的。 当然，中国象棋的棋盘不是8X8的，其他很多种棋类游戏也不是，而大多数人使用的PC是32位的处理器。但比特棋盘的方法对于设计高效的数据表示仍有积极意义。实际上不少PC平台上的顶级国际象棋程序都使用了比特棋盘，同64位主机相比，32位的PC处理器处理64位数可能多花一倍或更多的时钟周期，但仍比8X8的数据表示快得多。读者可以将类似的方法运用到自己的博弈程序当中。 本书的范例将采用最便于理解的表示方法，也就是9X