中国象棋项目中的极大值，极小值算法以及α-β剪枝技术技术 极大值，极小值算法1. 问题提出2. 代码实现 α-β剪枝优化1. 代码实现，注意和上面的代码进行比较（其实差别并不大）2. 代码分析3.其他可优化点
极大值，极小值算法 1. 问题提出
在中国象棋的人机对战模块的开发中，对于电脑如何选择下一步要走的棋时，首先很自然的想到要设立一个估值函数，然后暴力遍历所有可以移动的己方棋子以及每个棋子可以移动的目标位置，找到一个移动后估值函数值最大的移动方式。这里的估值函数最开始只是简单的为每颗棋子固定的设置不同的价值，然后用己方棋子价值之和减去对方棋子价值之和的最大值作为估值函数的返回值。这种方式效果很差，电脑在走的时候老是容易在原地打转，其实对比我们平常下棋就可以发现，我们在每走一步时，都会思考对方会怎么走，我们吃掉对方的一个棋子，会不会反而损失更多，总而言之，就是人会考虑多步，而我们只让电脑考虑了一步，那么就想到让电脑也考虑多步，可是要如何来实现呢？我们仔细分析一下，我们走棋（正常人下棋，不说cxddw）是要尽量可以吃掉对方的棋，然后让对方无法吃掉自己的棋，换句话说，就是我们选择时尽量得到最高的分，并且让对方得到尽量小的分，这就引出了极大值，极小值算法，在对方作出的所有对它自己价值大的选择中（意味着对己方价值小，或者为负）的选择中选择一个对自己价值最大的。
2. 代码实现
（1）需要考虑多少层
（2）递归调用终止条件
（3）求最大值(getMaxScore)和求最小值(getMinScore)函数中会调用getAllPossible函数，而这个函数会根据被谁调用内部会有不同的处理方式，因为求最大值相当于己方走一步棋，而求最小值相当于对方走一步棋（对于本项目，内部是根据该红棋走还是黑棋走返回对应的可能步骤）
（4）在最顶层之上，还应该有一个函数getBestStep开始去调用getMaxScore函数，并传入初始层级（对于本项目，这个函数会返回一个表示最佳选择的step，而不是一个分数）
（5）在本项目中，因为人走完一步后，电脑会立刻去计算它需要走的一步，如何考虑的层级较高，则会阻塞前端的渲染，解决方案为延时一点时间（使用定时器实现）再让电脑去计算（或者还可以考虑使用子线程）
//step是代表一步棋int getMaxScore(int level){//层级为0，直接计算当前分数返回if(level == 0) return calcScore();vector<step*> steps;//存放所有可能的走法getAllPossibleStep(steps);//获取所有可能的走法并放到steps中//step * res;//保存返回值int maxScore = int(1<<31);//保存最大分数for(auto it = steps.begin(); it != steps.end(); it++){step * cur = *it;fakeMove(step);//尝试去走某一步int score = getMinScore(level-1);//走完某一步后计算得分unFakeMove(step);//把这一步退回来if(score > maxScore){maxScore = score;}}return maxScore;}//取得最小分数函数和取得最大分数函数基本一样int getMinScore(int level){//层级为0，直接计算当前分返回if(level == 0) return calcScore();vector<step*> steps;//存放所有可能的走法getAllPossibleStep(steps);//获取所有可能的走法并放到steps中//step * res;//保存返回值int minScore = int(~(1<<31));//保存最大分数for(auto it = steps.begin(); it != steps.end(); it++){step * cur = *it;fakeMove(step);//尝试去走某一步int score = getMaxScore(level-1);//走完某一步后计算得分unFakeMove(step);//把这一步退回来if(score < maxScore){maxScore = score;}}return minScore;} α-β剪枝优化 1. 代码实现，注意和上面的代码进行比较（其实差别并不大） int getMaxScore(int level, int currentMin){//层级为0，直接计算当前分返回if(level == 0) return calcScore();vector<step*> steps;//存放所有可能的走法getAllPossibleStep(steps);//获取所有可能的走法并放到steps中//step * res;//保存返回值int maxScore = int(1<<31);//保存最大分数for(auto it = steps.begin(); it != steps.end(); it++){step * cur = *it;fakeMove(step);//尝试去走某一步int score = getMinScore(level-1);//走完某一步后计算得分unFakeMove(step);//把这一步退回来//剪枝代码，注意等号（有没有等号对最后的选择出来的结果都是不可控的，因为处理//各个情况的顺序无法控制，或者说无法确定得分相同的两种情况到底哪个好，所以//使用等号反而会提高一些效率，//因为我们在计算时棋子的类别并不多，这个分数很有可能相等）if(score >= currentMin){return score;}if(score > maxScore){maxScore = score;}}return maxScore;}//取得最小分数函数和取得最大分数函数基本一样int getMinScore(int level, int currentMax){//层级为0，直接计算当前分返回if(level == 0) return calcScore();vector<step*> steps;//存放所有可能的走法getAllPossibleStep(steps);//获取所有可能的走法并放到steps中//step * res;//保存返回值int minScore = int(~(1<<31));//保存最大分数for(auto it = steps.begin(); it != steps.end(); it++){step * cur = *it;fakeMove(step);//尝试去走某一步int score = getMaxScore(level-1);//走完某一步后计算得分unFakeMove(step);//把这一步退回来if(score <= currentMax){return socre;}if(score < maxScore){maxScore = score;}}return minScore;} 2. 代码分析
相比较与未优化状态，只是多了一个参数，多了一个判断。为什么可以直接剪掉呢？
首先，我们需要明确一点，对分数的计算是在最底那一层进行的（也就是level等与0的时候），就好比一个树的结构中的叶子节点，计算结果一层一层往上送，在送的过程中一层一层比较，未经剪枝的时候，所有的叶子节点都会被计算，然后往上送，进行比较，选出最大值或最小值继续往上送，直到递归起点，即获得所需的得分最好的走法。而剪枝剪掉的就是不必要的计算，因为这里的递归是一次到底后进行计算，然后回溯，再到底进行计算，这样的话，叶子节点的计算并没有连续进行，中间有一个回溯的过程。
（1）在求最大值函数中调用求最小值和函数，向其中传入一个当前的最大值，在求最小值函数中，若得到下层送上来的某个分数小于传入的最大值，则可以肯定在求最小值函数中的下层递归求解过程可以被剪掉，因为求最小值函数返回的值肯定不会大于那个比传入的最大值小的值。
（2）在求最小值函数中调用求最大值的函数，向其传入一个当前的最小值，在求最大值的函数中，若得到下层传上来的值大于传入的最小值，则可以肯定在求最大值函数中的下层递归求解过程可以被剪掉，因为要递交给上层求最小值函数一个自己的最大值，而这个最大值肯定不会小于那个比传入的最小值大的值，那么在求最小值的函数中肯定不会被使用。
3.其他可优化点
（1）若对当前层所有可能的情况以某种方式进行排序，使得可以更早的得到需要返回的值，那么在调用下一层时可以得到更好的剪枝效果。（具体的可以在求所有情况的函数中，遍历棋子的顺序作出调整，比如说车所有可以走的步先与兵所有可走的步放入下一步集合中，其实这个做的更细的话，应该结合估值函数来进行调整，有点像在中间层先简易的使用一下估值函数）。
（2）对估值函数的优化，原程序中每个棋子设定固定的分值，其实在不同的局势下，棋子应该有不同的价值，对其进行调整，应该能得到更好的选择。
（3）判断某个棋子是否可以移动到某个位置时用到的函数应该可以优化，以提高判断的效率，在获取所有可能步骤的时候，对于不同的棋子，可以确定它不能走到某个位置，那么可以直接过滤掉，而不是调用判断是否可以移动的函数，用填充的方法（而非遍历）去获取所有可能的移动步骤。