python国际象棋⼩游戏代码_⽤Python编写⼀个国际象棋AI程
序
最近我⽤Python做了⼀个国际象棋程序并把代码发布在Github上了。这个代码不到1000⾏，⼤概20%⽤来实现AI。在这篇⽂章中我会介绍这个AI如何⼯作，每⼀个部分做什么，它为什么能那样⼯作起来。你可以直接通读本⽂，或者去下载代码，边读边看代码。虽然去看看其他⽂件中有什么AI依赖的类也可能有帮助，但是AI部分全都在AI.py⽂件中。
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.children = children
self.parent = parent
pointAdvantage = None
depth = 1
这个类有五个属性。⾸先是move，即它包含的棋步，它是个Move类，在这不是很重要，只需要知道它是⼀个告诉⼀个起⼦往哪⾛的棋步，可以吃什么⼦，等等。然后是children，它也是个MoveNode类。第三个属性是parent，所以通过它可以知道上⼀层有哪些MoveNode。pointAdvantage属性是AI⽤来决定这⼀棋步是好是坏⽤的。depth属性指明这⼀结点在第⼏层，也就是说该节点上⾯有多少节点。⽣成棋步树的代码如下：
def generateMoveTree(self) :
moveTree = []
for move in AllMovesLegal(self.side) :
moveTree.append(MoveNode(move, [], None))
for node in moveTree :
评估报告
self.board.ve)
self.populateNodeChildren(node)
self.board.undoLastMove()
return moveTree
变量moveTree⼀开始是个空list，随后它装⼊MoveNode类的实例。第⼀个循环后，它只是⼀个拥有没有⽗结点、⼦结点的MoveNode的数组，也就是⼀些根节点。第⼆个循环遍历moveTree，⽤populateNodeChildren函数给每个节点添加⼦节点：
def populateNodeChildren(self, node) :
node.pointAdvantage = PointAdvantageOfSide(self.side)
node.depth = Depth()
if node.depth == self.depth :
return
side = self.board.currentSide
legalMoves = AllMovesLegal(side)
莫小棋儿子if not legalMoves :
if self.board.isCheckmate() :
return
elif self.board.isStalemate() :
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语句检查是否有符合规则的棋步。如果⼀个都没有，要么被将死了，要么和棋了。
如果是被将死了，由于没有其他可以⾛的棋步，把ve.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 = OptimalPointAdvantageForNode(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 = OptimalPointAdvantageForNode(moveNode)
if not bestMoveNodes :
bestMoveNodes.append(moveNode)
elif moveNode > bestMoveNodes[0] :
bestMoveNodes = []
bestMoveNodes.append(moveNode)
elif moveNode == bestMoveNodes[0] :
bestMoveNodes.append(moveNode)
return [ve 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。