人工智能之计算机博弈相关研究报告

《人工智能导论》课程项目报告项目名称__________________________________学生姓名__________________________学生学号__________________________课程号__________________________任课教师__________________________学生成绩_________________________________________________________院（部）____________________________专业________________班______年___月___日人工智能之计算机博弈相关研究报告曹航2013141463108软件学院软件工程920151210阮树骅311091020人工智能之计算机博弈相关研究报告曹航[e-mail]摘要：计算机博弈（也称机器博弈），是一个挑战无穷、生机勃勃的研究领域，是人工智能领域的重要研究方向，是机器智能、兵棋推演、智能决策系统等人工智能领域的重要科研基础。机器博弈被认为是人工智能领域最具挑战性的研究方向之一。国际象棋的计算机博弈已经有了很长的历史，并且经历了一场波澜壮阔的“搏杀”，“深蓝”计算机的胜利也给人类留下了难以忘怀的记忆。中国象棋计算机博弈的难度绝不亚于国际象棋，不仅涉足学者太少，而且参考资料不多。在国际象棋成熟技术的基础上，结合在中国象棋机器博弈方面的多年实践，总结出一套过程建模、状态表示、着法生成、棋局评估、博弈树搜索、开局库与残局库开发、系统测试与参数优化等核心技术要点,最后提出了当前研究的热点与方向。关键词：极大极小树、人工智能、计算机博弈1.计算机博弈--人工智能的经典领域1.1发展历史计算机博弈，历来是人工智能的一个重要的研究领域，早期人工智能的研究实践，正是从计算机下棋开始。因为人类开发下棋软件，目的是让计算机模仿人脑进行思维，如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心，那些能够存在与下棋活动中的重大原则，或许就存在于其它人格需要人类智能的活动中。所以说，下棋软件某种意义上可以代表人工智能的发展程度从上世纪六十年代的”跳棋机”到1997年的’’深蓝”,计算机下棋程序在人机博弈中取得了一个又一个胜利，但是这些程序虽然属于人工智能范畴，实际上它们并没有多少”智”的成分，主要部分都是在可行范围内搜索。各种研究也大都是怎样使搜索更快更有效。它们缺乏”智”的成分的根本原因，是我们自己并不清楚人类是以怎样的形式思考1的。比如你写一个名字问一位教师，这人是不是他班上的学生。教师马上可以回答是或不是。如果你问计算机，计算机搜索很快，全走一边几乎可以瞬间完成。但我们知道教师是不可能在短时间内把我们所有学生的名单过一遍的。类似的，我们看到一个人的照片，马上就知道我们以前见没见过这个人，我们不可能在短时间内把我们以前见过的人都检查一遍，那么我们是怎样得出结论的呢？现在我们对此还不是完全清楚[]i。1.2对于人类思维的挑战常见机器博弈系统的构成计算机博弈是要让计算机和人类一样能在对抗中做出决策，其典型表现让计算机下棋，下国际象棋，下中国象棋，等等各种棋。现在还有的科学家研究让计算机打牌，打扑克牌，打麻将等。让计算机能像人一样，能够思维、判断和推理，能够作出理性的决策。下棋过程是建立各种形式的数学模型，它属于博弈论的范畴，这是对于人类思维的挑战。下棋时候棋盘上可走的地方很多，但下棋的人并不是每种走法都去考虑。那么哪些为止不需要考虑，这就是”模式识别”问题。人脑有”模式识别”功能，可以很快得出一个大致的结论，计算机没有这种功能，只好所有的位置都考虑。在人机博弈中，计算机人工智能基本的思考方式是穷举法，即通过对所有可能的招法的演化结果进行比较，最后选择一个最好的招法。但是，国际象棋的变化总数达到10的123次方，而中国象棋的变化数量比这还要多得多，可达10的144次方以上，围棋的变化就更多达10的172次方以上，计算机不可能算出棋盘上的所有变化。因此，所谓的”利用穷举法选择最好的走法”，指的是棋局的局部，并且是在有限的步骤里，而不是通盘穷举，它更没办法对整盘棋的形势做正确判断。目前，在三大棋类项目中，国际象棋和中国象棋两项，计算机的水平都已经可以和最顶级的职业选手抗衡了，但在围棋项目中计算机的水平始终上不去，目前围棋计算机大赛获得冠军的软件也只勉强达到业余初段水平，和顶级职业棋手相比，大概要被让七子。1.3人工智能的经典领域2机器博弈是既简单方便、经济实用，又丰富内涵、变化无穷的思维逻辑的研究载体。人机对弈的程序，至少应该具备以下部分：1.某种在机器中表示棋局的方法，能够让程序知道博弈的状态，产生合法走法的规则并能够评估局面优劣；2.通过某个大师的大量棋谱，自动归纳这位大师的下棋风格与特点，长项与弱项。这是知识挖掘的典型课题；3.剖析一盘棋的胜败过程与原因，进而自动修改博弈程序，这是机器学习的典型例题；4.将围棋的各种定式进行表示和分辨，这是模式识别的典型问题；1.4未来趋势—应用前景分析机器博弈最直接的应用之一，便是在作战模拟领域。可以在两军对垒和作战形式上找到相互对应的模式与范例。如兵种的设计与配合、消灭有生力量、围而攻之夺取地盘等。部队的指挥机关在谋划一场战役（斗）之前总是要详细分析双方的兵力部署、战场的自然环境、对方的可能调动、以及大量难以预见的事件、战斗与结果。早期的战事谋划是在物理模型上进行的，称之为沙盘推演。近代的战事谋划，包括日军袭击珍珠港，联合国军诺曼底登陆，美军的海湾战争等都是事先进行过周密的“兵棋推演（”Wargaming,Warsimulation），以便做到“不打无准备之仗”。二战退役的老兵还专门开发了一种游戏，称之为“兵棋”[]ii。在兵棋推演数字化的情况下，兵棋推演的智能化便是必然的发展趋势。如何实现兵棋推演的智能化？如何研制无人作战飞机的联合作战策略？如何在未来的无人作战部队中实现自动指挥与配合？机器博弈的成果必然能够成为诸多关键技术的核心，因为它是人工智能的高级体现[]iii。联合博弈的多Agent学习：在研究Q-Learning算法的基础上,将博弈论中的团队协作理论引入到强化学习中,提出了一种基于联合博弈的多Agent学习算法。该算法通过建立多个阶段博弈,根据回报矩阵对阶段博弈的结果进行评估,为其提供一种有效的A-gent行为决策策略,使每个Agent通过最优均衡解或观察协作Agent的历史动作和自身当前情况来预测其所要执行的动作。对任务调度问题进行仿真实验,验证了该算法的收敛性[]iv。另一个重要的应用方面就是在游戏人工智能设计中，因为游戏中绝大多数人工智能的使用目的就是与玩家博弈，无论是棋牌类游戏，街机格斗类，动作类，还是回合制RPG游戏，处处都充斥了与玩家一较高下的博弈元素。而且由于游戏中游戏机制都是设计好了的，游戏内博弈需要的决策，常常都有规律可循，博弈所需要考虑的参数也往往是确定并且易得的，因此，在游戏中，博弈的程序相对于许多复杂的现实问题更好设计以及实现。下面会讲到游戏中双人博弈最经典的极大极小算法。32.计算机博弈关键技术分析--极大极小搜索算法2.1关于极大极小搜索极大极小搜索策略一般都是使用在一些双人博弈类的游戏之中：这样策略本质上使用的是深度搜索策略，所以一般可以使用递归的方法来实现。在搜索过程中，对一方有利的搜索点上应该取极大值，而对另一方有利的搜索点上应该取极小值。极小值和极大值都是相对而言的。实际上极大或极小都只是一种区分的标记方式而已，无论先手后手都可以用极大或者极小表示。另外极大极小搜索是用于寻找必胜法的。因此，算法的大致思想是先把每一步所导致的局面情况用一个数据结构记录下来。并且将该局面的各种下一步所产生后代局面作为其子节点。于是该游戏所有可能产生的局面便可记录在这一棵树中。2.2算法示例以及问题描述：游戏《大航海时代》中出现过的拿硬币小游戏：拿硬币游戏规则：一共有n枚，两个人轮流拿金币，一次可以拿1到3枚金币，拿到最后一枚金币的人输。2.3算法原理：先为游戏产生所有可能的局面的游戏树。第一位玩家为Max,选取最佳步骤进攻;第二位玩家为Min进行防守，两位玩家每次都尽力寻找必胜法。对于游戏中任意一次局面如果该局面中下一步由Max玩家采取措施且此时局面中存在Max玩家必胜法则将该局面标记为1，如果下一步由Min玩家采取措施且此时局面中存在Min玩家必胜法则将该局面标记0。先给游戏的结束状态如下赋值：Max赢得游戏的状态节点标记为1。Min赢得游戏的状态节点标记为0。然后不断从叶节点向上逐层回溯，对于回溯中遇到的每一个节点，如果他处于Max玩家行动产生下一局面的情况，则该层称为Max层，当子局面中含有被标记为1(即Max玩家可以必胜)时，该层节点也可被标记为1，即Max层（所有深度为偶数的层，树的深度从0开始）的节点其值取子节点中最大值，相反可知Min层（所有深度为奇数的层）的节点其值取子节点中最小值。42.4算法步骤：（1）遍历至每一个叶子节点，并分析游戏在该节点的状态，可以将先手赢标记为1，后手赢标记为0。然后使用一启发式算法为该节点产生一个值，值越高对Max越有利。相反，值越低对Min越有利。（2）进行树的回溯。若父节点为Min，则该父节点值为所有子节点中的最小值（AI选择时，选择最小的子节点的操作进行执行）；若父节点为Max,则父节点的值为所有子节点的最大值（AI选择时，选择最大的子节点的操作进行执行）；如果多个最小（大）值的子节点，则随机选一个（更lifelike）或选第一个(其他方法也可以)。2.5流程图：2.6实现结果评价：5运行截图：成功生成了某一金币下所有游戏的结果的最大最小树，遗憾的是未能以图形化打印树，而是使用了前序遍历输出最大最小树。能够正确判断谁能够在某一情况下必胜。由于不存在胜负不可定局（即任何情况下先手或者后手都能够必胜），所以估价函数f（p）的取值只有0及1两个值附录A：程序主要源代码及实验说明使用说明：开发环境：windows7ultimatex64,visualstudio2013使用环境：WINDOWSx64/x86操作方法：编译生成程序后运行，输入一个整数（起始金币数量，建议不要过大，内存空间会不足，建议在25以下）。按Enter，即可看到前序遍历输出的最大最小树，以及谁能必胜。最大最小树以前序遍历输出，每个节点用(剩余金币数量,f(p))格式输出，子树会在节点后的“{}”内输出实现代码：main.cpp#includeiostream#includeTree.husingnamespacestd;6intGOLD_COIN=3;/*!\curNum该回合后剩下的金币数量\minMaxVal最大最小值,1表示先手赢，0表示后手赢*/classtreeNode{public:intcurNum;intminMaxVal;};boolisChildrenAllEqual(TreetreeNode*tree,intequalVal){if(tree==NULL){returnfalse;}DListIteratorTreetreeNode::Node*it=tree-m_children.GetIterator();while(it.m_node!=tree-m_children.m_tail){if(it.Item()-m_data.minMaxVal!=equalVal){returnfalse;}it.Forth();}if(it.Item()-m_data.minMaxVal!=equalVal){returnfalse;}returntrue;}/*!\GOLD_COIN剩下金币的数量\depth树的深度，从0开始算*/7TreetreeNode*initMinMaxTree(intGOLD_COIN,intdepth){if(GOLD_COIN0||depth