博弈树剪枝相关

课上对博弈树的$\alpha-\beta剪枝$算法没有完全理解，写个博客理一理……

（双方、确定、有限状态、离散状态、完全信息下的零和博弈，极大极小策略下的情况）

代码部分

​ 因为代码部分实现比较简单，先从伪代码部分开始说起，无剪枝博弈树的深度优先策略伪代码如下:

• 函数succsor代表该状态可能的后继状态
• 函数value代表该状态的收益值
• 函数isTerminal判断是否是叶节点

gameTree(state,player):
	if isTerminal(state):
		return value(state)
	if player is MAX:
		return max(gameTree(next,MIN) for next in succsor(state))
	else:
		return min(gameTree(next,MAX) for next in succsor(state))

​ 下意识就写成了类似python的格式

​ 比较简单的算法（当然以为是伪代码所以并不是完整的实现），目的就是对MAX玩家而言，找到子节点中值最大的，对MIN玩家而言，找到子节点中最小的，不断迭代就好

​ 由于计算量比较大，所以引入了$\alpha-\beta剪枝$，用于剪掉一部分不必要的搜索，添加剪枝后的伪代码如下：

gameTree(state,player,alpha,beta):
	if isTerminal(state):
		return value(state)
	if player is MAX:
		for next in succsor(state)
			alpha = max(alpha, gameTree(next,MIN,alpha,beta))
			if alpha > beta:
				break
		return alpha
	else:
		for next in succsor(state)
			beta = min(alpha, gameTree(next,MIN,alpha,beta))
			if alpha < beta:
				break
		return alpha

​ 可以看到和之前相比就是MAX(MIN)中途如果检测到比父节点传来的beta(alpha)更大(小)的alpha(beta)就将后续的搜索全部剪掉。

​ 嗯，就是实现来说还是比较容易理解的，但是为什么能这样剪？

对alpha-beta剪枝的理解

临近分支情况

​ 由于alpha值只会在遍历到比他大的值时才会更新，所以只要能提前得知某个子节点的分支全部搜索完的alpha值必然小于或等于自己的alpha时，那么就可以直接省略掉该节点剩下的搜索了

​ 考虑到beta值只会在遍历到比他小的值时才会更新，只要我们发现MIN节点的当前的beta值小于或等于其父节点的alpha值时，我们就可以保证无论是否继续搜索下去，该MIN节点的beta值都会小于等于其父节点的alpha，故剩余的搜索就可以省略了，因为父节点必然不会采纳这个点来更新alpha

跨节点情况

​ 我们搜索子节点的目的就是需要更改祖先节点alpha或者beta值，所以我们需要剪枝的是那些没有办法更改的祖先节点。

​ 假设一个节点可以更改其祖先节点的值，那么它将会一层层向上传递，所以它至少需要满足的条件是：大于最大值祖先节点，或者值小于最小值祖先节点。

​ 剩下的推理就和临近分支类似了。