C language Design a human-machine battle five-childss chess program summary: Wuzi is a popular game, introducing the data structure, score rules, winning and negative judgment method of the five daughter chess programs, focusing on search algorithms, and playing in traditional games The algorithm has improved in the application of the five-child chess, so that the twigs are more effective and the calculation performance is better. Improvements include: do not use a Closed table; change the board search order; add a pointer to record the maximum board information. Experiments have proven that these improvements have high help to improve efficiency.
Key words: five sorrows; maximum minimal value; scutch; algorithm improvement
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? Here, take this as an example and everyone to discuss discussions.
In order to make the reader have an image of the five-child search complexity, a comparison of the number of Chinese chess and five signs (as shown). It can be seen that the five-child branch has a large number of branch factors, and the winning and negative conditions are also complex. Under the large branch coefficient, the maximum search depth of the search program adds 1 layer, and the time consuming operation time will increase much. Therefore, it is very important to design a valid search algorithm.
China chess five son chess pieces 14 2 chessboard size 9 × 10 15 × 15 branch coefficient about 40 about 200 chess pieces) Decrease increase the winning and negative conditions Some party will lose someone five chess pieces
The organization of the article is as follows: First, briefly introduce the basic method of the C language (Turbo C 2.0 environment) and the main loop control the chess module, followed by the design of the data structure of this five-child chess, and then introduces the score algorithm and the win-negative judgment. Finally, focus on implementing search algorithms.
1. Basic C Multi-Method and Maincy Control Module
Turbo C provides a very rich graphics function. All graphical functions are built in Graphics.h. When using graphics functions, make sure there is a display graphics driver * .bgi, integrated development environment Options / Linker Graphics lib is ON, and only this can only use a graphic function correctly.
This program calls an EGA, which can run a function of running independent graphics under VGA displays. The so-called stand-alone graphic running procedure is to load the corresponding driver (* .bgi) directly into the executive in compilation and connection, so that can be run on a separate computer, avoiding the need to recompile the connection to run (please refer to the reference book) 1 and source code). Turbo C performs drawpoints, line, closed graphical fill, and graphics text output only need to call the related functions in Graphics.h.
Main loop control module: Control the order of the chess, when the wheel goes down the next child, is responsible for transferring the program to the corresponding module, mainly as a schemer's role. This five-child chess program is to control chess with keyboard, so use the BIOS.h in Turbo C. Wait for the keyboard information in a cycle block, determine if the information entered by the keyboard needs to be in response, and the associated code is called (the main code in the source code).
2. Basic data structure of the five sons
Establish a form for the entire chessboard to record the chess pieces, use a 15 * 15 two-dimensional array chessman [15] [15] (15 * 15 is the size of the five-child chess board), each element of the array corresponds to a board Intersection, express space with "0", "1" represents a piece of hand, "2" represents the other party. This table is the foundation of future analysis. Second, a structure is to be established, mainly used in the search process, defined as follows: typedef struct five_chesters * point;
Struct Five_Chesters {
INT X;
Int Y;
int Layer;
Int value;
int Score;
INT Chess [Length] [Length];
INT record [Length] [Length];
}
X, y indicates a new node that is extended in a certain location, which represents the first few layers expansion for controlling the depth. Value indicates that the very large value of this point, Score represents the score of the leaf node, used to estimate the value of the parent node, and the two-dimensional array represents the extended board information, Record records the node that expands on X, Y point If there is 0 corresponding to a value of 0 if there is no extended Record. If there is no scaled node in Record, then the layer extension ends, returns a specific value.
The array and a structure constitute the basic data skeleton of the program. As long as some auxiliary variables will be added, it will be free.
3. Rules and winning judgments
Assess a coke disc's score, mainly by scanning the entire board, for each comment. The score is statistically statistically scored from the four directions (the angles from 0, 45, 90, 135), and then accumulates the total score, and finally the score of the entire board. In fact, the current situation is compared in the order of the rules below. If a rule is satisfied, the situation is scored and saved, and then the rule match is exited. Note that the rule here is based on a summary of the normal playback. When actual operation, the user can add rules and fix the score mechanism (some of the partial rules in the source code). The score rules are as follows:
l Judging whether it can be 5. If it is a robot, it gives 30,000 points. If it is a human, it gives -30000 points;
l Judging whether it can be activated 4 or die dead 4 or die 4 live 3, if it is a robot, give 100,000 points, if it is human, give -10000 points
l Judging whether it has become a double live 3, if it is a machine side, 5,000 points, if it is a human, to give -5000 points
l Judging whether it is killed 3 live 3, if it is a robot, give 1000 points, if it is human, give -1000 points
l Determines if it can be killed 4, if it is a robot, give 500 points, if it is a human, give -500 points
l Determine if it is possible to live 3, if it is a machine side, give 200 points, if it is a human, give -200 points
l Judging whether it has become a dual life 2, if it is a machine side, give 100 points, if it is a human party, give -100 points
l Determines if it can be killed 3, if it is a machine side, 50 points, if it is human, give it -50 points
l Judging whether it can be a double live 2, if it is a robot, 10 points, if it is human, give it -10 points
l Determine if it can be survived, if it is a robot, give 5 points, if it is a human, give it -5 points
l Determine if it can be died 2, if it is a machine side, give 3 points, if it is a human, it is actually judged according to the current situation of the current last fall. In fact, it is necessary to judge from the four positions, with the line of the starting point, vertical and two lines of 45 degrees and 135 degrees, etc., the purpose is to see if the one of the four directions constitutes a continuous five The chess pieces, if yes, it means that the board chess has been divided into the victory.
4. Realization of search algorithm
α-β twigs are developed based on a very large minimal search algorithm, so first analyze the classic maximum ultra-small search process, as follows:
1T: = (s, max), open: = (s), closed: = (); the tree is constructed by the initial node, and the OPEN table contains only S. 2LOOP1: IF open = () THEN Go Loop2; 3N: = first (open), remove (n, open), add (n, closed); 4IF N can directly determine to win, lose or lay then f (n): = ∨∨-∨ ∨0, go loop1else expand (n) → {ni}, add ({
}, T) IF D (Ni) }, Open), go loop1else calculate f ( ), Go loop1; Ni reaches deep K, calculates the Node F value of each end. 5LOOP2: if close = nil the go loop3else : = First (closed); 6IF ( ∈max) ∧ (f (f) ∈MIN) value) THEN F ( : = Max {f ( )}}, Remove ( , Closed; if the MAX all child nodes have a value, the max is made greatly. IF MIN) ∧ (f (f) ∈max) value) THEN F ( : = Min {f )}}, Remove ( , Closed; if the MIN all child nodes have a value, the min takes its minimum value. 7GO loop2; 8LOOP3: IF f (s) ≠ nil kil dam (End∨m (Move, T)); S value, end or mark step. The Minimax process is to separate the generation of the generation and pattern valuation of the search tree, that is, the gentleman is all searching the tree, and then performs a static valuation and inverting value calculation of the end node, which will obviously lead to inefficiency. In order to closely combine the generation and valuation process, search with the boundary depth priority policy is used, so when the node that reaches the specified depth, its static valuation function is immediately calculated, and once a non-terminal node is conditioned, it is fixed. Immediately calculate the value immediately when the value is pushed. This is the so-called α-β process. The α-β algorithm is summarized as follows: α-twig: An alpha value of the β value is less than or equal to the α value of the primary value of the node, α (first generation) ≥ β (rearlay layer) The search process below this min node in this minimum layer can be aborted. The final inverted value of this MIN node is determined to be this beta value β pruning: An alpha value of any polar large-scale layer node is greater than or equal to the β value of the primary small value layer node, that is, the α (rearlay layer) ≥ β (the ancestral layer), it can be suspended. The search process below this MAX node is below the value layer. The final inverted value of this MAX node is determined to be this α value. 5. Improvement of algorithm The algorithm improvement here is mainly concentrated on the maximum minimal and α-β pruning. The flow chart of this five-child algorithm is as follows (to expand two layers): Establish root node S0 (data structure: FIVE_CHESMAN) based on chess board information, and put the S0 into the stack Expansion S1 = TOP (); judgment S1-> Layer is equal to -1 S1-> Layer is not equal to -1, push (S1), expands S2 = TOP (), see if S2-> Layer is -1 S2-> Layer! = - 1, calculate the checkerboard score, and determine whether or not to change the minimum value of the previous layer S2-> Layer == - 1, POP (): Determine if the maximum value is changed, Max_Chess points to the highest scoreboard If S1-> layer = -1, the search end, return to the maximum board information MAX_CHESS The code segment written in C is as follows: S0 = malloc (SIZEOF (Struct Five_Chess); For (i = 0; i <3000; i ) Close [I] = NULL; For (i = 0; i For (j = 0; j S0-> chess [i] [j] = chessman [i] [j]; S0-> Record [i] [j] = chessman [i] [j]; } S0-> Layer = 0; S0-> Value = -30000; S0-> score = -30000; Push (S0); WHILE (is_empty ()! = 0) { S0 = TOP (); S1 = expand (s0); IF (S1-> Layer == - 1) { POP (); CONTINUE; } Close [NUM ] = S1; S1-> Value = 30000; Push (S1); While (1) { S2 = Expand (S1); IF (S2-> Layer == - 1) { S1 = TOP (); POP (); IF (S1-> Value> TOP () -> value) { TOP () -> value = S1-> value; MAX_CHESS = S1;} Break; } S2-> score = score (S2-> chess); Temps = TOP (); IF (S2-> Score Temps-> value = s2-> score; The main features of this program are: l Do not use the Closed table, and use a pointer to the maximum board information, and use a record form registration has expanded node. This does not need to have a lot of access to the Closed table, and greatly improve the search performance. l At the time of the extended node, divide the chessboard into three parts: intermediate layer (coordinate 5 <= x <10, 5 <= y <10), second layer (2 <= x <12, 2 <= y < 12 and remove those points of the intermediate layer), the third layer (0 <= x <14, 0 <= Y <14 removes the neutral node of the second layer). The basis for dividing the chessboard into such a three part extension is: The closer to the junction of the middle position, the thus starts calculation from the node of the score, then the number of twigs is more, and the operation is largely improved. effectiveness. In fact, the optimal algorithm is centered on intermediate nodes, using a spiral search to maximize efficiency. l Use a pointer TypeDef struct five_chers * point that records the highest score, this improvement can save a lot of space. Because the expansion process has a lot of nodes, if this improvement can be used, then the occupied space can be removed. In addition, when returning to the board information, it is very convenient to find a position. references: [1] Ma Shaiping, Zhu Xiaoyan. Artificial intelligence. Beijing: Tsinghua University Press, 2004 [2]. Wang Xiaoping. Analysis of senior examples of C language. Beijing: Tsinghua University Press, 2002 / * * Use the upper and lower left and bottom of the keyboard to move the chessboard, the space bar indicates the chess, the ESC button exits the program * / # include #define Player1 1 # Define Player2 2 # Define Computer 2 # Define Length 15 # define search_deep 2 / * * Used in function can_expand () to find the available node steps * / # Define Step 1 / ************ Global variable definition *************** / int X1 = 240, y1 = 240, OLDX = 240, Oldy = 240; intY = 240; int Key_Mode; int key_net; int checkman [length] [length]; int Depth = 2; / * Search depth * / int a = 0, b = 0; int flag_run; int win_flag = 0; typedef struct FIVE_CHESS * POINT; STRUCT FIVE_CHESS {INT X; INT Y; INT Layer; Double Value; Double Score; Int Chess [Length]; int record [length] [length];} a; INT stack_deep0 = 0; Point Stack_c [10]; Point Close [600]; Voidpush (Point S0) {IF (stack_deep0 <10) stack_c [stack_deep0 ] = s0;} PointTop () {if (stack_deep0> 0) Return Stack_c [stack_deep0 - 1]; / * Else Return What is something? * /} VoidPop () {if (stack_deep0> 0) stack_deep0--; INTIS_EMPTY () {if (stack_deep0! = 0) Return 1; Else Return 0;} / ************ Function declaration ************** / VOID FIVE (); void show (); int win_or_not (int X0, int y0, INT WHO, INT CHESSMAN [Length], INT A; void set_chersman (); void print_result (); / ************ Evaluation function part ******** **** / double score_row (INT I, INT J, INT CHESSMAN [Length]); Double Score_col (INT I, INT J, INT CHESSMAN [LENGTH] [Length]); Double Score_Diag_45 (INT I, INT J, int Chescesman [Length]; Double Score_Diag_135 (INT I, INT J, INT CHESSMAN [LENGTH] [Length]); Double Total_Score (int who_running, int checkman [length); Double Score INT CHESSMAN [Length]); int Rowdt (INT I, INT J, INT CHESSMAN [LENGTH] [Length]); int Coldt (INT I, INT J, INT CHESSMAN [LENGTH] [Length]); int Diadt (INT I, INT J, INT CHESSMAN [Length]); int Vdiadt (INT I, INT J, INT CHESSMAN [Length] [Length]); int CAN_EXPAND (Int i, int J, int Chessma N [length] [length]); Void Copy (Point S1, POINT S0); INTPOW (INT S, INT T) {Int Sum = S, I; IF (T <= 0) Return 1; for (i = 0 i } / * * Define Computer Adjust (Point S0) {INT FLAG; INT I, J; Point New_Chesters = (Point) Malloc (Struct Five_Chess); / ************ ************* Here is wrong ******************************************* / For (i = 0; i For (i = 0; i For (i = 0; I IF (S0-> Record [i] [j]) / * If there is a chess piece * / continue; if (can_expand (i, j, s0-> chess) == 0) / * If there is a chess piece, and horizontally, the tree Straight, left - upper right, upper right - left, four directions can be extended * / continue; S0-> Record [i] [j] = flag; new_chesters-> chess [i] [j] = flag; new_chess-> layer = S0-> Layer 1; new_chesters-> x = i; new_chesters-> y = j; new_chesters-> record [i] [j] = flag; return new_ches;} / * * for (i = 5; i < 10; i ) for (j = 5; j <10; j ) {if (S0-> Record [i] [j]) continue; * if (can_expand (i, j, s0-> chess) == 0) Continue; S0-> Record [i] [j] = flag; * new_chess-> x = i; new_chesters-> y = j; new_chesters-> record [i] [j] = flag; * new_chesters-> layer = S0 -> Layer 1; New_CHESS-> Chess [i] [j] = flag; return * new_ches;} for (i = 2; i <12; i ) for (j = 2; j <12; j ) {* IF (I> 4 && I <10 && J> 4 && J <10) Continue; if (S0-> Record [I] [J]) Continue; * IF (CAN_EXPAND (i, J, S0-> Chess) == 0) Continue; s0 -> Record [i] [j] = flag; * new_chess-> x = i; new_chesters-> y = j; new_chesters-> record [i] [j] = flag; * new_chesters-> layer = S0-> Layer 1; new_chesters-> chess [i] [j] = flag; RETU RN * new_CHESS; * *} for (i = 0; i New_chesters-> y = j; new_chesters-> record [i] [j] = flag; return * new_ches;} * / new_chess-> layer = -1; return new_chess;} VoidComputer () {INT I, J, K, NUM = 0; int break_now = 0; int buce_then = 0; int Go_on = 0; Point S0 = NULL, S1 = NULL, S2 = NULL, MAX_CHESS = NULL; POINT TEMPS = NULL, S01; / * * Stack of initialization * / stack_deep0 = 0; s0 = malloc (SIZEOF (Struct Five_Chesses)); for (i = 0; i <600; i ) / * Why is 600 * / close [i] = NULL; / * Close is a Point array * / close [Num ] = S0; for (i = 0; i Break;} S1-> Value = 30000; Push (S1); while (1) {S1 = TOP (); S2 = Expand (S1); if (S2-> Layer == -1) {POP (); IF (S1-> Value> TOP () -> value) {top () -> value = S1-> value; max_chesters = s1;} free (s2); break;} // end of if s2-> score = score (S2-> Chess); temps = top (); if (S2-> Score / ************************************************** ********* / voidmain () {int key; int play_with_who = 1; Printf ("1.Play with human / n2.play"); scanf ("% d", & play_with_who); FIVE (); / * Show chessboard * / show (); IF (play_with_who == 1) {/ * people play * / while (1) {/ * Set people playing interface * / setTextStyle (0, 0, 2); if ((Step_Sum 1)% 2 ) {SetColor (1); OutTextxy (500, 180, "player2"); setColor (4); Outtextxy (500, 180, "player1");} else {setColor (1); Outtextxy (500, 180, "Player1 "); SetColor (10); OUTTEXTXY (500, 180," Player2 "); IF (Bioskey (1)) / * * Press the keyboard so that True, execute the following code, this is the BIOS. h * / {key = bioskey (0); / * * Returns a keyboard value, if there is no button, wait * / switch (key) {case esc: exit (0); Case Left: IF (x1> 30) {X1 - = 30; show (); / * Display box * /} Break; Case Up: IF (Y1> 30) {Y1 - = 30; show ();} Break; Case Right: IF (x1 <450 ) {X1 = 30; show ();} Break; Case Down: IF (Y1 <450) {Y1 = 30; show ();} Break; Case Blank: / * Press the space button to place the piece * / {IF (Chessman [x1 / 30]) Break; / * If there is a chess piece, if there is a chess piece, you can't place it, exit * / step_sum ; / * If there is no chess, let's take 1 * / / * * P1 Set chess pieces * / if (step_sum% 2) {setColor (15); / * Painted chess * / setfillstyle (Solid_Fill, 15); / * Closed graphics, entity fill * / circle (x1, y1, 10); / * Painted round * / floodfill (x1, y1, 15); / * Filling round * / chessman [x1 / 30] [Y1 / 30] = Player1; / * Set board status * / win_flag = win_or_not (x1, y1, 1 , chessman, 0); / * Analyze whether the game ends, who is defeated * / if (win_flag == 1) Outtextxy (480, 240, "p1 w IN "); else if (win_flag == 3) Outtextxy (480, 240," dogfall); if (win_flag! = 0) {/ * If no one wins, the game continues * / while (Bioskey (1) == 0); Closegraph (); / * What this mean? * /}} Else {/ * p2 setup chess pieces * / SetColor (12); setFillStyle (Solid_Fill, 12); Circle (x1, y1, 10); floodfill (x1, y1, 12); chessman [x1 / 30] [Y1 / 30] = Player2; Win_FLAG = WIN_OR_NOT (x1, Y1, 2, chessman, 0); if (Win_FLAG == 2) OutTextxy (480, 240, "p2 win"); else if (win_flag == 3) OutTextxy (480, 240, "dogfall"); if (Win_Flag ! = 0) {while (bioskey (1) == 0); closegraph ();}}} break;}}}} else {chessman [7] [7] = cOMPUTER; / * play and the computer, the first computer Take a step * / setColor (12); setfillstyle (Solid_Fill, 12); Circle (240, 240, 10); floodfill (240, 240, 12); FLAG_Run = 0; / * Is there any use? * / Step_sum ; / * Who will go next step? * / While (1) {if (flag_run == 1) BREAK; if (Bioskey (1)) {key = bioskey (0); / * * Returns a keyboard value, if no button is not Waiting * / switch (key) { Case ESC: EXIT (0); Case Left: IF (x1> 30) {x1 - = 30; show ();} Break; Case Up: IF (Y1> 30) {Y1 - = 30; show ();} Break; Case Right: IF (x1 <450) {x1 = 30; show ();} Break; Case Down: IF (Y1 <450) {Y1 = 30; show ();} Break; Case Blank: { IF (Chessman [x1 / 30 - 1] [Y1 / 30 - 1]) Break; / * Have a chess piece, do not leave * / SetColor (15); setFillStyle (Solid_Fill, 15); / * Closed graphics, entity fill * / circle (x1, y1, 10); floodfill (x1, y1, 15); / * Painting chess * / chessman [x1 / 30 - 1] [Y1 / 30 - 1] = Player1; Flag_run = 1; / * What is the use? * / step_sum ; / * Next Who went to * / win_flag = Win_OR_NOT (x1, y1, 1, chessman, 0); / * Who wins Who negative * / if (Win_Flag == 1) OutTextxy (480, 240, "p1 win"); else if (win_flag == 3) Outtextxy (480, 240, "dogfall"); if (win_flag! = 0) {while (Bioskey (1) == 0 ); / * No people won to continue waiting to come to play * / closegraph ();}}} / * switch * / } } Computer (); / * Call the intelligent body * / / * * a, B storage is the location under the computer is now available * Return to a A, B structure is not better, use global variables unhappy * struct {* int a; * int b; *} * / SetColor (12); setFillStyle (Solid_Fill, 12); Circle (A, B, 10); Floodfill (A, B, 12); Chessman [A / 30 - 1] [B / 30 - 1] = Computer; Flag_Run = 0; step_sum ; win_flag = win_or_not (a, b, 2, chessman, 0); if (win_flag == 2) Outtextxy (480, 240, "computerwin); else if (win_flag == 3) Outtextxy (480, 240 , "Dogfall"); if (win_flag! = 0) {while (Bioskey (1) == 0); Closegraph ();} } } voidfive () {INT I, J; / * * Courier process * / int gDriver = detect, gmode; registerbgidriver; initgraph (& gdriver, & gmode, "); / * * Configuring display adapter * / Setbkcolor (1); For (i = 0; i <30; i ) {setColor ((i> = 2)? 9: i); Rectangle (i, i, 479 - i, 479 - i); / * Rectangular border * /} / * * Cash paper * / for (i = 1; i <14; i ) for (j = 1; j <14; j ) {setColor (14); line (30 30 * i, 30, 30 30 * i, 449); line (30, 30 30 * i, 449, 30 30 * i);} / * * Draws the border of the entire map * / for (i = 0; i <15; i ) {setColor (i); Rectangle (i, i, 640 - i, 480 - i); line (480 - i, 15, 480 - i, 465);} / * * Output information on the right side of the screen * / setColor (4) SettextStyle (0, 0, 2); Outtextxy (500, 45, "gobang); setColor (10); setTextStyle (0, 0, 1); OutTextxy (500, 90," designed by "); Outtextxy (514 , 118, "ye binbin"); Outtextxy (480, 140, "from class a of cs"); / * * Mobile cursor * / voidShow () {setColor (1); IF (Oldx <450) {IF (Oldy> 30) Line (Oldx 7, Oldy - 15, Oldx 15, Oldy - 15); if (Oldy> 30) Line (Oldx 15, Oldy - 15, Oldx 15, Oldy - 7); IF (Oldy <450) Line (Oldx 15, Oldy 7, Oldx 15, Oldy 15); if (Oldy <450) Line (Oldx 15, Oldy 15, Oldx 7, Oldy 15);} if (Oldx> 30) {IF (Oldy <450) LINE (Oldx - 7, Oldy 15, Oldx - 15, Oldy 15); if (Oldy <450) Line (Oldx - 15, Oldy 15, Oldx - 15, Oldy 7); IF (Oldy> 30) Line (Oldx - 15, Oldy - 7, Oldx - 15, Oldy - 15); if (Oldy> 30) Line (Oldx - 15, Oldy - 15, OLDX - 7, OLDY - 15);} setColor (12); if (x1 <450) {IF (Y1> 30) LINE (x1 7, y1 - 15, x1 15, y1 - 15); if (Y1> 30) line (x1 15, Y1 - 15, X1 15, Y1 - 7); IF (Y1 <450) line (x1 15, Y1 7, X1 15, Y1 15); if (Y1 <450) LINE (x1 15, Y1 15, X1 7, Y1 15);} IF (x1> 30) {IF (Y1 <450) LINE (x1 - 7, y1 15, X1 - 15, Y1 15; IF (Y1 <450) LINE (x1 - 15, y1 15, x1 - 15, y1 7 ); If (Y1> 30) LINE (x1 - 15, y1 - 7, x1 - 15, y1 - 15); if (Y1> 30) line (x1 - 15, y1 - 15, x1 - 7, y1 - 15 );} Oldx = x1; Oldy = Y1; } Voidset_chessman () {/ * * There are three states, 0 is not initial, 1 is the control party, 2 is the other party's chess pieces * / int I, J; for (i = 0; i <15; i ) for (J = 0; J <15; J ) chessman [i] [j] = 0;} / * * 0 means no win, 1 indicates P1 victory, 2 indicates P2 victory, 3 indicates a flat * / int win_or_not (int X0, int y0, int who, int checkman [length] [length], int a) {INT i = X0 / 30 - 1, j = Y0 / 30 - 1; int WHO_RUN = WHO; int line_sum = -1; int TMP_I = I, TMP_J = J; INT C; if (a == 1) {/ * * test Whether a layer expansion is satisfied * / c = chessman [i] [j]; chessman [i] [j] = who_run;} while (1) {/ * Find the co-friendly board piece connected to five * / While (tmp_i> = 0 && line_sum! = 4) {if (Chessman [TMP_I -] [J] == WHO_RUN) line_sum ; else break;} if (line_sum == 4) line_sum ; tmp_i = i; while (tmp_i <= 15 && line_sum! = 5) {IF (Chessman [TMP_I ] [J] == WHO_RUN) line_sum ; else break;} if (line_sum == 5) {IF (a == 1) Chessman [i] [J ] = C; Return WHO_RUN;} line_sum = -1; TMP_I = I; Break; } While (1) {/ * Find a listed piece of chess pieces connected to five * / while (tmp_j> = 0 && line_sum! = 4) {if (Chessman [i] [tmp_j--] == who_run) line_sum ; Else Break;} if (line_sum == 4) line_sum ; tmp_j = j; while (tmp_j <= 15 && line_sum! = 5) {if (Chessman [i] [TMP_J ] == WHO_RUN) line_sum ; else break;} (line_sum == 5) {if (a == 1) Chessman [i] [j] = C; returnire_run;} line_sum = -1; tmp_j = j; Break; } While (1) {/ * lookups if five * / while (line_sum! = 4 && tmp_i <= 15 && tmp_j> = 0) {if (checkman [tmp_i ] [tmp_j--] [TMP_J--] == WHO_RUN) LINE_SUM ; Else Break;} tmp_i = i; tmp_j = j; if (line_sum == 4) line_sum ; while (line_sum! = 5 && tmp_i> = 0 && tmp_j <= 15) {if (Chessman [TMP_i -] [TMP_J ] == WHO_RUN) LINE_SUM ; Else Break;} if (line_sum == 5) {IF (A == 1) Chessman [i] [j] = C; return = i; tmp_j = J; line_sum = -1; Break;} while (1) {/ * lookup Whether to connect five * / while (line_sum! = 4 && tmp_i> = 0 && tmp_j> = 0) {IF (Chessman [TMP_I -] [TMP_J -] == who_run) line_sum ; else break;} tmp_i = i; tmp_j = j; if (line_sum == 4) line_sum ; while (line_sum! = 5 && TMP_i <= 15 && tmp_j <= 15) {IF (Chessman [TMP_I ] [TMP_J ] == WHO_RUN) line_sum ; else break;} if (line_sum == 5) {IF (a == 1) Chessman [i] [j] = c Return WHO_RUN;} Break;} if (step_sum == 225) {IF (a == 1) Chessman [i] [j] = C; Return 3;} IF (a == 1) chessman [i] [j] = C; return 0; DoubleScore_Row (INT I, INT J, INT CHESSMAN [LENGTH]) {Int Sum_Chescen = 0; Double Score = 0; INT MID_J; INT Who_Running = Chessman [i] [J]; IF (j == length) { While (Chessman [I] [J] == WHO_Running) {J -; SUM_CHESSMEN ;} if (SUM_CHESSMEN> = 5) score = 200000; Else {IF (Chessman [i] [j] == 0) / * No Culture, live situation * / score = 2000 / pow (10, 4 - sum_chersmen); else score = 0; / * dead * /}} else {While (chessman [i] [j] == who_running && j ! = Length) {J ; Sum_ChesSmen ;} MID_J = J; J = J - SUM_CHESSMEN - 1; While (Chessman [i] [j] == Who_Running && J! = -1) {J -; SUM_CHESSMEN ;} IF (j> = 0 && mid_j DoubleScore_col (INT I, INT J, INT Chessman [length]) {int sum_chessmen = 0, MID_I; Double Score = 0; Int Who_Running = Chessman [i] [j]; if (i == length) {while (Chessman [I] [J] == WHO_Running) {i-; sum_chescen ;} if (sum_chersmen> = 5) score = 200000; if (Chessman [i] [j] == 0) score = 2000 / pow 10, 4 - SUM_CHESSMEN; Else Score = 0;} else {while (chessman [i] [j] == who_running) {i ; sum_chersmen ;} MID_I = i; if (i == length || chessman [i] [J]! = who_running) {i = i - sum_chescemen; while (checkman [i - 1] [j] == wh_running) {i-; sum_chersmen ;} if (i> = 0) {if (chessman [i ] [J] == 0 && Chessman [MID_I] [J] == 0) Score = 18000 / POW (50, 4 - Sum_Cssmen); Else IF ((Chessman [i] [J]! = 0 && chessman [MID_I ] [j]) == 0 || (Chessman [i] [j] == 0 && chessman [mid_i] [j]! = 0) SCIE = 2000 / POW (10, 4 - sum_chersmen; else score = 0;} i F (i <0 && mid_i DoubleScore_Diag_45 (INT I, INT J, INT Chessman [length]) {int sum_chessmen = 0; Double Score = 0; INT MID_I, MID_J; INT Who_Running = Chessman [i] [J]; IF (i == Length || j == length) {while (chessman [i] [j] == who_running && i> 1 && j> 1) {i-; j--; sum_chersmen ;} if (sum_chersmen> = 5) score = 200000; Else {IF (Chessman [i] [j] == 0) score = 2000 / pow (10, 4 - sum_chescen); else score = 0;}} else {while (checkman [i] [j] == WHO_RUNNING && I <= Length && J <= Length; Sum_CheSSMEN ;} MID_I = i; MID_J = J; I = i - Sum_Chessmen; J = J - Sum_Chescen; While (Chessman [i - 1] [J - 1] == WHO_Running) {i-; j-; sum_chescen ;} if (sum_chersmen> = 5) score = 200000; if (i> = 0 && j> = 0 && mid_i Length) {if (Chessman [MID_I] [MID_J] == 0) score = 2000 / pow (10, 4 - sum_chescen); else score = 0;}} Return score; DoubleScore_Diag_135 (INT i, INT J, INT CHESSMAN [length]) {int sum_chescen = 0; double score = 0; int MID_I, MID_J; int who_running = chessman [i] [j]; while (checkman [i] [J] == Who_Running && J! = -1 && i DoubleTotAl_score (int who_running, int shssman [length]) {/ * * Statistics at this point score, whload = 1 Represents people's chess pieces, 2 is the computer's chess pieces * / int I, J; double score = 0; for (i = 0; i / * * Expansion ----- During the process * / Introwdt (INT I, INT J, INT CHESSMAN [Length]) / * In Tree Direction * / {INT K; INT MIDJL = J - Step, / * Above the top * / midjr = J Step 1; / * The lower part of the chess pieces below ?????? * / if (midjl <0) midjl = 0; if (midjr> length) midjr = length; for (k = midjl; k INTCOLDT (INT I, INT J, INT CHESSMAN [Length]) / * Level direction * / {INT K; int midil = i step 1, / * Current right chess pieces of right * / midiu = i - Step; / * The left * / if (Midiu <0) MIDIU = 0; if (Midil> length) midil = length; for (k = midiu; k INTVDIADT (INT I, INT J, INT CHESSMAN [Length]) / * top left to upper right direction * / {INT K, MIDI, MIDJ; MIDI = I; MIDJ = J; for (k = 0; k < Step; k ) {midi-; midj-; if (MIDI <0 || Midj <0) Break; if (Chessman [MIDI] [MIDJ]! = 0) Return 1;} for (k = 0; k INTCAN_EXPAND (INT I, INT J, INT CHESSMAN [LENGTH] [Length]) {IF (Rowdt (I, J, Chessman)) Return 1; IF (Coldt (I, J, Chessman) Return 1; IF (DIADT I, J, Chessman) RETURN 1; IF (VDIADT (I, J, Chessman)) Return 1; / * * If it is not extended, return 0 * / return 0;} / ********** *********************************************************** /