用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.move = move
  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 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, 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

(0)

相关推荐

  • 简单介绍Python中的round()方法

    round()方法返回 x 的小数点四舍五入到n个数字. 语法 以下是round()方法的语法: round( x [, n] ) 参数 x --这是一个数值表达式 n --这也是一个数值表达式 返回值 该方法返回 x 的小数点四舍五入到n个数字 例子 下面的例子显示了round()方法的使用 #!/usr/bin/python print "round(80.23456, 2) : ", round(80.23456, 2) print "round(100.000056,

  • Python中给List添加元素的4种方法分享

    List 是 Python 中常用的数据类型,它一个有序集合,即其中的元素始终保持着初始时的定义的顺序(除非你对它们进行排序或其他修改操作). 在Python中,向List添加元素,方法有如下4种方法(append(),extend(),insert(), +加号) 1. append() 追加单个元素到List的尾部,只接受一个参数,参数可以是任何数据类型,被追加的元素在List中保持着原结构类型. 此元素如果是一个list,那么这个list将作为一个整体进行追加,注意append()和ext

  • CentOS 6.x系统升级Python到2.7版本的Shell脚本分享

    在CentOS 6.x上,默认自带的Python是2.6.x版本,这个版本的Python有点老了,比如"collections.OrderedDict"就是2.7才有的,而且著名的Python Web框架Django的新版(如:1.7)就不支持Python2.6,最低要求是2.7了.而一些公司或者共有云上的服务器就是使用CentOS6.x,所以也就有了升级Python到2.7的需求. 升级Python之前,需要先安装一些工具和软件库,否则后面安装Python或pip时可能出错. Pyt

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

    最近我用Python做了一个国际象棋程序并把代码发布在Github上了.这个代码不到1000行,大概20%用来实现AI.在这篇文章中我会介绍这个AI如何工作,每一个部分做什么,它为什么能那样工作起来.你可以直接通读本文,或者去下载代码,边读边看代码.虽然去看看其他文件中有什么AI依赖的类也可能有帮助,但是AI部分全都在AI.py文件中. AI 部分总述 AI在做出决策前经过三个不同的步骤.首先,他找到所有规则允许的棋步(通常在开局时会有20-30种,随后会降低到几种).其次,它生成一个棋步树用来

  • 使用python编写简单的小程序编译成exe跑在win10上

    每天的工作其实很无聊,早知道应该去IT公司闯荡的.最近的工作内容是每逢一个整点,从早7点到晚11点,去查一次客流数据,整理到表格中,上交给素未蒙面的上线,由他呈交领导查阅. 人的精力毕竟是有限的,所以不一定在每个整点都可以及时去做这项工作.灵机一动,这种一丝不苟的活儿应该让计算器来做,由它来在每个整点来告诉我该去工作了. 说干就干,平时只用c#写过小程序,由于办公电脑上是公用的,所以没有想自己电脑一样装有visual studio,索性心一横,用python试试吧.总是听说那句大名鼎鼎的"人生苦

  • Python编写一个验证码图片数据标注GUI程序附源码

    做验证码图片的识别,不论是使用传统的ORC技术,还是使用统计机器学习或者是使用深度学习神经网络,都少不了从网络上采集大量相关的验证码图片做数据集样本来进行训练. 采集验证码图片,可以直接使用Python进行批量下载,下载完之后,就需要对下载下来的验证码图片进行标注.一般情况下,一个验证码图片的文件名就是图片中验证码的实际字符串. 在不借助工具的情况下,我们对验证码图片进行上述标注的流程是: 1.打开图片所在的文件夹: 2.选择一个图片: 3.鼠标右键重命名: 4.输入正确的字符串: 5.保存 州

  • 基于Python编写一个计算器程序,实现简单的加减乘除和取余二元运算

    方法一: 结合lambda表达式.函数调用运算符.标准库函数对象.C++11标准新增的标准库function类型,编写一个简单的计算器,可实现简单的加.减.乘.除.取余二元运算.代码如下: #include "pch.h" #include <iostream> #include <functional> #include <map> #include <string> using namespace std; int add(int i

  • 基于Python编写一个自动关机程序

    目录 1.实现效果 2.实现步骤 3.全部代码 1.实现效果 2.实现步骤 模块导入 import os,sys,time from PyQt5 import QtCore,QtWidgets,QtGui 窗口设置 def pageShow(self,page): #设置窗口的位置和大小 page.setGeometry(400,400,400,200) #设置窗口的标题 page.setWindowTitle('Window shutdown') #设置窗口的图标 #page.setWindo

  • 基于Python编写一个根据姓名测性别的小程序

    目录 导语 一.准备环节 1.1安装环境 二.准备素材 三.开始敲代码 3.1导入模块 3.2定义界面 3.3预测性别 3.4读取数据 3.5附完整的源码 四.效果展示 总结 导语 以前上英语课老师都会教哪些名字一听就知道是男生的,比如David.Tom.Jerry,然后Angela.Sophia一听就是女生的名字.当你以为所有名字一听就可以辨别男女的时候,你就想错了~就像中文里面“贾凡”,你以为是男生,其实是女生也说不定.这种难分性别的名字 其实很多呢~为了避免宝宝的性别和提前取好的名字冲突,

  • 基于Python编写一个B站全自动抽奖的小程序

    目录 导语 开发工具 环境搭建 原理简介 导语 应好友邀请,帮他写了个小程序,功能类似于实时监控自己关注的UP主,如果关注的UP主中有人发布了抽奖的动态,就自动参与这个抽奖.这样就能不错过任何一个可以暴富的机会了.写完之后感觉这个想法还是挺有意思的,于是上来分享一波. 废话不多说,让我们愉快地开始吧~ 开发工具 Python版本:3.7.8 相关模块: DecryptLogin模块: 以及一些python自带的模块. 环境搭建 安装Python并添加到环境变量,pip安装需要的相关模块即可. 原

  • 基于Python编写一个计算器程序,实现简单的加减乘除和取余二元运算

    方法一: 结合lambda表达式.函数调用运算符.标准库函数对象.C++11标准新增的标准库function类型,编写一个简单的计算器,可实现简单的加.减.乘.除.取余二元运算.代码如下: #include "pch.h" #include <iostream> #include <functional> #include <map> #include <string> using namespace std; int add(int i

  • 基于Python编写一个微博抽奖小程序

    目录 导语 开发工具 环境搭建 先睹为快 原理简介 导语 带大家写个微博自动抽奖小程序吧,motivation和之前的B站自动抽奖小程序一样: 不想内卷了,整个B站全自动抽奖的小程序吧,万一不小心暴富了呢~ 废话不多说,让我们愉快地开始吧~ 开发工具 Python版本:3.7.8 相关模块: DecryptLogin模块: DecryptLoginExamples模块: 以及一些python自带的模块. 环境搭建 安装Python并添加到环境变量,pip安装需要的相关模块即可. 先睹为快 首先,

  • 用Python写一个自动木马程序

    电脑作为大家日常办公的工具,最怕的一件事情之一就是被偷,当我们的电脑被盗的时候,不仅仅是电脑本身,更重要的是电脑存储的资料都会丢失.如何尽快的找回电脑需要我们想点办法,今天就教大家一个好的技巧,虽说不能百分之百的好用,但是也能够发挥一定的效果. 小编本次是基于Linux下的展示,之所以基于Linux,是因为需要电脑在启动的时候,需要自动启动程序,做到出其不意,原因我会在最后给出. 程序是这样的,程序执行会首先调用笔记本的摄像头,拍摄笔记本面前的照片,然后,会给我们的预设邮箱,发送邮件,提醒我们电

随机推荐