突然心血來潮，想做《人工智能-一種現(xiàn)代方法第三版》的筆記，那就做吧：

不知不覺已經(jīng)研究到第五章，

ch5 Adversarial Searching，意味競爭搜索，廣泛用于兩人、多人博弈中。

先從簡單的兩人、完全信息、零和游戲開始：

零和：零和博弈表示所有博弈方的利益之和為零或一個常數(shù)，即一方有所得，其他方必有所失。雙方不合作。

我們考慮的是一個online search的方法，相對于offline search——給定輸入\輸出每一步該怎么走；我們輸入自己和對手的行為方式，輸出“我”下一步該怎么走（對方是不是按照我預計的出牌？我也不知道，所以是一個online search）

我們有一個抽象的效用函數(shù)（utility funciton），在terminal node（leaf node?）返回效用值

我們引入一個max-min搜索樹，max搜索對自己最有利的（選最大效用），min搜索對自己不利（模擬對手，選最小效用值），兩者交替，depth first search。Max函數(shù)先走。

此算法突出一個我中有你，你中有我：

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 # 此循環(huán)為Max-value函數(shù)內(nèi)，那么父級就一個Min-value函數(shù)，如果下界比父級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 # 此循環(huán)為Min-value函數(shù)內(nèi)，那么父級就一個Max-value函數(shù)，如果上界比父級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;

我們規(guī)定(alpha,beta)為一個節(jié)點能夠選擇的actions的untility value的區(qū)間。
max-value節(jié)點繼承父級的上下界，并得出自己下界，因為max-value能夠選擇的必須要比下界大。
min-value節(jié)點繼承父級的上下界，并得出自己的上界，因為min-value能夠選擇的必須要比上界小。

解釋一下，max-value節(jié)點父級是一個min-value節(jié)點，min-value節(jié)點只能選比自己當前上界(beta)小的action，一個子級max-value節(jié)點的alpha比父級min-value節(jié)點的beta還要大的話，我們就自動忽略這個max-value節(jié)點(pruning)

反之亦然，min-value節(jié)點父級是一個max-value節(jié)點，max-value節(jié)點只能選比自己當前下界(alpha)大的action，一個子級min-value節(jié)點的beta比父級max-value節(jié)點的alpha還要小的話，我們就自動忽略這個min-value節(jié)點(pruning)