包含几率因素的游戏

6.5 包含几率因素的游戏

在现实生活中，很多不可预知的外部事件会把我们推到没有预测到的情景中。许多游戏引入了随机因素（如掷骰子）来反映这种不可预测性。这样使游戏更接近实际，也值我们得来看一看随机因素是如何影响决策过程的。

西洋双陆棋（backgammon）是一个典型的结合运气和技术的游戏。在每一回合前要掷骰子来确定合法的步数。在图6.10里的双陆棋棋局中，白棋掷了一个6-5，所以有4种可能走法。

尽管白棋知道自己的合法行棋，但不知道黑棋会掷出几，也就无法知道黑棋会有哪些合法行棋。这意味着白棋无法构造我们在国际象棋和井字棋中见过的标准博弈树。双陆棋的博弈树必须在 MAX和MIN节点之外还包括几率节点。在图6.11中，几率节点用圆圈表示。从每个几率节点向下的分支代表可能的掷骰子结果，并且标记着骰子数及其出现的几率。两个骰子可以有36种组合，每种概率是相等的；不过掷出5-6和6-5是一样的，所以总共只有21个不同的掷法。6个有相同骰子数的组合（1-1到6-6）每个都以1/36的概率出现，而其它15种不同掷法每个以1/18的概率出现。

下一步是理解如何做出正确的决策。显然，我们仍然希望选择能够导致最佳棋局的行棋。然而，产生的棋局没有明确的极小极大值。作为替代，我们只能计算一个把所有可能出现的掷骰子结果考虑进去的期望值。这引导我们把确定性游戏中的极小极大值推广为包含几率节点的游戏的期望极小极大值。终止节点，MAX节点和MIN节点（掷骰子结果已知的）发挥和以前完全一样的作用，通过下面的公式把所有可能的掷骰子结果的值加权平均，对几率节点进行评价，也就是，

图6.10 典型的西洋双陆棋棋局。游戏的目标是把自己的棋子全部移出棋盘。白棋顺时针向25移动，黑棋逆时针向0移动。每个棋子可以按照掷出的骰子数移动到任意位置除非那里有多个对方棋子，如果那里只有一个对方棋子，这个棋子就被吃了，要重新开始。在所示棋局里，白棋掷了6-5，所以必须从4种合法移动(5-10,5-11)，(5-11,19-24)，(5-10,10-16)，(5-11,11-16)中选一个

图6.11 西洋双陆棋棋局的示意博弈树

其中几率节点n的后继函数简单地用状态n在不同掷骰子结果下所对应的后继状态s进行扩充，而P(s)是对应掷骰子结果出现的概率。这些公式可以把计算值递归地一直向上回传到树的根节点，和极小极大值算法一样。详细的算法我们留作习题。