一字棋示例

    下面以一字棋为例说明极小极大过程。一字棋的棋盘有三行三列，每个棋手轮流摆子，每次摆一个子，先形成三子一线者胜。设ＭＡＸ方的棋子用×标记，ＭＩＮ方的棋子用○标记，并规定ＭＡＸ方先走。为了对叶结点进行静态估价，我们规定估价函数e（p）如下。

     若p对任何一方都不是获胜的位置，则

          e（p）=（所有空格都放上ＭＡＸ的棋子组成的行、列和对角线的总数）－
            （所有空格都放上ＭＩＮ的棋子之后，全部由ＭＩＮ的棋子组成的
             行、列和对角线的总数）

     若p是ＭＡＸ的获胜位置，则

                                     e（p）=∞

     若p是ＭＩＮ的获胜位置，则

                                    e（p）=­－∞

例如，如果棋局p如图a所示，则估价函数e（p）=6－4=2。考虑到对称性，可认为下列棋局是
           
等价的，这样就可大大减小搜索空间。图４．１５画出了经过二层搜索生成的博弈树。叶结点的静态估值记在叶结点下面，非叶结点的倒推值记在结点旁边的圆圈内。由于初始结点的三个后继结点中，右边的结点具有最大的倒推值１，所以ＭＡＸ应选择右边的走法。假设ＭＡＸ走了这一步，轮到ＭＩＮ走步时，在×的上方空格中放上一子（这不是最好的走法，但我们不考虑ＭＩＮ的走法）。为了确定ＭＡＸ下一步的走法，再经过二层搜索生成一个博弈树如图４．１６所示。这一次初始结点有二个后继结点取最大的倒推值，因此可任过其中一个走法，比如选取图中注明的走法。轮到ＭＡＸ下一步的步法，再经过二层搜索生成一个博弈树如图４．１７所示。从图中可以看出，ＭＡＸ只有最左边一个走法可取，其它走法都会输。在ＭＡＸ选择最左边的走法后，下次ＭＩＮ方如何走子，都肯定会输了。

返回