我正在 SegmentFault 上录制一些 视频课程,欢迎购买收看,这是支持我创作更多技术内容的好机会哦。
基于业界最成熟的加密和版本控制工具 —— GPG 和 Git 的密码管理器:Elecpass
标签 #Node.js

WizardChess: 一个国际象棋 AI 的实现

这篇文章由我 6 月末在 LeanCloud 进行的一次技术分享整理而来。

我高一的时候曾读过一本「代码的力量:C/C++ 中国象棋程序入门与提高」,也想自己试着实现一个,连名字都想好了,就叫 Wizard Chess —— 哈利波特中的「巫师棋」。然而直到最近借着 AlphaGo 的热度,我才真正动起手来,代码开源在 GitHub,因为是纯前端程序,所以你可以直接访问托管在云引擎上的 Demo http://wizard-chess.leanapp.cn.

国际象棋是一种「透明」的、「没有随机元素」的博弈游戏,所谓「透明」是说在任一时间,博弈双方对局面的了解都是一致的(而不像牌类游戏看不到对方的手牌),大部分棋类游戏,例如五子棋、围棋都是如此,这类游戏需要的是非常强的逻辑推理能力去预见若干回合之后的局面,本文介绍的方法也大体适用于这些棋类游戏。

在技术选型上,我选择了用 TypeScript 来编写核心代码以便可以同时运行于浏览器和 Node.js, 借助 TypeScript 的编译期类型检查,可以让我们更早地发现和类型有关的错误,同时 Chrome 本身也有着非常好用的调试器和性能分析器来查找性能瓶颈。前端方面我选择用 React 来编写 UI, Web Worker 来运行计算 —— 毕竟如果在主线程进行 CPU 密集的运算会阻塞事件循环。

最近一段时间,我发现在这种偏重于数据结构的程序中,「不可变」的数据类型将会极大地减少复杂度并且提高性能,但在我调研了 Immutable.js 后并没有直接使用它,因为我觉得可能我不需要它提供的那么复杂的数据结构,而是自己在编码时注意不要修改参数、函数总是返回新的对象。

建模

第一步是将国际象的规则建模到代码中,首先是定义一些数据结构来表示国际象棋中的元素(阵营、棋子、棋盘):

enum ChessType {
  king, queen, rook, bishop, knight, pawn
}

enum Camp {
  black, white
}

interface Piece {
  type: ChessType;
  camp: Camp;
}

interface Board {
  /* from 0 to 63 */
  pieces: Array<Piece>;
}

然后需要为每一种棋子编写一个「生成走法」的函数,以便我们的程序知道一个棋子有哪些走法可走,在此以国王为例:

function generateMovesForKing(board, piece, camp) {
  for target in ([-1, -1], [0, -1], [1, -1], [-1, 0],
                 [1, 0], [-1, 1], [0, 1], [1, 1]) {
    if (target on the board and (target is empty or target.camp != piece.camp)) {
      yield target
    }
  }
}

按照国际象棋的规则,国王可以以直线或斜线的方式移动一格,因此上面的代码会检查相邻一格的位置是否在棋盘范围内、是否是空的或者有对面的棋子(吃子)。

然后还需要考虑到我们的程序和外部的输入输出,在国际象棋领域已有一个叫 FEN 的标准来表示当前的局势(各个棋子在棋盘上的位置),下面是一段表示开局状态的 FEN:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

FEN 为每种棋子规定了一个字母、用大小写表示黑棋或者白棋、用斜线分割不同的行、用数字表示空白。在我们的程序的 Web 界面中有一个填写 FEN 的文本框,当你填入一个新的 FEN 时,棋盘上的棋子会随之改变;反过来当你移动棋子时,FEN 也会跟着改变,这将会让我们后续的调试变得非常简单。

局面评估

我们的程序会在每个回合中,从众多可能的走法中选择一个对自己而言最优的走法,所以我们需要一个函数去评估和量化一个走法对我们而言的优势。

function evaluate(board: Board, camp: camp): number {
  var ourScore = 0;

  for piece on board {
    if (piece.camp == camp) {
      ourScore += getScode(board, piece)
    } else {
      ourScore -= getScode(board, piece)
    }
  }

  return ourScore;
}

这个函数会接受一个棋盘(board)和一个阵营(camp)作为参数,这个棋盘其实就是应用了某个走法之后,各个棋子的位置。这个函数会检查棋盘上每个棋子,如果这个棋子是我方的,就将其代表的分数加到「我方的优势分数」上;如果是对方的,就从我方的优势分数中减去对应的分数。

每个棋子所代表的分数则按照下表来计算:

棋子 基础分数 每多一种走法的额外分数
10000 2
皇后 1000 2
500 2
400 2
300 2
100 2

在这里我们凭「直觉」,按照棋子的重要性,给了每个棋子一个基础分数。但如果只有基础分数的话就会出现这样的情况:我们只能区分出出现吃子行为时的优势,如果不发生吃子,那么所有局面的优势都是一样的。为了解决这个问题,我们可以为「每一个可能的走法」再增加两点分数,因为在象棋中,我们可以走到一个格子,就说明我们对这个格子有一定的控制能力(如果对方的棋子走到这个格子我们就可以吃掉它),引入这个代表「灵活性」的分数后,我们会认为有更多走法的局面是更具有优势的局面。

关于局面评估函数应该考虑什么、不应该考虑什么是一个值得思考的话题。因为我们的 AI 主要是靠下文介绍的「搜索」算法来找到最优的走法的,搜索函数会模拟双方的走棋,如果棋子之间存在守护关系,会在搜索中得到体现,有时过于「自作聪明」的评估函数反而会影响到搜索。在五子棋这样简单(搜索树小)的游戏中,我们甚至可以将评估函数精简为一个「判断胜负」的函数,因为按照目前的计算力,是有可能直接在搜索中找到获胜的局面的,而在象棋这种搜索树庞大的游戏中,我们还是需要评估函数的。

在我们的程序中,我将「灵活性分数」做成了一个默认不开启的选项,默认只计算棋子的基础分数,这是因为计算走法是一个相对开销较大的运算,会比较明显地减少搜索层数(减少一层)。

极大极小搜索法

棋类游戏的博弈 AI, 最核心的就是搜索算法,即通过轮流模拟双方走棋,找到最优的走法。搜索的层数就是模拟走棋的回合数,搜索层数越深代表博弈程序可以考虑得越远,能力也就越强,响应地消耗的计算资源也越多。

我们首先介绍一个非常简单的搜索算法 —— 极大极小搜索法,这个算法平淡无奇,只是深度优先地轮流模拟双方走棋:

function negaMaxSearch(depth: number, board: Board, camp: Camp): number {
  if (depth <= 0) {
    return evaluate(board, camp);
  } else {
    return getAllMoves(board, camp).reduce( (best, move) => {
      return Math.max(best, -negaMaxSearch(depth - 1, board.move(move), anotherCamp(camp)));
    }, -Infinity);
  }
}

我将这个算法实现为了递归的形式,参数 depth 用于控制搜索的深度,每递归一层便减少 1, 当减少到 0 的时候结束递归,使用评估函数评估这个局面的优势值;depth 大于 0 时则递归地搜索当前所有可能的走法(getAllMoves),返回其中优势值最大的局面。

注意在进行递归时,我们需要用 anotherCamp 来切换阵营,同时对结果取负值。这是因为在象棋中,博弈双方是轮流走棋的,我们需要先模拟自己走棋,再模拟对方走棋。在模拟对方走棋时,我们需要站在对方的角度来考虑 —— 我们需要找到对我方最不利的走法,因为我们需要假设对方是聪明的,是会尽一切可能针对我方的,所以在递归时我们需要对 negaMaxSearch 的结果取负。

wizard-chess-negamaxsearch.jpg

在我的电脑上,这个算法可以在使用单核心的情况下,花费 1 分钟来搜索 4 层。在开局状态下,搜索树有 9341 个节点,最终评估了 220211 个局面:

White {search: 9341, evaluate: 220211}
Black {search: 9341, evaluate: 220211}

Alpha/Beta 剪支

但其实在前面的搜索树中,有很大一部分节点是「没有意义」的,即无论是否搜索这些节点,对最终的结果都不会有影响,我们可以通过接下来介绍的 Alpha/Beta 剪支算法来跳过对这些无意义的节点的搜索。

wizard-chess-alphabetasearch.jpg

例如在上图中,如果我们从左到右深度优先地搜索走法树,那么右侧灰色的节点就是我们需要跳过的节点。depth=1 最右标有 5 的节点的左侧子树(5 - 5 - 5)被搜索出之后,depth=1 最右标有 5 的节点的最小值就已经被确定为了 5 —— 因为在 depth=2 时我们需要站在对手的角度找到对我方估值最低的走法,既然左侧子树已经找到了 5, 那么无论其他子树的值是多少,这个节点估值都不可能比 5 更大了。

如果 depth=1 最右标有 5 的节点的估值小于等于 5, 那么它对于父节点也是没有意义的,因为在 depth=1 的层我们需要找到估值最高的走法,既然在 depth=1 这层我们已经找到了一个估值为 6 的走法,那么我们就对估值小于等于 5 的走法不感兴趣了,因此图中灰色的节点我们都可以跳过。

function alphaBetaSearch(depth: number, board: Board, camp: Camp, currentCamp: Camp, alpha: number, beta: number): number {
  if (depth <= 0) {
    return evaluate(board, camp);
  } else {
    for move in getAllMoves(board, camp) {
      if (camp == currentCamp) {
        alpha = Math.max(alpha,
          alphaBetaSearch(depth - 1, board.move(move), camp, anotherCamp(currentCamp), alpha, beta)
        );
      } else {
        beta = Math.min(beta,
          alphaBetaSearch(depth - 1, board.move(move), camp, anotherCamp(currentCamp), alpha, beta)
        );
      }

      if (beta <= alpha) {
        break;
      }
    }

    if (camp == currentCamp) {
      return alpha;
    } else {
      return beta;
    }
  }
}

我们在极大极小搜索法的基础上进行了修改,得到了带有剪支(跳过图中灰色节点)功能的 alphaBetaSearch, 它多了 currentCamp, alpha, beta 三个参数。alpha 表示在当前搜索路径中,我方至少可以得到 alpha 的分数,任何低于 alpha 的局面都不考虑(剪支);beta 表示在当前搜索路径中,对方至少可以拿到 beta 的分数,任何高于 beta 的局面都不考虑(剪支),因对方不会放任你拿到更高的分数的;而 currentCamp 和 camp 将用于在搜索中区分「我方」和「对方」。

在递归时,我们会区分当前是「我方」还是「对方」。我方走棋时,将最好的估值保存到 alpha, 对方走棋时,我们将最差的估值保存到 beta, 如果某个局面的估值在 beta 和 alpha 之间则进行剪支(break)。

depth worst case best case
n b^n b^⌈n/2⌉+b^⌊n/2⌋−1
0 1 1
1 40 40
2 1,600 79
3 64,000 1,639
4 2,560,000 3,199
5 102,400,000 65,569
6 4,096,000,000 127,999
7 163,840,000,000 2,623,999
8 6,553,600,000,000 5,119,999

这个表格列出了 Alpha/Beta 剪支搜索在最好和最差的情况下搜索的局面数量级,所谓最好的情况就是每个最左子树都是最理想的估值,其余子树都被剪掉了,最差的情况就是每个子树都有着比左侧子树更理想的估值,因此我们需要搜索所有子树来找到最理想的估值。当然实际情况肯定是会介于最好和最坏的情况之间,在开局状态下,我们的程序表现如下,相比于前面的极大极小搜索,我们剪掉了 95% 的局面,只评估了 15k - 34k 的局面。

White {search: 1748, evaluate: 15854, cut: 1136}
Black {search: 2071, evaluate: 34740, cut: 1547}

从上面的数据可以看到很有趣的一点,开局状态下明明黑白双方的棋子位置差不多,但搜索的局面数量却差了一倍。这是因为 Alpha/Beta 搜索会比较严重地依赖搜索每个走法的顺序 —— 如果先搜索的是估值理想的走法,那么就会触发更多的剪支,搜索更少的节点,反之则会搜索更多的节点。而我们完全没有对走法做排序,所以搜索的顺序会取决于棋子在棋盘上出现的顺序 —— 没错,差别就是这么大。

因此在搜索子树的时候,对子树(走法)做一个预先的排序就显得很重要了,可以很大程度地提高剪支的效率。但同时这又是一个很矛盾的事情 —— 我们搜索就是为了找到最好的走法,但在搜之前却又需要先对走法进行一个排序。所以这个排序必须直观而简单,例如优先搜索皇后、车这类重要的棋子,

写在后

说实话,因为我数学基础比较差,也没有进行太多的性能优化,最后实现出来的 AI 非常地弱,基本每一步棋都很「蠢」,但至少实现了一个棋类 AI 应有的骨架。我今后可能不会继续维护这个代码了,所以相比于代码,可能这篇文章对读者的帮助会更大。

参考链接

国际象棋规则:

FEN:

Alpha/Beta 搜索:

测试数据:

从被误解到最流行:论 JavaScript 如何完成华丽转身

有人说「JavaScript 是花了 10 天时间匆忙被设计出来的语言」,也有人说「凡是能用 JavaScript 写出来的,最终都会用 JavaScript 写出来」。写这篇文并非要对 JavaScript 做一个全面的优劣分析,而是想与大家分享一些存在于 JavaScript 及其生态系统中的、在我看来比较有趣的闪光点。

插件化的语言特征

JavaScript 曾经是一门兼容性最糟糕、升级最困难的语言。开发者们要苦等到所有用户都升级了浏览器,才敢使用新版本的特征。然而在最近几年,随着 Babel 等编译器的兴起,越来越多的 JavaScript 开发者们都放开了手,开始在生产环境中使用那些尚未被纳入标准的语言特征了。

使用了 Babel 的项目需要在发布之前引入一个「构建」的步骤,将使用了较新的语言特征的源代码转译为兼容性更好、被所有浏览器所支持的早期版本的 JavaScript,所以开发者就不必再去关心用户的浏览器是否支持这项新特征了。

Babel 是一个开源的、插件化的编译器框架,JavaScript 的每个语言特征(包括那些还未被纳入标准的)都被实现成了一个插件,插件可以遍历和替换 AST,进而对编译的结果施加影响。令人兴奋的一点是 Babel 让语言的特征形成了模块化,也就是说开发者可以在构建脚本中来配置要使用的语言特征。

Babel 的出现大大加速了 JavaScript 的进化。因为一旦有人希望在 JavaScript 中加入一个新特征,他首先会去实现一个 Babel 插件,然后很快就会有开发者去使用这个插件(这个过程不过是修改一下构建脚本)。这样新特征会得到来自一线开发者的验证和反馈,并有效地得以改进,如此形成一个良性循环。对比来看,某一些语言的新特征在设计和普及阶段进展非常缓慢。因为如果一个特征无法成为标准,就不会有开发者使用,而没有开发者使用,标准的制定者又无法得到足够的反馈,进而推迟进入标准的时间。

总有一种适合你的方言

除了对 JavaScript 本身的增强,社区中还有着上百种编译成 JavaScript 的「方言」。创造一种 JavaScript 的方言并不难,你只要编写一个从源代码到 ES AST 的词法和语法分析器,后续的步骤交给 Babel 就好。社区中比较知名的几种方言有:

这些方言有着各自的风格,从外观来看语法完全不同,但它们最终都会编译成标准的 JavaScript,这意味着它们之间是可以互操作的,你可以在一个 TypeScript 的项目中使用 CoffeeScript 编写的库,反之亦然。你甚至可以在一个项目中混用不同的方言。

开发者很少需要担心新特征或方言带来的不稳定性,因为代码最终会被编译成标准的 JavaScript,只要编译的过程没有错误,最后都是交由 JavaScript 引擎来执行,这并没有为 JavaScript 引擎带来新的复杂度。一旦有一天你决定不再使用某个特征或方言时也不要紧,直接使用编译后的 JavaScript 就好了。

这样一来,可以说 JavaScript 不再是一门语言,而是一个 JVM(JavaScript Virtual Machine)了。同时因为浏览器厂商(它们是这个世界上最大的科技巨头)之间的竞争和合作,JavaScript 有着几乎是所有虚拟机语言中最好的性能。

精简而灵活的语言核心

JavaScript 的标准库仅包含了非常有限的功能,某种程度上来说这也是件好事 —— 精简的标准库给第三方库留出了充分的竞争空间,真正得到大家认可的库才会被广泛使用,而不仅仅因为它被包含在了标准库中。

JavaScript 语言本身并没有定义得非常好的「范式」,你可以使用函数式的风格,比如函数作为参数和返回值、闭包、lodash 等函数式工具Immutable.js 提供的不可变数据类型(ES2015 甚至还包括了尾递归优化);你还可以使用面向对象的风格,比如使用原型 prototype 构造出具有静态成员和实例成员、支持继承和多态的类(ES2015 也添加了 class 这个关键字来更加方便直观地定义类)。

正是 JavaScript 的这种灵活性,赋予了类库的设计者很大的施展空间。很多知名的类库可以说是创造了一种新的编程范式:

  • Backbone:面向对象的 ORM,通过事件模型来通知对象的变化。
  • Express:通过定义串联的「中间件」来处理 HTTP 请求。
  • React:每当状态发生变化便重新渲染整个页面,减少用户界面状态管理的复杂度。

不止于浏览器环境

JavaScript 不仅可以在浏览器中运行,因为它精简的语言核心(甚至不包括任何 IO 相关的功能),现在已经被移植到了其他很多平台:

  • Node.js:提供了访问文件系统、进行网络操作的 API,用于构建 Web 后端等服务器程序。
  • Ionic / Cordova:提供访问移动设备的 API,使用 Web 技术来构建移动应用。
  • Electron:让 JavaScript 可以同时访问 Web 和 Node.js 的 API,以便用 Web 技术来构建桌面应用。
  • React Native:用 JavaScript 去操作原生 UI 组件来构建移动应用。

这些环境下有着和浏览器中完全不同的 API,但运行的都是同样的 JavaScript 代码,你的业务逻辑代码可以在这些环境间共用。JavaScript 社区中大部分已有的、不依赖具体运行环境的工具库都可以不加修改地运行在这些新环境中。

异步单线程是把双刃剑

无论在浏览器还是 Node.js 中,JavaScript 都采用了异步单线程的并发模型,所有的 IO 操作都采取异步执行,并通过「回调函数」来接收结果。以 Node.js 为例,引擎内部使用了一个固定数量的线程池,通过操作系统的「IO 多路复用」功能来进行 IO 操作,这样即使有大量并发的 IO 操作,也不过是多花了一点内存来维护相关的数据结构,并不会创建新的线程。这也是为什么大家都说 Node.js 适合高并发场景的原因了。同时 JavaScript 暴露给开发者的线程只有一个,只有这个线程会执行 JavaScript 代码,所以开发者不必象其他一些多线程语言那样去关心线程同步和线程安全的问题。JavaScript 开发者对于异步任务的接受程度也更高,他们会尽可能地让没有依赖关系的操作并行执行,让无谓的等待时间最小化

作为代价,JavaScript 中所有的 IO 操作都需要通过传递 回调函数 的方式来获取结果,初学者会为此非常苦恼 —— 编写循环、处理异常时会束手束脚,异步回调的写法也非常繁琐,一不留神回调函数的嵌套就会失去控制。为此社区创造了很多语言特性和工具来试图解决这个问题,包括 EventEmitter、async.js、Promise、co/generator、async/await 等。虽然基本可以认为 Promise 是未来的趋势,但目前还并没有普及到所有的 JavaScript 开发者,而且在这几种异步流程控制方案之间互相调用也很令人头痛。此外因为只有一个 JavaScript 线程在运行,所以如果在一个函数中有 CPU 密集的计算任务,它就会阻塞整个事件循环的处理,此时需要开发者手工让出线程,来处理事件循环中其他的事件。

好了,怕篇幅再长反而会分散大家对内容的理解和印象,就此收笔。我这儿还有些其他相关的内容,感兴趣的朋友可以继续读下去。

semver:语义化版本规范在 Node.js 中的实现

精子又开了一个新系列!我计划在这个系列中每篇文章介绍一个 NPM(Node Package Manager)上的包,来向大家分享一些我在使用这个包的过程中的经验,同时也会延伸到一些相关的技术,例如如果介绍 redis 这个包,那么我也会顺便介绍一下 Redis. 因为对于一些使用广泛的包我可能需要更多的时间来搜集资料,所以一开始会从一些比较小而专的包开始。

semver

我们先从 semver 这个不起眼的包开始,它是 语义化版本(Semantic Versioning)规范 的一个实现,目前是由 npm 的团队维护的,实现了版本和版本范围的解析、计算、比较,在 NPM 的被依赖(Most depended-upon)榜单中排名 34.

Semantic Versioning 是由 GitHub 的联合创始人 Tom Preston-Werner 建立的一个有关如何命名软件和库(包)版本的规范,用以解决在大型项目中对依赖的版本失去控制的问题(例如你可能因为害怕不兼容而不敢去更新依赖)。现在 Semantic Versioning 已经在开源社区中得到了广泛的认同,Node.js 的包管理工具 npm 也完全基于 Semantic Versioning 来管理依赖的版本。

semver 定义了两种概念:

  • 版本是指例如 0.4.11.2.71.2.4-beta.0 这样表示包的特定版本的字符串。
  • 范围则是对满足特定规则的版本的一种表示,例如 1.2.3-2.3.41.x^0.2>1.4.

在这两种概念上可以进行很多种计算,例如比较两个版本的大小、判断一个版本是否满足一个范围、判断一个版本是否比范围中的任何版本都大等。

显然这个包的使用场景就是与版本号打交道。例如你有一个客户端工具,需要在每次启动时向服务器发起一个查询来检查更新,那么用 semver 去比较版本将会是一个很好的选择:

console.log(semver.gt(lastestVersion, currentVersion) ? 'New Update available' : 'Already lastest version');

基于 Semantic Versioning 规范,我们还可以计算出两个版本之间的差异程度:

console.log(semver.diff(lastestVersion, currentVersion) == 'major' ? 'Major Release' : 'Minor or patch Release');

再比如你在实现一个插件化的系统,每个插件(在 package.json 中)都会声明一个所兼容的主程序的版本范围,而主程序在加载插件时需要检查这个版本并使当地给出警告:

plugins.forEach(function(plugin) {
  if (!semver.satisfies(platformVersion, plugin.engines.platform))
    console.log(plugin.name, 'require', plugin.engines.platform, 'but unable to meet');
});

在你使用 express 设计一个支持多种版本的 API 服务器时,你可以这样做:

app.get('/', apiVersion('<0.6'), function(req, res) {
  res.send('Less than 0.6');
});

app.get('/', apiVersion('1.2.3 - 2.3.4'), function(req, res) {
  // ...
});

app.get('/', apiVersion('*'), function(req, res) {
  res.send('Unsupported version');
});

其中 apiVersion 中间件的一个简单实现:

function apiVersion(range) {
  return function(req, res, next) {
    if (semver.satisfies(req.headers['accept-version'], range))
      next();
    else
      next 'route'; // skip this route
  };
}

也许你用字符串计算再配合一点正则也可以完成上述的场景,但你很难做到对 Semantic Versioning 的完备支持,在之后发布新版本后撰写版本号的时候也会受到限制,例如 semver 可以正确地比较 0.9.00.10.0 以及 0.9.0-beta.1,但自行实现这些支持将会非常繁琐。

所以其实选择 semver 的理由很简单 —— 让专业的包去完成专业的工作,相信这也是在 Node.js 社区得到了广泛认同的观点。

精子生于 1995.11.25, 21 岁,英文 ID jysperm.

订阅推送

通过邮件订阅精子的博客日志、产品和项目的最新动态,精子承诺每一封邮件都会认真撰写(历史邮件),有想和精子说的话也可以直接回复邮件。

该博客使用基于  Hexo  的  simpleblock  主题。博客内容使用  CC BY-NC-SA 3.0  授权发布。最后生成于 2018-09-16.