Recently, with the rapid development of the computer, all kinds of chess games have been invited to enter the computer, making those chess fans who love chess, often suffering from opponents, can be chess at any time. And this type of software is quite high, and there is a great potential to fight with the human brain. Among them, the "dark blue" of Casparov, the "deep blue" of Casparov is the most convincing representative; other "hand", chess "," will ", etc. also with its excellent artificial intelligence Chess fans love; and we will introduce you to the algorithm of the five daughter today. When we are fighting with computers, do you know how these software thinks like a human brain? Not long ago, I wrote a five-child game, here as an example to discuss it with everyone. In general, we assume that you are familiar with the basic rules of the five-child chess). If you let the computer know which point it is under, it is necessary to calculate the importance of each possible falling specimen according to the situation of the disk, that is, when this is falling What kind of chess type will be formed (such as "rushing four", "live three", etc.), and then open to select the most important point, this is the most basic algorithm. Of course, it is far less than the current disk, so that chess is easy to fell into the trap set by the player because it does not consider future changes. Therefore, on this basis, we joined the recursive call, ie, predict the various steps in the next few steps to make the best choice, which is what we often say when we play, "I want a few steps." As a result, your program has a certain level. what? Do not believe! Come and try it! After the overall thinking, the details are discussed below:
1. Data structure first look at the data structure, what variables we need? First, a table is created for the entire chessboard to record the chess pieces, we use a 15 * 15 two-dimensional array table [15] [15] (15 * 15 is the size of the five-child chess board), each element of the array corresponds to the chess board A intersection on the top, using '0', '1' represents the child, '2' represents the other's child; this table is the foundation of future analysis. Here, it is necessary to establish a chess type table Computer [15] [15] [4] and Player [15] [15] [4], which is used to store chess data. The importance of importance, such as using '20', the point of "rushing four", uses '15' represents "live three" point, then when calculating importance, it can be found according to 20> 15. When the next child, the computer will automatically select the "punching four". Then why should the chess form use a three-dimensional array? Because every point on the board can make a different chess type with the chess pieces in the four directions of the parse, vertical, left, left, right, so there is a total of 4 records; the other advantage of this is to easily judge Composite chess type, for example, if there is 2 '15' on the same point, there is a '15' and one '20' is four three. How! The three arrays constitute the basic data skeleton of the program. As long as you add some auxiliary variables, you can go paid. Should it be too difficult? OK! With so many useful data, we can go deep into the process of procedure.
2: Procedure Process We mainly discuss the core algorithm of the five-child, ie: artificial intelligence, while other graphic display, keyboard mouse control, etc., because it is not more introduced. First, please read the picture 1:
We see that this program consists of six basic function modules. The detailed analysis of each module is as follows: (1) Initialization: First, establish a disk array table [15] [15], the battle between the game Computer [15] [15] ] [4] and Player [15] [15] [4] cleans them; then initialize the input and output devices such as the display, keyboard, and rats and draw a checkerboard on the screen. (2) Maincy-loop control module: Control the order of the chess, when the turn is next to the child, responsible for transferring the program to the corresponding module, mainly as a schemer's role. (3) Players: When the wheel goes to the player, you can record '2' according to the location of the table, the program will record '2' according to the location of the Table [15] [15], to indicate The child is the player. (4) Capacity Fill in the chess table: one of the core modules of this program, the fundamental basis of the artificial intelligence algorithm! The specific implementation method is as follows: When you are in the next five daughter, you will first find some of the most important points on the board, such as "live three", "rush four", etc., then choose the drop point. However, the computer does not analyze the problem like someone. If it knows where "live three", which is "rushing four", you have to calculate on the board, step by step. First, let's analyze your own chess, we will search from the upper left corner of the chessboard. When you encounter a blank point, look for the left to the left, if you encounter your own child, record and continue, if you encounter To the other person, the blank point or boundary stops finding. After the left is completed, the same operation is performed to the right; finally merge the records on the left and right sides, the resulting data is the chess type in the transverse direction, then fill the number of the chess type to Computer [x] [y] [N ] In the middle of the line (X, Y represents coordinates, N = 0, 1, 2, 3 represents horizontal, vertical, left allah, right inverting direction). The other three-direction chess type can also be obtained in the same way. After searching for the full chart, the self-examination table is finished. Then fill in the other party with the same method. Note: All chess types must be defined in advance, the greater the number of numbers! OK! How? Is it a bit tired? But don't be discouraged! Because the priest is still behind. Let's go! (5) Computer under: There is two chess type tables above, now you want to let the computer know which point. The simplest calculation method is to traverse Chess Table Computer [15] [15] [4] and Player [15] [15] [4] to find the biggest value, in this point. However, the weakness of this algorithm is very obvious, only considering the interests of the eyes, can't take care of the overall situation, which makes a "short-light" problem like many five sisters. To solve this problem, we introduce a few steps in the next steps ', the specific method is this: First, let the computer analyze a possible point, if the sub-child will form a pair of chess pactions (for example:' rush Four ',' live three '); then the next opponent will defend you in your idea, so that the first step is completed.
At this time, the call module 4 performs disc analysis after the predicted chess, if there is a winning point such as 'four and three', 'double three' or 'double four', then the self will win (of course, the black chess is Double three ',' double four 'is a banner, otherwise followed by the same method, you can predict the second step, the third step ..., etc., if there is no opponent on the disk must be prevented Chess, what should I do? If the attack is incapable, you have to consider defense. If you call yourself and your opponent, then use the above method to predict the opponent's chess, which can prevent the opponent's smart attack, and can wait for the aircraft to start counterattack, why not ! But you must tell you that the computational volume of the prediction method is quite large. According to my experience, it takes 15 seconds to take an average of 15 seconds with Pentium-100 predictive 3 steps, so it is recommended to predict the amount within 5 steps. Don't be a little bit this 5 steps, sometimes it will even get out of the wonderful! (6) The winning and negative judgment: must have a lot of words, and some squares form five sons and wins; if black chess go out of 'Double 3', 'Double four' or long and connecting. So far, the entire five daughter software is basically completed, and the level is approximately intermediate. Of course, this algorithm is not the best, but I believe that its basic idea is correct. If you have any questions or good ideas, please send me E-mail: Softboy@sina.com, I am looking forward to your opinion. Wang Xin
