home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk1.iso / altsrc / articles / 10676 < prev    next >
Text File  |  1994-06-19  |  33KB  |  823 lines
  1. Newsgroups: alt.sources
  2. Path: wupost!psuvax1!news.pop.psu.edu!news.cac.psu.edu!howland.reston.ans.net!spool.mu.edu!torn!watserv2.uwaterloo.ca!watdragon.uwaterloo.ca!kppomaki
  3. From: kppomaki@jeeves.uwaterloo.ca (Keith Pomakis)
  4. Subject: Connect-4 algorithm  --  "c4.c", source code
  5. Message-ID: <CrILo4.M0I@watdragon.uwaterloo.ca>
  6. Sender: news@watdragon.uwaterloo.ca (USENET News System)
  7. Organization: University of Waterloo
  8. Date: Fri, 17 Jun 1994 00:07:15 GMT
  9. Lines: 812
  10.  
  11.  
  12. /****************************************************************************/
  13. /****************************************************************************/
  14. /**                                                                        **/
  15. /**                          Connect-4 Algorithm                           **/
  16. /**                                                                        **/
  17. /**                            By Keith Pomakis                            **/
  18. /**                     (kppomaki@jeeves.uwaterloo.ca)                     **/
  19. /**                                                                        **/
  20. /**                               Fall, 1993                               **/
  21. /**                                                                        **/
  22. /****************************************************************************/
  23. /**                                                                        **/
  24. /**  This file provides the functions necessary to implement a front-end-  **/
  25. /**  independent, device-independent Connect-4 game.  Multiple board sizes **/
  26. /**  are supported.  It is also possible to specify the number of pieces   **/
  27. /**  necessary to connect in a row in order to win.  Therefore one can     **/
  28. /**  play Connect-3, Connect-5, etc.  An efficient tree-searching          **/
  29. /**  algorithm (making use of alpha-beta cutoff decisions) has been        **/
  30. /**  implemented to insure that the computer plays as quickly as possible. **/
  31. /**                                                                        **/
  32. /**  The declaration of the public functions necessary to use this file    **/
  33. /**  are contained in "c4.h".                                              **/
  34. /**                                                                        **/
  35. /**  In all of the public functions, the value of player can be any        **/
  36. /**  integer, where an even integer refers to player 0 and an odd integer  **/
  37. /**  refers to player 1.                                                   **/
  38. /**                                                                        **/
  39. /****************************************************************************/
  40. /****************************************************************************/
  41.  
  42. #include <stdio.h>
  43. #include <stdlib.h>
  44. #include <unistd.h>
  45. #include "c4.h"
  46.  
  47. /* The static global variables required. */
  48.  
  49. #define NUM_OF_TEMP_STATES      42
  50. static int size_x, size_y, num_to_connect, win_places;
  51. static Boolean ***map;
  52. static Game_state real_state;
  53. static Boolean game_in_progress = FALSE, seed_chosen = FALSE;
  54. static void (*poll_function)(void) = NULL;
  55. static int poll_level;
  56. static Game_state temp_states[NUM_OF_TEMP_STATES];
  57. static Boolean temp_array[NUM_OF_TEMP_STATES];
  58. static int temp_states_allocated = 0;
  59.  
  60. /* Some macros for convenience. */
  61.  
  62. #define other(x) (((x)==1)? 0 : 1)
  63. #define real_player(x) (x & 1)
  64.  
  65. /* A declaration of the local functions. */
  66.  
  67. static void insure_game(void);
  68. static int num_of_win_places(int x, int y, int n);
  69. static void update_score(Game_state *state, int player, int x, int y);
  70. static Boolean drop_piece(Game_state *state, int player, int column);
  71. static int player_score(Game_state *state, int player);
  72. static Boolean winner(Game_state *state, int player);
  73. static Boolean tie(Game_state *state);
  74. static int goodness_of(Game_state *state, int player);
  75. static Game_state *copy_state(Game_state *state);
  76. static void destroy_state(Game_state *state);
  77. static int worst_goodness(Game_state *state, int player, int level, int depth,
  78.                                                                 int so_far);
  79. static void *emalloc(unsigned int n);
  80.  
  81.  
  82. /****************************************************************************/
  83. /**                                                                        **/
  84. /**  This function specifies that the computer should call the specified   **/
  85. /**  function from time to time, in essence polling it to see if the       **/
  86. /**  front-end interface requires any attention.  The specified function   **/
  87. /**  should accept void and return void.  level is the level of lookahead  **/
  88. /**  at which the function should be called.  This level is measured from  **/
  89. /**  the bottom.  Eg. If the lookahead level is set to 6 and level is set  **/
  90. /**  to 4, with a 7x6 board, this function will be called a maximum of     **/
  91. /**  7^2 = 49 times (once for each (6-4)th = 2nd level node visited.       **/
  92. /**                                                                        **/
  93. /**  Note that if a node is not visited due to apha-beta cutoff, this      **/
  94. /**  function will not be called at that node.  Therefore only a maximum   **/
  95. /**  number of calls can be predicted (with a minimum of 1).               **/
  96. /**                                                                        **/
  97. /**  If no polling is required, the polling function can be specified as   **/
  98. /**  NULL.  This is the default.  This function can be called an arbitrary **/
  99. /**  number of times throughout any game.                                  **/
  100. /**                                                                        **/
  101. /****************************************************************************/
  102.  
  103. void
  104. poll(void (*poll_func)(void), int level)
  105. {
  106.     poll_function = poll_func;
  107.     poll_level = level;
  108. }
  109.  
  110.  
  111. /****************************************************************************/
  112. /**                                                                        **/
  113. /**  This function sets up a new game.  This must be called exactly once   **/
  114. /**  before each game is started.  Before it can be called a second time,  **/
  115. /**  end_game() must be called to destroy the previous game.               **/
  116. /**                                                                        **/
  117. /**  width and height are the desired dimensions of the game board, while  **/
  118. /**  num is the number of pieces required to connect in a row in order to  **/
  119. /**  win the game.                                                         **/
  120. /**                                                                        **/
  121. /****************************************************************************/
  122.  
  123. void
  124. new_game(int width, int height, int num)
  125. {
  126.     int i, j, k, count;
  127.  
  128.     if (game_in_progress) {
  129.         fprintf(stderr, "new_game: game already in progress\n");
  130.         exit(1);
  131.     }
  132.  
  133.     if (width < 1 || height < 1 || num < 1) {
  134.         fprintf(stderr, "new_game: invalid parameters\n");
  135.         exit(1);
  136.     }
  137.  
  138.     size_x = width;
  139.     size_y = height;
  140.     num_to_connect = num;
  141.     win_places = num_of_win_places(size_x, size_y, num_to_connect);
  142.  
  143.     /* Set up a random seed for making random decisions when there is */
  144.     /* equal goodness between two moves.                              */
  145.     if (!seed_chosen) {
  146.         srand(getpid());
  147.         seed_chosen = TRUE;
  148.     }
  149.  
  150.     /* Set up the board */
  151.  
  152.     real_state.board = (char **) emalloc(size_x * sizeof(char *));
  153.     for (i=0; i<size_x; i++) {
  154.         real_state.board[i] = (char *) emalloc(size_y * sizeof(char));
  155.         for (j=0; j<size_y; j++)
  156.             real_state.board[i][j] = EMPTY;
  157.     }
  158.  
  159.     /* Set up the score array */
  160.  
  161.     real_state.score_array[0] = (int *) emalloc(win_places * sizeof(int));
  162.     real_state.score_array[1] = (int *) emalloc(win_places * sizeof(int));
  163.     for (i=0; i<win_places; i++) {
  164.         real_state.score_array[0][i] = 1;
  165.         real_state.score_array[1][i] = 1;
  166.     }
  167.  
  168.     /* Set up the map */
  169.  
  170.     map = (int ***) emalloc(size_x * sizeof(int **));
  171.     for (i=0; i<size_x; i++) {
  172.         map[i] = (int **) emalloc(size_y * sizeof(int *));
  173.         for (j=0; j<size_y; j++) {
  174.             map[i][j] = (int *) emalloc(win_places * sizeof(int));
  175.             for (k=0; k<win_places; k++)
  176.                 map[i][j][k] = FALSE;
  177.         }
  178.     }
  179.  
  180.     count = 0;
  181.  
  182.     /* Fill in the horizontal win positions */
  183.     for (i=0; i<size_y; i++)
  184.         for (j=0; j<size_x-num_to_connect+1; j++) {
  185.             for (k=0; k<num_to_connect; k++)
  186.                 map[j+k][i][count] = TRUE;
  187.             count++;
  188.         }
  189.  
  190.     /* Fill in the vertical win positions */
  191.     for (i=0; i<size_x; i++)
  192.         for (j=0; j<size_y-num_to_connect+1; j++) {
  193.             for (k=0; k<num_to_connect; k++)
  194.                 map[i][j+k][count] = TRUE;
  195.             count++;
  196.         }
  197.  
  198.     /* Fill in the forward diagonal win positions */
  199.     for (i=0; i<size_y-num_to_connect+1; i++)
  200.         for (j=0; j<size_x-num_to_connect+1; j++) {
  201.             for (k=0; k<num_to_connect; k++)
  202.                 map[j+k][i+k][count] = TRUE;
  203.             count++;
  204.         }
  205.  
  206.     /* Fill in the backward diagonal win positions */
  207.     for (i=0; i<size_y-num_to_connect+1; i++)
  208.         for (j=size_x-1; j>=num_to_connect-1; j--) {
  209.         /*
  210.         for (j=size_x-1; j>=size_x-num_to_connect; j--) {
  211.         */
  212.             for (k=0; k<num_to_connect; k++)
  213.                 map[j-k][i+k][count] = TRUE;
  214.             count++;
  215.         }
  216.  
  217.     real_state.num_of_pieces = 0;
  218.  
  219.     for (i=0; i<NUM_OF_TEMP_STATES; i++)
  220.         temp_array[i] = FALSE;
  221.  
  222.     game_in_progress = TRUE;
  223. }
  224.  
  225.  
  226. /****************************************************************************/
  227. /**                                                                        **/
  228. /**  This function drops a piece of the specified player into the          **/
  229. /**  specified column.  Note that column numbering starts at 0.  A value   **/
  230. /**  of TRUE is returned if the drop was successful, or FALSE otherwise.   **/
  231. /**  A drop is unsuccessful if the specified column number is invalid or   **/
  232. /**  full.                                                                 **/
  233. /**                                                                        **/
  234. /****************************************************************************/
  235.  
  236. Boolean
  237. make_move(int player, int column)
  238. {
  239.     insure_game();
  240.     if (column >= size_x || column < 0) return FALSE;
  241.     return drop_piece(&real_state, real_player(player), column);
  242. }
  243.  
  244.  
  245. /****************************************************************************/
  246. /**                                                                        **/
  247. /**  This function instructs the computer to make a move for the specified **/
  248. /**  player.  level specifies the number of levels deep the computer       **/
  249. /**  should search the game tree in order to make its decision.  This      **/
  250. /**  corresponds to the number of "moves" in the game, where each player's **/
  251. /**  turn is considered a move.  The column number of the column in which  **/
  252. /**  the piece was dropped is returned.  Note that column numbering starts **/
  253. /**  at 0.  If no move is possible (i.e. the game board is full), -1 is    **/
  254. /**  returned.  Note that for a standard 7x6 game of Connect-4, the        **/
  255. /**  computer is brain-dead at levels of three or less, while at levels of **/
  256. /**  4 or more the computer provides a challenge.                          **/
  257. /**                                                                        **/
  258. /****************************************************************************/
  259.  
  260. int
  261. automatic_move(int player, int level)
  262. {
  263.     int i, goodness, best_column, best_worst;
  264.     Game_state *temp_state;
  265.     int num_of_equal, real;
  266.  
  267.     insure_game();
  268.     real = real_player(player);
  269.  
  270.     if (level < 1) {
  271.         fprintf(stderr, "automatic_move: invalid level\n");
  272.         exit(1);
  273.     }
  274.  
  275.     best_worst = -2000000;
  276.     best_column = -1;
  277.  
  278.     /* Simulate a drop in each of the columns and see what the results are. */
  279.  
  280.     for (i=0; i<size_x; i++) {
  281.         temp_state = copy_state(&real_state);
  282.  
  283.         /* If this column is full, ignore it as a possibility. */
  284.         if (!drop_piece(temp_state, real, i)) {
  285.             destroy_state(temp_state);
  286.             continue;
  287.         }
  288.  
  289.         /* If this drop wins the game, it is a really good move! */
  290.         if (winner(temp_state, real)) {
  291.             best_worst = 1000000;
  292.             best_column = i;
  293.         }
  294.  
  295.         /* Otherwise, look ahead to see how good this move may turn out */
  296.         /* to be (assuming the opponent makes the best moves possible). */
  297.         else
  298.             goodness = worst_goodness(temp_state, real, level, 1, best_worst);
  299.  
  300.         /* If this move looks better than the ones previously considered, */
  301.         /* remember it.                                                   */
  302.         if (goodness > best_worst) {
  303.             best_worst = goodness;
  304.             best_column = i;
  305.             num_of_equal = 1;
  306.         }
  307.  
  308.         /* If two moves are equally as good, make a random decision. */
  309.         if (goodness == best_worst) {
  310.             num_of_equal++;
  311.             if (rand()%100000 < ((float)1/(float)num_of_equal) * 100000)
  312.                 best_column = i;
  313.         }
  314.  
  315.         destroy_state(temp_state);
  316.     }
  317.  
  318.     /* Drop the piece in the column decided upon. */
  319.  
  320.     if (best_column >= 0)
  321.         drop_piece(&real_state, real, best_column);
  322.  
  323.     return best_column;
  324. }
  325.  
  326.  
  327. /****************************************************************************/
  328. /**                                                                        **/
  329. /**  This function returns the state of the current game.  The Game_state  **/
  330. /**  structure returned is defined in "c4.h".                              **/
  331. /**                                                                        **/
  332. /****************************************************************************/
  333.  
  334. Game_state
  335. get_game_state(void)
  336. {
  337.     insure_game();
  338.     return real_state;
  339. }
  340.  
  341.  
  342. /****************************************************************************/
  343. /**                                                                        **/
  344. /**  This function returns the "score" of the specified player.  This      **/
  345. /**  score is a function of how many winning positions are still available **/
  346. /**  to the player and how close he/she is to achieving each of these      **/
  347. /**  positions.  The scores of both players can be compared to observe how **/
  348. /**  well they are doing relative to each other.                           **/
  349. /**                                                                        **/
  350. /****************************************************************************/
  351.  
  352. int
  353. score_of_player(int player)
  354. {
  355.     insure_game();
  356.     return player_score(&real_state, real_player(player));
  357. }
  358.  
  359.  
  360. /****************************************************************************/
  361. /**                                                                        **/
  362. /**  This function returns TRUE if the specified player has won the game,  **/
  363. /**  and FALSE otherwise.                                                  **/
  364. /**                                                                        **/
  365. /****************************************************************************/
  366.  
  367. Boolean
  368. is_winner(int player)
  369. {
  370.     insure_game();
  371.     return winner(&real_state, player);
  372. }
  373.  
  374.  
  375. /****************************************************************************/
  376. /**                                                                        **/
  377. /**  This function returns TRUE if the board is completely full, FALSE     **/
  378. /**  otherwise.                                                            **/
  379. /**                                                                        **/
  380. /****************************************************************************/
  381.  
  382. Boolean
  383. is_tie()
  384. {
  385.     insure_game();
  386.     return tie(&real_state);
  387. }
  388.  
  389.  
  390. /****************************************************************************/
  391. /**                                                                        **/
  392. /**  This function returns the coordinates of the winning connections of   **/
  393. /**  the specified player.  It is assumed that the specified player has    **/
  394. /**  indeed won the game.  The coordinates are returned in x1, y1, x2, y2, **/
  395. /**  where (x1, y1) specifies the lower-left piece of the winning          **/
  396. /**  connection, and (x2, y2) specifies the upper-right piece of the       **/
  397. /**  winning connection.  If more than one winning connection exists, only **/
  398. /**  one will be returned.                                                 **/
  399. /**                                                                        **/
  400. /****************************************************************************/
  401.  
  402. void
  403. win_coords(int player, int *x1, int *y1, int *x2, int *y2)
  404. {
  405.     int i, j, win_pos = -1, look_for = 1 << num_to_connect;
  406.     int realplayer;
  407.     Boolean found;
  408.  
  409.     insure_game();
  410.     realplayer = real_player(player);
  411.     for (i=0; i<win_places; i++)
  412.         if (real_state.score_array[realplayer][i] == look_for)
  413.             win_pos = i;
  414.  
  415.     if (win_pos == -1) {
  416.         fprintf(stderr, "win_coords: no winner\n");
  417.         exit(1);
  418.     }
  419.  
  420.     /* Find the lower-left piece of the winning connection. */
  421.  
  422.     found = FALSE;
  423.     for (j=0; j<size_y; j++)
  424.         for (i=0; i<size_x; i++)
  425.             if (map[i][j][win_pos] && !found) {
  426.                 *x1 = i;
  427.                 *y1 = j;
  428.                 found = TRUE;
  429.             }
  430.  
  431.     /* Find the upper-right piece of the winning connection. */
  432.  
  433.     found = FALSE;
  434.     for (j=size_y-1; j>=0; j--)
  435.         for (i=size_x-1; i>=0; i--)
  436.             if (map[i][j][win_pos] && !found) {
  437.                 *x2 = i;
  438.                 *y2 = j;
  439.                 found = TRUE;
  440.             }
  441. }
  442.  
  443.  
  444. /****************************************************************************/
  445. /**                                                                        **/
  446. /**  This function ends the current game.  It is assumed that a game is    **/
  447. /**  indeed in progress.  It is illegal to call any other game function    **/
  448. /**  immediately after this one except for new_game() and poll().          **/
  449. /**                                                                        **/
  450. /****************************************************************************/
  451.  
  452. void
  453. end_game(void)
  454. {
  455.     int i, j;
  456.  
  457.     insure_game();
  458.  
  459.     /* Free up the memory used by the game state. */
  460.  
  461.     for (i=0; i<size_x; i++) free(real_state.board[i]);
  462.     free(real_state.board);
  463.     free(real_state.score_array[0]);
  464.     free(real_state.score_array[1]);
  465.  
  466.     /* Free up the memory used by the map. */
  467.  
  468.     for (i=0; i<size_x; i++) {
  469.         for (j=0; j<size_y; j++)
  470.             free(map[i][j]);
  471.         free(map[i]);
  472.     }
  473.     free(map);
  474.  
  475.     /* Free up the memory of all the temporary states used. */
  476.  
  477.     for (i=0; i<temp_states_allocated; i++) {
  478.         temp_array[i] = FALSE;
  479.         for (j=0; j<size_x; j++) free(temp_states[i].board[j]);
  480.         free(temp_states[i].board);
  481.         free(temp_states[i].score_array[0]);
  482.         free(temp_states[i].score_array[1]);
  483.     }
  484.     temp_states_allocated = 0;
  485.  
  486.     game_in_progress = FALSE;
  487. }
  488.  
  489.  
  490. /****************************************************************************/
  491. /****************************************************************************/
  492. /**                                                                        **/
  493. /**  The following functions are local to this file and should not be      **/
  494. /**  called externally.                                                    **/
  495. /**                                                                        **/
  496. /****************************************************************************/
  497. /****************************************************************************/
  498.  
  499.  
  500. /****************************************************************************/
  501. /**                                                                        **/
  502. /**  This function insures that a game is in progress, and exits with an   **/
  503. /**  error if one is not.                                                  **/
  504. /**                                                                        **/
  505. /****************************************************************************/
  506.  
  507. static void
  508. insure_game(void)
  509. {
  510.     if (!game_in_progress) {
  511.         fprintf(stderr, "error: no game in progress\n");
  512.         exit(1);
  513.     }
  514. }
  515.  
  516.  
  517. /****************************************************************************/
  518. /**                                                                        **/
  519. /**  This function returns the number of possible win positions on a board **/
  520. /**  of dimensions x by y with n being the number of pieces required in a  **/
  521. /**  row in order to win.                                                  **/
  522. /**                                                                        **/
  523. /****************************************************************************/
  524.  
  525. static int
  526. num_of_win_places(int x, int y, int n)
  527. {
  528.     return 4*x*y - 3*x*n - 3*y*n + 3*x + 3*y - 4*n + 2*n*n + 2;
  529. }
  530.  
  531.  
  532. /****************************************************************************/
  533. /**                                                                        **/
  534. /**  This function updates the score of the specified player given that    **/
  535. /**  the player has just placed a game piece in column x, row y.           **/
  536. /**                                                                        **/
  537. /**  The specified game state is used, which may be a temporary state.     **/
  538. /**                                                                        **/
  539. /****************************************************************************/
  540.  
  541. static void
  542. update_score(Game_state *state, int player, int x, int y)
  543. {
  544.     int i;
  545.  
  546.     for (i=0; i<win_places; i++)
  547.         if (map[x][y][i]) {
  548.             state->score_array[player][i] <<= 1;
  549.             state->score_array[other(player)][i] = 0;
  550.         }
  551. }
  552.  
  553.  
  554. /****************************************************************************/
  555. /**                                                                        **/
  556. /**  This function drops a piece of the specified player into the          **/
  557. /**  specified column.  A value of TRUE is returned if the drop was        **/
  558. /**  successful, and FALSE if it was not (i.e. the specified column is     **/
  559. /**  full).                                                                **/
  560. /**                                                                        **/
  561. /**  The specified game state is used, which may be a temporary state.     **/
  562. /**                                                                        **/
  563. /****************************************************************************/
  564.  
  565. static Boolean
  566. drop_piece(Game_state *state, int player, int column)
  567. {
  568.     int y = 0;
  569.  
  570.     while (state->board[column][y] != EMPTY && ++y < size_y)
  571.         ;
  572.  
  573.     if (y == size_y) return FALSE;
  574.  
  575.     state->board[column][y] = player;
  576.     state->num_of_pieces++;
  577.     update_score(state, player, column, y);
  578.  
  579.     return TRUE;
  580. }
  581.  
  582.  
  583. /****************************************************************************/
  584. /**                                                                        **/
  585. /**  This function returns the "score" of the specified player.  This      **/
  586. /**  score is a function of how many winning positions are still available **/
  587. /**  to the player and how close he/she is to achieving each of these      **/
  588. /**  positions.  The scores of both players can be compared to observe how **/
  589. /**  well they are doing relative to each other.                           **/
  590. /**                                                                        **/
  591. /**  The specified game state is used, which may be a temporary state.     **/
  592. /**                                                                        **/
  593. /****************************************************************************/
  594.  
  595. static int
  596. player_score(Game_state *state, int player)
  597. {
  598.     int i, score = 0;
  599.  
  600.     for (i=0; i<win_places; i++)
  601.         score += state->score_array[player][i];
  602.  
  603.     return score;
  604. }
  605.  
  606.  
  607. /****************************************************************************/
  608. /**                                                                        **/
  609. /**  This function returns TRUE if the specified player has won the game,  **/
  610. /**  and FALSE otherwise.                                                  **/
  611. /**                                                                        **/
  612. /**  The specified game state is used, which may be a temporary state.     **/
  613. /**                                                                        **/
  614. /****************************************************************************/
  615.  
  616. static Boolean
  617. winner(Game_state *state, int player)
  618. {
  619.     int i, look_for = 1 << num_to_connect;
  620.  
  621.     for (i=0; i<win_places; i++)
  622.         if (state->score_array[player][i] == look_for)
  623.             return TRUE;
  624.  
  625.     return FALSE;
  626. }
  627.  
  628.  
  629. /****************************************************************************/
  630. /**                                                                        **/
  631. /**  This function returns TRUE if the board is completely full, FALSE     **/
  632. /**  otherwise.                                                            **/
  633. /**                                                                        **/
  634. /**  The specified game state is used, which may be a temporary state.     **/
  635. /**                                                                        **/
  636. /****************************************************************************/
  637.  
  638. static Boolean
  639. tie(Game_state *state)
  640. {
  641.     return (state->num_of_pieces == size_x * size_y);
  642. }
  643.  
  644.  
  645. /****************************************************************************/
  646. /**                                                                        **/
  647. /**  This function returns a measure of the "goodness" of the specified    **/
  648. /**  state for the specified player.  This goodness value is calculated by **/
  649. /**  subtracting the score of the player's opponent from the player's own  **/
  650. /**  score.  A positive value will result if the specified player is in a  **/
  651. /**  better situation than his/her opponent.                               **/
  652. /**                                                                        **/
  653. /****************************************************************************/
  654.  
  655. static int
  656. goodness_of(Game_state *state, int player)
  657. {
  658.     return player_score(state, player) - player_score(state, other(player));
  659. }
  660.  
  661.  
  662. /****************************************************************************/
  663. /**                                                                        **/
  664. /**  This function will return a copy of the specified state.  For         **/
  665. /**  efficiency, an array of allocated temporary states is kept, so that   **/
  666. /**  memory does not have to be allocated for a new state every time this  **/
  667. /**  function is called.  When the copy is finished with, it must be       **/
  668. /**  destroyed with destroy_state().                                       **/
  669. /**                                                                        **/
  670. /****************************************************************************/
  671.  
  672. static Game_state *
  673. copy_state(Game_state *state)
  674. {
  675.     int i, j, k;
  676.  
  677.     for (i=0; i<temp_states_allocated; i++)
  678.         if(!temp_array[i]) break;
  679.  
  680.     if (i==temp_states_allocated) {
  681.         if (i==NUM_OF_TEMP_STATES) {
  682.             fprintf(stderr, "copy_state: too many temp states\n");
  683.             exit(1);
  684.         }
  685.  
  686.         /* Allocate space for the board */
  687.  
  688.         temp_states[i].board = (char **) emalloc(size_x * sizeof(char *));
  689.         for (j=0; j<size_x; j++)
  690.             temp_states[i].board[j] = (char *) emalloc(size_y * sizeof(char));
  691.  
  692.         /* Allocate space for the score array */
  693.  
  694.         temp_states[i].score_array[0] =
  695.                                 (int *) emalloc(win_places * sizeof(int));
  696.         temp_states[i].score_array[1] =
  697.                                 (int *) emalloc(win_places * sizeof(int));
  698.  
  699.         temp_states_allocated++;
  700.     }
  701.  
  702.     temp_array[i] = TRUE;
  703.  
  704.     /* Copy the board */
  705.  
  706.     for (j=0; j<size_x; j++)
  707.         for (k=0; k<size_y; k++)
  708.             temp_states[i].board[j][k] = state->board[j][k];
  709.  
  710.     /* Copy the score array */
  711.  
  712.     for (j=0; j<win_places; j++) {
  713.         temp_states[i].score_array[0][j] = state->score_array[0][j];
  714.         temp_states[i].score_array[1][j] = state->score_array[1][j];
  715.     }
  716.  
  717.     return &temp_states[i];
  718. }
  719.  
  720.  
  721. /****************************************************************************/
  722. /**                                                                        **/
  723. /**  This function destroys the specified game state (assumed to have been **/
  724. /**  created by copy_state()).  For efficiency, the memory used by the     **/
  725. /**  state is not deallocated, so that copy_state() may use this memory    **/
  726. /**  again for a new state.                                                **/
  727. /**                                                                        **/
  728. /****************************************************************************/
  729.  
  730. static void
  731. destroy_state(Game_state *state)
  732. {
  733.     int i, j;
  734.  
  735.     for (i=0; i<temp_states_allocated; i++)
  736.         if(state == &temp_states[i]) break;
  737.  
  738.     if (i==temp_states_allocated) {
  739.         fprintf(stderr, "destroy_state: state doesn't exist\n");
  740.         exit(1);
  741.     }
  742.  
  743.     temp_array[i] = FALSE;
  744. }
  745.  
  746.  
  747. /****************************************************************************/
  748. /**                                                                        **/
  749. /**  This function determines how good the specified state may turn out to **/
  750. /**  be for the specified player.  It does this by looking ahead level     **/
  751. /**  moves.  It is assumed that both the specified player and the opponent **/
  752. /**  may make the best move possible.  Since this function is recursive,   **/
  753. /**  depth keeps track of the current depth of recursion.  so_far keeps    **/
  754. /**  track of the best worst goodness (if you dig my meaning) so far, so   **/
  755. /**  that if a goodness worse than that crops up, the game tree can be     **/
  756. /**  pruned to avoid searching unneccessary paths (this technique is       **/
  757. /**  called alpha-beta cutoff).                                            **/
  758. /**                                                                        **/
  759. /**  The specified poll function (if any) is called at the appropriate     **/
  760. /**  level.                                                                **/
  761. /**                                                                        **/
  762. /**  The worst goodness that the specified state can produce in the number **/
  763. /**  of moves (levels) searched is returned.  This is the best the         **/
  764. /**  specified player can hope to achieve with this state (since it is     **/
  765. /**  assumed that the opponent will make the best moves possible).         **/
  766. /**                                                                        **/
  767. /****************************************************************************/
  768.  
  769. static int
  770. worst_goodness(Game_state *state, int player, int level, int depth, int so_far)
  771. {
  772.     int i, goodness, best;
  773.     Game_state *temp_state;
  774.  
  775.     if (poll_function && level-depth==poll_level) (*poll_function)();
  776.     if (level == depth)
  777.         return goodness_of(state, player);
  778.     else {
  779.         /* Assume it is the other player's turn. */
  780.         best = -2000000;
  781.         for(i=0; i<size_x; i++) {
  782.             temp_state = copy_state(state);
  783.             if (!drop_piece(temp_state, other(player), i)) {
  784.                 destroy_state(temp_state);
  785.                 continue;
  786.             }
  787.             if (winner(temp_state, other(player)))
  788.                 goodness = 1000000 - depth;
  789.             else
  790.                 goodness = worst_goodness(temp_state, other(player), level,
  791.                                                 depth+1, best);
  792.             if (goodness > best)
  793.                 best = goodness;
  794.             destroy_state(temp_state);
  795.             if (-best < so_far) break;
  796.         }
  797.  
  798.         /* What's good for the other player is bad for this one. */
  799.         return -best;
  800.     }
  801. }
  802.  
  803.  
  804. /****************************************************************************/
  805. /**                                                                        **/
  806. /**  A safer version of malloc().                                          **/
  807. /**                                                                        **/
  808. /****************************************************************************/
  809.  
  810. void *
  811. emalloc(unsigned int n)
  812. {
  813.     void *ptr;
  814.  
  815.     ptr = (void *) malloc(n);
  816.     if ( ptr == NULL ) {
  817.         fprintf(stderr,"c4: emalloc() - Can't allocate %d bytes.\n", n);
  818.         exit(1);
  819.     }
  820.     return ptr;
  821. }
  822.  
  823.