做个中国象棋，遇到瓶颈了

Question

这是我目前发现的最强的基于JS的中国象棋AI：https://www.cnblogs.com/royhoo/p/6426394.html
该程序能思考6-8层（相当于3-4回合），用时不超5秒。足以对抗一般象棋玩家。下面是我写的象棋AI：该AI也是基于alpha-beta搜索。但目前搜索6层需要10多秒，在性能上和前面的差了很多。我写了很长时间了，感觉象棋AI理论也研究的差不多了，实在不知道为啥速度还是这么慢。谁写过这类程序，能否指点一二？

Answer 1

我写过一个黑白棋的AI
https://blog.csdn.net/jslang/article/details/46712823你用置换表了吗？可以加入历史启发和MTD(f)算法等加快alpha-beta搜索。
看看校验棋子走法和局面估价函数运算时间是不是过长。
代码中循环最好都用while()和for()。不要用数组的forEach()之类的方法。for( in )也尽量少用。

Answer 2

楼上的黑白棋写的很好，佩服。我感觉置换表适用于较深的搜索，即10层以上。而对于JS版的中国象棋程序，由于语言局限，想实现10层以上搜索基本不可能。（电脑思考时间不超过5秒）JS版中国象棋程序搜索层次也就是4-8层。这种较低层次下，置换表作用不大。我最开始提到的那个JS中国象棋，我下载代码后，把它的置换表注释掉，结果发现对速度影响并不大。而MTD(f)算法是更高级的技术了，我不打算考虑使用。我使用了历史启发和杀手启发，目前我6层搜索要查看到近100万的分支，耗时在10秒左右。开局、中局阶段每一步大约有40种走法，如果能在8次内找到最佳走法，6层搜索查到的分枝不到30万，剩下的都被剪了。如果在10次内找到最佳走法，那么要查找的分枝就是100万。我觉得自己的算法不好但也不太差。但10秒的用时太长了，我的目标是控在5秒内，最好是3秒左右，但必需保证6层搜索。我想在getMoves方法上下功夫，但我发现在编程中，无非就是空间换时间，但100万的分支，光是用来存贮mvs，就是惊人的空间消耗！我觉得自己已经技穷了。。

Answer 3

通过优化数组，6层用时减到7秒以下。这是在开局情况下，中局阶段棋子数量减少搜索用时也大幅减少。勉强能达到要求了。如果需要还可以把置换表再加上去。大家可以看看我写的文章：https://blog.csdn.net/Win32FanEx/article/details/89712719

Answer 4

加上置换表了，现在搜索6层（三个回合）平均用时低于10秒了。在速度上依然没法与开头我提到的JS象棋相比。我也研究了下它的代码，发现：
1. 双方在最基础的步法获取getMoves性能上是接近的，连续执行100万次，我的用时仅比它多数百毫秒。
2.我对搜索方法进行了尽可能优化，在alpha-beta方法里采用了杀手表及历史表启发。它的代码里诸如空着裁剪之类的技术被我注释掉了，仅保留杀手表及历史表。不同的是我对静态评分函数进行了精简，在消除水平线效应前提下，尽可能减少分枝。
3.在同样棋局下进行6层搜索，我的代码共搜索约100万个分枝，它的代码则比我多搜了二十多万分枝（它的静态评分函数未精简）。但让我搞不懂的是，它的速度反而大大快于我。目前我的代码还未做到最优化，比如车的出动速度慢，对空头炮的防御不足。但战斗力还是可观的，甚至可以做到弃大子绝杀。打败我这样的象棋菜鸟问题不大。只是在时间上让人不能完全满意。6层三回合的搜索，在电脑象棋软件里也就是最多一秒钟的事。最开头提到的那个JS象棋，我们在底层上是完全不一样的。这也是我搞不懂为啥它搜6层，分枝比我多，用时却大大小于我的原因。

Answer 5

昨天又发现一个中国象棋JS程序：
https://bbs.csdn.net/topics/390750777
下载地址：
http://download.csdn.net/detail/xzy88/7147611
这个JS象棋比较简洁易懂，从中我获得灵感，发现了我的程序和royhoo（最开头提到的）程序在底层代码上的差距，经过改进。现在我的6层搜索用时已成功降到5秒以下，和royhoo的不相上下了。我已经站到了royhoo的身后。