AI 部分总述
AI 在做出决策前经过三个不同的步骤首先, 他找到所有规则允许的棋步 (通常在开局时会有 20-30 种, 随后会降低到几种) 其次, 它生成一个棋步树用来随后决定最佳决策虽然树的大小随深度指数增长, 但是树的深度可以是任意的假设每次决策有平均 20 个可选的棋步, 那深度为 1 对应 20 棋步, 深度为 2 对应 400 棋步, 深度为 3 对应 8000 棋步最后, 它遍历这个树, 采取 x 步后结果最佳的那个棋步, x 是我们选择的树的深度后面的文章为了简单起见, 我会假设树深为 2
生成棋步树
棋步树是这个 AI 的核心构成这个树的类是 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, 所以通过它可以知道上一层有哪些 MoveNodepointAdvantage 属性是 AI 用来决定这一棋步是好是坏用的 depth 属性指明这一结点在第几层, 也就是说该节点上面有多少节点生成棋步树的代码如下:
- 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 类的实例第一个循环后, 它只是一个拥有没有父结点子结点的 MoveNode 的数组, 也就是一些根节点第二个循环遍历 moveTree, 用 populateNodeChildren 函数给每个节点添加子节点:
- 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()
这个函数是递归的, 并且它有点难用图像表达出来一开始给它传递了个 MoveNode 对象这个 MoveNode 对象会有为 1 的深度, 因为它没有父节点我们还是假设这个 AI 被设定为深度为 2 因此率先传给这个函数的结点会跳过第一个 if 语句
然后, 决定出所有规则允许的棋步不过这在这篇文章讨论的范围之外, 如果你想看的话代码都在 Github 上下一个 if 语句检查是否有符合规则的棋步如果一个都没有, 要么被将死了, 要么和棋了如果是被将死了, 由于没有其他可以走的棋步, 把 node.move.checkmate 属性设为 True 并 return 和棋也是相似的, 不过由于哪一方都没有优势, 我们把 node.pointAdvantage 设为 0
如果不是将死或者和棋, 那么 legalMoves 变量中的所有棋步都被加入当前结点的子节点中作为 MoveNode, 然后函数被调用来给这些子节点添加他们自己的 MoveNode
当结点的深度等于 self.depth(这个例子中是 2)时, 什么也不做, 当前节点的子节点保留为空数组
遍历树
假设 / 我们有了一个 MoveNode 的树, 我们需要遍历他, 找到最佳棋步这个逻辑有些微妙, 需要花一点时间想明白它 (在明白这是个很好的算法之前, 我应该更多地去用 Google) 所以我会尽可能充分解释它比方说这是我们的棋步树:
如果这个 AI 很笨, 只有深度 1, 他会选择拿象吃车, 导致它得到 5 分并且总优势为 + 7 然后下一步兵会吃掉它的后, 现在优势从 + 7 变为 - 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, its a move for the AIs 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 是如何工作的
注意: 部门内容参考于互联网
来源: http://www.bubuko.com/infodetail-2524568.html