国际象棋
快速阅读
记录上学时做过的一个国际象棋软件。
功能概述
- 玩家对战：玩家之间轮流控制各自的棋子，吃掉对方的王获得胜利。合法的落点高亮，不合法的落点不对鼠标做出响应。
- 人机对战：玩家通过鼠标控制自己的棋子，AI通过搜索算法获得将要移动的棋子及移动的目标位置。AI走棋没有控制阶段但设置了完整的过渡动画。
- 控制面板：控制面板能够修改游戏模式、重置游戏进度、调整AI难度。
- 特殊规则：
- 兵的升变：本方任何一个兵直进达到对方底线时，即可升变为除 “王” 和 “兵” 以外的任何一种棋子。
- 王车易位：这是国际象棋中比较特殊的行棋规则，车和王在一些情况下可以互换位置。
- 吃过路兵：如果对方的兵第一次行棋且直进两格，刚好形成本方有兵与其横向紧贴并列，则本方的兵可以立即斜进，把对方的兵吃掉，并视为一步棋。
核心节点
搜索算法
deepSearch(depth, chessBoard, AIRound, parentIndex)
depth代表搜索的深度，每次递归-1。chessBoard是搜索算法需要用到的棋盘数组。AIRound用来判断此轮搜索是否为 AI 走棋，若为AI走棋则遍历 AI 方的所有棋子的所有可行走法，并为生成的每个chessBoard创建一个树的结点，根节点即最初搜索时的chessBoard参数；若为玩家走棋同样遍历玩家方的所有棋子的所有可行的走法，但只创建一个结点，这个节点是所有生成的chessBoard中价值最小的，因为玩家走棋时理应选择对 AI 最不利的走法，即评价函数返回值最小的。
最终生成树是这样的：
不管 depth 值为多少，最终 AI 要选择的总是第一步的走法。无论 depth 是奇数还是偶数，只需要选择所有的叶子结点中价值最大的结点，并回溯到第一步的祖先节点，即为 AI 的最佳走法。
评价函数
AI 需要在所有可行的走法中选择一个最合适的，是否是最合适需要利用评价函数对棋盘的状态进行量化，选择值最大的作为最终决策。评价函数接收一个棋盘数组（记录了棋盘上的棋子分布）作为参数，累加棋盘上所有存在的棋子的价值（包括棋子的基础价值和基于棋子位置的偏移价值），将它们的和作为函数返回值。
线程阻塞
deepSearch 函数在 JS 主线程内执行时，若 depth 较高（>=6 时），耗费的时间会比较长，在这段时间内页面无法渲染，动画无法执行，会造成明显的视觉卡顿。为了解决这个问题，可单独创建 worker 线程执行 deepSearch 函数，此时主线程不会被阻塞，页面会及时刷新，不会出现卡顿。Worker 线程的 deepSearch 函数执行完毕时通过 postMessage 方法向主线程发送数据（包括将要移动的棋子坐标和要移动的目标位置），主线程通过 onmessage 方法接收，然后执行 AIset 函数，移动目标棋子并更新 chessBoard 棋盘数组。
运行效果
AI 算法
这里贴上以前花了几天时间摸索并总结的国际象棋 AI 算法。
核心功能
告诉 AI 要移动哪个棋子，以及把这个棋子移动到哪个位置。
从函数上看，AI 算法需要返回两个坐标，即 要移动的棋子坐标 和 目标位置的坐标。
遍历棋盘
以初始状态的棋盘作为参数（棋盘通常是一个 8*8 的二维数组，用于记录棋盘上的棋子分布），遍历棋盘上的所有己方棋子，对每个己方棋子，遍历它所有可行的走法，每种走法都生成一个 结点。
结点的数据结构由两部分组成：
- 本次移动的棋子坐标以及移动的目标位置坐标，它将作为函数的返回值。
- AI 算法执行时需要用到的一些临时变量。
对于生成的每个结点（每一个结点代表着一次 行棋），将行棋后的棋盘作为参数，并交换行棋回合。例如：
递归遍历 所有己方棋子 及其 所有可行的走法，一直到设定的深度时结束。这样就得到了在 depth 个回合内（depth 即设定的深度）所有可能产生的结果。
评价策略
评价函数 接收一个棋盘数组（记录了棋盘上的棋子分布）作为参数，根据当前棋盘的局势，返回一个数值作为当前棋盘的 局面评价。
评价策略一般是累加棋盘上所有存在的棋子的价值，将它们的和作为函数返回值。
棋子的价值由基础价值和偏移价值组成。
基础价值
- ♟ 兵：10.0
- ♞ 马：32.5
- ♝ 象：35.0
- ♜ 车：50.0
- ♛ 后：97.5
- ♚ 王：900.0
对方棋子的基础价值为己方同类棋子基础价值的 相反数（即取负值）。
偏移价值
偏移价值是一个 8*8 的二维数组，代表此类棋子在棋盘上不同位置时对应的价值偏移量，不同类型棋子的偏移数组是不同的。
基础价值和偏移数组对应坐标的值之和即为棋子的价值。
评价函数的返回值是 决策 的依据，因此 评价策略 是体现 AI 算法差异及 AI 强度的核心因素。
决策策略
在所有得到的结果中选择一个，并回溯到它 第一层的祖先结点（不管遍历深度为多少，最终要选择的总是第一层的某一种走法，因为只有第一层的遍历是基于初始状态的棋盘），将此结点保存的两个坐标作为函数返回值。
如何选择取决于算法的策略，这是体现 AI 算法差异及 AI 强度的重要因素。
剪枝策略
遍历到某一个结点时，根据某种策略进行判断：此结点是否可能作为最终决策？若可能则继续递归遍历其子结点；若不可能则停止递归。
剪枝 不会影响最终决策，因为被剪枝的是不可能作为最终决策的结点，但剪枝可以降低算法的时间复杂度，减少执行时间。
剪枝的策略是体现 AI 算法差异的重要因素，它 可能会影响到 AI 的强度。
剪枝不会影响最终决策 是建立在剪枝正确的前提下，即被剪枝的一定是不可能作为最终决策的结点，若剪枝错误则会影响到最终决策。
搜索方式
搜索可以采用：
- 深度优先搜索（优先递归 某结点的所有子结点）
- 广度优先搜索（优先遍历 同一深度的其他结点）
广度优先搜索相对于深度优先搜索会更适合于剪枝策略，因为深度优先搜索会优先递归，递归之前会进行剪枝判断，此时并未生成同一深度的其他结点，剪枝策略在判断是否应该递归时的依据会非常有限（剪枝策略的依据是已经生成的所有结点）。
深度搜索的方式会影响到剪枝的策略，可能会间接影响到 AI 的强度。
实现过程
数据结构
非叶子结点
- 本次行棋控制的棋子的坐标（用于返回值）
- 本次行棋移动的目标位置（用于返回值）
- 此结点的父节点序号（用于回溯到第一层的祖先结点）
叶子结点
- 本次行棋控制的棋子的坐标（用于返回值）
- 本次行棋移动的目标位置（用于返回值）
- 此结点的父节点序号（用于回溯到第一层的祖先结点）
- 当前棋盘的价值（即评价函数返回值，用于决策）
搜索方式
深度优先搜索，即优先递归。
评价策略
基础价值
| 棋子 | 基础价值 |
|---|---|
| ♟ 兵 | ± 10 |
| ♞ 马 | ± 32.5 |
| ♝ 象 | ± 35 |
| ♜ 车 | ± 50 |
| ♛ 后 | ± 97.5 |
| ♚ 王 | ± 900 |
偏移价值
共 12 个 8*8 的二维数组，例如 ♞ 马 的偏移数组：
1 | [ |
决策策略
在所有叶子结点中选择评价函数返回值最大的结点，回溯到它第一层的祖先结点，将此祖先结点作为最终决策。
剪枝策略
- 对于 AI 走棋的深度，不做剪枝，遍历 AI 方的所有棋子及其所有走法，并递归所有子结点。
- 对于玩家走棋的深度，遍历玩家方的所有棋子及其所有走法，保留评价函数返回值最小的结点并递归此结点，剪掉其他的结点。这样做的理由是默认玩家方会选择最不利于 AI 方的走法，因此只保留和递归评价函数返回值最小的结点，由此生成的决策树所有的叶子结点一定在最大的深度。
循环修正
有时 AI 会在同一个位置来回走子，原因是它的决策树中出现了多个评价值相同且最高叶子节点，由于程序顺序执行的原因导致 AI 总是选择这些叶子结点中的第一个，可以修改决策策略，使其在所有评价值最高的叶子结点中随机选择一个，就能避免此类问题。