博弈树

分钱币博弈。有一堆钱币，由两位选手轮流进行分堆。要求每个选手每次只能把其中某一堆分成数目不等的两小堆，直到不能再分为止。哪个选手遇到不能再分的情况，就为输。

假设这堆钱币的数量为7。博弈树如下。有max和min两个选手，节点中的min和max，表示当前节点由响应的选手进行选择。

局面评价函数

在分钱币博弈中，博弈树很短，在对手总是做出最佳选择的假设下，选手可用倒推法来进行决策。

但大多数博弈，博弈树都很深，不可能完全展开。这时需要局面评价函数，对每个节点给出一个分数。

比如一字棋。两个选手轮流在九宫格中落子，棋子先连成一条直线（包括对角线）的选手获胜。局面评价函数可这样定义：max获胜的可能路线数减去min获胜的可能路线数。见下图：

又比如象棋，红棋的个数减去黑棋的个数，就是一个局面评价函数。但这个函数是很不好的，因为不同的棋子价值不一样。所以应给不同的棋子赋予不同的分数。但这还不够，因为棋子位置不同，形势就不同。局面评价函数应把这些因素考虑进去。给出合理的局面评价函数是非常困难的，它直接决定着程序的质量。

围棋程序比象棋程序更难，并不是因为围棋可能的下法更多，从而博弈数的节点更多，更难搜索，而是因为很难给出合理的局面评价函数。

下棋是零和博弈，选手max尽量让博弈进行到分数高的节点，而选手min尽量让博弈进行到分数低的节点。

极大极小法

极大极小法假设对手总是做出最佳的选择。

比如下面这个博弈。轮到max决策。他向前想两个回合，然后根据评价函数给这博弈树中的叶节点赋予分数。

第三层中轮到max选择，他总是选择分数值更大的分支，所以第三层节点的分数值等于他孩子中最大的分数。而第二层节点由min进行决策，他总是选择分数小的分支，所以第二层节点的分数等于他孩子中最小的分数。而第一层的节点由max选择，他选择分数大的分支，和第三层一样。

在对所有节点赋值后，博弈树如下：

在根节点轮到max选择时，max选择第二层最左边的节点，因为它比其他两个节点分数高。

为什么不根据评价函数直接计算第二层节点的分数，而是计算叶节点的分数然后倒推给出其他节点分数值？因为在接近终局时，局面评价函数给出的分数值更准确。

如果是穷举搜索，则局面评价函数只需给出博弈结束时局面的分数就行，无需对所有局面进行打分。因为穷举搜索，叶节点一定是博弈结束的节点。

剪枝算法

剪枝算法的结果和极大极小算法是一样的，它是对极大极小算法的优化。

比如下面这个博弈中，max选择B节点，分值是19，如果选择C节点，而min选择D节点，则分值是17。所以max选择C节点肯定不如选择B节点，根本不用再考虑E节点和F节点，因为max选C时min将选择DEF中分值最小的一个，而这个分值不会超过17。所以将E和F剪掉，无需将博弈树在这里展开，也无需计算这些节点的分值。

     同理，在下面这个博弈中，min也无需考虑E和F节点，就直接选择B。

     在前面讨论的那个博弈，如果使用剪枝算法，得到的博弈树如下图。可看出它比极大极小算法效率提高很多。

剪枝算法的效率依赖于着法的寻找顺序。如果总是先去搜索最坏的着法，那么剪枝就不会发生，最终会找遍整个博弈树，这时该算法就如同极大极小算法一样，效率非常低。