精子又要搬家了,来  看一看有什么正在甩卖  吧。
归档 2016 年 6 月

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 密集的计算任务,它就会阻塞整个事件循环的处理,此时需要开发者手工让出线程,来处理事件循环中其他的事件。

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

1

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

订阅推送

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

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