AlphaBata剪枝算法
人工智能试图理解和建立智能实体，智能实体之间存在着一种对立关系，从而有了对抗搜索问题，通常被称之为博弈。
人工智能中的博弈通常指博弈论专家们称为拥有完整信息的，确定性的，轮流行动的，两个游戏者的零和游戏
本次我们基于MinMax算法，使用AlphaBata剪枝技巧来实现人工智能的博弈算法
alpha-beta 剪枝原理
极小极大值算法必须检查博弈树的全部结点，也就是游戏的全部状态，显然，搜索时间是指数级增长的。虽然我们无法消除指数级的运算规模，但是可以通过一些剪枝策略有效地将其减半，换言之，可能不需要遍历博弈树中每一个结点就可以计算出正确的极小极大值，αβ剪枝 Alpha-Beta 就是其中的一种。
αβ剪枝会减掉那些不可能影响决策的分支，最后返回和极小极大值算法同样的结果。上图的博弈树用αβ剪枝过程表达如下，每个结点上面标出了可能的取值范围，B下面的第一个叶子结点为3，剩余两个结点分别为12和8，因此B的取值范围更新为[3,3]，现在由此可以推断根结点A的取值范围为[3,+∞)。然后结点C下面的第一个叶子结点为2，因此C这个 MIN 结点的值最多为2，而又已知根结点A的最低取值为3，所以结点C的余下后继结点无需再考虑，这就是αβ剪枝的一个具体实例。余下的博弈树按照之前的思想逐步更新结点的取值范围，减掉不可能影响根结点取值的分支。
极小极大搜索时深度优先的，所以在任何时候都只需考虑树中某一路径上的结点，αβ剪枝的名称取自描述这条路径上的回传值的两个的参数：
α：到目前为止路径上发现的 MAX 的最佳选择（即极大值）
β：到目前为止路径上发现的 MIN 的最佳选择（即极小值）
αβ剪枝策略在搜索中不断更新α和β的值，并且当某个结点的值分别比目前的 MAX 的α或者 MIN 的β值更差的时候，减掉此结点剩下的分支（即终止递归搜索），完整算法的伪代码如下图所示：
# -*- coding:utf-8 -*-
import copy # 注意对象的深拷贝和浅拷贝的使用！！！
from ast import literal_eval
class GameNode:
'''博弈树结点数据结构
成员变量：
name - string 结点名字
val - int 结点值
children - list[GameNode] 子结点列表
'''
def __init__(self, name='', val=0):
self.name = name # char
self.val = val # int
self.children = [] # list of nodes
class GameTree:
'''博弈树结点数据结构
成员变量：
root - GameNode 博弈树根结点
成员函数：
buildTree - 创建博弈树
'''
def __init__(self):
self.root = None # GameNode 博弈树根结点
def buildTree(self, data_list, root):
'''递归法创建博弈树
参数：
data_list - list[] like this ['A', ['B', ('E', 3), ('F', 12)], ['C', ('H', 2)], ['D', ('K', 14)]]
root - GameNode
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
for i in range(1,len(data_list)):
if type(data_list[i]) == list:
root.children.append(GameNode(data_list[i][0]))
self.buildTree(data_list[i],root.children[i-1])
else:
root.children.append(GameNode(data_list[i][0],data_list[i][1]))
#********** End **********#
class AlphaBeta:
'''博弈树结点数据结构
成员变量：
game_tree - GameTree 博弈树
成员函数：
minmax_with_alphabeta - 带AlphaBeta剪枝的极大极小值算法，计算最优行动
max_value - 计算最大值
min_value - 计算最小值
get_value - 返回结点的值
isTerminal - 判断某结点是否为最终结点
'''
def __init__(self, game_tree):
self.game_tree = game_tree # GameTree 博弈树
def minmax_with_alphabeta(self, node):
'''带AlphaBeta剪枝的极大极小值算法，计算最优行动
参数：
node - GameNode 博弈树结点
返回值：
clf - GameNode 最优行动的结点
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
clf = self.max_value(node,-10000,10000)
for child in node.children:
if child.val == clf:
return child;
#********** End **********#
def max_value(self, node, alpha, beta):
'''计算最大值
参数：
node - GameNode 博弈树结点
alpha - int 剪枝区间下限值
beta - int 剪枝区间上限值
返回值：
clf - int 子结点中的最大的评估值
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
if self.isTerminal(node):
return self.get_value(node)
clf = -10000
for child in node.children:
clf = max(clf,self.min_value(child,alpha,beta))
if clf >= beta:
return clf
alpha = max(alpha,clf)
node.val = clf;
return clf
#********** End **********#
def min_value(self, node, alpha, beta):
'''计算最小值
参数：
node - GameNode 博弈树结点
alpha - int 剪枝区间下限值
beta - int 剪枝区间上限值
返回值：
clf - int 子结点中的最小的评估值
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
if self.isTerminal(node):
return self.get_value(node)
clf = 10000
for child in node.children:
clf = min(clf,self.max_value(child,alpha,beta))
if clf <= alpha:
return clf
beta = min(clf,beta)
node.val = clf;
return clf;
#********** End **********#
def get_value(self, node):
'''返回结点的值
参数：
node - GameNode 博弈树结点
返回值：
clf - int 结点的值，即 node.val
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
return node.val;
#********** End **********#
def isTerminal(self, node):
'''判断某结点是否为最终结点（无子结点）
参数：
node - GameNode 博弈树结点
返回值：
clf - bool 是最终状态，返回True，否则返回False
'''
#请在这里补充代码，完成本关任务
#********** Begin **********#
if node.val == 0:
return False
else:
return True
#********** End **********#