博弈树怎么看纳什均衡

博弈树看纳什均衡：纳什均衡和逆向归纳策略都是同一个，即与支付向量（1，3）相应的策略组合（决策1，决策3）。

博弈树探讨一下难度较大的棋类游戏程序，用这些程序来同人或其他程序对弈。有些程序是把计算机精心设计成一个棋盘，人们可以在其上对弈。这种程序更接近于系统模拟的领域，而不属于人工智能的范畴。此处所要介绍的却是让计算机能够“思考”如何下棋。

简介

纳什均衡（Nash equilibrium），又称为非合作博弈均衡，是博弈论的一个重要术语，以约翰·纳什命名。在一个博弈过程中，无论对方的策略选择如何，当事人一方都会选择某个确定的策略，则该策略被称作支配性策略。如果任意一位参与者在其他所有参与者的策略确定的情况下，其选择的策略是最优的，那么这个组合就被定义为纳什均衡。

探讨一下难度较大的棋类游戏程序，比如国际象棋和西洋跳棋

等等。用这些程序来同人或其他程序对弈。然而，有些程序是把计算机精心设计成一个棋

盘，人们可以在其上对弈（或者是一种单人玩的棋盘游戏）。这种程序更接近于系统模拟

的领域，而不属于人工

智能的范畴。我们此处所要介绍的却是让计算机能够“思考”如何下棋。

假定有两个人或者两台机器在下棋。我们把其中一名称为棋手，另一名称为对手。而我们

始终从棋手的角度来观看这场竞赛。这样一来，如果棋手赢了、对手输了，我们就说这盘

棋赢了；如果棋手输了、对手赢了，我们就说这盘棋输了。

假设现在该轮到棋手走了。在大多数情况下，棋手对这步棋可以有若干种选择。对于棋手

的每一种选择，对手也有若干可供选择的相应棋步。对于棋手的每一步棋以及对手的每一

步回棋，棋手又有自己进一步的选择。显然，这里所遇到的分支情况同我们在状态搜索中

遇到的情形相同的。

实际上，我们可以把一盘棋想象成具有一个入口（起始位置）和一组出口的迷宫。有些出

口标上了赢的记号；有些出口标上了输的记号；而有些出口标上了和局的记号。在入口处

，棋手选择某条路径起步，在路径的一个岔口，对手挑选了自己的路径回步，棋手和对手

就这样轮流选择自己的

路径走下去。棋手总是力争通向胜利的出口，而对手却总是把棋路引向输的出口。有时双

方各自的努力不相上下，最后在和局出口结束棋局。或者他们一直在这个迷宫中徘徊，直

到形势变得非常明朗：双方循环兜圈子，这时只好双方握手言和。

因此，下棋游戏同状态图搜索是相似的，就是要在状态图中找出一条从初始状态到目的状

态的路径。但是，它们之间却有一个很大的差别。在状态图搜索中，总是由一名选手来选

择下一步往哪走。而在棋类的对弈中，棋手只有一半选择的权利，另一半由对手作出决定

。棋手是一直朝着目标

努力，而对手却是通过它每一步棋对此设置障碍。寻找机会把棋手从通往目标的路径上引

开。

对于任何一种博弈竞赛，我们可以构成一个博弈树。它类似于状态图和问题求解搜索中使

用的搜索树。博弈树的结点对应于某一个棋局，其分支表示走一步棋；根部对应于开始位

置，其叶表示对弈到此结束。在叶节点对应的棋局中，竞赛的结果可以是赢、输或者和局

。

所谓棋局，就是所有那些必须记录下来的信息。根据这些信息，比赛在按计划暂停以后能

够得以继续进行下去。显然，这些信息包括了此时棋子在棋盘上的位置以及指出下一步是

轮到棋手走，还是对手走。

博弈树是一棵与／或树，不同于在状态搜索中使用的纯粹的或树。

其原因是：当轮到棋手走时，他可以决定选择哪一步棋走。如果起码有一步可以担保棋手

能够到达赢的棋局，那么棋手就会选择这一步并保证能够取胜。因此对应于棋手走的节点

是一个或节点。

当轮到对手走时，选择是由对手决定的。棋手没有任何选择的权利。只有对手的所有可以

走的棋布都会导致棋手赢时，这时棋手才能保证会赢。因此，对于对手走的结点是一个与

节点。

对于一场经过深思熟虑地棋局来说，其博弈树是非常庞大的（国际象棋来说有10^120个节

点）。以至于不可能把这样大的博弈树装入计算机，也不可能在任何合理的、有限的时间

内进行详细的搜索。尽管如此，首先深入的考察一下完整的博弈树，然后再看看如何来修

正我们的原来的想法，

以便把搜索树修整到一个合理的范围。这样做还是很有意义的。

博弈策略

假设我们对所讨论的博弈问题构造了一棵完整的博弈树，我们希望能从中找出棋手应采用

的策略。这种策略应当确保棋手会赢，或者起码能够得到和局的结果。

首先我们把该博弈树的每一个节点标上w（对应于赢）、d（对应于和局）或者l（对应于

输）。如果当前的棋局对应于标有w的节点，那么就存在一种策略可以担保棋手会赢；如

果结点标的是d，那么除非对手失误，否则棋手最好的前景就是争取和局；如果节标的是l

，那么棋手只好认输了，

除非对手下错了棋。

对一个节点标以w、d和l的过程，可以如下进行。

我们的讨论从叶节点开始，每一个叶结点对应于一场棋赛的结束的终局。根据博弈的规则

，叶节点确定了棋手的赢，输和和局。这样，我们就把每一个叶节点标上相应的值。

现在我们按照从叶往根本方向进行研究。按照每一节点的子节点的标号来标记该节点本身

。节点标注的规则如下： 轮到棋手走步时，如果该节点的子节点至少有一个标有w，那么

，该节点就标为w；如果所有子节点都标为l，那么该节点标为l。其他情况标上d。

轮到对手走步时，如果该节点的子节点都标上了w，那么该节点标为w；如果有一个以上的

子节点标上了l，那么该节点标为l。其他情况标上d。

根节点的标注表明，在对手不失误的情况下，棋手能够得到的最好结果。如果根节点为w

，那么棋手稳 *** 胜券；如果为l，那么对手一定能击败棋手；如果为d，那么在对手不失误

的条件下，棋手能够得到的最好结果就是平局。

一场比赛，如其根节点能够标上w或l，并且是很简单易于分析的话，就可以成为骗人的棋

局。该节点标作w的话，无论是谁先走，先走者都能赢；根节点为l的话，无论谁后走，则

后者也一定能赢。当然需要采取正确的策略。骗子知道哪一方面能够赢，以及要赢所需要

采用的策略。而这些，

受骗者肯定是不知道的。

棋手的策略应该遵循这样的原则：如果有一步棋能走到节点为W的棋局，那么就应当走这

步棋；如果所有的棋步都通向节点为l的棋局，那么就只好放弃这盘棋认输。其他情况下

，就要走到标为d的节点。

对手采取的策略正好相反：如果有一步棋能走到节点标为l的棋局，那么就下这步棋，如

果所有的棋步都通向节点为w的棋局，那就只有放弃认输。其他情况下，就要走到标为d的

节点。

当有两条以上的路径都能通往l节点，或者有两条以上的路径通往d节点时，棋手所采取的

策略就不再是决定性的了。在实际对弈中，棋手总是想选择w节点，达到了w节点，就使得

往后的对弈过程变得简单了。这样做就能减少棋手失误以致失去优势的机会。基于同样的

理由，棋手在达不到节

点时，应该选择d节点。这样就可以导致最复杂的情况产生。希望对手在这种情况下失误

以便使自己重新得到优势。到现在为止，我们的讨论还是很不充分的。因为在所有的w节

点或者所有的l节点之间，我们并没有给出任何差别。