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