或对角线的总数)-e( 那些仍为 MIN 空着的完全的行、列或对角线的总数)(2) 若P是MAX 必胜的棋局,则 e(P) =+∞。(3) 若P是B必胜的棋局,则 e(P) =-∞。比如 P如下图 2所示,则e(P)=6-4=2 “程序设计”课程设计报告 7 图2 下画出了经过两层搜索生成的博弈树,静态估值记在端节点下面,倒推值记在圆圈内。图3 现在图中MAX有两个可能“最好的”优先走步,假设MAX走了图上指明的那一步。而MIN 为了避免立即败北被迫走了另一步,从而产生如下棋局: MAX 再次搜索, 产生如下图 4的棋局: “程序设计”课程设计报告 8 图4 在这棵树中某些端节点(例如其中一个标记着 A)代表 MIN 获胜,因此它们的估值为—∞。当这些估值被倒推回去时,可看到 MAX 的最好的也是唯一能使他避免立即失败的一个走步。现在,MIN 可以看出 MAX 必然在他的下一走步中获胜,因此, MIN 只好认输。阿尔法- 贝塔法: 首先分析极小极大分析法效率,上述的极小极大分析法,实际是先生成一棵博弈树,然后再计算其倒推值,至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了α-β剪枝技术。α-β剪枝技术的基本思想或算法是,边生成博弈树边计算评估各节点的倒推值,并且根据评估出的倒推值范围,及时停止扩展那些已无必要再扩展的子节点,即相当于剪去了博弈树上的一些分枝,从而节约了机器开销,提高了搜索效率。具体的剪枝方法如下: (1) 对于一个与节点 MIN ,若能估计出其倒推值的上确界β,并且这个β值不大于 MIN 的父节点( 一定是或节点) 的估计倒推值的下确界α,即α≥β,则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为α剪枝。(2) 对于一个或节点 MAX ,若能估计出其倒推值的下确界α,并且这个α值
全文预览
