搜索算法
简单Minimax搜索
象棋属于零和博弈，有红方和黑方，双方的收益总和为0，一方的优势总是伴随着另一方的劣势。此时，我们可以使用Minimax进行搜索。
为了方便理解，我们暂且把Maximizing Player称为“红方”，把Minimizing Player称为“黑方”（实际上则不一定），我们的评估函数暂时返回的是相对于红方的分数（分高说明红方优势，分低说明红方劣势）。
博弈的双方都想让收益最大化，红方想让分数尽量高，黑方想让分数尽量低，这样就能最大程度上保证自己这方的优势，同时让对方占到的优势最小。
举个例子，红方在一个局面有两种走法。一种走法可以吃掉对方的车，此时的分数是+500，另一种走法是送掉自己的车，此时的分数是-500。红方当然会选择对自己有利的走法，即第一种，所以该节点的分数就是+500。
伪代码如下：
int minimax(int depth, bool isMaximizingPlayer) { // 层数, 是否红方
if (depth == 0 || isGameOver()) { // 搜索到叶子节点或游戏结束，直接返回评估
return evaluate();
}
if (isMaximizingPlayer) { // 如果当前是红方
int maxEval = INT_MIN; // 初始化为负无穷，方便程序找出所有走法中分数的最大值
for (Move move : getPossibleMoves()) { // 走法生成
makeMove(move); // 走子
int eval = minimax(depth - 1, false); // 向下一层搜索，获得该走法对应的子节点的分数
undoMove(move); // 恢复到走子前的局面
maxEval = std::max(maxEval, eval);
}
return maxEval;
} else { // 如果当前是黑方
int minEval = INT_MAX; // 初始化为正无穷，方便程序找出所有走法中分数的最小值
for (Move move : getPossibleMoves()) { // 走法生成
makeMove(move); // 走子
int eval = minimax(depth - 1, true); // 向下一层搜索，获得该走法对应的子节点的分数
undoMove(move); // 恢复到走子前的局面
minEval = std::min(minEval, eval); // 取最小值
}
return minEval;
}
}
Alpha-Beta剪枝的过程介绍
上面实现的简单Minimax搜索，效率其实是很低的。我们这时就要引入一种新的搜索策略——Alpha-Beta剪枝，这种剪枝方法可以在不改变结果的前提下大大减少搜索的节点数。
上文我们提到过，红方的目的是使得分尽量高，也就是说当前节点的分数是所有子节点分数的最大值，黑方则相反。
参考右图，我们可以举个例子说明一下Alpha-Beta剪枝的原理。
引擎搜完叶子节点的5和6，可以推断出这两个节点的父节点（图中ID：2）的分数是min(5,6)=5。这个节点的父节点在MAX层上（图中ID：1），是取其子节点分数的最大值，所以它的分数至少是5。子节点的分数只有>5才有搜下去的必要，否则不会比“ID：2”这一路线更优。
接下来我们继续搜索“ID：3”这一路线，搜完叶子节点的“7”和“4”之后，由于“ID：3”处在MIN层，其分数是取其子节点分数的最小值，所以这个节点的分数必然≤4，不可能比“ID：2”这一条路线更优，没有再搜下去的必要了，我们可以把后续的子节点（即灰色的5）剪掉。
其它灰色的部分也是同理，大家可自行按照上面的步骤推断。
根据理论推断是会了，但这仍是纸上谈兵，如何编写相关代码实现该功能呢？且听下回分解。
Alpha-Beta剪枝的代码实现
为了用代码实现Alpha-Beta剪枝，我们需要引入alpha和beta两个量，alpha是红方能保证至少获得的分数，beta是黑方能保证至多获得的分数（这里的分数都是从红方视角看的）。也就是说，最优走法的分数必然≥alpha而且≤beta。
在最开始调用“alphaBeta”函数的时候，我们应该把alpha设为负无穷，把beta设为正无穷。
当我们搜索一个节点的时候，我们需要接受从父节点传来的alpha和beta值，接着判断该节点处于MAX层还是MIN层。
这里还是举一个例子方便读者理解，假设我们处于MAX层（即红方），父节点传递的alpha值是5，beta值是8。
因为当前节点的分数是从子节点的分数中取最大值得到的，所以我们在搜索的时候可以保证当前节点的分数≥子节点的分数，应该根据子节点的分数更新alpha的值。如果我们此时搜到一个子节点，分数为10，此时当前节点的分数必定≥10。但我们不要忘了，上一层是MIN，取的是子节点中的最小分数。若当前节点的分数超过了beta，必然不会比其父节点之前搜过的某个子节点分数低，不会被父节点采纳；若当前节点的分数等于beta，必然不会比其父节点之前搜过的某个子节点更优。我们可以直接使用break跳出循环，进行Beta剪枝，同时返回目前搜过的子节点的最大分数（目前的搜索代码中，这里返回值不重要，只需要保证该节点不被父节点采纳即可）。
判断当前节点的分数是否≥beta，可以等同于判断alpha≥beta，因为alpha就是按照子节点的分数通过取最大值进行更新的。
MIN层同理，这里不再赘述。
伪代码如下：
int alphaBeta(int depth, int alpha, int beta, bool isMaximizingPlayer) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
if (isMaximizingPlayer) { // 如果当前是红方
int maxEval = INT_MIN; // 初始化为负无穷，方便程序找出所有走法中分数的最大值
for (Move move : getPossibleMoves()) { // 走法生成
makeMove(move); // 走子
int eval = alphaBeta(depth - 1, alpha, beta, false); // 向下一层搜索，获得该走法对应的子节点的分数
undoMove(move); // 恢复到走子前的局面
maxEval = std::max(maxEval, eval); // 取最大值
alpha = std::max(alpha, eval);
if (beta <= alpha)
break; // Beta剪枝
}
return maxEval;
} else { // 如果当前是黑方
int minEval = INT_MAX; // 初始化为正无穷，方便程序找出所有走法中分数的最小值
for (Move move : getPossibleMoves()) { // 走法生成
makeMove(move); // 走子
int eval = alphaBeta(depth - 1, alpha, beta, true); // 向下一层搜索，获得该走法对应的子节点的分数
undoMove(move); // 恢复到走子前的局面
minEval = std::min(minEval, eval); // 取最小值
beta = std::min(beta, eval);
if (beta <= alpha)
break; // Alpha剪枝
}
return minEval;
}
}