在当前文件夹下打开终端，输入python3 -m serv/可以在本地运行一个服务器，然后在浏览器上输入并打开网址127.0.0.1:8000，就可以下棋了。红方为玩家，黑方为电脑。

电脑默认的搜索时间为8秒（一般会严重超过这个时间），如果嫌下棋速度太慢，可以在web/py_lib/auto_chess2.py文件夹里找到auto_move函数，找到board_explore = BoardExplore(board, 8)，这里的第二个值“8”就是搜索时间，单位是秒。一般来说，搜索时间越长电脑越“聪明”（至少要搜索五步才不会那么傻，搜索六步才会比较聪明）。搜索时间为8秒（实际为十几秒）时程序的棋力略大于中级难度的电脑。

象棋巫师：https://www.xqbase.com/computer.htm

象棋wiki(Chess Programming wiki)：https://www.chessprogramming.org/Main_Page

np问题：http://www.matrix67.com/blog/archives/105

alphabeta剪枝法：

pvs(主要変例搜索，alphabeta的变种)法：

蒙特卡洛搜索树：

评估函数的设计：https://www.xqbase.com/computer/evalue_intro1.htm

置换表：https://www.xqbase.com/computer/search_hashing.htm

置换表中胜利条件的设置：https://www.xqbase.com/computer/other_winning.htm

由于alpha-beta，pvs等搜索方法要求比较好的着法的顺序(即前几个着法就可以得到本节点的界限值)，因此需要对着法进行排序。着法排序的方式也称为启发式。

静态启发搜索：吃子的着法大概率比不吃子的好，这里使用Mvv/Lva(最有价值受害者/最小没价值攻击者，Most Valuable Victim/Least Valuable Attacker)的评估方法对所有吃子着法进行评估。评估方法是：如果被吃的棋子没有被保护，那么该走法的分数是被吃的棋子子力值；如果被吃的棋子有被保护，那么分数就为被吃的棋子子力值减去移动的棋子子力值。在我的程序里，棋子的子力值包括了棋子的固定子力值和位置值，具体可以看sortCapMove函数。

动态启发搜索：

如果搜索深度是固定的，那么到达搜索深度后进行评分往往得不到准确的值，甚至有可能会得到错误的分数。例如搜索到最后一层时，假如此时有被将军或者其他棋子有被抓到的情况，此时对棋盘进行评分会得到一个错误的值（评分只统计局面上棋子的子力之和）。这种情况被称为水平线效应。为了避免这种情况，一般会用几种方法让搜索深度动态变化（使搜索变得更深）。

由于将军延伸和静态搜索在长将解将时会永远搜索下去，因此需要引入重复局面判断和最大搜索深度的限制。

这里我们假设分数总范围为[-10000, 10000]，那么就有以下的分布情况。

将胜利分数这么划分的原因是：

因此我们可以总结出，浅层搜索得到的胜利要比从深层搜索里得到的胜利好，非长将胜利要比长将胜利好。

因此，对于胜利分数，我们需要进行分数修正。

代码里的WIN_VALUE=9800即为极大值方胜利分数的下界，BAN_VALUE=9900即为长将分数的上界，取反就是极小值方相应的界限。

对于平局分数，可以看这篇文章里的内容：https://www.xqbase.com/computer/other_contempt.htm

置换表的分数修正：当使用置换表裁剪时，对于一个胜利分数，由于取出信息的时候，当前节点距离根结点的深度大概率是不等于置换表里节点距离根结点的深度的，如果还使用存入置换表里的已经做过处理的分数，那么肯定是有误的。因此当胜利分数存入置换表时，分数要加回存入时节点距离根结点的深度（极小值方就减去）。取出时，对于胜利分数，要减去取出时节点距离根结点的深度（极小值方要加上）。

注：如果根结点也使用了置换表裁剪，那么是有可能得到10000和-10000分数的（置换表里有根结点局面的信息，并且是胜利分数，且迭代加深还处于比较浅的时候）。

在使用置换表裁剪时，要根据表中记录的节点类型，决定是否能够使用裁剪。一共有三种类型的节点，alpha，beta和pv节点。对于极大值方玩家来说，alpha节点是指其分数不会超过所记录的分数，beta节点是指其分数不会低于所记录的分数，而pv节点则是指其分数刚好为所记录的分数。极小值方玩家的alpha节点是不会低于所记录的分数，beta节点是指其不会超过所记录的分数。

以下均以极大值方的视角阐述三种节点是如何在搜索过程中找到的。在alphabeta或者pvs搜索中，只要其某一个子节点的分数不小于规定的beta上界，那么此节点就为beta节点；搜索完所有子节点，如果得到的最大分数依然不大于alpha下界，那么这个节点就是alpha节点，而如果得到的最大分数在(alpha, beta)（注意是开区间）中，那么这个节点就是pv节点。

相应的，每一种类型节点的下法也有不同的保存情况，一般来说，只有beta节点和pv节点的节点会统计最好下法。这是因为对于极大值方，只有提高下界或者稳定的下法才有意义。相应的，对于极小值方只有降低上界和稳定的下法才有意义。beta节点的下法就是一种会提高下界（极大值方）或降低下界（极小值方）的下法。pv节点的下法是一种稳定得分的下法。而对于alpha节点，我根据“象棋巫师”网站的说法，也保存进了置换表中，搜索深度为0（见置换表更新的算法流程图）。这样除非alpha节点的分数是非长将的胜利分数，否则不会参与置换裁剪，当时它能提供一个不错的下法。

有些资料（wiki）里，alphabeta搜索可以看到有两种变型，一种是fail hard，即只会返回不超过beta值（极大值方）或alpha值（极小值方）的分数；一种是fail soft，会返回超过beta或alpha值的分数。这里我倾向于用fali soft方案。因为后面的置换表需要一些更加精确的值，因此还是fail soft好。

此外，这里要说明一个情况，即如果有几个走法得到了相同的分数，那么最早得到的那个下法一定是最好的。

图中绿色正方形为极大值方节点，蓝色圆形为极小值方节点。对于节点B，已经得到了一个子节点A的分数，因此确定了取值范围为[0, +∞]。此时对于子节点C，当它搜索到子节点D时，发现分数刚好等于0，那么此时C节点就触发了beta截断，成为了一个beta节点。这里我们可以看出，虽然A和C节点返回的分数都是一样的，但是由于C节点是个beta节点，它可能有更坏的情况。而对于A节点，其搜索时取值范围肯定是不小于C，所以A返回的分数更有可能接近精确值，因此越早搜索得到的下法，一定是更好的。

这里我直接套用了“象棋巫师”的子力数组。同时我发现电脑下棋比较喜欢下“窝心马”，因此我单独给出现窝心马的情况扣了分。