建立我自己的国际象棋引擎

上个月，我一直在学习国际象棋，以及如何编程象棋引擎（第一次）。在浏览了一些介绍性文字后，我坚信构建一个简单的象棋引擎（一个可以与休闲玩家进行公平竞争的引擎）将只需要几天。

但是我最终做到了这一点，并创建了一个令我感到骄傲的玩具国际象棋引擎（healeycodes / andoma）。它可以玩国际象棋游戏，并解决简单的象棋难题，例如二人伴侣或三人伴侣。它具有纤巧的UCI界面，这意味着可以通过lichess-bot（lichess API和国际象棋bot之间的桥梁）将其连接到lichess.org。

其发展的第一个减速是要掌握国际象棋的计算复杂性-搜索树的增长速度和宽度。开始下象棋游戏时，白色可以以二十种不同的方式打开，黑色可以以二十种不同的方式响应。第一个完整回合后，可能有400种变化。在第三个完整回合之后，超过了1.19亿。

克劳德·香农（Claude Shannon）在其开创性的论文《为计算机下象棋编程计算机》（1950年，他的开创性论文）中计算出大约有10 ^ 120种可能的国际象棋。内特·西尔夫（Nate Silver）引用迭戈·拉斯金·古特曼（Diego Rasskin-Gutman）的话：

有了无限的资源，实际上并不需要很多代码来计算国际象棋的每个合法变化。在这里，Python包python-chess用于董事会代表和合法举动的产生。

从国际象棋导入板，移动，STARTING_FEN＃邻接列表位置= {}＃从FEN字符串进行深度优先搜索def generate_tree（fen）：板=板（fen）Legal_moves =列表（board .legal_moves），如果fen在位置：position [fen] + = legal_moves else：位置[fen] =合法移动中的legal_moves：board .push（move）next_fen = board .fen（）board .pop（）generate_tree（next_fen）try：generate_tree（STARTING_FEN），除了RecursionError之外：打印（len（位置）+和（len（p）表示p在位置））

该程序引发RecursionError并打印59691 —搜索树崩溃时所包含的不同位置数。我们需要解决的是另一个在其中运行程序的世界。

考虑到要遵守的计算限制以及国际象棋的时间控制规则，必须对天真的暴力搜索进行改进。

为了寻找良好的职位，有必要了解使良好的职位变好的原因。描述位置强度的最简单方法是比较每一侧的总价值材料。

简化评估函数的作者Tomasz Michniewski定义了一些“专门为补偿缺乏其他国际象棋知识而设计的”值。这对我来说是完美的-初学者棋手。

此代码段使用Michniewski的件值汇总了初始板上的材料。

进口国际象棋=象棋.PAWN：100，象棋.ROOK：500，象棋.KNIGHT：320，象棋.BISHOP：330，象棋.QUEEN：900，象棋.KING：20000} board =象棋.Board（chess .STARTING_FEN） white_material = 0 black_material = 0，表示国际象棋中的正方形。SQUARES：件=棋盘.piece_at（正方形），如果不是件：如果件.color ==国际象棋，则继续。白色：white_material + =件值[piece .piece_type]否则：black_material + =件值[件.piece_type]

Michniewski还提供了一块正方形表，该块表根据其所在的正方形来改变一块的值。例如，典当最好沿着棋盘前进，骑士最好靠近棋盘中心。

平方的奖励可能是正数，中性或负数。平方尺表是由White的POV呈现的，必须与Black镜像。

＃骑士奖金取决于50，-40，-30，-30，-30，-40，-50，-40，-20、0、0、0，-， 20，-40，-30、0、10、15、15、10、0，-30，-30、5、15、20、20、15、5，-30，-30、0、15、20， 20、15、0，-30，-30、5、10、15、15、10、5，-30，-40，-20、0、5、5、0，-20，-40，-50， -40，-30，-30，-30，-30，-40，-50，

对于国王，Michniewski提供了两张桌子-一张用于中间游戏，一张用于结束游戏。他将结束游戏定义为：

具有女王/王后的每一侧都没有其他碎片或最多一个未成年人。

对棋盘的评估是使我一直对棋引擎感兴趣的原因之一。评估规则易于添加和删除。我将代码从Go重构为Python，以便能够更快地原型化不同的规则。

在棋子方桌之后，人们可能会查看棋子的结构，移动性，中心控制，连通性，被困棋子，国王安全性，空间，节奏和其他样式（此列表摘自国际象棋编程维基的“评估”页面）。

Minimax是一种搜索算法，它通过在最坏情况下将潜在损失最小化来找到下一个最佳移动。国际象棋是一种完美的信息游戏-通过观察棋盘，可以确切地知道对手的能力。但是，这种对移动的搜索受到评估功能和计算资源能够达到的深度的限制。

搜索空间是一棵合法举动的树，它在每个级别都呈指数增长（平均分支因子约为35）。在探索树时，已知通往许多未来棋盘的路径，以及该路径最大程度地限制了对手的可能收益。

树的叶节点返回其当前状态的评估。非叶节点从后代节点继承其值。最终，递归函数将减小到给定板的值。

通过在当前回合中可用的每个合法移动上调用此功能，可以使用它来选择下一个最佳移动。塞巴斯蒂安·拉格（Sebastian Lague）的“算法介绍”（该算法非常有用）是最小的视觉资源-minimax和alpha-beta修剪。

def minimax（board，depth，maximizing_player）：如果depth == 0或board .is_game_over（）：如果maximizing_player：value =-float（＆＃39; inf＆＃39;）返回评估（board）进行棋盘移动。 ：board .push（move）value = max（value，minimax（board，depth-1，False））board .pop（）返回值else：value = float（＆＃39; inf＆＃39;）用于在木板中移动.legal_moves：板.push（move）值=最小值（值，最小最大（板，depth-1，True））板.pop（）返回值

我的国际象棋引擎使用alpha-beta修剪作为对朴素的minimax算法的改进-与国际象棋的指数性质相去甚远。当很明显另一个分支显示出更多的承诺时，可以消除搜索树的分支。这大大减少了需要产生的移动次数。

通过减少无法开花结果的树枝的深度，我们可以更深地搜索树的更好部分。

可以通过应用移动顺序来提高alpha-beta修剪的速度。这是首先搜索搜索树中较有希望的分支的地方-这意味着在最差的分支上花费的时间更少，因为它们将尽早被切断。

在我的引擎中，便宜的（但不是完美的）move_value函数用于对初始合法移动节点从最佳到最坏的排序。该函数的逻辑是在其文档字符串中捕获的：

＆＃39;＆＃39;举动有多好？晋升很棒;较弱的人拿走更强的棋子是好事;较强的人拿走较弱的棋子是不好的;还考虑通过棋子改变位置-方桌。＆＃39;＆＃39;＆＃39;

通用国际象棋界面（UCI）是一种开放协议，可将国际象棋引擎连接到用户界面。通信通过标准输入和标准输出完成，消息以\ n结尾。移动格式是长代数符号-如e2e4或e1g1表示白色短整形，而提升为皇后的一个例子是a7a8q。

规范中有许多配置命令，乍一看似乎不胜枚举。调试之后，我发现将象棋引擎转到Hello World阶段并不需要很多。

为了使我的国际象棋引擎通过lichess-bot连接到lichess，我实现了以下内容。这些命令从lichess-bot发送到引擎：

位置起始位置动作e2e4-引擎将其内部状态设置为与动作列表匹配

go-引擎现在应该计算并做出下一个最佳移动，例如g8f6

在过去的一个月中，我与国际象棋社区互动感到非常高兴。 Lichess是一个了不起的资源，并且可以无休止地玩乐。用户界面光滑轻巧-赛后分析显示出来且易于使用。它是开源的，并依赖捐赠和赞助。

我在写这篇文章时休息了一下，以便在真正的棋盘上与爸爸下棋。我们缺少白色的白嘴鸦，并使用削笔器作为替换件。几十年前，他一直在告诉我有关下棋的故事-在IBM的“深蓝”游戏问世之前，在1997年的第二次尝试中击败了卫冕世界冠军加里·卡斯帕罗夫。

如果您属于我的社交圈，那么在过去的一个月中，您将经历过我对国际象棋和国际象棋引擎进行宣传的经历-既然我已经出版了此书，我保证会放松一点

国际象棋编程维基-这里蕴藏着难以置信的丰富知识。我花了几个小时阅读中级和高级概念，只是为了好玩

解释了算法–最小最大和alpha-beta修剪–塞巴斯蒂安·拉格（Sebastian Lague）的算法细分非常容易实现，这一点没有什么不同

构建简单的国际象棋AI的分步指南-该基于JavaScript的教程介绍了带有显式代码段的概念。最终解决方案的源代码也很可读

评论或问题？我喜欢通过电子邮件与读者交谈。我写代码。将我的帖子，项目和个人更新直接发送到您的收件箱！