極大極小樹的剪枝算法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