This article code: github.com/ParadeTo/ch…

Demo address: www.paradeto.com/vue-chinese…

At the end of the last article, I mentioned that there is room for further optimization of the Max/min algorithm.

Alpha beta – pruning

At the end of the previous article, it was mentioned that when the search depth of Max/min algorithm increases, its computational complexity will increase sharply. If there was a way to get rid of some branches, the algorithm would be more efficient, and that’s where alpha-beta pruning comes in. But instead of talking about the algorithm, let’s play the same game again.

There are two big bags, and inside each big bag are two small bags, each of which contains a different number of gold coins.

First, after walking through the bag on the left, the maximum you can currently achieve is three coins:

Then, when I we traverse to the right of the first small bag, because of its gold number is less than your current can achieve maximum benefits, so your opponent can not traverse the other bag, because this little bag is enough to make you give up to choose the right of the big bag, so when the opponent chooses gold for 2 small bag as its result can be:

Finally, you choose the bag on the left:

The above process is essentially max-min algorithm plus alpha-beta pruning. The idea of alpha-beta pruning is embodied in the way that the opponent stops traversing the remaining bags while traversing the large bag on the right.

Let’s talk about alpha-beta pruning. In alpha-beta pruning algorithm, we define:

  • Alpha records the maximum score currently available for a node in the maximum layer
  • The beta record is the minimum score currently available for the node of the minimum level

When the beta of a node in the minimum layer is less than alpha, the search for the remaining children of that node can be stopped. When alpha of a node in the maximum layer is greater than beta, the search for the remaining children of that node can be stopped.

I’m sure you don’t understand. Here’s an example.

  1. Initialize the root node alpha to -∞ and beta to +∞, and pass it all the way to the second-to-last row on the left.

  1. Iterate through the first child node, updating alpha to 4, and updating the current node value to 4. Determine if pruning is required (compare the alpha and beta of the current node and find that 4 is less than +∞ and cannot be pruned).

  1. Iterate through the second child node, updating alpha to 6 and updating the current node value to 6. Determine if pruning is required (compare alpha and beta of the current node and find that 6 is less than +∞, cannot be pruned).

  1. Return 6 to the previous level, update the beta of the first node to the left of the minimum level to 6, and update the current node value to 6. Determine whether pruning is required (compare the current node’s beta and alpha, find that 6 is greater than -∞, cannot be pruned).

  1. Pass alpha=-∞, beta=6 to the child node on the right, continue traversing the node where 7 is, update alpha to 7, and set the value to 7. Determine whether pruning is required (compare the beta and alpha of the current node and find that 6 is less than 7, which meets the pruning condition.

  1. Return 7 to the previous level without updating.

Without further elaboration, the reader can try to complete the rest for himself. The result is this:

To better understand:

Function alphabeta(node, depth, α, β, maximizingPlayer)is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    ifMaximizingPlayer then value := −∞for each child of node do
            value := max(the value, alphabeta (child, the depth -1, alpha, beta, FALSE) alpha :=max(alpha, value)ifAlpha or beta thenbreak(* beta cut - off *)return value
    elseValue: = + upfor each child of node do
            value := min(the value, alphabeta (child, the depth -1, alpha, beta, TRUE)) beta :=min(beta, value)ifAlpha or beta thenbreak(* alpha cut - off *)return value
Copy the code

These are the rules for alpha-beta pruning. Even if you subtract a few branches from each node, the speed optimization is very obvious.

The parallel search

Another optimization idea is parallel computing, which divides the moves generated each time into multiple tasks for parallel processing, and each parallel task generates local optimal solutions respectively. Finally, the global optimal solution can be summarized. One subtask for each move is the fastest, but if this is the case for each layer, the number of subtasks will be so large that it is impractical to implement either multi-process or multi-thread, so you need to limit the depth of parallel processing. Even enabling parallel computing at just the first layer can theoretically make the computation 30 times faster (assuming that each layer produces an average of 30 moves).

conclusion

It is possible to implement a simple chess AI program using Max/min and alpha-beta algorithms, but the AI is only good enough for entry-level players. One reason is that although the optimization method mentioned above is adopted, it is found in practice that when the search depth reaches 5, the calculation time of the algorithm is unacceptably slow, and it cannot continue to improve the search depth. Another reason is that the method of situation judgment is a little simple, we can consider adding some special “sets” of chess to improve the accuracy of situation judgment. And then optimize for these problems.

reference

  1. Alpha, beta pruning

Welcome to pay attention to the public account, thank you!