2012计算机博弈讲座 计算机博弈软件开发简介 ——亚马逊棋实现 2012-6.

Presentation on theme: "2012计算机博弈讲座 计算机博弈软件开发简介 ——亚马逊棋实现 2012-6."— Presentation transcript:

1 2012计算机博弈讲座 计算机博弈软件开发简介 ——亚马逊棋实现 2012-6

2 第 1 章 绪论 1.1 背景 亚马逊棋是欧洲国家的一种棋种，是1988年阿根廷的Walter Zamkauskas 发明的，它由国际象棋中后的走法衍生而来，与著名的八皇后问题貌似神合。作为在国内最近才兴起的棋类游戏，其计算机博弈技术的研究相对还很少。

3 1.2 国内外研究现状 机器博弈通俗来说就是让机器下棋，之所以称之为“博弈” ，是因为其中渗透着博弈论的思想。机器博弈是一种动态的博弈，是现代智能化研究水平的集中体现。人工智能的先驱者们曾认真的表明：如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心，因为它不仅是计算机硬件性能的较量，更是计算机智能软件的较量。

4 自从计算机诞生以来，众多著名学者都曾经涉足这一领域的研究工作。计算机之父冯·诺依曼就提出了极大极小定理用于解决博弈问题。信息论的创始人香侬教授，又给出了极大极小算法。著名的计算机学家阿兰·图灵也曾做过机器博弈方面的研究。伴随着计算机硬件的飞速发展，α-β 剪枝算法的提出、负极大值算法的给出、极小树的证明、迭代深化思想的实现都使得机器博弈有了长足进展。 近代机器博弈的研究是从四十年代后期开始至此，以国际象棋为例，从最初人类完全胜过机器，到如今电脑可以击败99.999%人类棋手，计算机博弈水平迅速上升。

5 第 2 章机器博弈系统介绍 人工智能是一门正在迅速发展的综合性很强的科学。其中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作，有诸多的研究领域，机器博弈即为其中之一。机器博弈属于博弈论研究的范畴，是博弈论和离散事件动态系统的交织学科。目前，研究最多的是棋类的机器博弈，因为棋类的信息是完全透明的，属于完全信息动态博弈。

6 2.1 博弈论基础知识 博弈论(Game Theory)，又称对策论，是使用严谨的数学模型研究冲突对抗条件下最优决策问题的理论，是研究决策主体的行为发生直接相互作用时候的决策以及这种决策的均衡问题。博弈论的早期思想源于游戏，最初主要研究象棋、桥牌、赌博中的胜负问题。

7 博弈的分类 按照参与人行动的次序可以把博弈论分为静态博弈和动态博弈。
按照参与人所掌握的有关其他参与人的特征、战略空间及支付函数知识的角度可以把博弈论划分为完全信息博弈和不完全信息博弈。 按照参与人之间的利益关系可以把博弈论划分为合作博弈和非合作博弈。 亚马逊、苏拉卡尔塔是完全信息动态博弈

8 2.2 机器博弈系统要素 机器博弈的核心思想就是对博弈树节点的估值和对博弈树搜索过程的结合。根据机器博弈的基本思想，可以确定一个机器博弈系统，主要应包括以下几部分： (1) 数字表示 某种在计算机中表示棋局的方法，程序可以通过它知道博弈的状态； (2) 着法生成 根据棋规产生合法走法，以使博弈公正地进行，并可判断对手是否乱走；

9 (3) 搜索技术 本着极大极小法则的思想，从所有合法的走法中选择最佳的走法的技术； (4) 审局函数 为当前的棋局状态进行综合估值，用以同上面的技术配合做出智能的选择。目前已经有学者将遗传算法应用到估值函数的研究中，并初见成效； (5) 对弈界面 有了它，这个程序才能用。

10 第3 章建模 以亚马逊棋为例 亚马逊棋是一种比较新的，典型的占领地盘的棋类，在国外比较盛行，最近在国内也受到了人们的注意，但对亚马逊棋机器博弈系统的研究还相对很少。其着法的特殊规则导致了亚马逊棋每步的着法非常多，被认为是复杂的游戏。正是因为其规则的特殊性，使得它更具有研究的意义。

11 3.1.1 亚马逊棋的描述 棋盘：棋盘是由10*10的格子组成，如图所示。
棋子：棋子共有八枚，双方各拥有四个(国际象棋)“皇后”(四个Amazons)，双方棋子的颜色不同。

12 棋规： (1) 布子：开局前一次性布子，双方棋子分别布于棋盘的固定位置
(2) 走子：双方轮流走子，双方着法都由两部分构成：走棋，设障碍，但不吃子。 走棋规则为每个棋子都相当于国际象棋中的皇后，即可以走到横向、竖向和斜向的任何空的棋位，但不能穿过阻碍，此棋位称之为“到达棋位”。当轮到一方行棋时，此方只能而且必须移动四个棋子中的一个，并在移动完成后，由当前移动的棋子释放一个障碍，障碍可以释放在从“到达棋位”向“后”可行的路径上的任一棋位，同样障碍的放置也是必须的。

13 (3) 胜负：双方走子放箭的目的都是圈出自己的大范围的地盘，当某方四颗棋子均不能再移动时将输掉比赛。
亚马逊棋终局

14 3.1.2 亚马逊棋的基本概念 棋子的走棋放箭过程为一步。 定义3.1 被棋子和障碍分隔出来的可以完全属于某一方的区域叫做某方的地盘。
定义3.2 棋子的自由度等于区域中棋子周围可行的空格数的最大值。 定义3.3 k -缺陷领域是指在一个区域内，棋子只可以走比空格数少k 的步数。

15 前两个是1-缺陷领域，有两个空格，但棋子只能走一步，另一个空格作废。 第三个是2-缺陷领域，有三个空格，棋子却只能走一步，两个空格作废。
最小的缺陷领域 前两个是1-缺陷领域，有两个空格，但棋子只能走一步，另一个空格作废。 第三个是2-缺陷领域，有三个空格，棋子却只能走一步，两个空格作废。 第四个中间的棋子不可避免地丢掉左边或右边的一串空格。走棋只有两个选择，放箭的最佳选择是A或者B，不管哪种着法都使6个空格作废。

16 (2) 断绝了与其它区域的关联，而使棋子自由度变小。 定义3.5 死局的缺陷数是指为了脱离当前死局而产生的废格子数量的最小值。
左图死局缺陷数为1，而右图死局缺陷数为2。 定义3.4 死局，满足以下两个性质之一： (1) 不能完全填充也就是产生了缺陷领域； (2) 断绝了与其它区域的关联，而使棋子自由度变小。 定义3.5 死局的缺陷数是指为了脱离当前死局而产生的废格子数量的最小值。

17 3.2 棋类游戏特点 (1) 棋类游戏规则简单明确，成功与失败的判定标准简单，不包含任何机会或偶然性；
(2) 棋类游戏中每个参与者不止一个策略可供选择，参与者策略的选择直接影响游戏结果； (3) 在对弈中，参与者的经验非常地重要，参与者可以根据棋局的状态推测出对方的目的； (4)问题的状态(棋局)数量在数学意义上是有限的。

18 3.3 博弈过程建模 根据对亚马逊棋的描述，双方行棋的目的就是为了使己方按照棋规走棋及所设的障碍使对方无格子可走，这样己方就获得胜利。为了表述清楚，棋局状态表达式采用10*10方阵表示。 亚马逊棋的棋盘格子位置用数字00-99表示，双方棋子初始位置分别为03、06、30、39及60、69、93、96。而且双方棋子分别用0、1表示，障碍用2表示，空格用-1表示。

19 亚马逊棋属于离散事件动态系统，根据事件对策理论，亚马逊棋博弈系统可定义为：E=(P, Q,Σ, R, F)，其中，   
P：参与人集合。P={P1,P2} Q={q0, q1, q2, q3,……, qn}，是棋中所有有效棋局的有限集合。 Q1={q0, q2,…… } (黑方) Q2= {q1, q3, ……} (白方) 式中为q0系统的初始状态。qn为终局。

20 系统的初始状态 q0：系统的初始状态。

21 系统的初始状态 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。

22 Σ：蓝方和黄方的可能着法的集合,它是棋局状态的函数。
着法序列 Σ ={ σ1, σ2, σ3, σ4, ……，σn} 是博弈过程，其中奇数项序列 为先手方着法，偶数项序列 为后手方着法。 状态转移函数 是着法σk使系统状态演化为 qk。 亚马逊棋的着法用三维向量X=[a b c]表示，其中a、b、c分别代表提子位置，落子位置，设障碍位置。亚马逊棋每步棋的着法都包含两个部分，走棋和设障碍。

23 R：双方轮流选择己方的一颗棋子走到到达棋位，然后在到达棋位向后的路径设障碍。
F：蓝黄双方的收益值，即棋局的估值。 亚马逊棋的棋局状态演化过程可以描述为参与者开始于初始状态q0，转换到状态qn。 这样，问题的求解就转化为从初始状态出发，搜索寻找目标状态的路径问题。搜索过程所得到的着法序列就反映了问题的解的路径。

24 第4章 亚马逊棋棋局分析 理论上可用纳什均衡研究下棋的策略选择问题。
子博弈是由一个动态博弈初始阶段后的任一后续博弈阶段构成，包含有初始信息集和进行博弈所需要的全部信息，能够自成一个博弈的一部分。 在一个具有完美信息的动态博弈中，若各方的策略组合在整个博弈及其子博弈中都构成纳什均衡，则该策略组合称为该动态博弈的一个子博弈完美纳什均衡。 纳什均衡理论的关键是在各种条件下，局中人都可以通过向其他局中人提出威胁和要求，寻求所有局中人都能够接受的解决方案。

25 4.1 开局分析 研究亚马逊棋的棋局状态的性质，就要研究每方棋子的位置关系及棋子的自由度，其行棋目的是用障碍或自身棋子将对方棋子堵死，使其不能移动或为己方圈地盘，所以棋盘上具体哪个格子被哪个游戏者占有并不重要，重要的是棋子对棋盘的控制力。

26 在亚马逊棋的开局阶段，每个棋子的自由度都非常高，可行着法非常多。在开局阶段着法的主要目标是将己方棋子扩散分布在棋盘上，而避免集中，这种布局有益于自己在残局阶段有最大的地盘。在开局的布局过程中，要求己方着法一定要对自己有利，尽量避免在边框，障碍等附近。中局可行区域变小，有的棋子的自由度也变小，主要两种途径“逃”和“围”，逃出自由度小的区域，而将对方围在自由度小的区域。

27 4.2 残局分析 (1) 棋局分解 随着双方不断设障，活动余地越来越小，亚马逊棋博弈到一定阶段，棋面就会出现被棋子和障碍分割出来的区域，这些区域都是独立的，棋子不能移动到而且也不能再将障碍设到其他区域。

28 图 (a)为一个棋局，(b)为去掉设障碍部分后它的基本分解。我们可以利用棋的着法与设障碍圈出属于己方的地盘。(c)是将(b)的细分，(b)中c区域被细分成c和d两个区域，其中c被黄方控制，也就是c属于黄方的地盘，d被蓝方控制就属于蓝方地盘。 区域a被细分为区域a和e，a为黄方地盘，而e属于蓝方地盘，显然占有e的蓝方棋子已经无格子可走，也就是死棋。而b区域是属于蓝黄两方的区域，需要再进行几步才能分出地盘。此时，蓝黄双方的最佳选择就是先不在区域a，c，d中行棋，而是选择首先在b中占领更大的属于自己的地盘。

29 (2) 亚马逊棋中的线段图表示 如果将亚马逊棋棋盘的格子看成点，相邻的格子之间用线段连结，就可以将当前棋局用线段图代表，不同的棋局可能有着相同的线段图，称为同构线段图。

30 当棋子已经在地盘中，则不在地盘中行棋，而考虑先在其它区域行棋，直到己方的每个棋子都在某一地盘中。
(3) 亚马逊棋的棋局处理技术 地盘处理技术分析： 当棋子已经在地盘中，则不在地盘中行棋，而考虑先在其它区域行棋，直到己方的每个棋子都在某一地盘中。 死局的处理技术分析： 放弃数目少的格子，争取数目多的格子，棋子向空格子多的路径行棋，并将障碍设在现棋子所在位置。 一个死局局势

31 4.3 纳什均衡 零和博弈，是博弈论里的一个概念，意思是双方博弈，一方得益必然意味着另一方吃亏，一方得益多少，另一方就吃亏多少，显然亚马逊棋为二人零和动态博弈。 亚马逊棋的每个回合都是整个博弈过程的一个子博弈，由于双方都是理性的，所以最后最好的结果是终局双方均无格子可走。

32 在弈棋过程中，双方追求的都是己方地盘的最大化，虽然在博弈中我们会处于一种均衡的状态，但博弈双方的目的都不是寻找这种均衡点，而是要抓住机会打破这种均衡，占得优势地位，以达到赢棋的目的，所以最后的结果往往并不是双方的最优收益。

33 双方虽然不会将达到均衡状态的策略集放在首先要考虑的范畴，但是这一纳什均衡在着法选择的过程中起着指导作用。在搜索策略时，往往不去选择导致双方收益瞬间变大的着法，而是稳中求变。在棋局不发生剧烈震荡的前提下，选择最有利于己方的策略。 在亚马逊棋中双方在不同的对弈阶段，需要从不同的角度对它的棋局进行评估，对实施的着法做出合理的评价。

34 开局阶段： 双方对弈过程中，均为己方布局，用纳什均衡理论来分析开局的布局方法，可以得出着法的选择要尽量保持双方所得的价值大致相当，将棋子分散地布在棋盘上，争取在开局阶段棋子对棋盘的掌控程度与对方保持相当，不至于使对方在开局阶段便获得主动权。如果双方对棋盘的掌控程度相当，双方均觉得己方不错，可以说是一系列纳什均衡的累计使棋局达到稳定。按照纳什均衡理论来对这种均衡的下法进行改进，在对方没有改变策略时，灵活地进行己方着法的改进，进行出招，使己方占有更大范围的地盘，占得优势。

35 中局阶段： 虽然双方的最终目的是使在终局对方无路可走而取得胜利，但在中局不能冒不必要的风险，本来想通过某一走棋设障碍的行动来达到围困对方的目的，反而被对方围困。 在选择着法的过程中，要把双方最强的着法考虑进去，形成一个双方都能够接受的策略集，这也正是纳什均衡理论所提议的。即在双方棋子分布均衡的情况下，先考虑己方活棋的方法，采取攻击时要确保对方围困时不致因为自由度小而无法逃脱，然后才能开始攻击对方。相反地，在采取防守着法时，首先要考虑对方是否有活棋的着法，要是对方没有较好的着法，那么我们就先走对己方有利的着法，再找合适的机会反攻对方。

36 残局阶段： 亚马逊棋对弈的最后阶段是残局阶段，残局阶段的每一步棋的价值都很大，足以影响整个棋局的胜负。 对残局的改进可以应用纳什均衡理论，我们首先搜索相应的能够导致棋局失去平衡的着法，并将它的价值权数增大。如果对方走棋放箭之后使得己方的某棋子的自由度非常小甚至堵死，而己方棋子没有合适的着法逃离这种攻势，这时的对方的着法的价值就应该被高估。

37 第5章机器博弈系统设计 5.1 亚马逊棋博弈系统分为界面和引擎两大部分，在进行系统设计时将整个软件分成几个模块，对每个模块分别进行设计，最后组合成为一个完整的系统。 分为五个模块：数据结构模块，着法生成模块，搜索模块，评估模块，界面模块。

38 亚马逊棋流程分析如下： (1) 开始一个新的棋局； (2) 判断人和计算机哪方先走棋，如果人先走棋那么执行(3)，如果计算机先走棋那么跳转到(5)； (3) 人在棋盘上走棋，设障碍； (4) 判断游戏是否结束，如果游戏结束那么显示双方输赢情况并退出程序，否则执行(5)； (5) 判断棋子是否全在区域内，然后根据着法生成函数生成的所有可能的着法展开博弈树，同时启动搜索引擎，调用评估函数进行估值； (6) 计算机走出最佳着法； (7) 判断游戏是否结束，如果游戏结束那么显示双方输赢情况并退出程序，否则转到(3)。

39 5.2 数据结构设计 让计算机下棋，首先要选用一种合适的方法记录棋局，以计算机能接收的数据格式表示棋盘、棋子、障碍等相关信息。这些信息是以后进行搜索和估值等算法操作的基础。

40 5.2.1棋盘坐标编码 实际上因为棋盘是10行10列的格子，恰好100个位置，因此用数字0-99对棋盘进行编码，用来表示100个格子

41 5.2.2棋子种类编码 棋子 甲棋 乙棋 空格 障碍 编码 1 -1 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； 棋子 甲棋 乙棋 空格 障碍 编码 1 -1 2

42 亚马逊棋的棋局状态数据由一个长度为100的一维数组表示，对应表示棋盘上的棋子、障碍和空格的信息。初始棋盘状态数组形式如下：
Amazon[100]={ -1, -1, 1, 0, -1, 1, 0, -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, }

43 5.2.3着法数据表示 亚马逊棋走棋与提子位置、落子位置、设障碍位置有关，定义如下： struct Go{ int f； //提子点
int t； //落子点 int p； } //放箭点 这里的f、t、p指00-99的棋盘位置编码。

44 5.2.4数据更新过程 当棋盘上有变化时就需要更新一些数据信息。通过消息响应函数确定提子位置，落子位置和设障碍位置的坐标，并将位置坐标传入后台棋盘，后台中相应的处理函数将在棋盘数组相应位置上置-1、2、0 或1，更新存储棋局状态的数组。在计算机搜索最佳着法的过程中，搜索完一个节点后，如果需要继续搜索同一层的下一个节点时，必须要恢复棋盘为原来的棋局状态。

45 5.3 着法生成模块的设计 着法生成是博弈树展开的依据，它是根据当前的棋局和走棋方信息，给出所有可能着法的那一部分程序，也就是用来告诉引擎的其他部分下一步可以怎么走的模块，从而不断扩展博弈树。不同的棋类有不同的规则，不同的复杂程度，所以要有一个相应的走法产生机制。

46 在亚马逊棋对弈中，着法生成是一个很关键的问题。扫描棋盘寻找所有的可行棋位，罗列出所有符合规则的下一步着法。
亚马逊棋着法生成步骤： (1) 确定走动的棋子的位置； (2) 根据规则，扫描棋盘，找到全部合理落子位置； (3) 根据落子位置，扫描棋盘，找到全部合理的设障碍的位置。

47 定义着法函数： makemove(Ifrom, Ito, Iput, Lmyturn) 函数包括4个参数： int Ifrom //提子位置 int Ito //落子位置 int Iput //放箭位置 bool Lmyturn //是黑方还是白方

48 5.4 搜索算法的研究 选择着法时要充分考虑到对手的存在，考虑己方和对方以后几步棋的可能下法，需要展开博弈树，搜索最佳着法。

49 5.4.1博弈树 在博弈过程中，按照博弈规则和着法状态过程分析，客观评判博弈双方在各自分枝节点上所获得的分数估计值，并以其中任何一方的角度而依次生成具有得分值表示的与或搜索树，称为博弈树。博弈树是根在上部，然后向下递归产生的一棵包含着所有可能的对弈过程的搜索树，是完全搜索树，包含了下棋者和计算机所有可能的着法和局面。搜索算法是计算机“思维”的核心。

50 一般，计算机直接通过棋盘信息判断某个着法的好坏并不精确。棋类程序中，通常通过使用“搜索”函数来寻找可能着法。搜索函数获得棋局信息，然后寻找对于计算机来说最好的着法。判断着法好坏的一个办法就是考察棋局走下去的结果，可以由博弈树向下搜索几步，然后比较发展下去的结果。

51 双方进行对弈，假设轮到白方走棋，对其任何一种走法，黑方也有若干种与之相对应的走法，对黑方的任何一种走法白方又有若干种与之相对应的走法，如此往复，构造出一棵博弈树，将所有的走法罗列出来。在博弈树中，节点为局面，树枝为着法，其中根结点为当前时刻的棋局，它的儿子节点是假设再行棋一步之后的各种棋局，孙子节点是从儿子节点的棋局再行棋一步的各种棋局，以此类推。双方轮流出手，偶数层节点属于白方，奇数层节点属于黑方。如果叶节点还不能给出胜负的最终局面，则要对叶节点进行评估，以便从有利局面选择当前着法，这便是博弈搜索的职能。

52 5.4.2极大-极小值搜索 极大极小值算法是香侬教授在1950年首先提出来的，极大极小值算法也是当代计算机博弈各种搜索算法的基础。由于对弈双方都是理智的，都想赢棋，在选择着法的时候都尽量让棋局朝着有利于自己的方面转化，所以在博弈树上，在不同层上就要有不同的选择标准。

53 极大极小搜索算法的基本思想： (1) 在偶数层节点的着法即轮到Max走棋的节点时，Max应考虑最好的情况，选择其全部子节点中评估值最大的一个，即 F(v) = max{F(v1), F(v2), ……, F(vn)} 其中，F ( ) 为节点估值，v1，v2，………vn为节点v的子节点。

54 (2) 在奇数层节点的着法即轮到Min走棋的节点时，Max应考虑最坏的情况，选择其全部子节点中评估值最小的一个，即
F(v) = min{F(v1), F(v2), ……, F(vn)} 其中，F ( ) 为节点估值，v1，v2，………vn为节点v的子节点。 (3) 评价往回倒推时，相当于两个局中人的对抗策略，交替使用(1)、(2)两种方法传递倒推值。

55 在进行极大-极小搜索的时候，首先要在有限深度内展开全部叶子节点，并进行评估，然后自下而上地进行搜索计算，一直反推到根结点。在反推的过程中始终要记住算出该值的子节点是谁，这样就可以得到一个从根结点到叶子节点的一条路径，这就是最佳路径，它是双方表现最佳的对弈着法序列。如图所示的博弈树，MAX层取下一层的极大值，MIN层取下一层的极小值。

56 极大极小算法伪代码 int minimax(position p,int depth) { int bestvalue,value;
if(gameover) // 检查棋局是否结束 return evaluation(p); // 棋局结束，返回估值 if depth<=0) // 是否是叶子节点 return evaluation(p); // 叶子节点，返回估值 if(p.color==RED) // 是否轮到红方走棋 bestvalue=-INFINITY; // 是，令初值最大值为极小 else bestvalue=INFINITY; // 否，令初值最小值为极大 for(each possibly move m) { // 对每一可能的走法 m makemove(m); // 产生第i 个棋面（子节点） value=minimax(p, depth -1); // 递归调用向下搜索子节点 unmakemove(m); // 恢复当前棋面 if(p.color==RED) bestval ue=max(value,bestvalue); // 取最大值 else bestval ue=min(value,bestvalue); // 取最小值 } return bestvalue; // 返回最大值或最小值

57 5.4.3负极大值算法 极大极小搜索是一种“变性”搜索，在偶数层进行Max搜索，而在奇数层进行Min搜索。如果把极大极小值算法稍做变形，就是负极大值算法。负极大值算法是Knuth和Moore在1975年提出的，是对极大极小算法的优化。

58 负极大值算法的思想在于：父节点的值是各子节点的值的负数的极大值，如图所示。在负极大值算法下，无论轮到人或者电脑走棋，选取的都是子节点负数最大的分枝，即
F(v) = -max{-F(v1), -F(v2), ……, -F(vn)} 其中，F ( ) 为节点估值，v1，v2，………vn为节点v的子节点。

59

60 负极大值搜索算法伪代码 int negamax(position p,int depth) {
int n, value, bestvalue=-INFINITY;; if(gameover) // 检查棋局是否结束 return evaluation(p); // 棋局结束，返回估值 if depth<=0) // 是否叶子节点 return evaluation(p); // 叶子节点，返回估值 for(each possibly move m) { // 对每一可能的走法 m makemove(m); // 产生第i 个局面（子节点） value=-negamax(p, depth -1); // 递归调用 minimax 向下搜索子节点 unmakemove(m); // 恢复当前局面 if(value >= bestvalue) bestvalue= value; // 取最小值 } return bestvalue; // 返回最大值或最小值

61 5.4.4宽度优先搜索和深度优先搜索 宽度优先搜索的基本思想是从初始节点开始，逐层地对节点进行扩展并考查它是否为目标节点。在第n层的节点没有全部扩展并考查之前，不对第 1 + n 层的节点进行扩展。宽度优先搜索是一种盲目搜索，时间和空间复杂度都比较高。

62 深度优先搜索的基本思想是从初始节点开始扩展，沿着树的最大深度方向进行的。只有当上次访问的节点不是目标节点且没有其它节点生成的时候才转到上次访问节点的父节点。深度优先搜索的优点是比宽度优先搜索算法需要较少的空间，该算法只需保存搜索树的一部分，它由当前正在搜索的路径和该路径上还没有完全展开的节点标志所组成。

63 在复杂度很高的机器博弈搜索中，比较适合选择深度优先搜索方法，可以在搜索过程中的任何时候仅仅生成整棵树的一小部分，搜索过的部分被立即删去。

64 5.4.5 α-β剪枝算法 在极大极小搜索过程中，遍历了整棵博弈树，每个节点都访问了一次，这样做的缺点是效率低下。在极大-极小搜索的基础上，以窗口的形式引进α-β 剪枝技术，使得搜索的效率显著提高。 α-β 剪枝把生成的搜索树和估值格局这两个过程结合起来，再根据一定的条件判定，有可能尽早剪掉一些无用的分枝。 α-β 剪枝的作用在于，当要得到一个非叶子节点的估值时，不一定要生成它的所有叶子节点后才计算。

65 α-β剪枝的规则如下: （1）α剪枝：若任一极小值层节点的β值小于或等于它任一先辈极大值层节点的α值，即α （先辈层）≥β（后继层），则可以中止该极小值层中这个min节点以下的搜索过程。这个min节点最终的倒推值就确定为这个β值。 （2）β剪枝：若任一极大值层节点的α 值大于或等于它任一先辈极小值层节点的β值，即α（后继层）≥β（先辈层），则可以中止该极大值层中这个max节点以下的搜索过程。这个max节点最终的倒推值就确定为这个α 值。

66 α剪枝

67 如果博弈树的局部为偶数层-奇数层-偶数层的关系，如图所示，在搜索完左边一枝之后，父节点得到一个值4，可以称之为α值。如果在其他支路的叶节点上发现了一个小于α的节点，则整个支路便可以剪掉，即没有必要再搜索下去，因为根据极大-极小算法的运算关系，这一枝不可能对局面有更好的贡献。图示中节点2取叶子节点5、6、7的极小值4，返回根结点1的α值为 4 ，节点3取叶节点8、9、10的极小值，

68 β剪枝

69 β剪枝出现在奇数层-偶数层-奇数层的子树部分。如图所示，在搜索完左边一枝后，父节点得到一个值7，可以称之为β值，如果在其他支路的叶子节点上发现了一个大于β值的节点，则整个支路便可以剪掉，即没有必要在搜下去。因为根据极大-极小的运算关系，这一枝不可能对局面有更好的贡献。分析过程同α剪枝过程，节点2取叶节点5、6、7的极大值7，返回根结点β值7 ，节点3取叶子节点8、9、10的极大值，搜索到节点9时将9返回节点3，节点3的值大于β值7，所以剪掉节点10，进而剪掉节点3，继续搜索节点11，将8返回到节点4，节点4的值大于β值7，剪掉节点12、13，进而剪掉节点4。图示中的最佳路径为1-2-7。所以β限定的是极大值。

70 在多层搜索中，α与β剪枝相互配合就实现了α-β剪枝搜索，虽然它没有遍历某些子树的大量节点，但它仍不失为穷尽搜索的本性。在搜索着法过程中，每个搜索过的着法都返回跟α和β有关的值，它们之间的关系非常重要，也许意味着搜索可以停止并返回。剪枝技巧的发现，一下便为博弈树搜索效率的提高开创了崭新的局面。

71 α-β只能用递归来实现。工作的过程是在搜索中传递两个值，第一个值是α，即上次搜索到的最好值，任何比它更小的值就没用了，因为策略就是知道α的值，任何小于或等于α的值都不会有所提高。第二个值是β，即上次搜索后得到的对于对手来说最坏的值。这是对手所能承受的最坏的结果，因为在对手看来，他总是会找到一个比β更好的对策。如果搜索过程中返回β或比β更好的值，那就够好的了，走棋的一方就没有机会使用这种策略了。因此β会不断减少。

72 如果某个着法的结果小于或等于α，那么它就是很差的着法，因此可以抛弃。在这个策略中，棋面对走棋的一方来说是以α为评价标准的。如果某个着法的结果大于或等于β，那么整个节点就作废了，因为对手不希望走到这个局面，而它有别的着法可以避免到达这个局面。因此如果我们找到的评价大于或等于β，就证明了这个节点是不会发生的，因此剩下的合理着法没有必要再搜索。

73 如果某个着法的结果大于α但小于β ，那么这个着法就是走棋一方可以考虑走的，除非以后有所变化。因此α会不断增加以反映新的情况。
同样也可以把α -β搜索算法写成负极大值形式，叫做 negamax 算法。

74 同极大极小值搜索算法类似，α-β搜索算法不仅要在奇数层进行α剪枝，而且还要在偶数层进行β剪枝。不过只要将负极大值的形式套用上去，这样在任何一层都只进行β剪枝，它就会同负极大值算法一样简洁。使用伪代码描述如下：

75 int alphabeta(int n,int alpha,int beta) {
if(gameover) // 检查棋局是否结束 return evaluation( ); // 棋局结束，返回估值 if(n<=0) // 是否叶子节点 return evaluation( ); // 叶子节点，返回估值 for(each possibly move m) { // 对每一可能的走法m makemove(m); // 产生第i个棋面（子节点） value=-alphabeta(n-1, -beta,-alpha); //递归调用向下搜索子节点 unmakemove(m); // 恢复当前棋面 if(value >= alpha) alpha = value; // 取最小值 if(alpha >= beta) break; //Beta 剪枝 } return alpha; // 返回最大值或最小值

76 5.4.6 极小窗口搜索算法 极小窗口搜索是在α-β算法的基础上形成的一种搜索方法，是以一个极小的窗口来搜索节点。
极小窗口搜索算法的过程是：对于第一个节点来说，假设它的第一个分枝节点是最佳的一步，我们先对它按照原来的α= -∞，β= +∞这样的范围进行搜索，我们会得到一个假设的最优解bestvalue。后继的分枝则以一个极小的窗口（也称为零窗口）（bestvalue，bestvalue + 1）搜索，因为不可能存在一个整数既大于bestvalue，又小于bestvalue + 1，如果搜索返回值大于零窗口，则证明这一分支亦为主变量。则对它进行窗口为（bestvalue + 1，β）的搜索，可是如果返回值小于零窗口，这一分支就可以忽略因为它的最佳走步还不如已有的走步。如果最优的子结点最先扩展，则此后的其他子结点通过α值对应的极小窗口进行搜索都可以轻松剪枝，搜索节点也更少。

77 5.4.7 渴望搜索算法 在α-β剪枝过程中，初始的搜索窗口往往是从α= -∞到β= +∞ ，在搜索进行中再不断缩小窗口，加大剪枝效果。渴望搜索就是渴望从一开始就用小的窗口，从而在搜索初起，就可以进行大量的剪枝。这个窗口的选定很重要，如果选择准确，即所要寻找的走步就在这个窗口内，搜索便可以继续进行。如果第一步搜索的返回值证明最佳走步大于β值，就需要重新确定窗口。以原来的β值为α值，以+∞ 的为新的β值，重新搜索。相反如果第一步的返回值证明最佳走步小于α值，重新确定的窗口就是以-∞为α值，原来的α值为β值了。可见第一次搜索猜测的窗口非常重要，如果猜测准确，搜索时间可以大大缩短，如果不准确，这一优势就不明显了。

78 猜测搜索的结果在x附近，那么可以令α= x -window（window是要搜索范围的大小的一半），β = x + window，再使用这样的一对值来进行剪枝来搜索结果。特别是当window很小的时候，搜索的效率会比较高，因为有了更多的剪枝。如果返回的值x –window≤ value ≤ x + window。在这种情况下，我们知道要找的值就在猜测的范围之内，可以直接使用导致找到最佳的步法。如果返回值不在这个范围，则重新调整窗口。

79 5.4.8 PVS 搜索 主要变例搜索，又叫 pvs 搜索，是α-β搜索的一种改进方法。 在α-β搜索中，任何结点都属于以下三种类型：
(1) α结点。每个搜索都会得到一个小于或等于α的值，这就意味着这里没有一个着法是好的，可能是因为这个局面对于要走的一方太坏了。 (2) β结点。至少一个着法会返回大于或等于β的值。 (3) 主要变例(PV)结点。有一个或多个着法会返回大于或等于α的值(即 PV 着法)，但是没有着法会返回大于或等于β的值。

80 主要变例搜索作了假设，如果在搜索一个结点时找到一个 PV 着法，那么就得到 PV 结点。即假设你着法排序已经足够好了，不必在其余的着法中找更好的 PV 着法或者高出边界的着法(这就会使结点变成β结点)。 你找到一个着法其值在 α和β之间，那么对其余的着法，搜索的目标就是证明他们都是坏的。跟要搜索出更好的着法相比，这种搜索也许要快一些。

81 如果这个算法发现判断是错的，即其中一个后续着法比第一个 PV 着法好，那么它会被再一次搜索，这次使用正常α-β搜索方法。这种情况有时会发生，这样就浪费时间了，但是这些时间通常不会超过前面所说的“证明是坏着法”所节约下来的时间。 整体看来，pvs 在效率上是优于（至少不次于）α-β的。因此许多博弈程序都采用以pvs 算法为核心的搜索算法。

82 5.4.8亚马逊棋博弈系统的搜索算法 宽度优先搜索适合用于解决节点个数少的问题，深度优先搜索一般用来求解节点数特别多的问题。极大极小算法虽然是经典的搜索算法，但是在搜索过程中总要判断哪一方要取极大值哪一方要取极小值。因此，选择它的优化算法负极大值算法，虽然它本质上与极大极小算法是一样的，仍然是一种穷尽搜索算法，但与极大极小算法相比较，程序要短而且简单。α-β 剪枝算法可以进行有效的剪枝。综合以上考虑，考虑选择 α-β 剪枝算法，深度优先搜索和负极大值搜索算法相结合作为基本搜索算法。

83 用α-β剪枝搜索算法首先要设定合适的α、β值，然后对当前棋局根据深度优先原则进行博弈树展开。
在负极大值搜索和α-β剪枝算法相结合的基础上，根据亚马逊棋对弈一定回合后必然出现每方的棋子在某固定区域的特点，本程序加入了一些信息，主要是对一些特殊区域的判断，也就是地盘的判断。

84 图中局势，黑方四颗棋子全在区域(A，B，C，D)内，白方不能进入。
定义一个区域判断函数。判断棋子是否全在固定的区域后，使用不同的搜索函数。

85 对棋局进行区域判断： (1) 经过区域判断，如果棋子不全在限定的区域内，那么按正常的方法搜索，定义搜索函数为： Search(int depth,int alpha,int bate,boolismyturn,int first,bool myturn) ismyturn//轮到哪方走棋，依层数改变 myturn //当前哪方走棋，不依层数改变

86 主要搜索部分的代码如下： GoNumber=PMakeHowDo(GoWay,ismyturn);//不全在区域内的着法生成函数 if(depth!=first)//判断是否走棋 { for(i=0;i<GoNumber;i++) //所有可能的走法 makemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],ismyturn);//将当前局面应用此走法，变为子节点的局面 value=-Search(depth-1,-bate,-alpha,!ismyturn,first,myturn);//递归搜索子节点 unmakemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],ismyturn); //撤销搜索过的子节点 if(alpha<value) alpha=value; //保存最大值 if(alpha>=bate) return alpha;//beta剪枝 } return alpha;//返回极大值 } else { for(i=0;i<GoNumber;i++) makemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],ismyturn); value=-Search(depth-1,-bate,-alpha,!ismyturn,first,myturn); unmakemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],ismyturn); if(alpha<value) alpha=value;//设置最佳走法 bestgo=i;//最佳走法就是电脑选择的着法

87 (2) 经过区域判断，如果棋子全在限定的区域内，那么进行特定的搜索。定义搜索函数为：
Search1(int depth,int first,int stu)//只搜索一个子

88 主要搜索部分的代码如下： GoNumber=PMake1HowDo(GoWay,stu);//全部在区域内的着法生成函数 if(depth!=first) { for(i=0;i<GoNumber;i++) makemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],false); value=Search1(depth-1,first,GoWay[i][1]); unmakemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],false); if(alpha<value) alpha=value; } return alpha; Else { for(i=0;i<GoNumber;i++) makemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],false); value=Search1(depth-1,first,GoWay[i][1]); unmakemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],false); if(alpha<value) alpha=value; bestgo=i; }

89 α-β剪枝算法通过“剪枝”技巧很大程度上缩小了博弈树的规模，另外，在搜索之前对棋局进行区域判断，对特定的棋局状态进行不同的搜索函数搜索，搜索效率明显得到提高。

90 搜索引擎的完整过程的流程

91 5.5 估值函数的设计 评估函数是除了搜索算法以外，另一个对博弈树求解的重要方面。只有有了良好的估值函数才能保证较快地找到最佳着法。而估值函数是对棋局的综合评估，该函数的好坏直接决定棋力的强弱。通常情况下，估值函数在很大程度上依赖于具体的游戏规则和我们对该游戏的经验知识。同时评估函数和搜索算法一样是博弈树搜索的核心。

92 由于亚马逊棋博弈的复杂性，在搜索树展开时不可能到达最终的状态，所以如果能对某些中间的状态进行较为准确的评估就不需要展开到真正的最终状态便可以得到不错的结果。所以，只有有了良好的评估函数，搜索模块才能保证有效地找到最优解，该函数的好坏直接影响搜索过程中的取舍而决定着法的好坏。虽然并不存在绝对准确的评估函数，但综合大量的亚马逊棋的相关知识，把局面的好坏程度转化为一个相对准确的数字，这个数字可以代表这个棋局的性质。

93 5.5.1棋子的自由度 在亚马逊棋博弈过程中，棋子的自由度是影响棋局非常重要的因素。本博弈系统中，在考虑棋子的自由度的基础上，计算棋子所在位置的八个方向上可行空格子的数量，而且对可行格子的数量赋予较大的分值10，每增加一个格子就加上10。其中黑方赋予正值，白方赋予负值。

94 5.5.2棋子位置的情况 对棋子所在位置情况的分析主要从棋子在棋盘边框，四周位置是己方棋子、对方棋子、障碍、空格五方面来对某一方布子所形成的棋局状态的评估。根据不同的情况对棋子的影响程度不同，分别对五种情况设定合适的分值。 设定在边框赋予分值3；周围为障碍赋予4；为对方棋子赋予3；为己方棋子赋予5。其中黑方为负值，白方为正值。双方棋子是邻居，赋一次分值。

95 5.5.3棋子的位置关系 一般来讲，某方棋子之间的位置联系相对小，也就是意味着本方棋子分布均匀，对棋盘的掌控能力也相对大。在对弈过程中双方的可行区域越来越小，构造的评估函数为： (1) 对弈50步以下时 Value=freedom+score+a+b 定义value为总的评估值，freedom为对棋子自由度的评估值，score为棋子所在位置旁边八个方向的情况的评估值，a、b为己方棋子、对方棋子之间的位置关系。

96 (2) 对弈50步以上时 Value=freedom+score 式中，只包括棋子的自由度和己方棋子和对方棋子所在位置周围的情况。 通过全盘搜索，对以上因素进行统计，然后根据评估函数赋值，对叶子节点进行估值。

97 5.6 界面设计 程序的主要功能主要在鼠标的左键消息中实现，它的流程图如右：

98 第6章总结 (1)通过加入各个棋种的策略来优化搜索算法。剪枝搜索算法能够在庞大的博弈树中利用已经搜索的信息剪掉不影响结果的子树，结合哈希技术，避免对相同的局面重复搜索，也有效地提高了搜索效率。在搜索中将各个棋种知识显示的表示出来并且指导搜索和剪枝，会使搜索的效率大幅提高，这样就可以节省更多的时间来做更深层次的搜索了。

99 第6章总结 （2）改进估值函数，使之对局势的判断更灵敏，使之对于局面的评估更为精确。
改进的估值函数对提高棋力也是必不可少的。亚马逊棋虽然采用的是传统的静态估值函数，但对各种因素的权值存在一些主观的因素加以判断，对局势的好坏判断不够灵敏。由于估值函数是与具体的棋类知识紧密结合的一部分，所以我们可以在估值函数中加入更多的棋种知识，使之对于局面的评估更为精确。

100 第6章总结 (3)在开局阶段单独使用负极大值（或最大最小值）形式的α-β剪枝搜索算法运作速度慢。加入开局库、残局库，提高亚马逊棋开局和残局阶段的速率和准确率。 (4) 完善人机界面，建立博弈公共平台，减少后期开发代价。