Black and white chess rule introduction
Black and white is a puzzle game made by two people and white. The chessboard is n × n checkered, and the black and white chess uses N2 chess pieces, each of which is positively opposite, and it is black and white. When the forward to one chess, the chess must be spaced apart from the opponent's chess pieces, requiring the underwind the chess pieces and the original rack of chess pieces (horizontal vertical clamps), then The clamped child becomes a colors (also known as eating). During the game, any chess pieces will not take away from the chessboard, and will not move from a plaid to another, when you eat, you will not have a chain reaction, and the eaten chess can not cover other children. When both sides have chess, or after the square is full, the chess game ends, and the child is more than the victory.
Black and chess manual intelligence
We take the checkerboard size of 10 × 10 squares. Use the array int State [10] [10] to represent the state of the chessboard, where 0 indicates that the square is empty, -1 indicates the black chess, 1 means white Chess.
On the 10 × 10 board, in addition to those who already have children, those who can't eat, they can't take them. How can I determine a point (x, y) can walk? By analyzing the rules of black and white chess, we know that in any of the eight directions in this square, as long as you satisfy: In this direction, there is a continuous number of each other's chess pieces, and then there is a self-owned child. We can affirm this to walk. So I define an array int Dirstate [8] (array starts from the right, such as Dirstate [0], Dirstate [1] represents the right, in this type, to represent the state, the value 1 is shown in this The one can be eaten in the direction, and the value of 0 means that it cannot be, and a function MOVEDIR (INT X, INT Y, INT MOVER) is defined to determine the state in each direction, and the specific implementation of the function MoveDir sees the source code, here in the right direction For example, the other directions are similar, the determination of the right direction can be implemented in the following statement:
INT TX = X 1, TY = Y, step = 0; // TX, TY is used to indicate indexes in the array in each point in the right direction.
Dirstate [0] = 0; // Initialization is not able
While (1)
{
IF (tx> 9) Break; // is in the boundary, exit cycle, the direction cannot be eaten
IF (state [type [tx] == 0) BREAK; // The air, exits the loop, the direction cannot be eaten
IF (state [type [tx]! = moVer) STEP ; // (tx, type) is different, STEP plus 1, connected
// Continued STEP's chess pieces and (x, y)
Else {IF (Step> 0) Dirstate [0] = 1; Break;} // (TX, TY) is in the chess, at the same time (TX, TY)
// and (x, y) If there is a continuous STEP one chess piece, then
/ / Indicates that you can eat in this direction, modify the Dirstate [0] state.
TX ;
}
We need to let the computer determine where to go, you must let it know where to go, the basic thinking of this problem is to be quantified, we have a very simple way to achieve this quantization, then It is the advantage of the number of the child to eat the number of parsers. In order to make the computer calculate the value, I define an int MoveTotal (int x, int y, int mover) function, which returns to this step can be eaten The number of the other party, his main implementation is similar to MOVEDIR, but also statistics for each direction, so this function can also be used to determine that the position can be enabled: int total = 0; // Total is used to count the total Eat the number of each other, the function finally returns this value
INT TX = x 1, TY = Y, step = 0;
While (1)
{
IF (TX> 9) Break;
IF (State [Ty] == 0) Break;
IF (State [Ty]! = Mover) Step ;
Else {IF (Step> 0) Total = step; break;} // Different from Movedir, here will add STEP to
// Total's statistical integer
TX ;
}
With these functions, the computer can use this favorable value to choose a location to play chess, so we will consider the change of the chess board after the black and white chess. We know, when we come in (x, y), it will cause the eligibility of the eight directions in this position (chess pieces and the original has been clamped by at least one chess piece) The change of the status of chess pieces. To do this, we define this function of the function Move (int X, int y, int mover), where x, y is the position of the play, Mover is -1 means the use of black chess, 1 means the hand with white chess, functions MOVE The main implementation is as follows (in the right direction, please see the source code in detail):
MoveDir (X, Y, Mover); // Call the MoveDir function, get the Dirstate array representation of the state in each direction
State [Y] = MOVER; / / Cast in this position, change the status of the chessboard in this position, change the empty state to MOVER
INT TX = X, TY = Y;
IF (Dirstate [0] == 1) / / 1 indicates that the direction of the other party can be eaten in the direction, clamp the other chess pieces.
/ /
{
While (state [type] == mover * (- 1)) / / loop until you encounter your own chess pieces
{
State [Ty] [TX] = MOVER; // Change the other party's chess pieces to your own chess pieces
}
}
At this point, a very simple black and white chess has been completed, seeing intelligent you will say here, such a computer is not too easy to win, yes, if you only see the number of people who can eat the other It is obvious that it is obviously wrong, it is obviously wrong, because the next other may eat more of you, so we have to pay, so we have to increase some algorithms, so that the location of the computer is close to the optimal, We must judge the steps after the step, predict the location of the other party, the computer's high-speed computing ability and high storage capacity provide us with the conditions for realization, where we use a depth priority method to generate a solution tree, Finding more proximity to the best solution, the prediction of the number of steps is the depth of the depth priority method, that is, the depth of the tree, which is to see the size of the specific computer, the deeper depth, the closer to the most Excellent solution, it is impossible to carry it too deep, otherwise you will not endure each step, and the memory limits the depth of your recurrence. The implementation of the recurrent function is as follows: 1. Int getBenefit (int x, int y, int mover, int N)
2. {
3. INT benefit = 0;
4. Benefit = MoveTotal (X, Y, Mover);
5. IF (benefit <= 0) Return 0;
6. if (n == 1)
7. {
8. Return Benefit;
9. }
10. Else
11. {
12. Int TempState [10] [10];
13. INT Good [10] [10];
14. INT i = 0, J = 0;
15. FOR (i = 0; i <10; i )
16. {
17. for (j = 0; j <10; j )
18. {
19. TempState [i] [j] = state [i] [j];
20. Good [i] [j] = 0;
twenty one. }
twenty two. }
23. Move (X, Y, Mover);
24. Mover = Move * (- 1);
25. n- = 1;
26. FOR (i = 0; i <10; i )
27. {
28. for (j = 0; j <10; j )
29. {
30. IF (state [i] [j]! = 0) Continue;
31. IF (MoveTotal (J, I, Mover)> 0)
32. {
33. IF (i == 0 && j == 0 || i == 9 && j == 0 || i == 0 && j == 9 || i == 9 && j == 9)
34. {35. if (Mover == Computermover)
36. Benefit = n 5;
37. IF (Mover! = Computermover)
38. Benefit- = N-5;
39.}
40. Good [i] [j] = getBenefit (J, I, Mover, N);
41.}
42.}
43.}
44. Benefit = Findmax (Good, 10, 10) * Mover Benefit;
45. FOR (i = 0; i <10; i )
46. {
47. for (j = 0; j <10; j )
48. {
49. State [i] [j] = TempState [i] [j];
50.}
51.}
52. Return Benefit;
53.}
54.}
Function Description:
1: The parameters of the function (x, y) indicate the position of the current, Mover is -1 means a black chess, 1 means that the heires use white chess, n is the depth of the recursive.
4 ~ 5: Calculate (x, y) to eat the number of the other party's chess pieces into the benefit, and judgment (x, y) can not put the loo, Benefit is greater than 0, otherwise, withdrawing the recurrent function, return 0 Can't put the loo.
6 ~ 11: Determine whether to reach the desired depth, when n is equal to 1 means completion of the recurrence, returning to this position can eat the number of chess pieces of the other party, otherwise continue to push.
12 ~ 22: Array INT TEMPSTATE [10] [10] Back up the current checkerboard, allowing the original checkerboard state when the execution function exits, the array int goods [10] [10] is used to store the subsection The other party can eat the number of chess pieces from the people in each position of the chessboard, initialize the 0.
23: In the (x, y) position, call the move function to implement, change the status of the board, before the time to perform the number of children's number of children next to the next step, of course, this change is temporary, in the end Recovered with array TEMPSTATE backups.
24 ~ 25: Change the chess party, and the depth is reduced
26 ~ 43: Tune the GetBenefit function on the chess position to the chess position, this is the main part of this function, saved the return value of the Call GetBenefit function of each location to the good array, so that the other party can eat the most s position.
33 ~ 39: This is an optimized part of this intelligence function. Considering that the four corners of the occupation are crucial to play chess, as long as they can occupy four corners, they increase or decrease this location (see current The recursive is in a hands-in-one or the other party) a weight, here I set this weight to N 5, related to the depth of the recursive, the smaller the chance to last, so the weight is smaller . 44: Using Findmax to find the largest value in the good array, multiplying MOVER's role is to be based on the current recursive black or white to judge the good array in black or white weight, The current recursive is in a hands push black or white, where Mover has changed there, so good is the opposite of the Benefit value to the front with the MoveTotal function in the 24th line.
45 ~ 51: Restore the chessboard to the state before entering the delivery function.
At this point, the core part of the program has been completed, and the above functions are integrated. We can get a function computerai () of a computer selection location, and his implementation is as follows:
1. INT i = 0, j = 0, MX = 0, my = 0, max;
2. INT benefit [10] [10];
3. for (i = 0; i <10; i )
4. {
5. for (j = 0; j <10; j )
6. {
7. Benefit [I] [J] = - 1000;
8. }
9. }
10. FOR (i = 0; i <10; i )
11. {
12. for (j = 0; j <10; j )
13. {
14. IF (State [i]! = 0) Continue;
15. IF (i == 0 && j == 0 || i == 0 &&j == 9 || i == 9 && j == 0 || i == 9 && j == 9)
16. {
17. IF (MoveTotal (J, I, Computermover> 0)
18. {
19. Move (J, I, Computermover);
20. Return;
twenty one. }
twenty two. }
23. IF (MoveTotal (J, I, Computermover> 0)
24. Benefit [I] [J] = GetBenefit (J, I, Computermover, AI);
25. IF (i == 1 || i == 8 || j == 1 || j == 8) Benefit [i] [j] = 1; 26.
27.}
28. Max = benefit [0] [0];
29. FOR (i = 0; i <10; i )
30. {
31. for (j = 0; j <10; j )
32. {
33. IF (benefit [i] [j]> max)
34. {
35. Max = benefit [i] [j];
36. mx = j;
37. my = i;
38.}
39.}
40.}
41. IF (MOVETAl (MX, MX, MX, Computermover> 0)
42. Move (MX, MX, MY, ComputerMover);
Function Description:
2 ~ 9: Array Benefit [10] [10] Used to store the weights you can get, similar to getBenefit's good array, initialization is a relatively large negative value, here to take -1000, because the weight is not More than 1000.
10 ~ 27: Try each location, call the GetBenefit function to carry the GetBenefit function, and put the value obtained at each location to the Benefit array.
14: The current point already has chess, don't consider, carry out the next loop.
15 ~ 22: If the current can be the next four diagonal points, then the diagonal point, no callus function is called.
23 ~ 24: Current location can be used, then call the GetBenefit recursive function to perform, the result is sent to the corresponding position of the array benefit.
28 ~ 40: Find the maximum value on the array Benefit and place the location of the maximum value on MX and my.
41 ~ 42: Call the MOVE function to implement
Get the computerai () function, this program is basically completed, and the board can be drawn according to the State array for black and white. Of course, such ai is still not enough, some simple traps can make the computer jump in, while the computer can find the best solution accordingly by predicting the future. However, because the "predicted step" is impossible to expand without limitation, our solution is always approximate. In order to compensate this shortcomings, we can tell the computer about some regular things that we think, so that it will take care of our experience while rational thinking, so that it is smarter, closer to human thinking, in me There are some such experience functions in the source code, and you can find his shortcomings, then analyze these insufficient places, and write them into these situations. Just add or reduce a weight to him, so that this program will become more and more powerful as your experience function is increasing. Due to deeper consideration, you can build a database for this, save some chess games, so your program will be more powerful as the number of times, AI is more powerful, but it has already discussed this article, there is Interests can look at the introduction of artificial intelligence on expert systems. Black and white chess program source code composition
It is mainly implemented by two classes to add a master program, namely the Chess class and the Show class.
The Chess class implements the package of chessboard status, artificial intelligence functions, experience functions, mainly composed of as follows:
Class Chess
{
PUBLIC:
Chess (int x, int y); // Constructor, x indicates that the computer is black and white paper, Y is the artificial used.
// Intelligent function selection
~ Chess (); // destructor
Void Move (int X, int y, int mover); // Go on the top
Void humanmove (int x, int y); // player chess, pass the location of the player to this function
INT MoveTotal (int X, int y, int mover); // Total number of people, see more
INT getBenefit (int x, int y, int mover, int n); // is augmented, see
Void Movedir (int x, int y, int mover); / / judge the status of each direction to the Dirstate array, specific
// see
INT Dirstate [8]; // Status in each direction
INT COMPUTERMOVER; / / Computer under black or white, -1 black child, 1 white
INT Ai; // The level of the AI to use
Int State [10] [10]; // Chessboard status
Private:
INT Findmax (int data [】 [10], int xsize, int tent zize); / / Find the maximum value of the Data array
Void ComputeRai (Char A); // According to the value of A, choose one of the following four AI functions.
Void ComputeRAI1 (); // Level 1 AI function
Void computeRai2 (); // Second level AI function
Void computerai3 (); // Level 3 AI function
Void computerai4 (); // fourth AI function
INT Addai6 (int X, int y, int mover); // experience function
INT Addai5 (int X, int y); // experience functions
INT Addai4 (int X, int y, int mover); // experience function
Int addai3 (int x, int y); // experience function
Int addai2 (int X, int y); // experience function
INT Addai (int X, int y); // Experience INT Checkbd (int X, int y); // border experience function
INT Checkbd2 (int X, int y); // border experience function
INT Checkbd3 (int X, int y, int mover); // border experience function
}
The SHOW class is mainly implemented by the interface of the black and white chess, as follows:
Class show
{
PUBLIC:
Void move (); // encapsulates the player to choose the change of the game
Void Draw (int data []); / / / / According to the child on the DATA number
Void DrawBk (int computermover); / / painting background and chessboard checkered
Void DrawBKRect (int X, int y, int width, int hotht); / / painting background rectangle
SHOW ();
Virtual ~ show ();
Int act;
INT X, Y;
Void Drawcircle (int X, int y, int mover); // packaged a circle function
Void DrawRect (int x, int y); // encapsulates a rectangular function
}
The main program is implemented by a loop, in which the function is implemented, and the user can be used to see the source program.
