只需五步!手把手教你搭建国际象棋AI机器人

王新民 编译 量子位 报道 | 公众号 QbitAI

在编程之前,我们先了解一些基本的概念,来帮助我们创建一个简单的象棋AI机器人:移动生成、棋局评估、最大最小搜索和α-β剪枝搜索过程这四个概念。

在每个步骤中,我们将会在已有的程序上加入上述经典的象棋编程优化技术,来进行改进我们的象棋机器人。同时我会向大家演示各种优化参数是怎么影响算法的下棋风格和计算速度的。

作者Lauri Hartikka提到:“我已经无法战胜我创造出来的象棋机器人。我觉得导致这个结果的原因不是因为我下棋技术太烂,就是算法已经足够优秀。”

步骤1:移动生成和棋局可视化

我们将使用chess.js库实现移动生成功能,并使用chessboard.js来可视化棋局。chess.js库基本上实现了象棋的所有规则。基于这个应用库,我们可以在给定某个棋局状态下计算出所有合法操作。

图1:对移动生成功能进行可视化:起始位置作为输入,输出是该棋局的所有可能移动.

使用这些库将有助于我们专注于最核心的任务:创建找到最佳走法的算法。接下来先创建一个函数,该函数能从棋局中所有可能的移动中返回一个随机移动的结果。

虽然加入这个函数的机器人还不是一个高超的象棋玩家,但这是一个很好的开始,因为我们已经可以与其进行对战。

图2:黑色方块代表下一步所有的合法移动

步骤2:位置评估

现在我们来试试看一下在确定位置上双方的哪个棋子具有更高的评估强度。实现这一点的最简单的方法是使用下表来计算棋局中的相对强度。

通过这个评估表,我们可以创建一个算法,能够让棋子选择具有最高评估分数的移动方向。

目前已经有了不错的进展,因为我们的算法现在已经可以尽可能吃掉对方的棋子。

图3:借助简单的评估功能,双方进行游戏

步骤3:使用Minimax搜索树

接下来,我们要利用Minimax(极大极小)搜索树算法,它可以从多种选择中确定最佳方法。

在该算法中,能将递归树的所有可能移动探索到给定深度,并且在递归树的子节点处评估该位置的好坏。

之后,我们将子节点的最小值或最大值返回给父节点,父节点通过下步将移动白棋还是黑棋来选择合适值。也就是说,我们试图尽可能地减少或最大限度地提高每一级的评估值。

图4:在人为选择位置时,可视化极大极小算法。白棋的最佳走法是b2-c3,此时能够达到评估为-50的位置

通过加入极大极小算法,我们的算法了解象棋的基本策略。

评估极大极小算法的有效性,在很大程度上取决于计算性能可以实现的搜索深度。我们接下来的工作是通过优化算法来加大搜索深度。

步骤4:α-β剪枝搜索

α-β剪枝搜索是极小极大算法的一种优化方法,允许我们忽略搜索树中的一些分支,这有助于我们在使用相同的计算资源时更深入地评估极大极小搜索树。

α-β剪枝搜索的原理是是如果我们找到比已经发现的动作更糟糕的情况,那我们可以停止评估搜索树那一部分的情况。

α-β剪枝搜索不会影响极大极小算法的结果,而是大大加速其计算过程。

如果我们碰巧刚开始就得到了产生最优操作的路径,那么α-β剪枝算法也更有效。

图6:我们不需要关注使用α-β剪枝搜索所删去的分支,以及是否按照规定顺序访问搜索树

使用α-β剪枝搜索,我们可以显着提升极大极小算法的计算速度,如下例所示:

图7:如果我们要执行深度为4的Minmax算法,使用α-β剪枝的优化算法和正常算法所需要评估的位置数

步骤5:改进评估功能

初始的评估功能非常简单,因为我们只能计算在棋局上发现的信息。为了改善这一点,我们将棋子的位置也作为评估的一个因素。在实际情况中,棋盘中心的棋子比棋盘边缘的棋子更好,因为它有更多的选择,显得更加活跃。

我们将使用在维基象棋编程中提出的一种棋子价值表。

图8:对棋子价值表进行可视化,我们可以根据棋子的位置减少或增加评估值。

通过如上改进,我们已经获得了象棋机器人,至少已经能够与业余玩家进行对战了。

图9:加上评估方法和α-β剪枝优化的极大极小算法表现,设置搜索深度为3。

结论

对于一个简单的象棋机器人,它的优点是不会产生愚蠢的错误操作。但是它仍然缺乏对象棋的战略性理解。

通过上面介绍的方法,我们能够创建一个象棋机器人,可以和你一起玩象棋。最终的实现代码只有200行,这意味着这个算法的基本概念实现起来非常简单,你可以在GitHub上查看象棋机器人的最终版本。

我们还可以对这个算法进行深入的改进,例如移动排序、更快的移动生成和对残局的具体评估等。如果您想了解更多关于象棋机器人的信息,请查看维基上象棋项目程序,去探索更多关于搜索算法的优化程序。

原文发布于微信公众号 - 量子位(QbitAI)

原文发表时间:2017-04-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏量子位

哈佛用NBA比赛数据生成报道,评测各模型效果 | 数据集+论文+代码

安妮 编译整理 量子位出品 | 公众号 QbitAI 近日,哈佛大学的三名研究人员公开发表论文《Challenges of Data-to-Document G...

42480
来自专栏大数据文摘

科技网红Siraj最新油管视频:如何用4分钟搭建神经网络

20880
来自专栏张善友的专栏

一个开源的,跨平台的.NET机器学习框架ML.NET

18460
来自专栏人工智能头条

浅析强化学习及使用Policy Network实现自动化控制

19720
来自专栏机器之心

资源 | Picasso:开源的CNN可视化工具

选自Medium 机器之心编译 参与:侯韵楚、李泽南 神经网络在图像处理中应用广泛,但经常面临难以调整参数的问题。最近,来自 Merantix 的 Ryan H...

45480
来自专栏机器学习算法与Python学习

由你定义吃鸡风格!CycleGAN,你的自定义风格转换大师

如果你是一名玩家,你一定听说过现在两场疯狂流行的大战「大逃杀」,堡垒之夜和绝地求生。他们是两个非常相似的游戏,其中有 100 个玩家在一个小岛上出没,直到剩下一...

7800
来自专栏玉树芝兰

如何用Python和深度神经网络发现即将流失的客户?

想不想了解如何用Python快速搭建深度神经网络,完成数据分类任务?本文一步步为你展示这一过程,让你初步领略深度学习模型的强大和易用。

27130
来自专栏ATYUN订阅号

谷歌开源基于TensorFlow的通用框架AdaNet,快速且易于使用

Ensemble learning结合不同机器学习模型预测,被广泛用于神经网络以实现最先进的性能,得益于丰富的历史和理论保证,成功的挑战,如Netflix奖和各...

8220
来自专栏机器之心

学界 | Fashion-MNIST:替代MNIST手写数字集的图像数据集

机器之心转载 公众号:PaperWeekly 作者:肖涵 FashionMNIST 是一个替代 MNIST 手写数字集 [1] 的图像数据集。 它是由 Zala...

46590
来自专栏CDA数据分析师

猫奴的自我修养,教你如何用机器学习识别猫的品种

之前我进行过一个简单的机器学习实验,来判断图像是否为墨西哥卷饼。 使用相同的基于云的认知机器学习技术 Custom Vision,我想处理一个更复杂的场景。 如...

40180

扫码关注云+社区

领取腾讯云代金券