$\alpha-\beta$剪枝算法minimax算法是一种在两人游戏中寻找最佳着法的方法。Alpha-beta剪枝是一种寻找最优极小极大解的方法，同时避免搜索不会被选中的移动子树。在双人博弈的搜索树中，有两种节点，一种是代表你的走法的节点，一种是代表你对手的走法的节点。代表你走法的节点一般画成正方形（也可能是向上的三角形）：博弈零和博弈的基本概念是完全信息、确定性、回合（round），两个参与者的博弈都有完全信息，双方都可以查询游戏的完整历史完整信息示例不完整信息示例国际象棋、围棋、双陆棋、红色警戒、文明6零，游戏结束时双方效用值代数和为0。效用valueutival是一个变量，用来表示对局结束时的结果，比如围棋中的黑棋。utival=1，白方utival=-1，表示黑方获胜。在博弈树上，如果根节点是MAX节点，那么叶子节点上的值就是MAX方的效用值。Minimax算法最大值搜索针对当前情况（父节点），计算所有可能放置点的情况得分，选择得分最高的（最大子节点）作为放置点。Minimax搜索假设我方为MAX方，对方为MIN方，utival为效用值。假设双方都同样明智。MAX方的目标是最大化效用值utival，MIN方的目标是最小化utival，双方轮流进行。现在我们从下往上考虑。考虑顶点为MAX，深度为n，每一层从上到下MAX1,MIN2,MAX3,MIN4,...,MIN_n顺序的博弈树。这棵树的MIN_n层下的所有最终叶节点。考虑MIN_n层的节点Ni，Ni的子节点都是最终（叶）节点。这是MIN方的最后一步，所以它肯定会选择效用值最小的叶子节点进行移动，所以在零和博弈的情况下，节点Ni的下一步是确定的。也就是说，MIN_n层所有节点的下一步都是可确定的。我们把节点Ni的最小值和最大值minimax保存在Ni上。同样，对于MAX_(n-1)层的节点Mi，下一步也是可确定的。Yes取其所有子节点的最大值，即Mi的minimax值，保存在Mi上。以此类推，直到计算出根节点MAX1的极小极大值。minimax算法使用简单的递归算法来计算每个后续节点的最大值和最小值。该算法从上到下推进到树的叶子节点，然后逐层返回最小值和最大值。在返回最小值和最大值的过程中，记录移动的位置，即记录子节点的索引。最后，我们得到根节点的放置策略。Python实现类Tree:def__init__(self,val,children=None,maxormin='max'):self.val=valself.childs=children#listself.maxormin=maxormindefis_leaf(self):#是否当前node是叶子节点returnself.childsisNonedefMax(self):#返回子节点的最大值returnmax([child.valforchildinself.childs])defargmax(self):#返回索引子节点的最大值return[child.valforchildinself.childs].index(self.Max())defMin(self):#返回子节点的最大值returnmin([child.valforchildinself.childs])defargmin(self):#返回子节点最大位置的索引return[child.valforchildinself.childs].index(self.Min())defminimax(self):inf=999999999choices=dict()#记录每一步的选择，choises[tree]=indexarg=-1#存储最大值或最小值的索引defmax_value(tree=self):iftree.is_leaf():returntree.valnonlocalargv=-inffori,childinenumerate(tree.childs):minval=min_value(child)如果minval>v:v=max(v,minval)arg=ichoices[tree]=arg#print(v,choices)返回vdefmin_value(tree=self):iftree.is_leaf():returntree.valnonlocalargv=inffori,childinenumerate(tree.childs):maxval=max_value(child)如果maxval
