4实验四 博弈树搜索
（一）实验名称：
博弈树搜索
（二）目的：
熟悉和掌握博弈树搜索算法过程，包括极小极大分析法和α-β剪枝方法，理解求解流程。
（三）原理：
极小极大分析法实际是先生成一棵博弈树，然后再计算其倒推值。但是极小极大分析法效率较低，于是在其基础上提出了α-β剪枝技术。α-β剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。
（四）步骤：
极大极小过程的基本思路：
① 对于每一格局（棋局）给出（定义或者倒推）一个静态估价函数值。值越大对MAX越有利，反之越不利
② 对于给定的格局，MAX给出可能的走法，然后MIN对应地给出相应的走法，这样重复若干次，得到一组端节点（必须由MIN走后得到的，由MAX下的棋局）。这一过程相当于节点扩展
③ 对于每一个端节点，计算出它们的静态估价函数，然后自下而上地逐层计算倒推值，直到MAX开始的格局。在MIN下的格局中取估值的最小值，在MAX下的格局中取估值的最大值
④ 取估值最大的格局作为MAX要走的一招棋
符号：
OPEN：存放待扩展的节点，此时为队列，即以宽度优先的策略扩展节点
CLOSED：存放已扩展的节点，此时为堆栈，即后扩展的节点先计算静态估价函数
值
算法分成两个阶段：
第一阶段：用宽度优先算法生成规定深度 k 的全部博弈树，然后对其所有端节点计算 e(P) 第二阶段：自下而上逐级求节点的倒推估价值，直至求出初始节点的 e(S) 为止，再由 e(S) 选得相对较好的走法，过程结束
1
（五）实验结果与分析：
2
