[ppt]-计算机博弈软件开发简介——亚马逊棋实现

计算机博弈软件开发简介亚马逊棋实现,2012-6,2012计算机博弈讲座,第 1 章 绪论,1.1 背景亚马逊棋是欧洲国家的一种棋种，是1988年阿根廷的Walter Zamkauskas 发明的，它由国际象棋中后的走法衍生而来，与著名的八皇后问题貌似神合。作为在国内最近才兴起的棋类游戏，其计算机博弈技术的研究相对还很少。,1.2 国内外研究现状,机器博弈通俗来说就是让机器下棋，之所以称之为“博弈” ，是因为其中渗透着博弈论的思想。机器博弈是一种动态的博弈，是现代智能化研究水平的集中体现。人工智能的先驱者们曾认真的表明：如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心，因为它不仅是计算机硬件性能的较量，更是计算机智能软件的较量。,自从计算机诞生以来，众多著名学者都曾经涉足这一领域的研究工作。计算机之父冯诺依曼就提出了极大极小定理用于解决博弈问题。信息论的创始人香侬教授，又给出了极大极小算法。著名的计算机学家阿兰图灵也曾做过机器博弈方面的研究。伴随着计算机硬件的飞速发展，- 剪枝算法的提出、负极大值算法的给出、极小树的证明、迭代深化思想的实现都使得机器博弈有了长足进展。近代机器博弈的研究是从四十年代后期开始至此，以国际象棋为例，从最初人类完全胜过机器，到如今电脑可以击败99.999%人类棋手，计算机博弈水平迅速上升。,第 2 章机器博弈系统介绍,人工智能是一门正在迅速发展的综合性很强的科学。其中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作，有诸多的研究领域，机器博弈即为其中之一。机器博弈属于博弈论研究的范畴，是博弈论和离散事件动态系统的交织学科。目前，研究最多的是棋类的机器博弈，因为棋类的信息是完全透明的，属于完全信息动态博弈。,2.1 博弈论基础知识,博弈论(Game Theory)，又称对策论，是使用严谨的数学模型研究冲突对抗条件下最优决策问题的理论，是研究决策主体的行为发生直接相互作用时候的决策以及这种决策的均衡问题。博弈论的早期思想源于游戏，最初主要研究象棋、桥牌、赌博中的胜负问题。,博弈的分类,按照参与人行动的次序可以把博弈论分为静态博弈和动态博弈。按照参与人所掌握的有关其他参与人的特征、战略空间及支付函数知识的角度可以把博弈论划分为完全信息博弈和不完全信息博弈。按照参与人之间的利益关系可以把博弈论划分为合作博弈和非合作博弈。亚马逊、苏拉卡尔塔是完全信息动态博弈,2.2 机器博弈系统要素,机器博弈的核心思想就是对博弈树节点的估值和对博弈树搜索过程的结合。根据机器博弈的基本思想，可以确定一个机器博弈系统，主要应包括以下几部分：(1) 数字表示某种在计算机中表示棋局的方法，程序可以通过它知道博弈的状态；(2) 着法生成根据棋规产生合法走法，以使博弈公正地进行，并可判断对手是否乱走；,(3) 搜索技术本着极大极小法则的思想，从所有合法的走法中选择最佳的走法的技术；(4) 审局函数为当前的棋局状态进行综合估值，用以同上面的技术配合做出智能的选择。目前已经有学者将遗传算法应用到估值函数的研究中，并初见成效；(5) 对弈界面有了它，这个程序才能用。,第3 章建模,以亚马逊棋为例亚马逊棋是一种比较新的，典型的占领地盘的棋类，在国外比较盛行，最近在国内也受到了人们的注意，但对亚马逊棋机器博弈系统的研究还相对很少。其着法的特殊规则导致了亚马逊棋每步的着法非常多，被认为是复杂的游戏。正是因为其规则的特殊性，使得它更具有研究的意义。,3.1.1 亚马逊棋的描述,棋盘：棋盘是由10*10的格子组成，如图所示。棋子：棋子共有八枚，双方各拥有四个(国际象棋)“皇后”(四个Amazons)，双方棋子的颜色不同。,棋规：,(1) 布子：开局前一次性布子，双方棋子分别布于棋盘的固定位置(2) 走子：双方轮流走子，双方着法都由两部分构成：走棋，设障碍，但不吃子。走棋规则为每个棋子都相当于国际象棋中的皇后，即可以走到横向、竖向和斜向的任何空的棋位，但不能穿过阻碍，此棋位称之为“到达棋位”。当轮到一方行棋时，此方只能而且必须移动四个棋子中的一个，并在移动完成后，由当前移动的棋子释放一个障碍，障碍可以释放在从“到达棋位”向“后”可行的路径上的任一棋位，同样障碍的放置也是必须的。,(3) 胜负：双方走子放箭的目的都是圈出自己的大范围的地盘，当某方四颗棋子均不能再移动时将输掉比赛。,亚马逊棋终局,3.1.2 亚马逊棋的基本概念,棋子的走棋放箭过程为一步。定义3.1 被棋子和障碍分隔出来的可以完全属于某一方的区域叫做某方的地盘。定义3.2 棋子的自由度等于区域中棋子周围可行的空格数的最大值。定义3.3 k -缺陷领域是指在一个区域内，棋子只可以走比空格数少k 的步数。,前两个是1-缺陷领域，有两个空格，但棋子只能走一步，另一个空格作废。第三个是2-缺陷领域，有三个空格，棋子却只能走一步，两个空格作废。第四个中间的棋子不可避免地丢掉左边或右边的一串空格。走棋只有两个选择，放箭的最佳选择是A或者B，不管哪种着法都使6个空格作废。,最小的缺陷领域,定义3.4 死局，满足以下两个性质之一：(1) 不能完全填充也就是产生了缺陷领域；(2) 断绝了与其它区域的关联，而使棋子自由度变小。定义3.5 死局的缺陷数是指为了脱离当前死局而产生的废格子数量的最小值。,左图死局缺陷数为1，而右图死局缺陷数为2。,3.2 棋类游戏特点,(1) 棋类游戏规则简单明确，成功与失败的判定标准简单，不包含任何机会或偶然性；(2) 棋类游戏中每个参与者不止一个策略可供选择，参与者策略的选择直接影响游戏结果；(3) 在对弈中，参与者的经验非常地重要，参与者可以根据棋局的状态推测出对方的目的；(4)问题的状态(棋局)数量在数学意义上是有限的。,3.3 博弈过程建模,根据对亚马逊棋的描述，双方行棋的目的就是为了使己方按照棋规走棋及所设的障碍使对方无格子可走，这样己方就获得胜利。为了表述清楚，棋局状态表达式采用10*10方阵表示。亚马逊棋的棋盘格子位置用数字00-99表示，双方棋子初始位置分别为03、06、30、39及60、69、93、96。而且双方棋子分别用0、1表示，障碍用2表示，空格用-1表示。,亚马逊棋属于离散事件动态系统，根据事件对策理论，亚马逊棋博弈系统可定义为：E=(P, Q, R, F)，其中， P：参与人集合。P=P1,P2Q=q0, q1, q2, q3, qn，是棋中所有有效棋局的有限集合。Q1=q0, q2, (黑方)Q2= q1, q3, (白方)式中为q0系统的初始状态。qn为终局。,系统的初始状态,q0：系统的初始状态。,系统的初始状态,qn：终局状态集合，从初始状态出发，由一系列着法驱动达到的棋局状态，应该满足下列条件之一：(1) 四个0的周围全为2；(2) 四个1的周围全为2；(3) 四个0的周围为2或1，且存在其它1的周围为-1；(4) 四个0的周围为2或1，且1的周围为2或0；(5) 四个1的周围为2或0，且存在其它0的周围为-1；(6) 四个1的周围为2或0，且0的周围为2或1。,：蓝方和黄方的可能着法的集合,它是棋局状态的函数。着法序列 = 1, 2, 3, 4, ，n 是博弈过程，其中奇数项序列 为先手方着法，偶数项序列 为后手方着法。状态转移函数 是着法k使系统状态演化为 qk。亚马逊棋的着法用三维向量X=a b c表示，其中a、b、c分别代表提子位置，落子位置，设障碍位置。亚马逊棋每步棋的着法都包含两个部分，走棋和设障碍。,R：双方轮流选择己方的一颗棋子走到到达棋位，然后在到达棋位向后的路径设障碍。F：蓝黄双方的收益值，即棋局的估值。亚马逊棋的棋局状态演化过程可以描述为参与者开始于初始状态q0，转换到状态qn。这样，问题的求解就转化为从初始状态出发，搜索寻找目标状态的路径问题。搜索过程所得到的着法序列就反映了问题的解的路径。,第4章 亚马逊棋棋局分析,理论上可用纳什均衡研究下棋的策略选择问题。子博弈是由一个动态博弈初始阶段后的任一后续博弈阶段构成，包含有初始信息集和进行博弈所需要的全部信息，能够自成一个博弈的一部分。在一个具有完美信息的动态博弈中，若各方的策略组合在整个博弈及其子博弈中都构成纳什均衡，则该策略组合称为该动态博弈的一个子博弈完美纳什均衡。纳什均衡理论的关键是在各种条件下，局中人都可以通过向其他局中人提出威胁和要求，寻求所有局中人都能够接受的解决方案。,4.1 开局分析,研究亚马逊棋的棋局状态的性质，就要研究每方棋子的位置关系及棋子的自由度，其行棋目的是用障碍或自身棋子将对方棋子堵死，使其不能移动或为己方圈地盘，所以棋盘上具体哪个格子被哪个游戏者占有并不重要，重要的是棋子对棋盘的控制力。,在亚马逊棋的开局阶段，每个棋子的自由度都非常高，可行着法非常多。在开局阶段着法的主要目标是将己方棋子扩散分布在棋盘上，而避免集中，这种布局有益于自己在残局阶段有最大的地盘。在开局的布局过程中，要求己方着法一定要对自己有利，尽量避免在边框，障碍等附近。中局可行区域变小，有的棋子的自由度也变小，主要两种途径“逃”和“围”，逃出自由度小的区域，而将对方围在自由度小的区域。,4.2 残局分析,(1) 棋局分解随着双方不断设障，活动余地越来越小，亚马逊棋博弈到一定阶段，棋面就会出现被棋子和障碍分割出来的区域，这些区域都是独立的，棋子不能移动到而且也不能再将障碍设到其他区域。,图 (a)为一个棋局，(b)为去掉设障碍部分后它的基本分解。我们可以利用棋的着法与设障碍圈出属于己方的地盘。(c)是将(b)的细分，(b)中c区域被细分成c和d两个区域，其中c被黄方控制，也就是c属于黄方的地盘，d被蓝方控制就属于蓝方地盘。区域a被细分为区域a和e，a为黄方地盘，而e属于蓝方地盘，显然占有e的蓝方棋子已经无格子可走，也就是死棋。而b区域是属于蓝黄两方的区域，需要再进行几步才能分出地盘。此时，蓝黄双方的最佳选择就是先不在区域a，c，d中行棋，而是选择首先在b中占领更大的属于自己的地盘。,(2) 亚马逊棋中的线段图表示如果将亚马逊棋棋盘的格子看成点，相邻的格子之间用线段连结，就可以将当前棋局用线段图代表，不同的棋局可能有着相同的线段图，称为同构线段图。,(3) 亚马逊棋的棋局处理技术地盘处理技术分析：当棋子已经在地盘中，则不在地盘中行棋，而考虑先在其它区域行棋，直到己方的每个棋子都在某一地盘中。死局的处理技术分析：放弃数目少的格子，争取数目多的格子，棋子向空格子多的路径行棋，并将障碍设在现棋子所在位置。,一个死局局势,4.3 纳什均衡,零和博弈，是博弈论里的一个概念，意思是双方博弈，一方得益必然意味着另一方吃亏，一方得益多少，另一方就吃亏多少，显然亚马逊棋为二人零和动态博弈。亚马逊棋的每个回合都是整个博弈过程的一个子博弈，由于双方都是理性的，所以最后最好的结果是终局双方均无格子可走。,在弈棋过程中，双方追求的都是己方地盘的最大化，虽然在博弈中我们会处于一种均衡的状态，但博弈双方的目的都不是寻找这种均衡点，而是要抓住机会打破这种均衡，占得优势地位，以达到赢棋的目的，所以最后的结果往往并不是双方的最优收益。,双方虽然不会将达到均衡状态的策略集放在首先要考虑的范畴，但是这一纳什均衡在着法选择的过程中起着指导作用。在搜索策略时，往往不去选择导致双方收益瞬间变大的着法，而是稳中求变。在棋局不发生剧烈震荡的前提下，选择最有利于己方的策略。在亚马逊棋中双方在不同的对弈阶段，需要从不同的角度对它的棋局进行评估，对实施的着法做出合理的评价。,开局阶段：双方对弈过程中，均为己方布局，用纳什均衡理论来分析开局的布局方法，可以得出着法的选择要尽量保持双方所得的价值大致相当，将棋子分散地布在棋盘上，争取在开局阶段棋子对棋盘的掌控程度与对方保持相当，不至于使对方在开局阶段便获得主动权。如果双方对棋盘的掌控程度相当，双方均觉得己方不错，可以说是一系列纳什均衡的累计使棋局达到稳定。按照纳什均衡理论来对这种均衡的下法进行改进，在对方没有改变策略时，灵活地进行己方着法的改进，进行出招，使己方占有更大范围的地盘，占得优势。,中局阶段：虽然双方的最终目的是使在终局对方无路可走而取得胜利，但在中局不能冒不必要的风险，本来想通过某一走棋设障碍的行动来达到围困对方的目的，反而被对方围困。在选择着法的过程中，要把双方最强的着法考虑进去，形成一个双方都能够接受的策略集，这也正是纳什均衡理论所提议的。即在双方棋子分布均衡的情况下，先考虑己方活棋的方法，采取攻击时要确保对方围困时不致因为自由度小而无法逃脱，然后才能开始攻击对方。相反地，在采取防守着法时，首先要考虑对方是否有活棋的着法，要是对方没有较好的着法，那么我们就先走对己方有利的着法，再找合适的机会反攻对方。,残局阶段：亚马逊棋对弈的最后阶段是残局阶段，残局阶段的每一步棋的价值都很大，足以影响整个棋局的胜负。对残局的改进可以应用纳什均衡理论，我们首先搜索相应的能够导致棋局失去平衡的着法，并将它的价值权数增大。如果对方走棋放箭之后使得己方的某棋子的自由度非常小甚至堵死，而己方棋子没有合适的着法逃离这种攻势，这时的对方的着法的价值就应该被高估。,第5章机器博弈系统设计,5.1 亚马逊棋博弈系统分为界面和引擎两大部分，在进行系统设计时将整个软件分成几个模块，对每个模块分别进行设计，最后组合成为一个完整的系统。分为五个模块：数据结构模块，着法生成模块，搜索模块，评估模块，界面模块。,亚马逊棋流程分析如下：(1) 开始一个新的棋局；(2) 判断人和计算机哪方先走棋，如果人先走棋那么执行(3)，如果计算机先走棋那么跳转到(5)；(3) 人在棋盘上走棋，设障碍；(4) 判断游戏是否结束，如果游戏结束那么显示双方输赢情况并退出程序，否则执行(5)； (5) 判断棋子是否全在区域内，然后根据着法生成函数生成的所有可能的着法展开博弈树，同时启动搜索引擎，调用评估函数进行估值；(6) 计算机走出最佳着法；(7) 判断游戏是否结束，如果游戏结束那么显示双方输赢情况并退出程序，否则转到(3)。,5.2 数据结构设计,让计算机下棋，首先要选用一种合适的方法记录棋局，以计算机能接收的数据格式表示棋盘、棋子、障碍等相关信息。这些信息是以后进行搜索和估值等算法操作的基础。,5.2.1棋盘坐标编码,实际上因为棋盘是10行10列的格子，恰好100个位置，因此用数字0-99对棋盘进行编码，用来表示100个格子,5.2.2棋子种类编码,具体定义双方的八颗棋子。这里定义每颗棋子的初始位置如下：,B 0.Situation=03；B 1.Situation=06；B 2.Situation=30；B 3.Situation=39；,Y 0.Situation=60；Y 1.Situation=69；Y 2.Situation=93；Y 3.Situation=96；,亚马逊棋的棋局状态数据由一个长度为100的一维数组表示，对应表示棋盘上的棋子、障碍和空格的信息。初始棋盘状态数组形式如下：,Amazon100=-1, -1, 1, 0, -1, 1, 0, -1, -1, -1, -1, -1, 1,-1, -1, 1, -1, -1, -1, -1, -1, -1, 1,-1, -1, 1, -1, -1, -1, -1, 0, -1, 1,-1, -1, 1, -1, -1, -1, 0, -1, -1, 1,-1, -1, 1, -1, -1, -1, -1, -1, -1, 1,-1, -1, 1, -1, -1, -1, -1, 1, -1, 1,-1, -1, 1, -1, -1, -1, 1, -1, -1, 1,-1, -1, 1, -1, -1, -1, -1, -1, -1, 1,-1, -1, 1, -1, -1, -1, -1, -1, -1, 1,1, -1, 1, 1, -1, -1, -1, ,5.2.3着法数据表示,亚马逊棋走棋与提子位置、落子位置、设障碍位置有关，定义如下：struct Goint f；/提子点int t；/落子点int p； /放箭点这里的f、t、p指00-99的棋盘位置编码。,5.2.4数据更新过程,当棋盘上有变化时就需要更新一些数据信息。通过消息响应函数确定提子位置，落子位置和设障碍位置的坐标，并将位置坐标传入后台棋盘，后台中相应的处理函数将在棋盘数组相应位置上置-1、2、0 或1，更新存储棋局状态的数组。在计算机搜索最佳着法的过程中，搜索完一个节点后，如果需要继续搜索同一层的下一个节点时，必须要恢复棋盘为原来的棋局状态。,5.3 着法生成模块的设计,着法生成是博弈树展开的依据，它是根据当前的棋局和走棋方信息，给出所有可能着法的那一部分程序，也就是用来告诉引擎的其他部分下一步可以怎么走的模块，从而不断扩展博弈树。不同的棋类有不同的规则，不同的复杂程度，所以要有一个相应的走法产生机制。,在亚马逊棋对弈中，着法生成是一个很关键的问题。扫描棋盘寻找所有的可行棋位，罗列出所有符合规则的下一步着法。亚马逊棋着法生成步骤：(1) 确定走动的棋子的位置；(2) 根据规则，扫描棋盘，找到全部合理落子位置；(3) 根据落子位置，扫描棋盘，找到全部合理的设障碍的位置。,定义着法函数：makemove(Ifrom, Ito, Iput, Lmyturn)函数包括4个参数：int Ifrom /提子位置int Ito /落子位置int Iput /放箭位置bool Lmyturn /是黑方还是白方,5.4 搜索算法的研究,选择着法时要充分考虑到对手的存在，考虑己方和对方以后几步棋的可能下法，需要展开博弈树，搜索最佳着法。,5.4.1博弈树,在博弈过程中，按照博弈规则和着法状态过程分析，客观评判博弈双方在各自分枝节点上所获得的分数估计值，并以其中任何一方的角度而依次生成具有得分值表示的与或搜索树，称为博弈树。博弈树是根在上部，然后向下递归产生的一棵包含着所有可能的对弈过程的搜索树，是完全搜索树，包含了下棋者和计算机所有可能的着法和局面。搜索算法是计算机“思维”的核心。,一般，计算机直接通过棋盘信息判断某个着法的好坏并不精确。棋类程序中，通常通过使用“搜索”函数来寻找可能着法。搜索函数获得棋局信息，然后寻找对于计算机来说最好的着法。判断着法好坏的一个办法就是考察棋局走下去的结果，可以由博弈树向下搜索几步，然后比较发展下去的结果。,双方进行对弈，假设轮到白方走棋，对其任何一种走法，黑方也有若干种与之相对应的走法，对黑方的任何一种走法白方又有若干种与之相对应的走法，如此往复，构造出一棵博弈树，将所有的走法罗列出来。在博弈树中，节点为局面，树枝为着法，其中根结点为当前时刻的棋局，它的儿子节点是假设再行棋一步之后的各种棋局，孙子节点是从儿子节点的棋局再行棋一步的各种棋局，以此类推。双方轮流出手，偶数层节点属于白方，奇数层节点属于黑方。如果叶节点还不能给出胜负的最终局面，则要对叶节点进行评估，以便从有利局面选择当前着法，这便是博弈搜索的职能。,5.4.2极大-极小值搜索,极大极小值算法是香侬教授在1950年首先提出来的，极大极小值算法也是当代计算机博弈各种搜索算法的基础。由于对弈双方都是理智的，都想赢棋，在选择着法的时候都尽量让棋局朝着有利于自己的方面转化，所以在博弈树上，在不同层上就要有不同的选择标准。,极大极小搜索算法的基本思想：(1) 在偶数层节点的着法即轮到Max走棋的节点时，Max应考虑最好的情况，选择其全部子节点中评估值最大的一个，即F(v) = maxF(v1), F(v2), , F(vn)其中，F ( ) 为节点估值，v1，v2，vn为节点v的子节点。,(2) 在奇数层节点的着法即轮到Min走棋的节点时，Max应考虑最坏的情况，选择其全部子节点中评估值最小的一个，即F(v) = minF(v1), F(v2), , F(vn)其中，F ( ) 为节点估值，v1，v2，vn为节点v的子节点。(3) 评价往回倒推时，相当于两个局中人的对抗策略，交替使用(1)、(2)两种方法传递倒推值。,在进行极大-极小搜索的时候，首先要在有限深度内展开全部叶子节点，并进行评估，然后自下而上地进行搜索计算，一直反推到根结点。在反推的过程中始终要记住算出该值的子节点是谁，这样就可以得到一个从根结点到叶子节点的一条路径，这就是最佳路径，它是双方表现最佳的对弈着法序列。如图所示的博弈树，MAX层取下一层的极大值，MIN层取下一层的极小值。,极大极小算法伪代码,int minimax(position p,int depth) int bestvalue,value; if(gameover) / 检查棋局是否结束 return evaluation(p); / 棋局结束，返回估值 if depth= beta) break; /Beta 剪枝 return alpha; / 返回最大值或最小值 ,5.4.6 极小窗口搜索算法,极小窗口搜索是在-算法的基础上形成的一种搜索方法，是以一个极小的窗口来搜索节点。极小窗口搜索算法的过程是：对于第一个节点来说，假设它的第一个分枝节点是最佳的一步，我们先对它按照原来的= -，= +这样的范围进行搜索，我们会得到一个假设的最优解bestvalue。后继的分枝则以一个极小的窗口（也称为零窗口）（bestvalue，bestvalue + 1）搜索，因为不可能存在一个整数既大于bestvalue，又小于bestvalue + 1，如果搜索返回值大于零窗口，则证明这一分支亦为主变量。则对它进行窗口为（bestvalue + 1，）的搜索，可是如果返回值小于零窗口，这一分支就可以忽略因为它的最佳走步还不如已有的走步。如果最优的子结点最先扩展，则此后的其他子结点通过值对应的极小窗口进行搜索都可以轻松剪枝，搜索节点也更少。,5.4.7 渴望搜索算法,在-剪枝过程中，初始的搜索窗口往往是从= -到= + ，在搜索进行中再不断缩小窗口，加大剪枝效果。渴望搜索就是渴望从一开始就用小的窗口，从而在搜索初起，就可以进行大量的剪枝。这个窗口的选定很重要，如果选择准确，即所要寻找的走步就在这个窗口内，搜索便可以继续进行。如果第一步搜索的返回值证明最佳走步大于值，就需要重新确定窗口。以原来的值为值，以+ 的为新的值，重新搜索。相反如果第一步的返回值证明最佳走步小于值，重新确定的窗口就是以-为值，原来的值为值了。可见第一次搜索猜测的窗口非常重要，如果猜测准确，搜索时间可以大大缩短，如果不准确，这一优势就不明显了。,猜测搜索的结果在x附近，那么可以令= x -window（window是要搜索范围的大小的一半）， = x + window，再使用这样的一对值来进行剪枝来搜索结果。特别是当window很小的时候，搜索的效率会比较高，因为有了更多的剪枝。如果返回的值x window value x + window。在这种情况下，我们知道要找的值就在猜测的范围之内，可以直接使用导致找到最佳的步法。如果返回值不在这个范围，则重新调整窗口。,5.4.8 PVS 搜索,主要变例搜索，又叫 pvs 搜索，是-搜索的一种改进方法。在-搜索中，任何结点都属于以下三种类型： (1) 结点。每个搜索都会得到一个小于或等于的值，这就意味着这里没有一个着法是好的，可能是因为这个局面对于要走的一方太坏了。 (2) 结点。至少一个着法会返回大于或等于的值。 (3) 主要变例(PV)结点。有一个或多个着法会返回大于或等于的值(即 PV 着法)，但是没有着法会返回大于或等于的值。,主要变例搜索作了假设，如果在搜索一个结点时找到一个 PV 着法，那么就得到 PV 结点。即假设你着法排序已经足够好了，不必在其余的着法中找更好的 PV 着法或者高出边界的着法(这就会使结点变成结点)。 你找到一个着法其值在 和之间，那么对其余的着法，搜索的目标就是证明他们都是坏的。跟要搜索出更好的着法相比，这种搜索也许要快一些。,如果这个算法发现判断是错的，即其中一个后续着法比第一个 PV 着法好，那么它会被再一次搜索，这次使用正常-搜索方法。这种情况有时会发生，这样就浪费时间了，但是这些时间通常不会超过前面所说的“证明是坏着法”所节约下来的时间。 整体看来，pvs 在效率上是优于（至少不次于）-的。因此许多博弈程序都采用以pvs 算法为核心的搜索算法。,5.4.8亚马逊棋博弈系统的搜索算法,宽度优先搜索适合用于解决节点个数少的问题，深度优先搜索一般用来求解节点数特别多的问题。极大极小算法虽然是经典的搜索算法，但是在搜索过程中总要判断哪一方要取极大值哪一方要取极小值。因此，选择它的优化算法负极大值算法，虽然它本质上与极大极小算法是一样的，仍然是一种穷尽搜索算法，但与极大极小算法相比较，程序要短而且简单。- 剪枝算法可以进行有效的剪枝。综合以上考虑，考虑选择 - 剪枝算法，深度优先搜索和负极大值搜索算法相结合作为基本搜索算法。,用-剪枝搜索算法首先要设定合适的、值，然后对当前棋局根据深度优先原则进行博弈树展开。在负极大值搜索和-剪枝算法相结合的基础上，根据亚马逊棋对弈一定回合后必然出现每方的棋子在某固定区域的特点，本程序加入了一些信息，主要是对一些特殊区域的判断，也就是地盘的判断。,图中局势，黑方四颗棋子全在区域(A，B，C，D)内，白方不能进入。定义一个区域判断函数。判断棋子是否全在固定的区域后，使用不同的搜索函数。,对棋局进行区域判断：(1) 经过区域判断，如果棋子不全在限定的区域内，那么按正常的方法搜索，定义搜索函数为：Search(int depth,int alpha,int bate,boolismyturn,int first,bool myturn)ismyturn/轮到哪方走棋，依层数改变myturn /当前哪方走棋，不依层数改变,主要搜索部分的代码如下：GoNumber=PMakeHowDo(GoWay,ismyturn);/不全在区域内的着法生成函数if(depth!=first)/判断是否走棋for(i=0;i=bate)return alpha;/beta剪枝,return alpha;/返回极大值elsefor(i=0;iGoNumber;i+)makemove(GoWayi0,GoWayi1,GoWayi2,ismyturn);value=-Search(depth-1,-bate,-alpha,!ismyturn,first,myturn);unmakemove(GoWayi0,GoWayi1,GoWayi2,ismyturn);if(alphavalue)alpha=value;/设置最佳走法bestgo=i;/最佳走法就是电脑选择的着法,(2) 经过区域判断，如果棋子全在限定的区域内，那么进行特定的搜索。定义搜索函数为：Search1(int depth,int first,int stu)/只搜索一个子,主要搜索部分的代码如下：GoNumber=PMake1HowDo(GoWay,stu);/全部在区域内的着法生成函数if(depth!=first)for(i=0;iGoNumber;i+)makemove(GoWayi0,GoWayi1,GoWayi2,false);value=Search1(depth-1,first,GoWayi1);unmakemove(GoWayi0,GoWayi1,GoWayi2,false);if(alphavalue)alpha=value;return alpha;,Elsefor(i=0;iGoNumber;i+)makemove(GoWayi0,GoWayi1,GoWayi2,false);value=Search1(depth-1,first,GoWayi1);unmakemove(GoWayi0,GoWayi1,GoWayi2,false);if(alphavalue)alpha=value;bestgo=i;,-剪枝算法通过“剪枝”技巧很大程度上缩小了博弈树的规模，另外，在搜索之前对棋局进行区域判断，对特定的棋局状态进行不同的搜索函数搜索，搜索效率明显得到提高。,搜索引擎的完整过程的流程,5.5 估值函数的设计,评估函数是除了搜索算法以外，另一个对博弈树求解的重要方面。只有有了良好的估值函数才能保证较快地找到最佳着法。而估值函数是对棋局的综合评估，该函数的好坏直接决定棋力的强弱。通常情况下，估值函数在很大程度上依赖于具体的游戏规则和我们对该游戏的经验知识。同时评估函数和搜索算法一样是博弈树搜索的