Abstract: This paper briefly introduces computer game algorithms. The computer game belongs to artificial intelligence in some form, and this article only introduces one of the simple forms - zero and games, and gives an example - black and white.
Keywords: search, valuation, twig, alpha-beta, zero and game
introduction
With the rapid speed of computer processing speed, people have already proposed questions: Will the computer beyond humans? The World Chess Master has been defeated by the computer, the computer has exceeded human beings? After reading this article, I believe you will understand the smart of your computer chess.
concept
What is a game? Sarrency, the game in the game refers to gambling, and the game is to play. Gambling does not advocate, here, the game is just a single game. In the case of a game, one party wins, the other party will lose, in some chess, if the two sides are deadlocked, form a chess. In short, at any time of a game, the benefits of the party are equivalent to the other loss. That is, there will be a "win-win" situation. Such problems are called zero and games, because the resulting income of both parties is equal to 0.
Excellent fitting
Humans will definitely choose to take the most favorable ways, the computer is the same, and people prepared to inherit the way of thinking, that is, find the most favorable way to themselves. This most favorable way of walking is usually a way to win the victory. For example, a way to take the other party in a way, as a party in black and white chess, then our way is trying to There are many chess pieces, and the opponent's chess, of course, such a black and white chess is very weak, and this problem will be said.
Search algorithm
But the chess game is impossible to win, and the chess is impossible to die; and the judgment of a chess game cannot be completely accurate, in black and white chess, there are more chess pieces. It is not necessarily final victory because the opponent may reverse the situation during the later game. Think about how people go chess, I will generally assume that I will take this step, then how the opponent will respond, if the opponent responds to a step, I will leave again, if the opponent responds to another step, I should go; then Suppose I take another step, so repeatedly. This process is called a search.
Here we must first review the "tree" data structure as well as the traversal of the tree, as shown in Figure 1.
Figure one
Figure 1 is a three-layer, 12 node tree. The traversal of the tree has a deep priority traversal and wide priority (if you are unclear, please refer to the books of the data structure), the depth is prioritized due to the simple programming, the memory occupation is small, and more in the game. Now let's assume a chess game, the computer will go first, it can have several ways, and there are several ways to take each way, the computer's opponent has a certain way, and the sentence is launched, I got a similar picture tree. Just take the map, the initial game is A. At this time, there are three kinds of ways, which lead to the chess bureau B, C, D. There are three kinds of ways of the chess bureau, which lead to the chess game E, F, G, for the chess game C, the opponent's walking method, causing the chess game H, I, and so on.
So which kind of way should the computer choose to choose from the initial chess bureau? Obviously, the computer is to choose B, C, D, which is most advantageous for this advantage, and the computer is generally expressed in score, such as the more advantageous, the higher the score, the higher, and many procedures for intuitive It will be set to 0 points for both parties equality. However, B, C, and D are not the end of the chess, and the chess bureau will continue, and the forward to the opponent's chess, then for the chess bureau B, the opponent should choose one from E, F, G, the most beneficial to himself For the chess game C, the opponent should choose one from H, I to choose one of himself. Note that the most favorable to the opponent is the most unfavorable, the score of B should be e, f, g, the score of c should be the smallest in h, i, etc., and a score should be B. , The biggest in C, D. This is the basic principle of very small search. About searching, there is an important issue, that is, the computer's opponent. During the search process, the computer needs to assume a opponent, and this opponent is smart enough. So who is this opponent? In fact, this opponent is the computer yourself.
If we turn this tree to expand, until the chess bureau is divided into winning, then we have established a complete game tree, called the largest and minimum tree, and the tree contains the playful game in the process of chess. Moreover, the leaves of the tree are chess games that can be divided. This is a good way, as long as this complete game tree can find a road to victory, it is so good. But I will know if I add analysis, this tree is found to be built. For example, chess, you can move a piece of chess, this tree has no end; for black and white chess, although the chess game is affirmed, the node on this tree is also an astronomical figure, even if 1 second can generate 10 ^ 10 nodes, the generation time of this tree is also an astronomical figure. Therefore, it is totally un practical in establishing a complete game tree.
Surface valuation
But we will still play chess, and the level is not bad. Why is this? Because we will estimate, the chess game is evaluated. For example, a situation in chess, my car is full, and you have no car, then this situation is obviously beneficial to me. In black and white chess, my chess is more than you, so it is good for me. (Note: This evaluation method is actually very poor, because the black and white chess has a problem, and one step can reach more than 10, so the current situation is favorable for me, but the next situation is not necessarily, so the chess pieces The number of evaluation methods are generally used in the last step, that is, the so-called final.
In the game program, we also teach this method to the computer. The computer only performs a limited depth search. When the depth is reached, the search will stop searching, and the value of the prestition is changed, and this valuation is used as the value of the node. In this way, the computer can examine the situation after several steps to find a best way to walk. Of course, this "best" is derived in the same intelligence of opponents and computers.
Obviously, it is impossible to accurately, no matter how it is necessary, no matter if it is searched. But the valuation must have a generally precise direction, only so that the search engine searches in the correct direction. The chess difference between the different programs is also self-evaluation function. In the case of the same search depth, different search engines determine the efficiency, and the valuation function determines the chess.
Valuation This part of this part and the program writer have a lot of relationships, it is hard to imagine a program that people who are not proficient in black and white can write a very powerful program.
Integrated application
Binding the search algorithm, walking method, and the situation estimate can get the easiest and practical program. An example is made in the form of a pseudo code here.
INT MinMax (Side P, INT Depth) // Depth is the search depth {
Int BestValue, Value;
/ / In general, there is a function that judges whether or not the chess game ends. Once the game ends, it is not necessary to continue searching, and the extreme value is returned directly. However, since the black and white chess does not have the end of the way, it is omitted.
IF (depth <= 0) // Leaf node
{
Return the valuation (P); // Directly return to the valuation of the situation
}
IF (currently a computer play)
{
BestValue = -Inf; // The initial best value is set to endless
}
Else
{
BestValue = INF; // The initial best value is set to be endless
}
FOR (Each legal way to walk the method) // process is closely related to the specific problem, the specific method is omitted
{
Take a pace of chess; // Surface P
Value = MinMax (p, depth-1); / / Search child nodes
Undo the first step; // Restore the situation P
IF (currently a computer play)
{
IF (value> bestvalue) // take maximum
{
BestValue = Value;
IF (is the initial situation)
{
Save the best way to walk;
}
}
}
Else
{
Value { BestValue = Value; } } } Return BestValue; } This extremely small search is somewhat cumbersome, and it is necessary to perform great and very small search according to the current chess. Considering the interests of the opponent is your own losses, which takes out the negative large search algorithm. It is not very much so easy to understand, but it is very simple, do not judge the current chess party. However, the valuation of the negative pole is sensitive to the chess, so there is a parameter that needs to have a chess party in the function parameters. Long Negamax (Side P, ING SIDE, INT Depth) // Depth is the search depth { Int BestValue, Value; IF (depth <= 0) // Leaf node { Return the valuation (p, side); / / directly return to the valuation of the situation } BestValue = -Inf; // The initial best value is set to endless FOR (Each legal way to walk the method) // process is closely related to the specific problem, the specific method is omitted { Take a pace of chess; // Surface P Value = - Negamax (p, opside, defth-1); / / Search child nodes, pay attention to the front negative, Opside is an opponent Undo the first step; // Restore the situation P IF (value> bestvalue) // take maximum { BestValue = Value; IF (is the initial situation) { Save the best way to walk; } } } Return BestValue; } Seeing this, the reader can write a smart module of a black and white chess. Just add the way to generate and the valuation function. There is a simple black and white chess smart module program I wrote in the compressed package. If BCB6 is installed, you can compile it directly, trial. Of course, for the principle, this example program has not been optimized, and the speed is very slow. Readers can find it to optimize it, such as using a chessboard with 10 * 10 to avoid border inspections, or use a one-dimensional array to represent a chessboard, with bit chessboard technology, and speed, I estimate optimization can improve performance at least 30%. In addition, the valuation part is too simple, the chess is very weak, and the same reader can write a valuation function to improve the chess. In terms of the Finance Search, readers can also search themselves. Strengthening the search algorithm The efficiency of the extremely small search is very low because all the nodes are switched, so that the number of search nodes increases with the increase in search depth. Suppose each situation has 10 kinds of ways, then search 6 floors will search for 10 ^ 6 nodes, and the 9th floor is searching for 10 ^ 9 nodes, which cannot endure. Fortunately, this problem can be solved, this is the alpha-beta twig. The following content is basically taken from the Black and White World Website (http://blacwet.yeah.net) Look at the fragment of the search tree, the node represents the falling point, the number on the edge of the node is the value of the node. Now, we assume that E3-F2 F3 F4 F5 F6 is searched, then search for C3-C2 D3 E6 F5, then C5-B6 C6 D6 E6 F6. This way we will find that after searching E3 branch, the value of the root node (that is, the initial game) is (-1), see the extremely large minimum search algorithm. After searching D3 branch, you don't have to search for E6 and F5, because if the next value is larger than D3, it will not assign a value to C3. If the value is smaller than D3, it will not assign a value to the root node after the value is given, because The node takes the maximum value, and now the root node is (-1) and does not take a smaller value. Similarly, you don't have to search for E6 and F6 after searching D6. That is, you don't have to search if you are searching for a value that is less than or equal to (-1). During the search, the current optimal value of the board nodes under the computer is called α value (ie the value of the initial chess game), the current optimal value of the border of the opponent is referred to as beta value (ie the value of C3 in the example ). At the beginning of the search, the α value is infinite, the β value is endless, during the search process, the α value is incremented, the β value is reduced, and the two constitute a range. This range is called a window, and the final optimal value of the node of the opponent's chess will fall in this window. Once the node of the computer chess gets the return value of its sub-node is greater than the beta value, it is score. Int alphabeta (situation p, int defth, int alpha, int beta) // depth is a search depth { INT Value, BestValue; / / In general, there is a function that judges whether or not the chess game ends. Once the game ends, it is not necessary to continue searching, and the extreme value is returned directly. However, since the black and white chess does not have the end of the way, it is omitted. IF (depth <= 0) // Leaf node { Return the valuation (P); // Directly return to the valuation of the situation } FOR (Each legal way to walk the method) // process is closely related to the specific problem, the specific method is omitted { Take a pace of chess; // Surface P Value = MinMax (p, depth-1, alpha, beta); // Search child node Undo the first step; // Restore the situation P IF (currently a computer play) { IF (value> alpha) // take maximum { Alpha = value; BestValue = alpha; IF (is the initial situation) { Save the best way to walk; } IF (alpha> = beta) { Return Beta; // } } } Else { Value { Beta = value; BestValue = Beta; IF (alpha> = beta) { Return alpha; // } } } } Return BestValue; } Similarly, Alpha-beta also has similar negative simple forms, which is most common in the utility. Long Negaalphabeta (Surface P, ING SIDE, INT DEPTH, Long Alpha, Long Beta) // DEPTH is search depth { Int value; IF (depth <= 0) // Leaf node { Return the valuation (p, side); / / directly return to the valuation of the situation } FOR (Each legal way to walk the method) // process is closely related to the specific problem, the specific method is omitted { Take a pace of chess; // Surface P Value = - Negaalphabeta (p, opside, defth-1, -beta, -alpha); / / Search child nodes, pay attention to the front negative, Opside is an opponent Undo the first step; // Restore the situation P IF (value> = alpha) // take maximum { Alpha = value; IF (is the initial situation) { Save the best way to walk; } IF (alpha> = beta) { Break; // } } } Return alpha; } It should be noted that the alpha-beta pruning is extremely sensitive to the search order. For the above chess game, if the order of the search is C5-D6 B6 C6 E6 F6, then the four nodes are brought, pay attention to cut The branch not only cuts the node itself, but also branches of the subtots under those nodes, but if it is C5-B6 C6 E6 F6 D6, there is no branch of a node. In the worst case of nodes, Alpha-Beta and extremely small are the same, and they are searching for all nodes. Therefore, it is very important to sort node based on certain information. I don't have an alpha-beta program case, which is easy to understand the principles of the great minimal algorithm and the principle of Alpha-Beta, write the code, is a chance to practice, there is great help. In addition to Alpha-beta, there are also a variety of enhanced programs such as PVS, MTD (F), MPC, etc., and have multiple techniques such as replacement table, historical inspiration. Recommend a book "PC Game Programming (Human Game)", there are many ways, and there is a Chinese chess server. See here, is there any idea to write a smart program? Chess with your own procedure, see if people are amazing or the procedure. I have no high level in my own, and there is not much chess. I want to go to the final decision to use black and white as an example to write this article. The following is to see the black and white chess beginners, the master can write a valuation function yourself, and you can try it with your program. Black and white chess beginner guide This title is because people who understand the black and white chess in China do not seem to have, here is the way of the black and white game rules. To write a good program, you must first be proficient in it. In order to concentrate on the design of the intelligent part, I divide the smart module and the interface, and the win-win judgment program is separated, so everyone can only achieve a DLL. Chess method Black and white chessboard is a chessboard with 8 * 8 checkered board. When chess, put the chess in the space, not like Go, on the intersection. At the beginning, there was a white black four chess pieces in the chessboard. Black chess is always next. The method of the next is: put the color of his color on the board of the chessboard, and when you put the chess pieces in the horizontal, vertical, oblique eight direction with a self, it is the middle of the middle, it will become your own piece. Also, only where you can flip the chess pieces, and, when you have chess, you must go. If there is no place on the board, the opponent is connected. Chess game end conditions Both sides have no chess pieces to end, and the papers will win. Score method The current provisions are: Both the two parties of the two orientations (such as 4 bureaus), win 1 point, lose 0 points, flat 0.5 points, and more scores. If the score is the same, the winning louder is calculated by the number of chess pieces. So how is the number of chess pieces? If both parties will be full of boards, it is certainly judged. If the board is over, there are 34 children in black, and there are 30 children in white, then the black chess will win 34-30 = 4. But if the chessboard is not full, such as 34 children, white chess has 27 children. At this time, there are two scorachable methods: Japan's scoring method is that the remaining spaces are all giving victory, then black chess 34 3-27 = 10. The European scoring method is that the remaining spaces each have half, then the black chess (34 1.5) - (27 1.5) = 7. Valuation technology As mentioned earlier, it is quite weak to determine the fundamental factors that determine the chess power. The valuation method of the number of the number of chess pieces in the example program is quite weak, so how is it valued? The current black and white chess program uses the valuation method of three, based on the valuation of chess pieces, based on the valuation of action, and is based on the template-based valuation. Template-based valuation because I don't know, I can't say it. Here, there are two other valuation methods. 1. Valuation based on chess pieces Many people just learn to be more greedy when they learn black and white, always want to eat more chess pieces in the opponent, and the results are often lost. However, they will gradually find the essentials, the chess pieces on the four corners will never be turned, so the chess pieces on the corner have a high value, and the chess pieces are not easy to be turned, and the value is also high, especially, If you have your own chess pieces on a corner, there is a high value of the three chess pieces in this corner. This is the basic principle based on the valuation of the position value of the chess pieces. Every location on the board has different value, the value of the corner is the greatest value, to prevent the opponent from occupying the corner, you must avoid walking around the corner, so there is no chess place on the corner The value around the horns should be very low, but if there is already your own chess pieces on the corner, the situation is different. So, in general, you should prepare a piece of position value form for yourself and opponents, and also designed to adjust these two value tables according to the current chess game before each valuation. This valuation method is very simple and fast, so it is used in a program written in many beginners. The programs for using this valuation method are not strong, but because more than the beginners are written, it is still possible to beat its author. 2. Valuation based on action A better estimate is valued based on action and potential action. First introduce these two concepts. The action is to refer to a place where chess can be checked, such as 10 places in some situation, can come chess, then the action is 10. The potential action is generally referring to the number of spaces around the opponent's chess, because only the space next to the opponent is the place where you may come, so on a situation, the more yourside next to your opponent, the more beneficial to yourself, this is the potential line Dynamic valuation. In actual procedures, the operational valuation is usually used in combination with the value of the chess position. Sometimes, although the action is not high, every place is a good chess, it is worth it. In short, the principle is to leave a goodss for yourself, but let the opponent don't have a good chess. This valuation method is relatively strong, the preparation, the beginners generally do not win their own procedures. Finance search Black and white has its own characteristics, that is, the chess bureau will end, and when the chess course is also determined. The remaining spaces are often in the corner before the end of the chess game. This is the key area of the two sides. This step of the end of the game is called the Finance. And the efficiency method of taking action often leads to a result, which is very small in your own chess (please consider this is why). And the wins of black and white have only the number of chess pieces, so the action is not applicable when the operational force is in the end office. In fact, the Finance of the black and white chess is very simple. Just consider the number of chess pieces, other factors don't have to be considered, so the estimated speed will increase, the search depth can be more deeper, the general final search 10 floors is light Good programs can search for about 20 layers. When actually programming, it is generally the first number of spaces in the board. If it is greater than a value (such as 12), the search function of the integrated valuation is called, otherwise directly enter the final search, and the depth of the final sector is set to 12, This way can the program have been searching for the game. With this method, the average person is very difficult to win the program, especially in the Finance, if the program is judged when the process begins to lose, then you will definitely lose, and generally lose more miserable. The article is over here, thanks to the Black and White Chess World Website (http://blacwet.yah.net), let me learn a lot of knowledge about black and white chess. Finally, I wish you all a strong black and white chess program! 2004-09-23 Beijing The instance can be downloaded by my homepage. http://nowcan.yeah.net http://vip.6to23.com/nowcan1