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

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

We all know there are three steps to putting an elephant in a fridge. Similarly, writing a chess AI program takes only three steps:

  1. Walk through all the possible moves
  2. Choose the best move
  3. go

The third step here is actually just making up the numbers and can be removed to make it easier to write an AI program. It only takes two steps.

The first step is not too difficult for those with a little knowledge of chess and programming, as long as you pay attention to the special rules of some pieces, such as “horse” crass, “cannon” need to eat the pieces, etc., this part is beyond the scope of this article.

The second step is the focus of this paper. The first question we need to solve is, given a chess game, how to judge whether it is good or bad?

The situation assessment

Many scholars have studied the evaluation of chess situation, including static monad type, future situation type, chess knowledge type, situation additional information and so on. This paper adopts static monad type.

Type of assessment, the so-called static list refers to each piece on the board to consider the type and location, according to the importance of the type and position of the pros and cons of determine the assessment value of it, then all their pieces to the board’s assessment values summed up to get their own capabilities, will all the pieces of appraisal value accumulation are opponents force value, Subtracting your opponent’s power from your own is worth the final situation assessment.

For example, according to the importance of the chess pieces, we can specify the weight of the chess pieces as:

Marshal/general: 1000000 Shi: 110 Elephant/phase: 110 Horse: 300 roar: 600 Run: 300 pawn/pawn: 70Copy the code

For example, the position weight of the red “car” is as follows:

Max and min algorithms

With a situation evaluation method, the simplest chess AI is to walk through all possible moves at a time and pick the move with the highest situation score. But the AI will be a little stupid and a little myopic. Take, for example, the following chess game:

Assuming it is now the red team’s turn, according to our algorithm, “rook One into seven” to defeat the black “gun”, can obtain the maximum situation assessment value. But, obviously, that’s the way to lose. The problem is, our algorithm only takes into account one layer, and this kind of algorithm is obviously unreliable for the immediate benefit.

In this case, you might want to consider a few more layers before calculating the situation score, and then choose the highest-scoring move from all the branches. It looks like this:

I iterate over all possible moves (the black square in the image), then continue to iterate based on the moves of that layer (the white square in the last row of the image), then calculate the situation score and select the move with the highest score, which is the move with the black square on the left.

But what you forget is that once you’re done, it’s your opponent’s turn to move, and if you want to get 100, you need your opponent to cooperate with your move of 100. Obviously your opponent is not going to be that stupid, he’s going to try to prevent you from getting a high score, so he’s going to take the one.

If you choose the black square move on the right, your opponent will choose the move with a score of 33, and you will get a higher score.

People can easily make such decisions, but how do you teach a computer to think the same way? And that’s where the Max and min algorithms come in. The maximum and minimum algorithm divides the search tree into maximum layer and minimum layer. AI is in the maximum layer and the opponent is in the minimum layer. The maximum layer always selects the maximum value from the next layer as the result, and the minimum value layer always selects the minimum value from the next layer as the result. As shown below:

With that in mind, the code is very simple to implement. Here is a piece of pseudo-code from wiki:

/** */ function minimax(node, depth, depth) MaximizingPlayer) is // reach the bottom of the search, If depth = 0 or node is a terminal node then return the heuristic value of node If maximizingPlayer then value := −∞ for each child of node do value := Max (value, minimax(child, depth − 1, FALSE)) return value // Minimizing player *) value := +∞ for each child of node do value := min(value, minimax(child, Depth − 1, TRUE)) return valueCopy the code

The algorithm can also be simulated using a boring game with the following rules:

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

Now you need to choose a large bag, and then your opponent chooses a small bag inside for you. Your job is to get as much gold as possible, and your opponent’s job is to prevent you from getting as much gold as possible.

First of all, the game can be divided into four branches:

In the opponent layer (corresponding to the minimum layer in the algorithm), the bag with the fewest coins will be selected from the next layer:

In your layer (corresponding to the maximum layer in the algorithm), the bag with the most gold is selected from the next layer:

conclusion

This paper describes the basic steps of implementing a chess AI, introduces the Max/min algorithm and analyzes it through a boring game. However, this algorithm is time-consuming. Assuming that each traverse produces an average of 30 moves, the AI with depth 5 will need to perform a total of 24.3 million situation score calculations. In fact, the algorithm can be optimized by certain rules, which will be discussed in the next article.

reference

  1. Research on Computer Game Situation Evaluation technology of Chinese Chess
  2. Minimax
  3. IntelligentChineseChessSystem
  4. gobang

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