众所周知，TypeScript 是图灵完备的，因此，只要我们愿意，那当然是可以用它来实现一个象棋程序的。于是我们就快乐地开始了，为了理解方便，我们不考虑性能优化策略，纯粹从功能实现角度去构建。另外，我们尝试用中文来编写这个程序，因为类型运算中需要用到的操作符很少，类型本质上是一种对现实世界的描述，某种程度上算是一种业务描述语言，使用中文也挺好的。

需求拆解

首先我们要先来分析一下，需要实现哪些功能。

象棋的核心功能就是走棋，走棋如果用一个函数来表达，那就是：走棋<当前棋局, 源位置, 目标位置>，因此，这里就涉及两个要素：

  • 棋局结构：棋子行、列的组织
    • 棋子结构：类型、颜色
    • 位置：横坐标，纵坐标
  • 棋子的移动
    • 这个棋子能放在这里吗？
    • 这个棋子能这么移动吗？

比较多的细节会出现在棋子的移动规则上，但是，不重要，都是细节，我们挨个来解释吧。

基础结构

棋子

棋子的话，比较简单，没有什么特别的，只要表达出颜色和种类就可以了：

  1. type 棋子 = {
  2.   颜色: 棋子颜色
  3.   种类: 棋子种类
  4. }
  6. type 构造棋子<某颜色, 某种类> = 某颜色 extends 棋子颜色
  7.   ? 某种类 extends 棋子种类
  8.     ? {
  9.         颜色: 某颜色
  10.         种类: 某种类
  11.       }
  12.     : 不可能
  13.   : 不可能

本节使用的技巧非常简单，就是一个合法性判断而已。

位置

位置就会复杂不少了，主要原因是，在类型系统里面，我们要表示整数及其运算是一件比较麻烦的事情，而偏偏在计算走棋规则的时候，这部分很重要，所以，不得不去做。

定义整数和加减法的部分，在其他文章里可以找到，不在这里叙述了，假定已经存在了一些常用的整数变量，可以得到对于位置信息的表达：

  1. type 棋子横坐标 = 零 | 一 | 二 | 三 | 四 | 五 | 六 | 七 | 八
  2. type 棋子纵坐标 = 零 | 一 | 二 | 三 | 四 | 五 | 六 | 七 | 八 | 九
  4. type 最大横坐标 = 八
  5. type 最大纵坐标 = 九
  7. type 棋子坐标 = {
  8.   横: 棋子横坐标
  9.   纵: 棋子纵坐标
  10. }
  12. type 构造棋子坐标<横坐标, 纵坐标> = 横坐标 extends 棋子横坐标
  13.   ? 纵坐标 extends 棋子纵坐标
  14.     ? {
  15.         横: 横坐标
  16.         纵: 纵坐标
  17.       }
  18.     : 不可能
  19.   : 不可能

位置比棋子要复杂的原因是，要支持一些运算，比如，判断两个位置是否相同

  1. type 相同位置<位置1, 位置2> = 位置1 extends 棋子坐标
  2.   ? 位置2 extends 棋子坐标
  3.     ? 相等<位置1['横'], 位置2['横']> & 相等<位置1['纵'], 位置2['纵']>
  4.     : 否
  5.   : 否

然后，我们又会需要，对一个位置进行移动，用来定义寻找相对位置的快捷操作，比如，上下左右相邻位置的坐标，需要注意的是，这里要做一下合法性校验，避免越界。

  1. type 左邻位<位置> = 位置 extends 棋子坐标
  2.   ? 大于<位置['横'], 零> & 构造棋子坐标<减一<位置['横']>, 位置['纵']>
  3.   : 不可能
  5. type 右邻位<位置> = 位置 extends 棋子坐标
  6.   ? 小于<位置['横'], 最大横坐标> & 构造棋子坐标<加一<位置['横']>, 位置['纵']>
  7.   : 不可能
  9. type 上邻位<位置> = 位置 extends 棋子坐标
  10.   ? 大于<位置['纵'], 零> & 构造棋子坐标<位置['横'], 减一<位置['纵']>>
  11.   : 不可能
  13. type 下邻位<位置> = 位置 extends 棋子坐标
  14.   ? 小于<位置['纵'], 最大纵坐标> & 构造棋子坐标<位置['横'], 加一<位置['纵']>>
  15.   : 不可能

本节使用的规则稍稍复杂一些，但主要复杂度不在这里，而是在定义数字运算的地方。

棋局

在棋局这里，我们第一次面对了复杂的状况，整个这部分，需要解决这么一些问题：

  • 棋子的行列结构如何构造？
  • 如何基于某个位置的横纵坐标进行棋子的获取？
  • 如何为棋子规则提供必要的帮助？
  • 如何移动棋局中的棋子？

我们逐一来解决这些问题。

棋局结构

棋局结构的建模，是与取值操作密切相关的，需要注意到的是，我们并没有使用数字字面量去代表数字，而是自定义了整数类型，这就意味着，取值操作的索引是很复杂的，它无法直接得到。

在我们使用的整数定义中，数字是用一级一级嵌套表达的，当我们表示数字五，其等价形态为：

  1. type 整数 = 零 | { 前一个数: 整数; 是零吗: 否 }
  3. type 五 = 加一<加一<加一<加一<加一<零>>>>>

当我们得到一个数字，并且想要知道它真正表达的是多少，需要去统计从它到零的距离，也就是说，要反向去根据是零吗和前一个数这两个类型属性，一直往前找到零的位置。

有鉴于此，我们选择把棋局也构建为类似形式：

  • 棋局的内容是棋局行形成的链表，棋局持有第零行
  • 每行的内容是单元格形成的链表，棋局行持有第零格
  1. type 构造棋局单元<内容参数, 下一个> = 内容参数 extends 单元格内容参数
  2.   ? 下一个 extends 棋局单元 | 空
  3.     ? {
  4.         内容: 内容参数
  5.         下一个: 下一个
  6.       }
  7.     : 不可能
  8.   : 不可能
  10. type 构造棋局行<内容参数, 下一行> = 内容参数 extends 行内容参数
  11.   ? 下一行 extends 棋局行 | 空
  12.     ? 内容参数 extends [
  13.         infer 第零格,
  14.         infer 第一格,
  15.         infer 第二格,
  16.         infer 第三格,
  17.         infer 第四格,
  18.         infer 第五格,
  19.         infer 第六格,
  20.         infer 第七格,
  21.         infer 第八格
  22.       ]
  23.       ? {
  24.           内容: 构造棋局单元<
  25.             第零格,
  26.             构造棋局单元<
  27.               第一格,
  28.               构造棋局单元<
  29.                 第二格,
  30.                 构造棋局单元<
  31.                   第三格,
  32.                   构造棋局单元<
  33.                     第四格,
  34.                     构造棋局单元<
  35.                       第五格,
  36.                       构造棋局单元<
  37.                         第六格,
  38.                         构造棋局单元<第七格, 构造棋局单元<第八格, 空>>
  39.                       >
  40.                     >
  41.                   >
  42.                 >
  43.               >
  44.             >
  45.           >
  46.           下一行: 下一行
  47.         }
  48.       : 不可能
  49.     : 不可能
  50.   : 不可能
  52. type 构造棋局<内容 extends 棋局内容参数 = 棋局内容参数> = 内容 extends [
  53.   infer 第零行,
  54.   infer 第一行,
  55.   infer 第二行,
  56.   infer 第三行,
  57.   infer 第四行,
  58.   infer 第五行,
  59.   infer 第六行,
  60.   infer 第七行,
  61.   infer 第八行,
  62.   infer 第九行
  63. ]
  64.   ? {
  65.       内容: 构造棋局行<
  66.         第零行,
  67.         构造棋局行<
  68.           第一行,
  69.           构造棋局行<
  70.             第二行,
  71.             构造棋局行<
  72.               第三行,
  73.               构造棋局行<
  74.                 第四行,
  75.                 构造棋局行<
  76.                   第五行,
  77.                   构造棋局行<
  78.                     第六行,
  79.                     构造棋局行<
  80.                       第七行,
  81.                       构造棋局行<第八行, 构造棋局行<第九行, 空>>
  82.                     >
  83.                   >
  84.                 >
  85.               >
  86.             >
  87.           >
  88.         >
  89.       >
  90.     }
  91.   : 不可能

这个看上去非常诡异，但是我们后续对它的取值就很简单了。

本节主要使用了一个 infer 来定义临时变量，然后就是递归去构造了（这里可能是有简便写法的，不过我暂时想不到）。

棋局的取值

这一步，我们的目标是实现根据给定位置，从棋局中获取对应的棋子。

先来考虑如何根据一个行号获取指定行，其实很简单，让行号与棋局行链表同步移动就可以了，行号每次减一，行链表每次后移一行，那么，当行号减小到零的时候，行链表指向的就是所要的那行了：

  1. type 根据链表获取棋局指定行<
  2.   行链表 extends 棋局行 | 空,
  3.   行号 extends 棋子纵坐标
  4. > = 行链表 extends 棋局行
  5.   ? 是 extends 相等<行号, 零>
  6.     ? 行链表
  7.     : 根据链表获取棋局指定行<行链表['下一行'], 减一<行号>>
  8.   : 不可能

同理，在一行中获取某一列，也是一样的方式：

  1. type 根据链表获取棋局某行的指定单元格<
  2.   单元链表 extends 棋局单元 | 空,
  3.   列号 extends 棋子横坐标
  4. > = 单元链表 extends 棋局单元
  5.   ? 是 extends 相等<列号, 零>
  6.     ? 单元链表
  7.     : 根据链表获取棋局某行的指定单元格<单元链表['下一个'], 减一<列号>>
  8.   : 不可能

我们把这两者组合起来，即可得到根据位置查找棋子的类型函数：

  1. type 获取棋局某位置的单元<
  2.   某棋局 extends 棋局,
  3.   某位置 extends 棋子坐标
  4. > = 获取某行的指定单元格<获取棋局指定行<某棋局, 某位置['纵']>, 某位置['横']>

本节的主要技巧是类型递归，获取行、单元格的时候，都是递归调用当前的类型函数自身去取值的。

辅助规则的提供

在计算棋子位置关系的时候，我们会需要一些判断规则，这些规则的实现，都可以通过组合现有函数的方式去实现。

一些简单规则我们就不去探讨了，比如说，马的“日”字顶角，象的“田”字顶角，还有马脚，象眼等等，都可以反复组合之前我们做好的计算邻位的四个函数，比如：

  1. type 象可以走到右上的目标位置<当前位置> = 右邻位<
  2.   右邻位<上邻位<上邻位<当前位置>>>
  3. >

我们重点来看一个相对复杂的：统计一条直线上两个棋子之间的棋子数量。这里的麻烦在于，统计个数需要有一个累加计数功能，有趣的是，它仍然可以利用递归。

  1. /**
  2.  * 当需要寻找一条线上两点之间有几个棋子的时候，步骤是：
  3.  * - 如果两点重合，返回零
  4.  * - 否则沿着起点方向逐步向终点靠近，如果下一个点不是终点，并且有棋子，则累加一
  5.  */
  6. type 同一水平线上两个位置之间有几个棋子<
  7.   纵坐标,
  8.   横坐标1,
  9.   横坐标2,
  10.   当前棋局 extends 棋局,
  11.   初始值 extends 整数
  12. > = 将两个整数从小到大排序<[横坐标1, 横坐标2]> extends [infer 小, infer 大]
  13.   ? 小 extends 棋子横坐标
  14.     ? 大 extends 棋子横坐标
  15.       ? 是 extends 相等<小, 大>
  16.         ? 初始值
  17.         : 同一水平线上两个位置之间有几个棋子<
  18.             纵坐标,
  19.             加一<小>,
  20.             大,
  21.             当前棋局,
  22.             是 extends 相等<加一<小>, 大>
  23.               ? 初始值 // 下一个就是终点了，中间没有棋子可以累加了
  24.               : 是 extends 该位置有棋子<
  25.                   当前棋局,
  26.                   构造棋子坐标<加一<小>, 纵坐标>
  27.                 >
  28.               ? 加一<初始值>
  29.               : 初始值
  30.           >
  31.       : 不可能
  32.     : 不可能
  33.   : 不可能

本节使用了一个小技巧，先把两个坐标排序了一下。这样后续的递归方向可以不需要判断，否则要考虑两个方向。

棋子的移动

棋子的移动，本质上很简单，就是把目标位置的棋子内容替换掉就可以了，但是，在 TypeScript 的类型系统里，“替换”是个不太可行的事情，它是 immutable 的，所谓的替换，实际上是创建了新的。

这样，我们就得实现棋局每个层级的拷贝构造操作了，这也不难：

  1. type 从内容构造棋局单元<
  2.   内容参数 extends 单元格内容参数,
  3.   下一个 extends 棋局单元 | 空
  4. > = {
  5.   内容: 内容参数
  6.   下一个: 下一个
  7. }
  9. type 从内容构造棋局行<单元链表 extends 棋局单元, 下一行 extends 棋局行 | 空> = {
  10.   内容: 单元链表
  11.   下一行: 下一行
  12. }
  14. type 从内容构造棋局<行链表 extends 棋局行> = {
  15.   内容: 行链表
  16. }

然后，真正复杂的是替换过程中的重新构造，以替换棋局中的某一行为例，这实际上是一个一边遍历，一边根据需要构造的过程，本质上是一个 copy on write 结构，理解了这点之后，写起来就不难了，仍然是递归：

  1. type 将棋局的某行替换为指定行<
  2.   某棋局 extends 棋局,
  3.   行号 extends 棋子纵坐标,
  4.   新内容 extends 棋局单元,
  5.   当前迭代行号 extends 整数
  6. > = 当前迭代行号 extends 棋子纵坐标
  7.   ? 根据链表获取棋局指定行<
  8.       某棋局['内容'],
  9.       当前迭代行号
  10.     > extends infer 原先的这行
  11.     ? 原先的这行 extends 棋局行
  12.       ? 是 extends 相等<行号, 当前迭代行号>
  13.         ? 从内容构造棋局行<新内容, 原先的这行['下一行']> // 如果是要替换的这行，重新构造整个行，把原来的后续单元挂接过来就行了
  14.         : 从内容构造棋局行<
  15.             原先的这行['内容'],
  16.             将棋局的某行替换为指定行<某棋局, 行号, 新内容, 加一<当前迭代行号>>
  17.           >
  18.       : 不可能
  19.     : 不可能
  20.   : 空

同理，替换单元格也可以写出来：

  1. type 将棋局行的某单元替换为指定单元<
  2.   某行 extends 棋局行,
  3.   列号 extends 棋子横坐标,
  4.   新内容 extends 单元格内容参数,
  5.   当前迭代列号 extends 整数
  6. > = 当前迭代列号 extends 棋子横坐标
  7.   ? 根据链表获取棋局某行的指定单元格<
  8.       某行['内容'],
  9.       当前迭代列号
  10.     > extends infer 原先的这个单元
  11.     ? 原先的这个单元 extends 棋局单元
  12.       ? 是 extends 相等<列号, 当前迭代列号>
  13.         ? 从内容构造棋局单元<新内容, 原先的这个单元['下一个']> // 如果是要替换的单元格，重新构造这个单元格，把原来的后续单元挂接过来就行了
  14.         : 从内容构造棋局单元<
  15.             原先的这个单元['内容'],
  16.             将棋局行的某单元替换为指定单元<
  17.               某行,
  18.               列号,
  19.               新内容,
  20.               加一<当前迭代列号>
  21.             >
  22.           >
  23.       : 不可能
  24.     : 不可能
  25.   : 空

然后组合两者，就可以得到在棋局上指定位置替换棋子的函数：

  1. type 将棋局某位置替换为指定棋子<
  2.   某棋局 extends 棋局,
  3.   某位置 extends 棋子坐标,
  4.   某棋子或者空 extends 单元格内容参数
  5. > = 获取棋局某位置的单元<某棋局, 某位置> extends infer 原位置的单元
  6.   ? 原位置的单元 extends 棋局单元
  7.     ? 获取棋局指定行<某棋局, 某位置['纵']> extends infer 原有的行
  8.       ? 原有的行 extends 棋局行
  9.         ? 从内容构造棋局<
  10.             将棋局的某行替换为指定行<
  11.               某棋局,
  12.               某位置['纵'],
  13.               将棋局行的某单元替换为指定单元<
  14.                 原有的行,
  15.                 某位置['横'],
  16.                 某棋子或者空,
  17.                 零
  18.               >,
  19.               零
  20.             >
  21.           >
  22.         : 不可能
  23.       : 不可能
  24.     : 不可能
  25.   : 不可能

两次使用这个替换，即可得到走棋的函数：

  1. type 走棋<
  2.   当前棋局 extends 棋局,
  3.   起始位置 extends 棋子坐标,
  4.   目标位置 extends 棋子坐标
  5. > = 获取棋局某位置的棋子<当前棋局, 起始位置> extends infer 待移动的棋子
  6.   ? 待移动的棋子 extends 棋子
  7.     ? 是 extends 棋子可以从这里走到那里吗<起始位置, 目标位置, 当前棋局>
  8.       ? 将棋局某位置替换为指定棋子<
  9.           将棋局某位置替换为指定棋子<当前棋局, 起始位置, 空>,
  10.           目标位置,
  11.           待移动的棋子
  12.         >
  13.       : 不可能
  14.     : 不可能
  15.   : 不可能

本节没有出现新的技巧，只是因为之前的链表结构实现，导致复制起来相对复杂一些。

棋局的渲染

当我们建立了棋局的走棋规则之后，实际上象棋已经可用了，但为了显示的友好，还需要多做一步。

最基础的渲染单元，是单个的单元格，这个非常简单，直接根据颜色和种类进行两级映射就可以了。

  1. type 渲染棋子<某个棋子> = 某个棋子 extends 棋子
  2.   ? {
  3.       红: {
  4.         将: '帅'
  5.         士: '仕'
  6.         象: '相'
  7.         马: '傌'
  8.         车: '俥'
  9.         炮: '炮'
  10.         兵: '兵'
  11.       }
  12.       黑: {
  13.         将: '将'
  14.         士: '士'
  15.         象: '象'
  16.         马: '马'
  17.         车: '车'
  18.         炮: '砲'
  19.         兵: '卒'
  20.       }
  21.     }[某个棋子['颜色']][某个棋子['种类']]
  22.   : 不可能
  24. type 渲染单元格<某单元格> = 某单元格 extends 棋子 ? 渲染棋子<某单元格> : '➕'

稍微复杂一些的是渲染行，考虑到我们之前把棋局行实现成了单元格链表，这个就需要一个递归了。

  1. type 渲染单元链表<
  2.   某单元 extends 棋局单元,
  3.   初始渲染结果 extends string
  4. > = 某单元['下一个'] extends 棋局单元
  5.   ? 渲染单元链表<
  6.       某单元['下一个'],
  7.       `${初始渲染结果} ${渲染单元格<某单元['内容']>}`
  8.     >
  9.   : `${初始渲染结果} ${渲染单元格<某单元['内容']>}`

接下来，我们需要把每行的渲染结果合并输出，由于在 TypeScript 中，不管是字符串还是数组，都无法控制在 IDE 提示中的换行，因此，我们需要把结果渲染成对象结构。又因为通过字符串形态的整数，无法关联到真实的整数类型，所以需要建立一个辅助索引。

  1. type 数字键值对 = {
  2.   零: 零
  3.   一: 一
  4.   二: 二
  5.   三: 三
  6.   四: 四
  7.   五: 五
  8.   六: 六
  9.   七: 七
  10.   八: 八
  11.   九: 九
  12. }
  14. type 渲染棋局<某个棋局 extends 棋局> = {
  15.   [key in
  16.     | '零'
  17.     | '一'
  18.     | '二'
  19.     | '三'
  20.     | '四'
  21.     | '河'
  22.     | '五'
  23.     | '六'
  24.     | '七'
  25.     | '八'
  26.     | '九']: key extends '河'
  27.     ? '┠ ～ 楚 河 ～ ～ ～ 汉 界 ～ ┨'
  28.     : 渲染指定行<
  29.         某个棋局,
  30.         key extends keyof 数字键值对 ? 数字键值对[key] : 不可能
  31.       >
  32. }

这样，整个棋局就可以被渲染出来了。

本节使用的技巧主要是字符串的拼接，以及对象结构的输出。

小结

本文的意图主要是在不考虑优化的情况下，如何借助类型系统的运算来解构这么一个象棋逻辑。

主体功能都还是比较容易实现的，从目前的实现来看，调用栈太深了，现在走棋已经很难跑出来了，需要优化，比如把数字的计算改成打表，可以优化不少，暂时先不去做它了。

特别鸣谢在此文编写过程中提供帮助的引证老师。

本文提到的代码在：https://github.com/xufei/type-chess

在线预览地址

后记：这是近期胡思乱想引起的一个点子，算是挑战一下自己，也是对类型系统加深认知的一个过程。写完了这篇，我的 TypeScript 水平终于可以说是成功从小学二年级提高到三年级了，整个代码还是有挺多可提高的地方的，待改进。

至于为什么选择象棋呢，因为规则比较简单，只需要考虑怎么用类型系统实现就行了。