不用神经网络强化学习，只用搜索实现的下象棋！我们的中国象棋使用python实现，总共2000+行代码，分为走法计算、评估函数与搜索和UI三部分，并采用历史启发算法进行优化，有着不错的效果。可以实现正常的人机对战，有着普通人的棋力。

为了方便大家下载，这里提供了两种不同下载方式。 github完整源代码下载 百度云完整源代码下载。 链接：https://pan.baidu.com/s/1OEoUUVGbI81LsaQTdSmy2Q 提取码：nmd0

搜索深度：

我们的算法在搜索深度为4的时候可以达到立刻出结果的效果，经过优化后平均搜索步数为10000左右，在搜索深度为6的时候平均搜索步数为90万左右，计算较为缓慢。深度不能太深的原因是，这个搜索算法本身就是指数级别复杂度，就算进行优化，也只能减小常数，而且评估函数复杂，所以使用这种方法深度不能太深，不然只能牺牲精度。

棋力效果：

我们设计的评估函数较为详细，考虑方面周全，基本具备一个正常人的棋力。

具体效果如下(6步时)：

更改搜索深度方式如下： 指定停止位置： 最大搜索深度

算法流程图如下： 核心代码如下：

流程图如下：

Alpha-beta搜索使用一颗n叉树来表示整个下棋的流程。电脑在选择走棋的时候，会尽可能选择对自己最有利的走法。可以通过尝试每一种走法，然后对每种局面进行比较，最终选出能够对自己最有利的走法。

在使用alpha-beta搜索算法需要遍历整个n叉树，我们可以看出搜索每迭代一层，复杂度就指数级增长。通常中国象棋合理的招数多达50种，所以每增加一层复杂度增加50倍。在搜索六步时的复杂度接近200亿，在搜索10步的时候复杂度超过几千万亿。所以搜索复杂度很高，效率较低。

象棋是博弈的过程，我们需要让自己的局面最优，让对手的局面最劣。Alpha-beta的算法就是在搜索的过程中利用已知信息进行剪枝的实现方法。它的实现基于一种想法：如果已经有选择比当下选择更好，那么只要能证明当下选择劣于某个更好选择，就可以进行剪枝，不需要对这种选择继续进行考虑。

Alpha-beta算法在搜索时，始终记录节点的α值和β值。其中α值是该节点的子节点能到达的最大值，β值是该节点的子节点能够到达的最小值。通过比较不同节点之间的α、β值来进行剪枝。例如某个子节点的得分=β时，也可以进行剪枝，因为对手可以通过之前的某种策略避免这种情况的发生。

算法核心实现如下

如一种所说，在搜索过程中需要记录节点的α值和β值。所以需要在每个叶子节点对当前局面进行评价来表示局面的优劣。评价函数的合理性将直接影响整个程序的性能。好的评价函数能够考虑到场面上的各种配合等等，从而对局面做出最正确的判断，所以在实现评价函数的时候需要考虑种种因素：

棋子的位置价值。中国象棋局势不仅仅取决于子力大小，更与棋子位置联系巨大。棋子在不同位置上应该给予不同的评价。例如卒在初始位置时，作用较小，位置值较小；而当卒进入对方九宫格之后对对方威胁极大，位置值较大。再例如，当头炮的威胁值较大，而在其他路的时候威胁则稍微小一些。因此也需要根据设计者的经验，对不同棋子不同位置的价值给予不同的评价。

棋子灵活度评估值。棋子威力的发挥取决于其灵活度。灵活度高的棋子，例如车，可以在战场上快速发挥作用，评价值较高。而灵活度较差的棋子则评分较低。

棋子威胁、保护评估值。每个棋子可能处于对方威胁下，也可能处于己放棋子保护之中。这将直接影响到这颗棋子的安全系数，进而影响战局。因此需要考虑被威胁和保护的棋子。当棋子处于威胁之中时，应当降低评价值；当棋子处于保护之中时，应当增加评价值。

我们分了不同数量保护的情况，来进行局面关系评分，核心代码如下：

将帅安全评估值。将帅的安全整局游戏的关键。需要从将的位置以及和其他棋子的位置关系中体现出来；例如当头炮、窝心马对将帅的威胁较大，体现在这些棋子的位置价值中。

既然Alpha-Beta搜索算法是在“最小-最大”的基础上引入“树的裁剪”的思想以期提高效率，那么它的效率将在很大程度上取决于树的结构——如果搜索了没多久就发现可以进行“裁剪”了，那么需要分析的工作量将大大减少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪”操作，那此时“裁剪”也已经失去了它原有的价值（因为你已经分析了所有情况，这时的Alpha-Beta搜索已和“最小-最大”搜索别无二致了）。因而，要想保证Alpha-Beta搜索算法的效率就需要调整树的结构，即调整待搜索的结点的顺序，使得“裁剪”可以尽可能早地发生。

我们可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。因为，通常当一个局面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面（如个别无关紧要的棋子位置有所不同）也是较好的。由J.Schaeffer所提出的“历史启发”（History Heuristic）就是建立在这样一种观点之上的。在搜索的过程中，每当发现一个好的走法，我们就给该走法累加一个增量以记录其“历史得分”，一个多次被搜索并认为是好的走法的“历史得分”就会较高。对于即将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法（“历史得分”高的走法）排在前面，这样Alpha-Beta搜索就可以尽可能早地进行“裁剪”，从而保证了搜索的效率。