用Python编写一个国际象棋AI程序(2)

在假设它的深度为2。将会看到它用“后”吃“马”导致分数-4，移动“后”导致分数+1，“象”吃“车”导致分数-2。因此，他选择移动后。这是设计AI时的通用技巧，你可以在这找到更多资料（极小化极大算法）。

所以我们轮到AI时让它选择最佳棋步，并且假设AI的对手会选择对AI来说最不利的棋步。下面展示这一点是如何实现的：

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

这也是个递归函数，所以一眼很难看出它在干什么。有两种情况：当前结点有子节点或者没有子节点。假设棋步树正好是前面图中的样子（实际中每个树枝上会有更多结点）。

第一种情况中，当前节点有子节点。拿第一步举例，Q吃掉N。它子节点的深度为2，所以2除2取余不是1。这意味着子节点包含对手的一步棋，所以返回最小步数（假设对手会走出对AI最不利的棋步）。

该节点的子节点不会有他们自己的节点，因为我们假设深度为2。因此，他们但会他们真实的分值（-4和+5）。他们中最小的是-4，所以第一步，Q吃N，被给为分值-4。

其他两步也重复这个步骤，移动“后”的分数给为+1，“象”吃“车”的分数给为-2。

选择最佳棋步

最难的部分已经完成了，现在这个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中。

最后一步是从最佳棋步中随机选择一个(AI能被预测是很糟糕的)

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

这就是所有的内容。AI生成一个树，用子节点填充到任意深度，遍历这个树找到每个棋步的分值，然后随机选择最好的。这有各种可以优化的地方，剪枝，剃刀，静止搜索等等，但是希望这篇文章很好地解释了基础的暴力算法的象棋AI是如何工作的。

本文由 伯乐在线 - 许世豪 翻译自 mbuffett。