什么来自是博弈树，怎么用来分析？( 二 ) _博弈

走的棋布都会导致棋手赢时，这时棋手才能保证会赢。因此，对于对手走的结点是一个与
节点。
对于一场经过深思熟虑地棋局来说，其博弈树是非常庞大的（国际象棋来说有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节点。这样就可以导致最复杂的情况产生。希望对手在这种情况下失误

什么来自是博弈树，怎么用来分析？( 二 )

猜你喜欢