人工智能技术导论——博弈树搜索
我在之前整理过一篇博客关于博弈论和纳什均衡的几个例子https://www.cnblogs.com/wkfvawl/p/11725263.html
这里来介绍博弈树搜索。
一、博弈树的概念在博弈过程中,任何一方都希望自己取得胜利。因此,当某一方当前有多个行动方案可供选择时,他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时,如果我们站在A方的立场上,则可供A方选择的若干行动方案之间是“或”关系,因为主动权操在A方手里,他或者选择这个行动方案,或者选择另一个行动方案,完全由A方自己决定。当A方选取任一方案走了一步后,B方也有若干个可供选择的行动方案,此时这些行动方案对A方来说它们之间则是“与”关系,因为这时主动权操在B方手里,这些可供选择的行动方案中的任何一个都可能被B方选中,A方必须应付每一种情况的发生。 这样,如果站在某一方(如A方,即在A要取胜的意义下),把上述博弈过程用图表示出来,则得到的是一棵“与或树”。描述博弈过程的与或树称为博弈树,它有如下特点： (1)博弈的初始格局是初始节点。 (2)在博弈树中,“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系,对方扩展的节点之间是“与”关系。双方轮流地扩展节点。 (3)所有自己一方获胜的终局都是本原问题,相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。
二、极小极大值分析法在二人博弈问题中,为了从众多可供选择的行动方案中选出一个对自己最为有利的行动方案,就需要对当前的情况以及将要发生的情况进行分析,从中选出最优的走步。最常使用的分析方法是极小极大分析法。其基本思想是： (1)设博弈的双方中一方为A,另一方为B。然后为其中的一方(例如A)寻找一个最优行动方案。(2)为了找到当前的最优行动方案,需要对各个可能的方案所产生的后果进行比较。具体地说,就是要考虑每一方案实施后对方可能采取的所有行动,并计算可能的得分。 (3)为计算得分,需要根据问题的特性信息定义一个估价函数,用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。 (4)当端节点的估值计算出来后,再推算出父节点的得分,推算的方法是：对“或”节点,选其子节点中一个最大的得分作为父节点的得分,这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点,选其子节点中一个最小的得分作为父节点的得分,这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。 (5)如果一个行动方案能获得较大的倒推值,则它就是当前最好的行动方案。
倒推值的计算
在博弈问题中,每一个格局可供选择的行动方案都有很多,因此会生成十分庞大的博弈树。据统计,西洋跳棋完整的博弈树约有1040个节点。试图利用完整的博弈树来进行极小极大分析是困难的。可行的办法是只生成一定深度的博弈树,然后进行极小极大分析,找出当前最好的行动方案。在此之后,再在已选定的分支上扩展一定深度,再选最好的行动方案。如此进行下去,直到取得胜败的结果为止。至于每次生成博弈树的深度,当然是越大越好,但由于受到计算机存储空间的限制,只好根据实际情况而定。
例一字棋游戏。设有如图(a)所示的九个空格,由A,B二人对弈,轮到谁走棋谁就往空格上放一只自己的棋子,谁先使自己的棋子构成“三子成一线”谁就取得了胜利。
一字棋
设A的棋子用“a”表示,B的棋子用“b”表示。为了不致于生成太大的博弈树,假设每次仅扩展两层。估价函数定义如下： 设棋局为P,估价函数为e(P)。 (1)若P是A必胜的棋局,则e(P)=+∞。 (2)若P是B必胜的棋局,则e(P)=-∞。 (3)若P是胜负未定的棋局,则e(P)=e(+P)-e(-P)其中e(+P)表示棋局P上有可能使a成为三子成一线的数目；
e(-P)表示棋局P上有可能使b成为三子成一线的数目。
例如,对于图(b)所示的棋局,则
按照棋盘上红色连线安放棋子a使得三子成一线，共6条连线。
按照棋盘上蓝色连线安放棋子b使得三子成一线，共4条连线。e(P)=6-4=2
另外,我们假定具有对称性的两个棋局算作一个棋局。还假定A先走棋,我们站在A的立场上。 下图给出了A的第一着走棋生成的博弈树。图中节点旁的数字分别表示相应节点的静态估值或倒推值。由图可以看出,对于A来说最好的一着棋是S3,因为S3比S1和S2有较大的倒推值。
一字棋极小极大搜索
在A走S3这一着棋后,B的最优选择是S4,因为这一着棋的静态估值较小,对A不利。不管B选择S4或S5,A都要再次运用极小极大分析法产生深度为2的博弈树,以决定下一步应该如何走棋,其过程与上面类似,不再重复。
三、α-β剪枝技术
上述的极小极大分析法,实际是先生成一棵博弈树,然后再计算其倒推值。这样做的缺点是效率较低。于是,人们又在极小极大分析法的基础上,提出了α-β剪枝技术。 这一技术的基本思想是,边生成博弈树边计算评估各节点的倒推值,并且根据评估出的倒推值范围,及时停止扩展那些已无必要再扩展的子节点,即相当于剪去了博弈树上的一些分枝,从而节约了机器开销,提高了搜索效率。具体的剪枝方法如下:
(1)对于一个与节点MIN,若能估计出其倒推值的上确界β,并且这个β值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界α,即α≥β,则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为α剪枝。(2)对于一个或节点MAX,若能估计出其倒推值的下确界α,并且这个α值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界β, 即α≥β,则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为β剪枝。
认真品味上面的两句规则，下面给出一个具体的α-β剪枝的实例。
使用ScreenToGif截的PPT图，关于ScreenToGif的使用说明参见https://www.cnblogs.com/wkfvawl/p/11625823.html
这里来说一下剪枝过程，F下的第一个节点是K，其值为4，这时作为MIN节点的F上确界β为4，F下的第二个节点L和第三个节点M的值都拿来比较，但都大于4，所以F节点MIN值还是4。这时MAX节点C的下确界α为4，并将α传递给MIN节点G。
G下的第一个节点为1，此时作为MIN节点G的上确界β为1，留意到此时G的α=4＞β，所以无需再探索G的剩余子节点，把未探索的子节点通过α剪枝剪掉。
这里C的父节点A是一个MIN节点，A的估计上确界β便是4。接着我们对A的右子树进行查找，并将β传递下去。
对于MIN节点H，其下的第一个子节点P值为5，大于4，因而接着比较第二个子节点Q值为8，也大于4，因而H节点MIN值的上确界β便是5，P的父节点D是一个MAX节点，因而此时D的下确界α值为5。
由于D的父节点A是一个MIN节点，A的估计倒推值的上确界β为4，小于D的下确界5，因而就不必去扩展MAX节点D的其他子节点了，进行了β剪枝。
这是就可以确定节点A的父亲节点S0，其为MAX节点的下确界α为4，这就对S0右子树进行查找。并直接将下确解α沿着S0->B->E->I传递，深入到I。
对于MIN节点I，其下的第一个子节点R值为0，这时作为MIN节点I的上确界β为0，留意到此时I的α=4＞β，所以无需再探索I的剩余子节点，把未探索的子节点通过α剪枝剪掉。
I的父节点是一个MAX节点，更新其父节点E的下确界α为0。将E的α传递给J。
这时对于MIN节点J，其下的第一个子节点S值为-6，这时作为MIN节点I的上确界β为-6，留意到此时J的α=0＞β，所以无需再探索J的剩余子节点，把未探索的子节点通过α剪枝剪掉。
这时确定了E，E的父亲节点B是一个MIN节点，通过E其上确界β更新为0，但E的父亲节点的α为4，α=4＞β，所以无需再探索B的剩余子节点，把未探索的子节点通过α剪枝剪掉。
最终确定S0，搜索完成。
关于α-β剪枝的过程，还想要了解一个，可以参考这篇博客
https://www.7forz.com/3211/
http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html
一些碎碎念，今天给同学讲α-β剪枝，把他弄迷糊了，后来我想可能还是太官方了，这种剪枝策略其本质思想是朴素的，就是在确定父亲节点的一个上确界或下确界之后，如果子节点不在该外围内就不去探索了，这就是剪枝。
《人工智能（第2版）》之状态空间图
本文摘自人民邮电出版社《人工智能（第2版）》item.jd.com/12401871.ht…在本章中，我们从在人工智能中经常遇到的最重要的问题之一——搜索开始学习。我们的目标是介绍在AI中用于求解问题的最流行方法：搜索、知识表示和学习。我们开始学习基本的搜索算法——所谓的“无信息搜索”或“盲目搜索”的方法。这些算法不依赖任何问题领域的特定知识。正如我们将看到的，这些算法通常需要大量的空间和时间。
2.0 简介：智能系统中的搜索搜索是大多数人生活中的自然组成部分。我们都放错过房子钥匙或电视遥控器，然后检查口袋，翻箱倒柜。有时候，搜索可能更多是在大脑中进行。你可能有时突然不记得自己到访过的地方的名字、真正喜欢的电影中演员的名字，或者不记得曾经谙熟于心的歌词。要想起来这些事，可能需要几秒钟（记忆力衰退时或许更长）。
许多算法专门通过列表进行搜索和排序。当然，人们同意，如果数据按照逻辑顺序组织，那么搜索就会比较方便一些。想象一下，如果姓名和电话号码随机排列，那么搜索相对较大城市的电话簿会有多麻烦。因此，搜索和信息组织在智能系统的设计中发挥了重要作用，这并不奇怪。也许我们要搜索曾经到访过地方的名字或序列中的下一个数字（见第1章），抑或是井字游戏或跳棋游戏中下一步最佳移动（见第4章和第16章）。人们认为，可以非常快地解决此类问题的人，通常比其他人更聪明。软件系统也通常使用相同的术语，例如，人们也认为，性能更好的国际象棋博弈程序比同类型的程序更加智能。
本章介绍了几种基本搜索算法。2.1节首先介绍一个有助于形式化搜索过程的数学结构——状态空间图。在众所周知的假币问题（FalseCoinProblem）中，人们必须通过对两个或更多个硬币进行称重来识别假币，其中就展示了这种结构。接下来，本章介绍和解释了生成和测试（generate-and-test）搜索范式。生成器模块系统地提出了问题的可能解，而测试器模块验证了解的正确性。
本章还引入了两种经典的搜索方法：贪婪算法和回溯。这两种方法都是先将问题分成若干步骤。例如，如果你要将8个皇后放在棋盘上，任何两个皇后都不会互相攻击，也就是说，任何两个皇后都没有占据同一行、同一列或同一对角线。第1步就是将第一个皇后放在棋盘上，第2步就是将第二个皇后放在安全的方格中，以此类推。正如你在2.2节中所看到的，在选用何种标准做出具体选择方面，这两种方法互不相同。
2.3节解释了盲目搜索算法。盲目或无信息搜索算法是一种不需要使用问题领域知识的方法。例如，假设你正在迷宫中找出路。在盲目搜索中，你可能总是选择最左边的路线，而不考虑任何其他可替代的选择。两种典型的盲目搜索算法是宽度优先搜索（BFS）和深度优先搜索（DFS）——在第1章中已经做了简要介绍。回想一下，在继续前进之前，BFS在离开始位置的指定距离处仔细查看所有替代选项。BFS的优点是，如果一个问题存在解，那么BFS就会找到它。
但是，如果在每个节点的可替代选项很多，那么BFS可能会因需要消耗太多的内存而变得不切实际。DFS采用了不同的策略来达到目标：在寻找可替代路径之前，它追求寻找单一的路径来实现目标。DFS内存需求合理，但是它可能会因偏离开始位置无限远而错过了相对靠近搜索起始位置的解。具有迭代加深的DFS是介于BFS和DFS之间的折中方案，它将DFS中等空间需求与BFS提供能找到解的确定性结合到了一起。
2.1 状态空间图状态空间图（state-spacegraph）是对一个问题的表示，通过问题表示，人们可以探索和分析通往解的可能的可替代路径。特定问题的解将对应状态空间图中的一条路径。有时候，我们要搜索一个问题的任意解；而有时候，我们希望得到一个最短（最优）的解。本章将主要关注所谓的盲目搜索方法，即寻找发现任意解。第3章将重点关注知情搜索算法，这些算法通常可以发现问题的最佳解。
假币问题在计算机科学中，一个众所周知的问题是假币问题。有12枚硬币，已知其中一枚是假的或是伪造的，但是不知道假币是比其他币更轻还是更重。普通的秤可以用于确定任何两组硬币的质量，即一组硬币比另一组硬币更轻或更重。为了解决这个问题，你应该创建一个程序，通过称量三组硬币的组合，来识别假币。
在这一章中，我们将解决一个相对简单的问题实例，这只涉及6枚硬币；与上述的原始问题一样，它也需要比较三组硬币，但是在这种情况下，任何一组硬币的硬币枚数相对较少，我们称之为最小假币问题。我们使用符号Ci1Ci2…Cir：Cj1Cj2…Cjr来指示r枚硬币，比较Ci1Ci2…Cir与另r枚硬币Cj1Cj2…Cjr的质量大小。结果是，要么这两组硬币同样重，要么不一样重。我们不需要进一步知道左边盘子的硬币是否比右边盘子的硬币更重或是更轻（如果要解决这个问题的12枚硬币的版本，就需要知道其他知识）。最后，我们采用记号[Ck1Ck2…Ckm]来指示具有m枚硬币的子集是所知道的包含了假币的最小硬币集合。图2.1给出了这个最小假币问题的一个解。
如图2.1所示，状态空间树由节点和分支组成。一个椭圆是一个节点，代表问题的一个状态。节点之间的弧表示将状态空间树移动到新节点的算符（或所应用的算符）。请参考图2.1中标有（*）的节点。这个节点[C1C2C3C4]表示假币可能是C1、C2、C3或C4中的任何一个。我们决定对C1和C2以及C5和C6之间的质量大小（应用算符）进行比较。如果结果是这两个集合中的硬币质量相等，那么就知道假币必然是C3或C4中的一个；如果这两个集合中的硬币质量不相等，那么我们确定C1或C2是假币。为什么呢？状态空间树中有两种特殊类型的节点。第一个是表示问题起始状态的起始节点。在图2.1中，起始节点是[C1C2C3C4C5C6]，这表明起始状态时，假币可以是6枚硬币中的任何一个。另一种特殊类型的节点对应于问题的终点或最终状态。图2.1中的状态空间树有6个终端节点，每个标记为[Ci]（i=1,…,6），其中i的值指定了哪枚是假币。
图2.1 最小假币问题的解
问题的状态空间树包含了问题可能出现的所有状态以及这些状态之间所有可能的转换。事实上，由于回路经常出现，这样的结构通常称为状态空间图。问题的解通常需要在这个结构中搜索（无论它是树还是图），这个结构始于起始节点，终于终点或最终状态（goalstate）。有时候，我们关心的是找到一个解（不论代价）；但有时候，我们可能希望找到最低代价的解。
说到解的代价，我们指的是到达目标状态所需的算符的数量，而不是实际找到此解所需的工作量。相比计算机科学，解的代价等同于运行时间，而不是软件开发时间。
到目前为止，我们不加区别地使用了节点（node）和状态（state）这两个术语。但是，这是两个不同的概念。通常情况下，状态空间图可以包含代表相同问题状态的多个节点，如图2.2所示。回顾最小假币问题可知，通过对两个不同集合的硬币进行称重，可以到达表示相同状态的不同节点。
图2.2 状态空间图中的不同节点可以表示相同的状态
如图2.1所示，这是最小假币问题的解。解决这个问题的人穿着一件蓝色的衬衫，或者在处理12硬币版本的问题时，其他人需要一大杯咖啡，这些可能都是真的。但是，这些细节应该与解无关。抽象允许你抛开这样的细节。
在求解过程中，可以有意忽略系统的某些细节，这样就可以允许在合理的层面与系统进行交互，这就是在第1章中定义的抽象。例如，如果你想玩棒球，那么抽象就可以更好地让你练习如何打弧线球，而不是让你花6年时间成为研究物体如何移动的力学方面的博士。
人工智能
文章目录启发性信息估价函数启发式搜索依据的是问题自身的启发性信息。而启发性信息又通过估价函数作用到搜索过程中。启发性信息是指与具体问题求解过程有关的，并可制导搜索过程朝着最有希望方向前进的控制信息
有效地帮助确定扩展节点的信息有效地帮助决定哪些后继节点生成的信息能决定在扩展一个节点时哪些节点应从搜索树上删除的信息启发性信息的启发能力越强，扩展的无用节点越少。
估价函数用以估计节点的重要性的函数。被定义为从初始节点S0S_0S
1、软件测试为什么要自动化自动化测试的优缺点有哪些
理解软件自动化1、自动化测试的含义2、软件测试为什么要自动化？3、自动化测试的优点？4、自动化测试的缺点？5、自动化测试应用场合6、不正确的自动化测试期望7、自动化测试工具的选择1、自动化测试的含义自动测试就是用程序代替人的手工操作，完成一系列测试的过程。自动化工具能自动打开程序、自动执行测试用例、自动查找控件、自动产生数据、自动输入数据、自动操作控件、自动收集结果、自动比较实际结果与预期结果是否一致。
2、软件测试为什么要自动化？软件测试是一件工作量巨大的工作软件测试包含大量的重复性操作；软件测试的某些环节包含一些非智力创造性活动；很多情况下手工测试难以模拟真实的环境；手工测试无法提供精确的测试结果。3、自动化测试的优点？自动化测试可重复执行，能执行更多、更频繁的测试。能执行一些手动测试比较困难或不可能进行的测试。能更好地利用资源，可利用晚上或周末空闲的设备执行自动化测试。自动化让测试人员腾出时间和精力，测试人员可以投入更多的精力设计出更多、更好的测试用例，从而提高测试准确性和测试人员的积极性。自动测试具有一致性的特点，能够保证测试更客观，从而提高了软件的信任度。4、自动化测试的缺点？不能完全代替人工测试，不是所有的测试用例都可以自动化，工具本身不具备思维能力。设计用例。界面和用户体验测试。正确性检查。不能保证100%的测试覆盖率。需要更长的时间去分析和隔离所发现的缺陷。自动化测试对软件质量依赖性较大。如果测试人员不熟悉某些测试工具，测试工作的进度就有可能受到影响。不能立即降低测试投入，提高测试效率。自动化测试的成本问题可能高于人工测试，因为工具的购买及维护的开支很大。5、自动化测试应用场合6、不正确的自动化测试期望6.1有了工具，一切测试过程都变得自动了。→如果项目中使用了很多第三方控件或自定义控件，而这些控件的可测性很差，这种测试则不适合自动化。
6.2有了工具，测试工作马上就减轻了。→购买测试工具后，还需要编写和维护测试脚本，这些费时、费力；可以在界面雏形时期，检查界面中的控件是否可测，从而选择合适的工具。
6.3自动测试工具都是简单易用的。→功能越完备操作通常越复杂，要求使用者掌握更多的技能。
6.4自动化测试尽早执行。→自动化测试需要过早计划但不宜过早执行；自动化测试需要循序渐进进行。
7、自动化测试工具的选择选择测试工具的指导原则
一般不是在项目初期完成工具选择，往往是在开发工具确定很长时间以后才能完成，甚至是项目后期才明确。选择适合自己公司项目的产品，只买对的，不买贵的。不要轻信测试销售人员的介绍就轻易购买，一定要组织详细的试用，确认适合项目使用，才能购买。分阶段、逐步引入测试工具。选择技术支持完善的产品。尽量选择主流的测试工具。如需多种工具，尽量选择一个公司的产品。考虑测试工具的集成能力(操作系统、开发工具、其他测试工具)。需要考虑：与开发语言一致的测试脚本语言，还要注意第三方控件与脚本语言能否匹配。测试工具未必支持所有的控件【可能会出现不识别的问题，不能花太多时间去研究为什么不识别，应该先用最简单的方法解决，使自动化测试得以进行是最重要的。遇到不能识别控件的问题时，可以向开发寻求帮助，让开发提供对软件的编程接口，更换一个同等效果的工具等。】测试用例的自动化应该注意顺序：先自动化简单的、主要功能的用例，然后向次要功能等扩展。