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

php中文网
发布: 2016-06-10 15:18:38
原创
2486人浏览过

最近我用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。他的初始化方法如下:

1

2

3

4

5

6

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属性指明这一结点在第几层,也就是说该节点上面有多少节点。生成棋步树的代码如下:

1

2

3

4

5

6

7

8

9

10

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函数给每个节点添加子节点:

立即学习Python免费学习笔记(深入)”;

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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来说最不利的棋步。下面展示这一点是如何实现的:

1

2

3

4

5

6

7

8

9

10

11

12

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要做的事就是从最高分值的棋步中做选择。

1

2

3

4

5

6

7

8

9

10

11

12

13

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能被预测是很糟糕的)

1

2

bestMoves = self.bestMovesWithMoveTree(moveTree)

randomBestMove = random.choice(bestMoves)

登录后复制

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

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

最佳 Windows 性能的顶级免费优化软件
最佳 Windows 性能的顶级免费优化软件

每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。

下载
相关标签:
ai
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号