Search Algorithms
Simple Minimax search
Xiangqi is a zero-sum game with a Red side and a Black side. The payoffs of the two sides sum to 0, so one side's advantage always comes with the other side's disadvantage. In this case, we can search with Minimax.
To make things easier to understand, let's call the Maximizing Player "Red" and the Minimizing Player "Black" (in practice this is not necessarily so), and for now let our evaluation function return the score from Red's point of view (a high score means Red is ahead, a low score means Red is behind).
Both sides want to maximize their payoff: Red wants the score as high as possible and Black wants it as low as possible. This secures the largest possible advantage for one's own side while leaving the opponent the smallest advantage.
For example, in some position Red has two possible moves. One captures the opponent's Chariot, giving a score of +500; the other gives away Red's own Chariot, giving a score of -500. Red will of course choose the move that favors itself, the first one, so this node's score is +500.
The pseudocode is as follows:
int minimax(int depth, bool isMaximizingPlayer) { // depth (plies), whether it is Red's turn
if (depth == 0 || isGameOver()) { // reached a leaf node or the game is over: return the evaluation directly
return evaluate();
}
if (isMaximizingPlayer) { // if it is Red's turn
int maxEval = INT_MIN; // initialize to negative infinity so the program can find the maximum score among all moves
for (Move move : getPossibleMoves()) { // move generation
makeMove(move); // make the move
int eval = minimax(depth - 1, false); // search one level deeper to get the score of the child node for this move
undoMove(move); // restore the position before the move
maxEval = std::max(maxEval, eval);
}
return maxEval;
} else { // if it is Black's turn
int minEval = INT_MAX; // initialize to positive infinity so the program can find the minimum score among all moves
for (Move move : getPossibleMoves()) { // move generation
makeMove(move); // make the move
int eval = minimax(depth - 1, true); // search one level deeper to get the score of the child node for this move
undoMove(move); // restore the position before the move
minEval = std::min(minEval, eval); // take the minimum
}
return minEval;
}
}How Alpha-Beta pruning works
The simple Minimax search implemented above is actually very inefficient. This is where we introduce a new search strategy, Alpha-Beta pruning, which greatly reduces the number of nodes searched without changing the result.
As mentioned above, Red's goal is to make the score as high as possible, which means the score of the current node is the maximum of all its child nodes' scores; for Black it is the opposite.
Using the figure above, we can illustrate the principle of Alpha-Beta pruning with an example.
After the engine has searched the leaf nodes 5 and 6, it can infer that the score of their parent node (ID: 2 in the figure) is min(5,6) = 5. The parent of this node is on a MAX level (ID: 1 in the figure), which takes the maximum of its children's scores, so its score is at least 5. A child node is only worth searching further if its score is > 5; otherwise it cannot be better than the "ID: 2" line.
Next we continue with the "ID: 3" line. After searching its leaf nodes "7" and "4", since "ID: 3" is on a MIN level and takes the minimum of its children's scores, this node's score must be ≤ 4. It cannot be better than the "ID: 2" line, so there is no need to search further, and we can prune the remaining child nodes (the gray 5).
The other gray parts work the same way; you can work them out yourself by following the steps above.
That covers the theory, but it is still armchair strategy. How do we write code to implement it? Read on.
Implementing Alpha-Beta pruning in code
To implement Alpha-Beta pruning in code, we need to introduce two values, alpha and beta. Alpha is the score Red can guarantee to obtain at least, and beta is the score Black can guarantee to obtain at most (all scores here are from Red's point of view). In other words, the score of the best move must be ≥ alpha and ≤ beta.
When we first call the "alphaBeta" function, we should set alpha to negative infinity and beta to positive infinity.
When searching a node, we receive the alpha and beta values passed down from the parent node, and then determine whether the node is on a MAX level or a MIN level.
Here is another example to help the reader. Suppose we are on a MAX level (that is, Red), and the alpha value passed down from the parent is 5 and the beta value is 8.
Because the current node's score is obtained by taking the maximum over its child nodes' scores, during the search we can be sure that the current node's score is ≥ each child node's score, and we should update alpha according to the children's scores. If we now find a child node with a score of 10, the current node's score must be ≥ 10. But don't forget that the level above is MIN, which takes the minimum score among its children. If the current node's score exceeds beta, it cannot be lower than the score of some child the parent has already searched, so the parent will not adopt it; if the current node's score equals beta, it cannot be better than some child the parent has already searched. We can simply use break to exit the loop and perform Beta pruning, returning the highest score among the children searched so far (in the current search code the return value here doesn't matter; all that's needed is to make sure this node is not adopted by the parent).
Checking whether the current node's score is ≥ beta is equivalent to checking whether alpha ≥ beta, because alpha is updated by taking the maximum of the children's scores.
The MIN level works the same way, so it is not repeated here.
The pseudocode is as follows:
int alphaBeta(int depth, int alpha, int beta, bool isMaximizingPlayer) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
if (isMaximizingPlayer) { // if it is Red's turn
int maxEval = INT_MIN; // initialize to negative infinity so the program can find the maximum score among all moves
for (Move move : getPossibleMoves()) { // move generation
makeMove(move); // make the move
int eval = alphaBeta(depth - 1, alpha, beta, false); // search one level deeper to get the score of the child node for this move
undoMove(move); // restore the position before the move
maxEval = std::max(maxEval, eval); // take the maximum
alpha = std::max(alpha, eval);
if (beta <= alpha)
break; // Beta pruning
}
return maxEval;
} else { // if it is Black's turn
int minEval = INT_MAX; // initialize to positive infinity so the program can find the minimum score among all moves
for (Move move : getPossibleMoves()) { // move generation
makeMove(move); // make the move
int eval = alphaBeta(depth - 1, alpha, beta, true); // search one level deeper to get the score of the child node for this move
undoMove(move); // restore the position before the move
minEval = std::min(minEval, eval); // take the minimum
beta = std::min(beta, eval);
if (beta <= alpha)
break; // Alpha pruning
}
return minEval;
}
}Simplifying further: introducing Negamax
So far our scores have been from Red's point of view, which forces us to handle Red and Black separately and obviously complicates the code. To solve this, we introduce Negamax.
With Negamax, we can use the same handling for both sides, so there is no need to write separate code for the MIN side, but the evaluation function must be changed to return the score relative to the side to move.
If the side to move is Red, it must return the score relative to Red; if it is Black, it must return the score relative to Black.
Since we have merged the two cases into one, the parameter that distinguishes Red from Black can be removed.
When searching child nodes, we need to switch from a MAX level to a MIN level, or from MIN to MAX. How do we do that?
Let's continue with an example. Suppose the current node received an alpha of 5 and a beta of 8 from its parent, meaning the score of the best move must be between 5 and 8. Now we switch the score perspective to the opponent: the score of the best move must be between -8 and -5, and -8 and -5 are exactly the alpha and beta values passed to the child node.
So the alpha and beta passed to the child node should be -beta and -alpha.
Here is the pseudocode after introducing Negamax:
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
int maxEval = INT_MIN; // initialize to negative infinity so the program can find the maximum score among all moves
for (Move move : getPossibleMoves()) { // move generation
makeMove(move); // make the move
int eval = -alphaBeta(depth - 1, -beta, -alpha); // search one level deeper to get the score of the child node for this move
undoMove(move); // restore the position before the move
maxEval = std::max(maxEval, eval);
alpha = std::max(alpha, eval);
if (alpha >= beta)
break; // Beta pruning
}
return maxEval;
}Some references may give the code like this:
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
for (Move move : getPossibleMoves()) {
makeMove(move);
int val = -alphaBeta(depth - 1, -beta, -alpha);
undoMove(move);
if (val >= beta) {
return beta; // Beta pruning
}
if (val > alpha) {
alpha = val; // update the value of Alpha
}
}
return alpha;
}The two are actually equivalent. Normally alpha < beta, so the only way to get alpha ≥ beta is for the score update to raise alpha, which triggers Beta pruning; comparing directly against val is therefore the same thing.
Null Move Pruning
Generally speaking, in a position, if our side does nothing (that is, plays a "null move") and hands the move to the opponent, we are at a disadvantage. In other words, the score of the best move is generally not lower than the score of the "null move".
We can use this to write a pruning strategy: null move pruning. It is a risky strategy built on the assumption above: it prunes moves that score lower than the "null move".
To speed up the search, we can additionally reduce the depth of the "null move" search by R (generally 2-3) plies. Since we only care whether the null move's score is larger or smaller than beta, we should use a zero-window search ([beta - 1, beta]), which lets Alpha-Beta pruning do the most work when searching the null move.
Because the side to move is swapped, the alpha and beta values passed to the child node must also be converted in the way described before, that is, -beta and -beta + 1.
Based on the assumption that the null move's score ≤ the best move's score: if the returned evaluation is ≤ beta - 1, this node's alpha may still fail to reach beta later, so we don't prune; if the returned evaluation is ≥ beta, the best move's score must also be ≥ beta, which means that when alpha is updated later it will also be ≥ beta, so we can prune right away.
However, some positions do not satisfy the assumption mentioned above, such as zugzwang positions in chess. Using null move pruning there makes the engine misjudge, so we can design an "isNullMoveAllowed" function to check whether the conditions for null move pruning are met, in order to avoid this as much as possible.
The pseudocode is as follows:
// R is the number of extra plies subtracted in the null move pruning search
const int R = 3;
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
// Null Move Pruning
if (depth >= R + 1 && isNullMoveAllowed()) {
makeNullMove(); // play a "null move"
int nullMoveEval = -alphaBeta(depth - R - 1, -beta, -beta + 1); // search with [beta - 1, beta]
undoNullMove(); // restore
if (nullMoveEval >= beta) {
return beta; // if beta is not even as high as the "null move" score, prune directly
}
}
int value = INT_MIN;
for (Move move : getPossibleMoves()) { // move generation
makeMove(move); // make the move
value = std::max(value, -alphaBeta(depth - 1, -beta, -alpha));
undoMove(move); // restore
alpha = std::max(alpha, value);
if (alpha >= beta) {
break; // Beta pruning
}
}
return value;
}PVS (Principal Variation Search)
PVS is an enhancement of Alpha-Beta pruning that improves its efficiency. Simply put, PVS first searches the first child node with the full window [alpha, beta], and then searches the remaining child nodes with the zero window [alpha, alpha+1]. After a zero-window search, if the evaluation returned for that node is between (alpha, beta), the node looks promising, so a full-window search is run again. If the returned evaluation falls outside (alpha, beta), the node is certain to be pruned.
The pseudocode is as follows:
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return evaluate();
}
int maxEval = INT_MIN; // initialize to negative infinity so the program can find the maximum score among all moves
bool firstChild = true; // flag for whether this is the first child node
for (const Move& move : getPossibleMoves()) { // move generation
makeMove(move); // make the move
int eval;
if (firstChild) {
// use a full-window search for the first child node
eval = -alphaBeta(depth - 1, -beta, -alpha);
firstChild = false;
} else {
// use a zero-window search for the remaining child nodes
eval = -alphaBeta(depth - 1, -alpha - 1, -alpha);
if (eval > alpha && eval < beta) {
// if the zero-window search could not prune with certainty, re-search with the full window
eval = -alphaBeta(depth - 1, -beta, -eval);
}
}
undoMove(move); // restore the position before the move
maxEval = std::max(maxEval, eval);
alpha = std::max(alpha, eval);
if (alpha >= beta) {
break; // Beta pruning
}
}
return maxEval;
}Note
To keep the code simple, null move pruning is not included here; likewise, each method below is introduced on its own rather than stacked on top of the others.
Quiescence search
Quiescence search can be used to overcome the horizon effect. Generally, when pieces are exchanged, the evaluation function changes drastically; introducing quiescence search lets us return a more stable evaluation. With it, when we reach a leaf node we do not return the evaluation function's value directly, but instead run a quiescence search that keeps exploring capturing moves.
The pseudocode is as follows:
int qsearch(int alpha, int beta) {
int standPat = evaluate(); // evaluation of the current position if no action is taken
if (standPat >= beta) {
return beta; // pruning
}
if (alpha < standPat) {
alpha = standPat; // update alpha
}
for (Move move : getPossibleCaptures()) { // consider only capturing moves
makeMove(move);
int eval = -qsearch(-beta, -alpha); // quiescence search one level deeper
undoMove(move);
if (eval >= beta) {
return beta; // pruning
}
if (eval > alpha) {
alpha = eval; // update alpha
}
}
return alpha;
}
int alphaBeta(int depth, int alpha, int beta) {
if (depth == 0 || isGameOver()) {
return qsearch(alpha, beta); // enter quiescence search at depth 0 or when the game is over
}
int maxEval = INT_MIN; // initialize to negative infinity
for (Move move : getPossibleMoves()) { // generate all moves
makeMove(move); // make the move
int eval = -alphaBeta(depth - 1, -beta, -alpha); // recursive search
undoMove(move); // undo the move
maxEval = std::max(maxEval, eval);
alpha = std::max(alpha, eval);
if (alpha >= beta) {
break; // Beta pruning
}
}
return maxEval;
}