最近我用Python做了一個國際象棋程序并把代碼發(fā)布在Github上了。這個代碼不到1000行，大概20%用來實(shí)現(xiàn)AI。在這篇文章中我會介紹這個AI如何工作，每一個部分做什么，它為什么能那樣工作起來。你可以直接通讀本文，或者去下載代碼，邊讀邊看代碼。雖然去看看其他文件中有什么AI依賴的類也可能有幫助，但是AI部分全都在AI.py文件中。

AI 部分總述

AI在做出決策前經(jīng)過三個不同的步驟。首先，他找到所有規(guī)則允許的棋步（通常在開局時會有20-30種，隨后會降低到幾種）。其次，它生成一個棋步樹用來隨后決定最佳決策。雖然樹的大小隨深度指數(shù)增長，但是樹的深度可以是任意的。假設(shè)每次決策有平均20個可選的棋步，那深度為1對應(yīng)20棋步，深度為2對應(yīng)400棋步，深度為3對應(yīng)8000棋步。最后，它遍歷這個樹，采取x步后結(jié)果最佳的那個棋步，x是我們選擇的樹的深度。后面的文章為了簡單起見，我會假設(shè)樹深為2。

生成棋步樹

棋步樹是這個AI的核心。構(gòu)成這個樹的類是MoveNode.py文件中的MoveNode。他的初始化方法如下：

def __init__(self, move, children, parent) :
  self.move = move
  self.children = children
  self.parent = parent
  pointAdvantage = None
  depth = 1

這個類有五個屬性。首先是move，即它包含的棋步，它是個Move類，在這不是很重要，只需要知道它是一個告訴一個起子往哪走的棋步，可以吃什么子，等等。然后是children，它也是個MoveNode類。第三個屬性是parent，所以通過它可以知道上一層有哪些MoveNode。pointAdvantage屬性是AI用來決定這一棋步是好是壞用的。depth屬性指明這一結(jié)點(diǎn)在第幾層，也就是說該節(jié)點(diǎn)上面有多少節(jié)點(diǎn)。生成棋步樹的代碼如下：

def generateMoveTree(self) :
  moveTree = []
  for move in self.board.getAllMovesLegal(self.side) :
    moveTree.append(MoveNode(move, [], None))
 
  for node in moveTree :
    self.board.makeMove(node.move)
    self.populateNodeChildren(node)
    self.board.undoLastMove()
  return moveTree

變量moveTree一開始是個空list，隨后它裝入MoveNode類的實(shí)例。第一個循環(huán)后，它只是一個擁有沒有父結(jié)點(diǎn)、子結(jié)點(diǎn)的MoveNode的數(shù)組，也就是一些根節(jié)點(diǎn)。第二個循環(huán)遍歷moveTree，用populateNodeChildren函數(shù)給每個節(jié)點(diǎn)添加子節(jié)點(diǎn)：

def populateNodeChildren(self, node) :
  node.pointAdvantage = self.board.getPointAdvantageOfSide(self.side)
  node.depth = node.getDepth()
  if node.depth == self.depth :
    return
 
  side = self.board.currentSide
 
  legalMoves = self.board.getAllMovesLegal(side)
  if not legalMoves :
    if self.board.isCheckmate() :
      node.move.checkmate = True
      return
    elif self.board.isStalemate() :
      node.move.stalemate = True
      node.pointAdvantage = 0
      return
 
  for move in legalMoves :
    node.children.append(MoveNode(move, [], node))
    self.board.makeMove(move)
    self.populateNodeChildren(node.children[-1])
    self.board.undoLastMove()

這個函數(shù)是遞歸的，并且它有點(diǎn)難用圖像表達(dá)出來。一開始給它傳遞了個MoveNode對象。這個MoveNode對象會有為1的深度，因?yàn)樗鼪]有父節(jié)點(diǎn)。我們還是假設(shè)這個AI被設(shè)定為深度為2。因此率先傳給這個函數(shù)的結(jié)點(diǎn)會跳過第一個if語句。

然后，決定出所有規(guī)則允許的棋步。不過這在這篇文章討論的范圍之外，如果你想看的話代碼都在Github上。下一個if語句檢查是否有符合規(guī)則的棋步。如果一個都沒有，要么被將死了，要么和棋了。如果是被將死了，由于沒有其他可以走的棋步，把node.move.checkmate屬性設(shè)為True并return。和棋也是相似的，不過由于哪一方都沒有優(yōu)勢，我們把node.pointAdvantage設(shè)為0。

如果不是將死或者和棋，那么legalMoves變量中的所有棋步都被加入當(dāng)前結(jié)點(diǎn)的子節(jié)點(diǎn)中作為MoveNode，然后函數(shù)被調(diào)用來給這些子節(jié)點(diǎn)添加他們自己的MoveNode。

當(dāng)結(jié)點(diǎn)的深度等于self.depth（這個例子中是2）時，什么也不做，當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)保留為空數(shù)組。

遍歷樹

假設(shè)/我們有了一個MoveNode的樹，我們需要遍歷他，找到最佳棋步。這個邏輯有些微妙，需要花一點(diǎn)時間想明白它(在明白這是個很好的算法之前，我應(yīng)該更多地去用Google)。所以我會盡可能充分解釋它。比方說這是我們的棋步樹：

如果這個AI很笨，只有深度1，他會選擇拿“象”吃“車”，導(dǎo)致它得到5分并且總優(yōu)勢為+7。然后下一步“兵”會吃掉它的“后”，現(xiàn)在優(yōu)勢從+7變?yōu)?2，因?yàn)樗鼪]有提前想到下一步。

在假設(shè)它的深度為2。將會看到它用“后”吃“馬”導(dǎo)致分?jǐn)?shù)-4，移動“后”導(dǎo)致分?jǐn)?shù)+1，“象”吃“車”導(dǎo)致分?jǐn)?shù)-2。因此，他選擇移動后。這是設(shè)計(jì)AI時的通用技巧，你可以在這找到更多資料（極小化極大算法）。

所以我們輪到AI時讓它選擇最佳棋步，并且假設(shè)AI的對手會選擇對AI來說最不利的棋步。下面展示這一點(diǎn)是如何實(shí)現(xiàn)的：

def getOptimalPointAdvantageForNode(self, node) :
  if node.children:
    for child in node.children :
      child.pointAdvantage = self.getOptimalPointAdvantageForNode(child)
 
    #If the depth is divisible by 2, it's a move for the AI's side, so return max
    if node.children[0].depth % 2 == 1 :
      return(max(node.children).pointAdvantage)
    else :
      return(min(node.children).pointAdvantage)
  else :
    return node.pointAdvantage

這也是個遞歸函數(shù)，所以一眼很難看出它在干什么。有兩種情況：當(dāng)前結(jié)點(diǎn)有子節(jié)點(diǎn)或者沒有子節(jié)點(diǎn)。假設(shè)棋步樹正好是前面圖中的樣子（實(shí)際中每個樹枝上會有更多結(jié)點(diǎn)）。

第一種情況中，當(dāng)前節(jié)點(diǎn)有子節(jié)點(diǎn)。拿第一步舉例，Q吃掉N。它子節(jié)點(diǎn)的深度為2，所以2除2取余不是1。這意味著子節(jié)點(diǎn)包含對手的一步棋，所以返回最小步數(shù)（假設(shè)對手會走出對AI最不利的棋步）。

該節(jié)點(diǎn)的子節(jié)點(diǎn)不會有他們自己的節(jié)點(diǎn)，因?yàn)槲覀兗僭O(shè)深度為2。因此，他們但會他們真實(shí)的分值（-4和+5）。他們中最小的是-4，所以第一步，Q吃N，被給為分值-4。

其他兩步也重復(fù)這個步驟，移動“后”的分?jǐn)?shù)給為+1，“象”吃“車”的分?jǐn)?shù)給為-2。

選擇最佳棋步

最難的部分已經(jīng)完成了，現(xiàn)在這個AI要做的事就是從最高分值的棋步中做選擇。

def bestMovesWithMoveTree(self, moveTree) :
  bestMoveNodes = []
  for moveNode in moveTree :
    moveNode.pointAdvantage = self.getOptimalPointAdvantageForNode(moveNode)
    if not bestMoveNodes :
      bestMoveNodes.append(moveNode)
    elif moveNode > bestMoveNodes[0] :
      bestMoveNodes = []
      bestMoveNodes.append(moveNode)
    elif moveNode == bestMoveNodes[0] :
      bestMoveNodes.append(moveNode)
 
  return [node.move for node in bestMoveNodes]

此時有三種情況。如果變量bestMoveNodes為空，那么moveNode的值是多少，都添加到這個list中。如果moveNode的值高于bestMoveNodes的第一個元素，清空這個list然后添加該moveNode。如果moveNode的值是一樣的，那么添加到list中。

最后一步是從最佳棋步中隨機(jī)選擇一個(AI能被預(yù)測是很糟糕的)

bestMoves = self.bestMovesWithMoveTree(moveTree)
randomBestMove = random.choice(bestMoves)

這就是所有的內(nèi)容。AI生成一個樹，用子節(jié)點(diǎn)填充到任意深度，遍歷這個樹找到每個棋步的分值，然后隨機(jī)選擇最好的。這有各種可以優(yōu)化的地方，剪枝，剃刀，靜止搜索等等，但是希望這篇文章很好地解釋了基礎(chǔ)的暴力算法的象棋AI是如何工作的。

本文由 伯樂在線 - 許世豪 翻譯自 mbuffett。