极大极小树的剪枝算法1 alpha-beta剪枝

Alpha-Beta 剪枝算法用于减少极大极小算法所搜索的节点数目，Alpha-Beta 剪枝算法的效率很大依赖于节点的排列，在理想的排序下，算法复杂度为O（b^(d/2)）,可使搜索节点的数量减少一半，从而使在相同时间下的搜索深度增长一倍。在随机排序下，算法复杂度平均为O（b^(d*3/4)）node

算法使用了两个值，分别为alpha和beta，分别表明最佳得分的最小下界和最大上界，最初alpha，beta被设为无穷大和无穷小，随着搜索的进行，这个上界和下界逐渐收敛。算法

1） 任何max节点的alpha值大于其父节点的beta值，则把该节点剩余的枝剪去，由于这说明在该节点以前至少有一个节点的alpha值比它的上界要小，而父节点是min节点，因此这个节点明显不是min节点所想要的。或者说这个节点对对手有利。函数

2） 同理任何min节点的beta值小于其父节点的alpha值，则把该节点剩余的枝剪去。lua

下面引用一个wiki上的例子

spa

上图中第4层的4 beta = 4 比 其父节点的 alpha值5要小，因此将其剩余的枝剪去code

下面是算法的伪代码排序

alphaBeta(node,alpha,beta,depth,player)
	if (depth = 0)
		return valuation(player)调用估值函数
	else 
		if （player = maxplayer）
			foreach child of node
				value :=alphaBeta(child,depth-1,alpha,beta,minplayer)
				if(value>alpha)alpha:=value
				if(alpha>=beta)break
			return alpha
		else
			foreach child of node
				value :=alphaBeta(child,depth-1,alpha,beta,maxplayer)
				if(value<beta)beta:=value
				if(alpha>=beta)break
			return beta

negaAlphabeta(node,alpha,beta,depth)
	if (depth = 0)
		return valuation()调用估值函数
	else 
		foreach child of node
			value :=-negaAlphabeta(child,depth-1,-beta,-alpha)
			if(value>alpha)alpha:=value
			if(alpha>=beta)break
		return alpha