突然心血来潮，想做《人工智能-一种现代方法第三版》的笔记，那就做吧：
不知不觉已经研究到第五章，
ch5 Adversarial Searching，意味竞争搜索，广泛用于两人、多人博弈中。
先从简单的两人、完全信息、零和游戏开始：
零和：零和博弈表示所有博弈方的利益之和为零或一个常数，即一方有所得，其他方必有所失。双方不合作。
我们考虑的是一个online search的方法，相对于offline search——给定输入\输出每一步该怎么走；我们输入自己和对手的行为方式，输出“我”下一步该怎么走（对方是不是按照我预计的出牌？我也不知道，所以是一个online search）
我们有一个抽象的效用函数（utility funciton），在terminal node（leaf node?）返回效用值
我们引入一个max-min搜索树，max搜索对自己最有利的（选最大效用），min搜索对自己不利（模拟对手，选最小效用值），两者交替，depth first search。Max函数先走。
此算法突出一个我中有你，你中有我：
def Max-Value(state): # returns a maximal utility value
if Terminal-Test(state):
return Utility(state)
v = -infinity
for a in Actions(state):
v = max(v, Min-Value(Result(state,a)))
return v
def Min-Value(state): # returns a minimal utility value
if Terminal-Test(state):
return Utility(state)
v = +infinity
for a in Actions(state):
v = min(v, Max-Value(Result(state,a)))
return v
def MinMax-Decision(state): # returns an optimal action
return arg-max(Min-Value(Result(state,a)) for a in Actions(state)) #此句同样可以写成：v = Max-Value(state); return an action in Actions(state) with value v;
def Max-Value(state,alpha,beta): # returns a utility value
if Terminal-Test(state):
return Utility(state)
v = -infinity
for a in Actions(state):
v = max(v, Min-Value(Result(state,a)))
if v >= beta: return v # 此循环为Max-value函数内，那么父级就一个Min-value函数，如果下界比父级Min-value的上界还要大，是可定不会选这个分支的，直接返回即可
alpha = max(alpha, v)
return v
def Min-Value(state,appha,beta): # returns a utility value
if Terminal-Test(state):
return Utility(state)
v = +infinity
for a in Actions(state):
v = min(v, Max-Value(Result(state,a)))
if v<=alpha: return v # 此循环为Min-value函数内，那么父级就一个Max-value函数，如果上界比父级Max-value的下界还要小，是可定不会选这个分支的，直接返回即可
beta = min(v,beta)
return v
def Aplpha-Beta-search(state): # returns an optimal action
v = Max-Value(state,-infinity,+infinity)
return an action in Actions(state) with value v;
我们规定(alpha,beta)为一个节点能够选择的actions的untility value的区间。
max-value节点继承父级的上下界，并得出自己下界，因为max-value能够选择的必须要比下界大。
min-value节点继承父级的上下界，并得出自己的上界，因为min-value能够选择的必须要比上界小。
解释一下，max-value节点父级是一个min-value节点，min-value节点只能选比自己当前上界(beta)小的action，一个子级max-value节点的alpha比父级min-value节点的beta还要大的话，我们就自动忽略这个max-value节点(pruning)
反之亦然，min-value节点父级是一个max-value节点，max-value节点只能选比自己当前下界(alpha)大的action，一个子级min-value节点的beta比父级max-value节点的alpha还要小的话，我们就自动忽略这个min-value节点(pruning)
