多人游戏中的最优决策

6.2.3 多人游戏中的最优决策

许多流行的游戏允许多于两个的参加者。让我们来看一看如何把极小极大思想推广到多人游戏中。这在技术观点上看比较直接，但产生了一些有趣的概念问题。

首先我们需要把每个节点上的单一值替换成一个向量值。例如在一个有三个人A，B和C的游戏中，每个节点都与一个向量〈vA, vB, vC〉相关联。对于终止状态，这个向量给出了从每个人角度出发得到的状态效用值。（在两人的零和游戏中，由于效用值总是正好相反，所以二维向量可以简化为一个单一值。）简单的实现这个的方法是让函数UTILITY返回一个效用值向量。

现在我们来看非终止状态。考虑在图6.4中的博弈树上标为X的节点。在这个状态，轮到游戏者C选择做什么。两种选择导致的终止状态的效用值向量分别是：〈vA=1, vB=2, vC=6〉和〈vA=4, vB=2, vC=3〉。由于6比3大，所以C应该选择第一种走法。这也意味着如果到达了状态X，后继的招数会走到效用值向量为〈vA=1, vB=2, vC=6〉的终止状态。因此X的回传值就是这个向量。一般来讲，节点n的回传值是该游戏者在节点n选择的效用值最高的后继者的效用值向量。

图6.4 有三个游戏者（A, B, C）的博弈树中的前三层。每个节点标有从每个游戏者角度出发的值。根节点标示了最佳步骤

任何玩过诸如 DiplomacyTM（外交游戏）这样的多人游戏的人很快会意识到这比双人游戏要复杂得多。多人游戏通常会涉及在游戏者之间出现正式或者非正式的联盟的情况。随着游戏的进行，联盟也建立或者解散。我们如何去理解这种行为呢？是否在多人游戏中对每个游戏者来说联盟是最优策略的一个自然结果？看起来可能是这样的。例如A和B相对比较弱，而C很强。那么对于A和B而言，它们一起进攻C比等C逐个消灭它们要好，这样通常是最优的。如此，合作从纯自私的行为中涌现出来。当然，一旦C在联合攻击下被削弱，联盟就失去了价值，于是A或者B就会破坏协议。某些情况下，外在的联盟仅仅是把将要发生的具体化。在另一些情况下，违反盟约会损害社会声誉，所以游戏者要在毁约得到的直接利益和被认为不可信任而带来的长期弊端之间寻求平衡。在第17.6节中我们会有更详细的讨论。

如果游戏是非零和的，那么合作也可能发生在两人游戏中。例如，假设有一个终止状态的效用值向量是〈vA=1000,vB=1000〉，并且1000对于两个游戏者都是最高的可能效用值。那么双方的最优策略就是做一切可能的招数来到达这个状态——也就是说，双方会自动合作来达到共同渴望的目标。