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