解井字棋游戏

《风险-收益分析：理性投资的理论与实践（第2卷）》解井字棋游戏,页面无弹窗的全文阅读!

我们假设大多数读者知道，井字棋游戏是在一个如图8-1中所示的3×3的格子棋盘（grid）上玩的。图8-1显示了第四次行动后游戏的一个可能状态。游戏（在t=0时）从一个空格开始。第一个参与人在9个空方格的任何一个中画上“X”。这是第一次行动，在下面的时间轴中它被标记为行动1。行动1将系统从初始状态s0转换成下一个状态s1。紧接着，另一个参与人在8个仍然空着的方格的任意一个中画“○”。这是行动2，它将状态s1转换成状态s2。再接着，参与人X在7个仍未被占据的方格的任意一个中画上“X”，依此类推。直到下列情况之一发生，游戏结束：

（1）参与人X在一行、一列或两条3方格对角线的任意一条中画上了3个X，则参与人X获胜；

（2）参与人○先于参与人X做了同样的事情（当然，是画上3个○），则参与人○获胜；

（3）9个方格都被填上，但没有任何一个参与人获胜。

图8-1　4次行动后的井字棋游戏

分别给结果（1）、（2）和（3）赋予得分＋1、－1和0。参与人X试图使得分最大化，而参与人○则试图使得分最小化。因此，参与人X的博弈效用是其博弈的得分，参与人○的效用是其得分的相反数（在一个确定性博弈中，选择仅由结果的序数排列而非基数效用确定）。

每一个参与人的最优策略，以及每一个参与人都采取最优策略时的博弈得分，可按照如下方式计算。在动态规划方法下，首先分析博弈结束时（时点t=9）的可能状态。这些可能的状态由各种棋局组成，在其中一个参与人获胜或另一个参与人获胜，或所有的格子都填上了但没有人获胜。如果在博弈的第9次行动之前已经有人获胜，那么在t=9时仍有一些方格是空的。因此，可以把填有X、○的格子和空格组成的3×3棋局划分为4个集合，即

A.参与人X获胜；

B.参与人○获胜；

C.棋盘被填满但没有人获胜；

D.棋局不可能是s9，这或者是因为博弈仍在进行，或者是因为该棋局不可能出现，比如因为它有错误个数的X和○。

对子集A中的每一个棋局存储“1”，对子集B中的每一个棋局存储“-1”，对子集C中的每一个棋局存储“0”，并删除（或者做上适当的标记）子集D中的每一个棋局。

接下来在时点t=8处理所有最多有8个非空格的棋局。再一次将这些棋局划分为4个子集，分别标记为A、B、C和D。同样，子集A包含了X获胜的完整博弈，子集B包含了○获胜的完整博弈，以及子集D包含的是在t=8时不可能出现的棋局。

子集C包含了剩下的棋局，即那些在t=8时能够出现，但尚没有参与人获胜的棋局。具体而言，它们恰好包含一个空格，因为在t=8时有多于一个空格的棋局必定已经有一个胜者。如时间轴提示我们的，在t=8时轮到参与人X采取行动9，即在唯一的空格中画上一个X。这样就产生了一个没有空格的棋局。在之前的一步（t=9）中，所有这样的棋局都被赋予一个得分。它也是t=8时子集C中每一个棋局的得分，因为如果出现了这一棋局，那么它必然是博弈的得分。

接下来处理t=7时最多有7个非空格的棋局。这一步将更充分地展示在这个例子中和类似的在一般动态规划运算中通常会发生什么。与之前一样，将有至少两个空格的棋局划分为四个子集，划分的依据是：A.X获胜；B.○获胜；D.该棋局在t=7时不可能出现；C.博弈仍在进行中，并且轮到○来采取行动。在最后一种情形中，参与人○采取博弈的第8次行动，在两个空方格之一中画○。理性决策的（RDM）参与人○决定在哪个空格中画○的方法如下：

对于子集C中的每一个棋局，以及棋局两个空格中的每一个，试探性地在一个空格中画○。这样得到了一个只有一个空格的棋局。所有这样的博弈的值已经确定。对于t=7时子集C中的特定棋局，理性决策的参与人○将会（在两个可行的行动中）选择使博弈得分极小的行动（对于参与人○而言这是最优的）。这个极小值就是t=7时该特定棋局的得分，因为它必然是博弈的得分。

类似地，对于参与人X，当t=6时：

对于一个博弈结果尚未确定的可能棋局，在三个空格中的每一个，试探性地画上X。这得到了一个t=7时的棋局，它的得分已经确定了。选择使博弈得分（也是参与人X的效用）极大的行动。这个极大得分将是博弈的最终得分，如果在剩余博弈中每一个参与人都选择对自己而言最优行动的话。

现在阐述一般情形，不仅针对井字棋游戏t≤5时的行动，而且针对任意完全信息的确定性博弈。在这样的博弈中，考虑T－1时每一个可能的状态sT-1，启动动态规划运算。T－1是博弈仍在进行时能够做决策的最后可能时点（在t=T时，不需要做什么决策）。一般来说，即便不是在井字棋游戏中，此时参与人将要采取的行动仍可能是当前系统状态sT-1的一个函数。然而，在井字棋游戏中，如同一般情形，有可能没有“参与人采取行动”，因为博弈已经结束。要采取行动的参与人（如果有的话）依次考虑他在该状态下所能采取的每一个行动，并选择这样一个行动，由该行动导致的下一个（和最终）状态sT，使所说的要采取行动的参与人具有最高的效用。不失一般性，我们可以假设这个效用仅为最终状态sT的函数。

在两人零和博弈之外的博弈中，选择最佳行动时遇到结点，必须由某个明确的、所有参与人预先知道的规则来破解。这是因为在一个n人博弈中，对要采取行动的参与人同样好的两个行动，可能并非对所有参与人都同样好或坏，包括对两人非零和博弈中的另一个参与人也是如此。为在这样一个博弈中执行动态规划运算，每一个参与人都必须知道其他参与人在每一个随后可能出现的状态下会怎样行动。

除了找出在给定的倒数第二个状态sT-1下的最佳行动外，动态规划运算还确定了每个参与人I依附于该状态的效用UI（sT-1）。如果达到了状态sT-1，并且采取行动的参与人做出了其最优的最后行动，那么它将是参与人I的博弈效用。这允许动态规划运算向后迭代一期至t=T-2，并重复在t=T-1时用到的过程，但现在是以为可称之为导出博弈的导出效用函数。在每一个时点t，采取行动的参与人都通过恰当选择状态st下可选择的行动，最大化一个单期效用函数。

我们将会看到，在那些每一个参与人都知道当前状态但下一个状态是随机的博弈中，动态规划运算也像刚才讨论的那样进行，除了使用期望效用而非已知的确定性效用外。在不完全信息博弈中，理性决策者（RDM）在所拥有的信息条件下最大化其期望效用。为给出正式的定义，并证明这些有关动态规划的结论，我们需要讨论条件期望值。

是我们从动态规划中寻求的核心概念。它是在t+1时状态st+1以及每个参与人都在t+1及之后采取最优行动（当然，是对他自己而言）的条件下，参与人I的整个博弈的期望效用值。即是导出效用函数。给定状态st下的可能选择，采取行动的参与人在时点t状态st下选择它的行动，以最大化这一单期导出效用函数的期望值，也即最大化。