计算机博弈-讲义

计算机博弈-讲义

计算机博弈游戏设计\n课程简介《计算机博弈游戏设计与开发》课程是科技素质教育公共选修课程。《计算机博弈游戏设计与开发》是以博弈算法研究工作为逻辑起点，以全校各专业二年级以上本科学生为讲授对象，是集理论性与应用性为一体的学科。\n课程简介设置本课程的目的是：1.普及计算机博弈的基础知识2.掌握计算机博弈算法的理论、方法、技术3.具备编程实现计算机博弈算法的实际技能4.通过比赛选拔出优秀学生参加国内及国际大赛\n课程简介学习本课程的要求是学习者应在熟练掌握一门编程语言的基础上，掌握计算机博弈（机器博弈）的相关概念，了解计算机博弈的历程及已经取得的成果，掌握计算机博弈的技术构成与内涵，熟悉博弈平台的接口设计，并能按照软件工程的要求编写程序实现一个五子棋博弈策略算法最终在博弈平台上进行比赛决出胜负。\n课程简介先修课程要求必须系统学习过至少一门程序设计语言课程，最好学习过数据结构、数据库原理、算法分析与设计等相关课程。\n教材与参考资料教材PC游戏编程（人机博弈）王小春编著重庆大学出版社2002参考书人工智能及其应用（第4版），蔡自兴，清华大学出版社，2010网络资源东北大学机器博弈研究室，http://www.caaigames.net/index.html中国人工智能网，http://www.chinaai.org/象棋百科全书，http://www.xqbase.com/五子棋资料，http://www.jjie.net/\n考核方法学生成绩由平时成绩和博弈算法程序成绩两部分组成。其中平时成绩占30%，教师将从上课、上机、参与讨论等方面进行考察；博弈算法程序成绩占70%，教师则根据学生形成的算法程序在博弈平台上参与比赛的情况判定等级，并给出最终成绩。\n目录计算机博弈概述棋盘表示走法产生基本搜索技术博弈评估五子棋博弈实例高级搜索技术实训平台：计算机博弈竞赛平台\n1、计算机博弈概述1.1机器博弈简介1.2机器博弈的历史1.3中国象棋人机大战\n1、计算机博弈概述博弈的特征：智力竞技博弈是智力竞技。机器博弈，意味着机器参与博弈，参与智力竞技。机器博弈可以是机器与机器之间的博弈，也可以是机器与人类之间的博弈。我们这里的博弈只涉及双方博弈，即双方对垒的智力游戏，常见的是棋类游戏，如：中国象棋，军旗，围棋，以及国际象棋等。\n1、计算机博弈概述博弈的目标：击败对手博弈的目标是取胜，取胜的棋局如同状态空间法中的目标状态。与华容道游戏一样，游戏者需要对棋局进行操作，以改变棋局，使其向目标棋局转移。然而，华容道游戏只涉及一个主体，不是博弈。博弈涉及多个主体，他们按规则，依次对棋局进行操作，并且，他们的目标是击败对手。\n1、计算机博弈概述双方博弈实例围棋以围棋为例，竞技的双方分为黑方和白方，由黑方开棋，双方轮流行棋，最终，谁占据的地盘大，谁就成为获胜方。\n§01计算机博弈概述计算机博弈（ComputerGames，亦称：机器博弈）就是让计算机能够像人类一样思维，能够下棋。下棋是超越各种专业领域知识局限的智力游戏，并且成为一种智力体育项目，深受广大青少年的喜爱。计算机博弈竞赛是将计算机技术、人工智能技术与体育比赛相结合，以计算机为研究平台，以青年学生耳闻乐见的、娱乐性强的、高对抗性的棋牌为研究载体，借此调动广大青年学生的学习热情与研究兴趣。目前，它已发展成为国内外流行的标准竞赛平台。显然开展计算机博弈竞赛活动，便能充分发挥其推动教学与研究进展的能动作用。\n§01关于计算机博弈早在上世纪50年代，计算机和信息论的先驱者阿兰·图灵（AlanTuring）、克劳德·香浓（ClaudeShannon）等老前辈就都非常重视计算机博弈的研究，指出计算机博弈具有理论的重要性，它的圆满解决，可以帮助解决类似并且重要的其它问题；而且有着很好的应用前景。半个多世纪的实践也证实了他们的预言。\n§01关于计算机博弈下棋本来是孩童就会玩的事情，但是让计算机实现这种思维过程，便成为计算机与人工智能领域的颇具挑战性的研究课题。因为在计算机博弈程序的设计与开发当中，不仅涉及到程序语言、程序设计方法学、图形人机界面、数据结构、软件工程、数据库、知识库、优化与学习算法等等，而且必然面对规模庞大（天文数字）的博弈树的各种搜索算法，如：极大极小、α-β剪枝、迭代深化、蒙特卡洛、基于威胁、证据计数算法等等，内容丰富，变化无穷，可以让年轻人的聪明才智得到充分的发挥。\n§01关于计算机博弈计算机博弈进入门槛并不高，其中的项目特别适合于团队协作，团队成员通过分工合作，完成项目的分析、策略、算法、建模、编程、测试等各项任务，因此，只要会计算机、懂计算机的青年学生都能进入计算机博弈项目小组，都能发现适合自己特点和能力的工作任务。\n1.2机器博弈的历史\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n中国象棋人机大战-2006\n中国象棋人机大战-2006\n中国象棋人机大战-2006\n中国象棋人机大战-2006\n1.3、人机博弈系统1.3.1人机博弈系统的构成1.3.2棋盘表示1.3.3走法产生1.3.4搜索技术1.3.5估值\n1.3.1人机博弈系统的构成人机对弈的程序，至少能具备如下几个部分：某种在机器中表示棋局的方法，能够让程序知道博弈的状态。产生合法走法的规则，以使博弈公正的进行，并可判断人类对手是否乱走。从所有合法的走法中选择最佳的走法的技术。一种评估局面优劣的方法，用以同上面的技术配合做出智能的选择。一个界面，有了它，这个程序才能用。\n1.3.2棋盘表示棋盘表示就是使用一种数据结构来描述棋盘及棋盘上的棋子，通常是使用一个二维数组。一个典型的中国象棋棋盘是使用9X10的二维数组表示。每一个元素代表棋盘上的一个交点。一个没有棋子的交点所对应的元素是0，一个黑帅对应的元素是1，黑士则用2表示等等，依此类推。棋盘的数据表示直接影响到程序的时间及空间复杂度。为了追求更高效率，研究人员针对不同棋类提出了多种不同的表示方法。\n1.3.3走法产生博弈的规则决定了哪些走法是合法的。对有的游戏来说，这很简单，比如五子棋，任何空白的位置都是合法的落子点。但对于象棋来说，就有马走日、象走田等一系列复杂的规则。走法产生是博弈程序中一个相当复杂而且耗费运算时间的方面。不过，通过良好的数据结构，可以显著地提高生成的速度。\n1.3.4搜索技术对于计算机来说，直接通过棋盘信息判别走法的好坏并不精确。除了输赢这样的局面可以可靠地判别外，其他的判断都只能做到大致估计。判别两种走法孰优孰劣的一个好方法就是察看棋局走下去的结果，也就是向下搜索若干步，然后比较发展下去的结果，为了避免差错，我们假定对手的思考也和我们一样，也就是，我们想到的内容，对手也想到了，这就是极大极小搜索算法的基本原则。极大极小搜索算法是本书中所有搜索算法的基础。极大极小搜索算法的时间复杂度是O(bn)。这里b是分枝因子(branchingfactor），指棋局在各种情况下的合法走步的平均值：n是搜索的最大深度，也就是向下搜索的博弈双方的走步。\n1.3.5估值然而，现有的计算机的运算能力仍然十分有限。不可能一直搜索到分出输赢的那一步，在有限搜索深度的末端，我们用一些静态的方法，来估计局面的优势。这些方法在很大程度上依赖于具体的游戏规则和我们对于该游戏的经验知识，其中相当一部分不完全可靠。例如：中国象棋的程序通常将一个炮赋予远高于一个兵的价值，但一个兵在高手的运用之下往往可以产生不次于炮的作用。写出一个好的估值函数并不是一件轻松的事，它需要你对所评估的棋类相当了解，最好是一个经验丰富的高手。然后还要进行无数次的试验，经历几番失败后才可能得到一个令人满意的估值函数。\n2、棋盘表示2.1一般表示法2.2比特棋盘\n2.1一般表示法棋盘表示主要探讨的是使用什么数据结构来表示棋盘上的信息。一般说来，这与具体的棋类知识密切相关。通常，用来描述棋盘及其上棋子信息的是一个二维数组。例如，可以用一个9X10个字节的二维数组来表示中国象棋的棋盘，数组中每一个字节代表棋盘上的一个交点，其值表明这个交点上放置的是一个什么棋子或是没有棋子，如图2.1所示：也可以用19X19个字节的二维数组来表示围棋的棋盘，在其上用值为0的字节表示该点空白，1表示该点有一个黑棋，2表示该点有一个白棋。\n2.1一般表示法\n2.1一般表示法设计一种数据结构来表示一种棋类游戏的状态往往要考虑3个方面的问题：占用的空间数量操作速度使用方便与否\n2.1一般表示法在早期的博弈编程中，由于内存极其有限，一些程序采用了极为紧凑的数据结构来表示棋盘上的信息。例如：中国象棋共有14种不同的棋子，红黑各7种，所以棋盘上1个交点的状态最多只能有15种，停放某种棋子或者空白。基于这种思想，显然可以用4位来表示一个交点。也就是说，可以用一个字节来表示两个交点。这样表示整个棋盘的信息就只需要一个9X5个字节的二维数组了。可以让每个字节的高4位代表奇数行的交点，让低4位代表偶数行的交点。一个棋盘状态总共需要45个字节来表示。\n如果从棋子的观点出发，将棋盘看作是一个平面坐标系，可以看出每一个棋子的位置信息，包含一个小于10的横坐标和一个小于11的纵坐标。显然，我们使用一个有32个字节的一维数组就可以表示所有32个棋子的位置，每个字节的高4位表示该棋子的横坐标，低4位表示该棋子的纵坐标。已被吃掉的棋子用一个坐标范围以外的数表示。这样整个棋盘上的信息就被装进了这32个字节当中。\n2.1一般表示法紧凑的数据表示会赢得空间上的优势，这往往也伴随着时间上的优势。复制32个字节的棋盘信息无疑会快于90个字节的棋盘，但并不意味着所有的运算和操作都会更快。使用32个字节的数据表示，程序员在确定一个棋子的位置时往往需要增加额外的移位操作以取出一个字节中含有的两个坐标信息。\n2.2比特棋盘随着计算机存储能力的大幅度提高，棋盘表示的空间需求往往已不是设计人员最为关注的问题。而考虑更多的问题是性能。不太直观的紧凑结构往往不那么容易被理解和使用，这意味这更多的潜在错误和更长的调试时间。当然如果能够使内存需求量降低并且无损性能，设计人员（尤其是为硬件能力较低的掌上电脑或手机编程的人员）仍会倾向于使用紧凑的结构。\n2.2比特棋盘在高性能的博弈程序里，往往有一些特别的数据表示。例如在国际象棋的棋盘表示中，很多情况下会采用8X8的数组来表示棋盘。但是有一种更精巧的结构，比特棋盘（BitBoards），也获得了广泛使用。20世纪60年代末，前苏联的KAISSA项目组提出了比特棋盘的技术。此技术后来应用于64位主机，用一个64位数表示一种棋子的位置。这样一个国际象棋棋盘上的全部信息就可用12个比特棋盘表示，也就是12个64位数。使用比特棋盘可以极大程度地提高某些运算的速度。例如在一个国际象棋的局面里，你要检查黑王是否被白后将军了。如果采用8*8的数组表示，你需要完成如下步骤：\n2.2比特棋盘先扫描数组找到白后的位置。往往要多次载入\比较操作。找出白后可到达的位置，检查黑王是否在其中一个位置上；如果是，就可以断定将军了。这往往也要多次比较操作。而使用比特棋盘表示，你只需执行如下操作：载入代表白后的比特棋盘，一个64位数。利用这个比特棋盘，在预先建立的数据库中索引到代表白后可攻击到的位置的比特棋盘。将这个比特棋盘和代表黑王的比特棋盘执行按位与操作，如果结果是0，则没有将军；否则，黑王就被白后将军了。\n2.2比特棋盘两种方法在运算量上的差异是巨大的。当然，中国象棋的棋盘不是8X8的，其他很多种棋类游戏也不是，而大多数人使用的PC是32位的处理器。但比特棋盘的方法对于设计高效的数据表示仍有积极意义。实际上不少PC平台上的顶级国际象棋程序都使用了比特棋盘，同64位主机相比，32位的PC处理器处理64位数可能多花一倍或更多的时钟周期，但仍比8X8的数据表示快得多。读者可以将类似的方法运用到自己的博弈程序当中。本书的范例将采用最便于理解的表示方法，也就是9X10的二维数组来表示中国象棋的棋盘信息。目的在于让读者清晰地把握棋盘表示的本质，并能够将注意力集中到本书所介绍的方法上，以免对读者的理解构成不必要的障碍。\n3、走法产生3.1产生方法3.2产生效率3.3逐个与全部3.4内存分析\n3.1产生方法走法产生是指将一个局面的所有可能的走法全部罗列出来。五子棋象棋\n3.2产生效率走法产生需要搜索为了提高产生的速度，需要进行优化，优化和具体棋类规则有关象棋中，每个棋子的移动需要复杂的判断构建数据库可以减少判断的计算量，就可以计算出合法的走法以象棋中的象为例\n3.3逐个与全部逐个产生对于一个局面的所有直接后继，一次产生一种走法，然后搜索之全部产生一次产生所有走法，然后搜索之绝大部分情况是一次产生一个局面的全部走法，然后调整顺序\n3.4内存分析产生走法时，通常将走法队列置于预先的内存中，以避免频繁申请以中国象棋为例\n4、基本搜索技术什么是搜索盲目搜索一个一个的检查对抗性搜索\n4、基本搜索技术4.1博弈树4.2极大极小值算法4.3深度优先搜索4.4负极大值算法\n4.1博弈树博弈树把所有的走法都列出来树根是棋局的初始局面根的若干子节点是甲的每种可能走法所生成的局面，而这些节点的子节点又是对方每种可能走法产生的局面树的末梢是结束局面：一方获胜、平局\n4.1博弈树博弈树从根部向下递归产生的一颗包含所有可能的对弈过程的搜索树，是完全搜索树搜索过程分析不可能建立完全搜索树很多情形根本到达不了叶节点节点数量太多，超过计算机的处理能力\n4.2极大极小值算法棋局优劣的评价标准假设甲胜的局面为1，乙胜的局面为-1，和局的值为0如何搜索？最有利于甲，最不利于乙的走法假设甲胜的局面为+∞，乙胜的局面为-∞，和局的值为0如何搜索？静态估值函数\n4.3深度优先搜索\n4.4负极大值算法\n5、博弈评估博弈评估是通过既有的棋类知识来评估局面优劣的过程对棋类知识依赖很深，但仍有规律可循\n5、博弈评估5.1棋子的价值评估5.2棋子的灵活性与棋盘控制5.3棋子关系的评估5.4与搜索算法配合\n5.1棋子的价值评估以中国象棋为例每个棋子赋予权值一方的棋子价值计算公式棋子价值评估要和其他知识相结合，可以提供评估函数的知识水平兵是否过河\n5.2棋子的灵活性与棋盘控制\n5.3棋子关系的评估\n5.4与搜索算法配合\n6、五子棋博弈实例\n7、高级搜索技术