技能 | 只要五步,教你撸一个缩减版国际象棋AI

从国际象棋到中国围棋,人类与“机器”已经较上了劲。

看过那么多场对战,你是不是也想上手体验一把?

来来来,简单五步,手把手教你撸一个缩减版的国际象棋AI。

首先,我们来看一些基础概念:

  • 移动生成
  • 棋面评估
  • Minimax算法
  • alpha beta剪枝

在每个步骤中,我们将通过一个国际象棋程序技术来改进算法。我将演示每个步骤是如何影响算法的。

你可以在GitHub上查看AI算法的最终版本。

https://github.com/lhartikk/simple-chess-ai

我无法打败自己写的象棋程序,是我太差劲还是算法太强大?

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

在该步骤中,我们使用chess.js 库进行移动生成,使用chessboard.js库可视化棋面。chess.js 库基本上包含国际规则象棋的所有规则。在此基础上,我们可以对给定棋面中所有可行的移动方法进行计算。

https://github.com/jhlywa/chess.js https://github.com/oakmac/chessboardjs/

移动生成功能的可视化。起始位置被用作输入,而从该位置开始的所有可行性移动都是输出。

使用这两个库有助于我们专注于最有趣的任务:创建算法并找到最佳走法。

我们首先构建一个函数,使它可以基于所有可行走法返回一个随机的棋局走法:

var calculateBestMove =function(game) { //generate all the moves for a given position var newGameMoves = game.ugly_moves(); return newGameMoves[Math.floor(Math.random() * newGameMoves.length)]; };

这个算法不是一个很强的对手,但是个不错的陪练。

黑子的移动是随机的

体验地址:https://jsfiddle.net/lhartikk/m14epfwb/4

步骤2:棋面评估

我们需要研究在某个特定位置,对战双方哪一方更有优势。想要达到这个目的,最简单的办法是用下方的表格来计算棋盘上每个棋子的相对强度。

通过评估函数,我们可以创建一个算法,该算法能选择评分最高的走法:

var calculateBestMove = function (game) { var newGameMoves = game.ugly_moves(); var bestMove = null; //use any negative large number var bestValue = -9999; for (var i = 0; i < newGameMoves.length; i++) { var newGameMove = newGameMoves[i]; game.ugly_move(newGameMove); //take the negative as AI plays as black var boardValue = -evaluateBoard(game.board()) game.undo(); if (boardValue > bestValue) { bestValue = boardValue; bestMove = newGameMove } } return bestMove; };

对于我们来说,一个切实的提升——我们的算法可以尽可能地吃掉每个棋子。

通过简单的评估函数,上图黑子已经能进行对弈了,体验地址:

https://jsfiddle.net/lhartikk/m5q6fgtb/1/

步骤3:使用 Minimax 搜索树

通过Minimax算法我们创建了一个简单的搜索树,算法可以从中选择最佳移动方法。在该算法中,可将递归树的所有可能移动探索到特定的深度,并在递归树的子节点处对位置进行评估。

https://en.wikipedia.org/wiki/Minimax

在此之后,我们向父节点返回子节点的最小或者最大值,这取决于黑子移动还是白子移动。(也就是说,我们试图最大化或者最小化每一级的结果)

从“我方”的角度可视化极大极小算法。对于白子来说,最佳移动位置是b2-c3,因为我们确定可以达到评估为-50 的位置

var minimax = function (depth, game, isMaximisingPlayer) { if (depth === 0) { return -evaluateBoard(game.board()); } var newGameMoves = game.ugly_moves(); if (isMaximisingPlayer) { var bestMove = -9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } else { var bestMove = 9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } };

通过适当的极大极小算法,我们的算法已经开始理解国际象棋的一些基础策略。

体验地址:https://jsfiddle.net/k96eoq0q/1

步骤四: Alpha-beta 剪枝

Apha-beta剪枝是Minimax算法的优化,允许我们减去搜索树中的一些分支。在相同的资源下,这种方法有助于我们加深Minimax搜对索树的评估。如果发现某个走法会导致更糟糕的局势,那么Alpha-beta 剪枝就会停止评估该分支。这个方法不会影响Minimax算法,相反会提升算法速度。如果一开始就能发现最佳走法,

那么Alpha-beta算法就会更有效。

通过alpha-beta剪枝,我们的极大极小算法就会获得极大的提升,演示如下:

查看chess AI的alpha-beta增强版本:https://jsfiddle.net/Laa0p1mh/3/

步骤五: 优化评估函数

最初的评估函数非常简单,我们仅仅计算棋面上能看到的局势。

想要改善这一点,我们需要添加一些评估元素,比如,棋盘中间的骑士比处于棋盘边缘的骑士更具优势(因为中心位置的骑士有更多选择,也更加活跃)。

我们将会使用piece-square table稍稍调整过的版本,就是我们上边在国际象棋编程设计wiki中提到的。

https://chessprogramming.wikispaces.com/Simplified+evaluation+function

更加直观的piece-square table,我们会根据棋子的位置,增加或者减少评估元素。

通过优化,我们的算法更像一个正儿八经的算法了,至少从一个业余玩家的角度看是这样滴。

在线体验地址https://jsfiddle.net/q76uzxwe/1/

总结

该算法的优势在于它不会犯一些愚蠢的错误,但同时它缺乏战略性的理解。

通过文中方法,我们已经编写了一个能进行简单对战的国际象棋程序算法。算法中涉及AI的部分仅有200行代码,可以实现象棋中的一些基本概念。你可以在GitHub上查看最终的版本。

https://github.com/lhartikk/simple-chess-ai

未来可改进的方向包括:

  • 移动顺序

https://chessprogramming.wikispaces.com/Move+Ordering

  • 更快地移动生成棋局

https://chessprogramming.wikispaces.com/Move+Generation

  • 残局的评估

https://chessprogramming.wikispaces.com/Endgame

想了解更多内容,可以查看国际象棋程序设计的wiki。

原文:https://medium.freecodecamp.com/simple-chess-ai-step-by-step-1d55a9266977

每日荐文

点击图片查看更多精彩内容

机器人啥都能干的话,人还用的着学习吗?

病毒、木马变身AI后,你的杀毒软件还有意义吗?

数据!数据!所有人都冲着AI狂热,所有人都高呼大数据,只有这位老头,真正穷其一生冲破数据的藩篱

版权申明:该文章版权归AI100所有,如需转载、摘编、复制等,请后台留言征得同意。若有直接抄袭,AI100将追究其责任。

原文发布于微信公众号 - AI科技大本营(rgznai100)

原文发表时间:2017-05-10

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技评论

开发 | Kaggle机器学习之模型融合(stacking)心得

此文道出了本人学习Stacking入门级应用的心路历程。 在学习过程中感谢@贝尔塔的模型融合方法(https://zhuanlan.zhihu.com/p/25...

653130
来自专栏专知

【前沿】用AlphaGo Zero方法实现增强学习下棋

【导读】Google DeepMind AlphaGo团队在Nature上发表两篇论文《Mastering the game of Go without Hum...

40180
来自专栏数据结构与算法

超几何分布与二项分布及其期望

惊奇的发现选修2-3上有期望的介绍,不过我没有课本啊qwq。只能去网上找资料了。。

11220
来自专栏PPV课数据科学社区

如何使用R语言解决可恶的脏数据

在数据分析过程中最头疼的应该是如何应付脏数据,脏数据的存在将会对后期的建模、挖掘等工作造成严重的错误,所以必须谨慎的处理那些脏数据。 脏数据的存在形式主要有如下...

30050
来自专栏新智元

重磅 | 经典教材 R. Sutton《增强学习导论》最新版(548PDF)

45920
来自专栏kalifaの日々

机器学习CS229:lesson2&exercise4

这是一个分类学习问题,已知80名学生两次考试的成绩和他们是否被大学录取。要求预测学生能否被大学录取。解决方法是用批梯度上升的方法求使得极大似然函数最大的thet...

38490
来自专栏一名叫大蕉的程序员

社区发现有啥鸟用No.14

当当当,同学们说要听算法,那今天就说说算法,关于社区发现的一系列算法。 最近一段时间工作上使用到了社区发现,虽然只是小小一部分。但是呢,工作量还是不小的,在网上...

68270
来自专栏CVer

CVPR 2018 收录论文名单全公布

本文将介绍 CVPR 2018 所有录用论文的标题, 包括每篇论文属于 oral, spotlight还是 poster的情况. 大家可以根据论文的标题去 go...

20820
来自专栏积累沉淀

数据挖掘算法之贝叶斯网络

贝叶斯网络 序 上上周末写完上篇朴素贝叶斯分类后,连着上了七天班,而且有四天都是晚上九点下班,一直没有多少时间学习贝叶斯网络,所以更新慢了点,利用清明节两天假期...

1.2K100
来自专栏IT派

推荐|Kaggle机器学习之模型融合(stacking)心得

此文道出了本人学习Stacking入门级应用的心路历程。 在经过了几天漫长的查询资料和整理,脑子不好,理解顿悟花了不少时间。在学习过程中感谢@贝尔塔的模型融合...

48950

扫码关注云+社区

领取腾讯云代金券