home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_07_03 / v7n3092a.txt < prev    next >
Text File  |  1989-01-27  |  32KB  |  933 lines
  1. /*-----------------------------------------------------------------------------
  2. OTHELLO.H
  3.  
  4. This file contains global function prototypes, external variable declarations,
  5. and manifest constant definitions for the othello program.
  6.  
  7. Revision History
  8. ----------------
  9. Jon Ward    17 Oct 1988    Initial Revision.
  10. Jon Ward    30 Oct 1988    Added typedef for move type.
  11. Jon Ward    01 Nov 1988    Added constant defs and macros.
  12. Jon Ward    04 Dec 1988    Changed fa_ndx_struct from a structure to an
  13.                            array.
  14. Jon Ward    12 Dec 1988    Started adding function prototypes and external
  15.                            declarations for global variables.
  16. Gary Culp   15 Dec 1988    Added declaration for delta_array, BELONGS macro.
  17. Gary Culp   19 Dec 1988    Updated prototypes for functions in PROTECT.C
  18. Gary Culp   22 Dec 1988    Added MAX_AFFECTED_PIECES.
  19. Gary Culp    2 Jan 1989    Added STATIC and BT_MAX_DEPTH
  20. Jon Ward     3 Jan 1989    Added prototypes for minimax functions.
  21.                 added prototype for limb removing DB function
  22. Jon Ward     7 Jan 1989    Added last_max_score extern for MINIMAX.C.
  23. -----------------------------------------------------------------------------*/
  24.  
  25.  
  26. /*-----------------------------------------------------------------------------
  27. For debugging purposes, it is sometimes useful to change 'static' functions and
  28. variables to global, so they will appear in MAP files.  This definition makes
  29. that easier to do.  Just define STATIC to be an empty string (For MSC, the
  30. command line option "/DSTATIC=" will do this.) Do not use STATIC to declare
  31. static variables inside functions!  They will turn into automatics, and cease
  32. to work correctly.
  33. -----------------------------------------------------------------------------*/
  34. #ifndef STATIC
  35. #define STATIC static
  36. #endif
  37.  
  38.  
  39. /*-----------------------------------------------------------------------------
  40. This constant represents the number of axes on the othello board that can 
  41. contain a capture. There are obviously 8 vertical and 8 horizontal columns and 
  42. rows. There are also 15 diagonal "rows" forward and 15 diagonal "rows" 
  43. backward. However, 4 of each of these 15 are eliminated because a row must 
  44. contain 3 or more cells for a capture to occur. The 2 diagonal "rows" nearest 
  45. each corner have only 1 and 2 cells.
  46. -----------------------------------------------------------------------------*/
  47.  
  48. #define NUM_CAPTURABLE_AXES (11 + 11 + 8 + 8)
  49.  
  50.  
  51. /*-----------------------------------------------------------------------------
  52. The following board structure will contain the definition for a particular
  53. board.
  54.  
  55. The board element will contain bits (as defined below) that tell whether a cell
  56. is empty or occupied and whether the piece in that cell is protected along an
  57. axis. Once a piece is protected along all 4 axes, it has become permanent and
  58. can never be changed in the remainder of this game.
  59.  
  60. The fa_bits (fa being full axis) is an array of bits that tell if a particular
  61. axis is completely full.  1 is added for the non-capturable axes and 7 is added
  62. to round up to the nearest byte.
  63. -----------------------------------------------------------------------------*/
  64.  
  65. #define FA_BITS_SIZE ((NUM_CAPTURABLE_AXES + 1 + 7) / 8)
  66.  
  67. struct board_struct
  68.   {
  69.   unsigned char board [10][10];
  70.   unsigned char fa_bits [FA_BITS_SIZE];
  71.   };
  72.  
  73. typedef struct board_struct board_type;
  74.  
  75.  
  76. /*-----------------------------------------------------------------------------
  77. Board manifest constants and macros for the board_struct board element.
  78.  
  79. Note that the first four bits (NO_PIECE thru OFF_BOARD) are mutually exclusive.
  80. Only one of them may be set at a given time.
  81.  
  82. This bit mapping is NOT arbitrary.  The IS_PERM macro is a good example of why
  83. it is not.  The program exploits the numerical properties of the variables
  84. built with these definitions, as well as extracting bits from them.
  85. -----------------------------------------------------------------------------*/
  86.  
  87. #define NO_PIECE    0x01    /* Empty cell, No disk there */
  88. #define US_PIECE    0x02    /* Cell occupied by our disk */
  89. #define THEM_PIECE    0x04    /* Cell occupied by their disk */
  90. #define OFF_BOARD    0x08    /* Cell is off the board */
  91. #define BD_AX        0x10    /* Backward diagonal axis protected */
  92. #define FD_AX        0x20    /* Forward diagonal axis protected */
  93. #define H_AX        0x40    /* Horizontal axis protected */
  94. #define V_AX        0x80    /* Vertical axis protected */
  95.  
  96. #define IS_PERM(cell) ((cell) > (NO_PIECE | BD_AX | FD_AX | H_AX | V_AX))
  97. #define BELONGS(cell,code) ((cell)&(code))
  98.  
  99. #define TEST_BITS(cell,bits) ((cell) & (bits))
  100. #define SET_BITS(cell,bits) ((cell) |= (bits))
  101. #define CLR_BITS(cell,bits) ((cell) &= ~(bits))
  102.  
  103.  
  104. /*-----------------------------------------------------------------------------
  105. Full axis table for FA index table and macros for setting and testing the FA
  106. bits.
  107. -----------------------------------------------------------------------------*/
  108.  
  109. typedef unsigned char fa_type [4];
  110.  
  111. #define BD_NDX 0    /* index for backward diagonal FA bit */
  112. #define FD_NDX 1    /* index for forward diagonal FA bit */ 
  113. #define H_NDX  2    /* index for horizontal FA bit */       
  114. #define V_NDX  3    /* index for vertical FA bit */         
  115.  
  116. #define WHICH_BYTE(ndx) ((unsigned char) (ndx) >> 3)
  117. #define BIT_N_BYTE(ndx) ((unsigned char) 1 << ((ndx) & 0x07))
  118.  
  119. #define SET_FA_BIT(fa,bit) ((fa) [WHICH_BYTE(bit)] |= BIT_N_BYTE(bit))
  120. #define CHK_FA_BIT(fa,bit) ((fa) [WHICH_BYTE(bit)] & BIT_N_BYTE(bit))
  121.  
  122.  
  123. /*-----------------------------------------------------------------------------
  124. The following type is used to represent a number used for indexing into the
  125. database manager when referencing a node (limb) in one of the move trees.
  126. -----------------------------------------------------------------------------*/
  127.  
  128. typedef unsigned int key_type;
  129.  
  130. #define NO_KEY ((key_type) 0xFFFF)
  131.  
  132.  
  133. /*-----------------------------------------------------------------------------
  134. The following type is used to represent the row and column of an othello move.
  135.  
  136. Since there are only 8 rows and 8 columns on the othello board, the move can be
  137. reduced to 6 bits, 3 for the row and 3 for the column.  One of the remaining
  138. bits is used to indicate that the player (computer or opponent) has no valid
  139. moves.  The other bit will be used by the DBM to indicate that there is a board
  140. associated with a limb entry.
  141.  
  142. The GET_ROW/GET_COL macros extract and normalize the row and col stored in a
  143. move_type.
  144.  
  145. The SET_ROW/SET_COL macros initialize the row and col for a move_type.
  146.  
  147. The CLR_ROW/CLR_COL macros clear the row and col for a move_type.
  148. -----------------------------------------------------------------------------*/
  149.  
  150. typedef unsigned char move_type;
  151.  
  152. #define ROW_MASK    0x07    /* 3 bits for row number */
  153. #define COL_MASK    0x38    /* 3 bits for col number */
  154. #define NO_MOVE_MASK    0x40    /* bit set for no valid moves */
  155. #define BOARD_MASK    0x80    /* bit set in DBM if bottom level of tree */
  156. #define HASNT_MOVED BOARD_MASK /* returned by check_for_input() when
  157.                                   move has not been entered yet */
  158.  
  159. #define GET_ROW(move) ((move) & ROW_MASK) 
  160. #define GET_COL(move) (((move) & COL_MASK) >> 3)
  161.  
  162. #define SET_ROW(move,row) ((move) |= ((row) & 0x07))
  163. #define SET_COL(move,col) ((move) |= ((col) & 0x07) << 3)
  164.  
  165. #define CLR_ROW(move) ((move) &= ~ROW_MASK)
  166. #define CLR_COL(move) ((move) &= ~COL_MASK)
  167.  
  168. #define SET_ROW_COL(m,r,c) ((m) |= (((c) & 0x07) << 3) | ((r) & 0x07))
  169.  
  170.  
  171. /*-----------------------------------------------------------------------------
  172. The limb_type type represents the data that is contained at each branch (limb)
  173. in the move tree.
  174.  
  175. The bc union is either a key for the board at this limb, or is a key for the
  176. first child of this limb.  The move struct element will have the BOARD_MASK
  177. bit set if the bc element is a board key.  If the BOARD_MASK bit is NOT set,
  178. bc will be the child_key.
  179.  
  180. A value of NO_KEY indicates that there are no children or siblings.
  181. -----------------------------------------------------------------------------*/
  182.  
  183. struct limb_struct 
  184.   {
  185.   move_type move;        /* what we did to get here */
  186.   int score;            /* value of this limb */
  187.   key_type sibling_key;        /* key for next sibling of this limb */
  188.  
  189.   union
  190.     {
  191.     key_type child_key;        /* key for the limb's first child */
  192.     key_type board_key;        /* key for board at this limb */
  193.     } bc;
  194.  
  195.   };
  196.  
  197. typedef struct limb_struct limb_type;
  198.  
  199.  
  200. /*-----------------------------------------------------------------------------
  201. Maximum depth to build the tree
  202. -----------------------------------------------------------------------------*/
  203. #define BT_MAX_DEPTH 11
  204.  
  205.  
  206. /*-----------------------------------------------------------------------------
  207.                    BD_EVAL.C
  208. -----------------------------------------------------------------------------*/
  209. int bd_eval(
  210.    struct board_struct *board_ptr,
  211.    unsigned char which_color);
  212.  
  213. /*-----------------------------------------------------------------------------
  214.                     BDTTY.C
  215. -----------------------------------------------------------------------------*/
  216. void disp_board (board_type *board);
  217. void disp_row (int row);
  218. void disp_col (int col);
  219. void disp_clr_row_col (void);
  220. void disp_init (void);
  221. void disp_error_msg (char *msg);
  222. void disp_player_move (unsigned char player);
  223. void disp_player_cant_move (unsigned char player);
  224. void disp_player_moved_to (unsigned char player);
  225. void disp_pieces (int us, int them);
  226.  
  227. extern char us_char;
  228. extern char them_char;
  229.  
  230.  
  231. /*-----------------------------------------------------------------------------
  232.                    BUILDLVL.C
  233. -----------------------------------------------------------------------------*/
  234. int build_tree (
  235.    int depth_to_build,
  236.    unsigned char movers_color);
  237.  
  238. void update_tree_after_our_move (
  239.    key_type our_move);
  240.  
  241. /*-----------------------------------------------------------------------------
  242.                     FATABL.C
  243. -----------------------------------------------------------------------------*/
  244. extern fa_type fa_tabl [8][8];
  245.  
  246.  
  247. /*-----------------------------------------------------------------------------
  248.                     GETMOV.C
  249. -----------------------------------------------------------------------------*/
  250. move_type check_for_input (void);
  251. void init_input_vars (void);
  252.  
  253.  
  254. /*-----------------------------------------------------------------------------
  255.                    MINIMAX.C
  256. -----------------------------------------------------------------------------*/
  257. key_type find_best_move (
  258.    key_type root,
  259.    int depth);
  260.  
  261. key_type find_worst_move (
  262.    key_type root,
  263.    int depth);
  264.  
  265. extern int last_max_score;    /* score for last tree evaluated */
  266.  
  267.  
  268. /*-----------------------------------------------------------------------------
  269.                     MOVEIT.C
  270. -----------------------------------------------------------------------------*/
  271. int verify_move_and_update_board (
  272.   move_type move,
  273.   unsigned char player);
  274.  
  275. /*-----------------------------------------------------------------------------
  276.                    MOVE_GEN.C
  277. -----------------------------------------------------------------------------*/
  278. int find_move(
  279.    struct board_struct *board_ptr,
  280.    int start_displacement,
  281.    unsigned char movers_color,
  282.    int *affected_list);
  283.  
  284. /* affected_list needs room for this many entries */
  285. #define MAX_AFFECTED_PIECES 19
  286.  
  287.  
  288. /*-----------------------------------------------------------------------------
  289.                     OTHDBM.C
  290. -----------------------------------------------------------------------------*/
  291. void free_limb (key_type limb);
  292. void db_init (void);
  293. void db_kill (void);
  294.  
  295. key_type db_add_child (
  296.    key_type parent_key,
  297.    unsigned char move,
  298.    board_type *board,
  299.    int score);
  300.  
  301. int db_retrieve_board (
  302.    key_type key,
  303.    board_type *board);
  304.  
  305. limb_type far *db_retrieve_limb (
  306.    key_type key);
  307.  
  308. int db_delete_subtree (
  309.    key_type parent,
  310.    key_type child);
  311.  
  312. int db_almost_full (void);
  313. void init_borders (board_type *bd);
  314.  
  315. /*-----------------------------------------------------------------------------
  316.                    OTHELLO.C
  317. -----------------------------------------------------------------------------*/
  318. void main (void);
  319.  
  320. extern board_type curnt_bd;        /* board -- used for display */
  321. extern key_type curnt_top_limb;        /* key of limb for current board */
  322.  
  323.  
  324. /*-----------------------------------------------------------------------------
  325.                    PIECE_CT.C
  326. -----------------------------------------------------------------------------*/
  327. int piece_count(
  328.    struct board_struct *board_ptr,
  329.    unsigned char piece_type);
  330.  
  331. unsigned char who_can_move(struct board_struct *board_ptr);
  332.  
  333. /*-----------------------------------------------------------------------------
  334.                    PROTECT.C
  335. -----------------------------------------------------------------------------*/
  336. void update_protection_for_board(
  337.    struct board_struct *board_ptr,
  338.    int *affected_list, /* list of affected pieces, beginning with new piece */
  339.    int num_affected,   /* number of pieces in affected list */
  340.    unsigned char new_color);  /* new color for affected pieces */
  341.  
  342. void handle_changed_pieces(
  343.    struct board_struct *board_ptr,
  344.    int *affected_list,
  345.    int num_affected,
  346.    unsigned char new_color,
  347.    int prot_check_flag);
  348.  
  349. /*
  350.    For movement along an axis within a board, add or subtract
  351.    delta_array[axis_number] to a pointer to a cell within the board.
  352. */
  353. extern const int delta_array[4];
  354.  
  355.  
  356. /*-----------------------------------------------------------------------------
  357. -----------------------------------------------------------------------------*/
  358.  
  359. /*-----------------------------------------------------------------------------
  360. MINIMAX.C
  361.  
  362. This file contains the tree searching minimax algorithms.
  363.  
  364. Revision History
  365. ----------------
  366. Jon Ward     2 Jan 1989    Initial Revision
  367. Jon Ward     7 Jan 1989    Added last_max_score var for statistical stuff.
  368. -----------------------------------------------------------------------------*/
  369.  
  370. #include <stdio.h>
  371. #include <limits.h>
  372.  
  373. #include "othello.h"
  374.  
  375.  
  376. /*-----------------------------------------------------------------------------
  377.               Global Variable Declarations
  378. -----------------------------------------------------------------------------*/
  379. int last_max_score;
  380.  
  381. /*-----------------------------------------------------------------------------
  382.                Local Function Prototypes
  383. -----------------------------------------------------------------------------*/
  384. STATIC int mm_max (
  385.    key_type parent,        /* limb whose children will be maxd */
  386.    int depth,            /* number of levels to minimax */
  387.    key_type *best);        /* pointer to best move */
  388.  
  389. STATIC int mm_min (
  390.    key_type parent,        /* limb whose children will be mind */
  391.    int depth,            /* number of levels to minimax */
  392.    key_type *worst);        /* pointer to worst move */
  393.  
  394.  
  395. /*-----------------------------------------------------------------------------
  396. STATIC int mm_max (
  397.    key_type parent,
  398.    int depth,
  399.    key_type *best);
  400.  
  401. This function will find the maximal board score depth levels below the parent.
  402. The value returned is the maximal score.
  403. -----------------------------------------------------------------------------*/
  404.  
  405. STATIC int mm_max (
  406.    key_type parent,        /* limb whose children will be maxd */
  407.    int depth,            /* number of levels to minimax */
  408.    key_type *best)        /* pointer to best move */
  409. {
  410. register int max;        /* value for the maximal limb */
  411. int score;            /* score for the current limb */
  412. limb_type far *l;        /* pointer to the limb for the current limb */
  413. register key_type limb;        /* key for the current limb */
  414.  
  415. max = INT_MIN;            /* minimum int value */
  416.  
  417. limb = (db_retrieve_limb (parent))->bc.child_key;
  418.  
  419. for (; limb != NO_KEY; limb = l->sibling_key)
  420.   {
  421.   l = db_retrieve_limb (limb);
  422.  
  423.   score = (depth) ? mm_min (limb, depth - 1, NULL) : l->score;
  424.  
  425.   if (score > max)
  426.     {
  427.     max = score;
  428.     if (best)
  429.       *best = limb;
  430.     }
  431.   }
  432.  
  433. return (max);
  434. }
  435.  
  436.  
  437. /*-----------------------------------------------------------------------------
  438. STATIC int mm_min (
  439.    key_type parent,
  440.    int depth,
  441.    key_type *worst);
  442.  
  443. This function will find the minimal board score depth levels below the parent.
  444. The value returned is the minimal score.
  445. -----------------------------------------------------------------------------*/
  446.  
  447. STATIC int mm_min (
  448.    key_type parent,        /* limb whose children will be mind */
  449.    int depth,            /* number of levels to minimax */
  450.    key_type *worst)        /* pointer to worst move */
  451. {
  452. register int min;        /* value for the minimal limb */
  453. int score;            /* score for the current limb */
  454. limb_type far *l;        /* pointer to the limb for the current limb */
  455. register key_type limb;        /* key for the current limb */
  456.  
  457. min = INT_MAX;            /* maximum int value */
  458.  
  459. limb = (db_retrieve_limb (parent))->bc.child_key;
  460.  
  461. for (; limb != NO_KEY; limb = l->sibling_key)
  462.   {
  463.   l = db_retrieve_limb (limb);
  464.  
  465.   score = (depth) ? mm_max (limb, depth - 1, NULL) : l->score;
  466.  
  467.   if (score < min)
  468.     {
  469.     min = score;
  470.     if (worst)
  471.       *worst = limb;
  472.     }
  473.   }
  474.  
  475. return (min);
  476. }
  477.  
  478.  
  479. /*-----------------------------------------------------------------------------
  480. key_type find_best_move (
  481.    key_type root,
  482.    int depth);
  483.  
  484. This function returns the key of the maximal move for the root referenced by
  485. the root argument. Note that the root key is the key for the currently
  486. displayed board and that its children are the moves that will finally be
  487. considered. The depth argument is the number of levels of children that exist
  488. below the root.  For example, depth = 1 means that there is only one level
  489. built below the root.
  490. -----------------------------------------------------------------------------*/
  491.  
  492. key_type find_best_move (
  493.    key_type root,        /* key to root of tree */
  494.    int depth)            /* levels below root to look */
  495. {
  496. key_type best_move;
  497.  
  498. last_max_score = mm_max (root, depth - 1, &best_move);    /* do the minimax */
  499. return (best_move);            /* return the limb key of the best move */
  500. }
  501.  
  502. /*-----------------------------------------------------------------------------
  503. -----------------------------------------------------------------------------*/
  504.  
  505. /*-----------------------------------------------------------------------------
  506. Update board
  507.  
  508. Revision History
  509. ----------------
  510. Gary Culp   3-14 Dec 1988  Initial version.
  511. Gary Culp   19 Dec 1988    Added prot_check_flag to handle_changed_pieces, so
  512.                            that the display routines can use it, too.
  513. -----------------------------------------------------------------------------*/
  514.  
  515. /*
  516. Glossary terms:        ***!!!
  517.    permanent  (piece)
  518.    axis
  519.    hostile    (piece or color)
  520.    friendly   (piece or color)
  521.    off-board  (piece or color)
  522.  
  523. A common piece of advice to Othello players is to take the corners of the
  524. board, because they can never be captured from you.  Not only can you depend
  525. upon their contributing to your final count of pieces, they make a good
  526. solid foundation upon which to build.  Something I haven't heard pointed out
  527. though, is that corners aren't the only pieces that can't be captured.
  528. I call any piece that can't be captured a permanent piece.  My strategy when
  529. playing Othello is to acquire as many permanent pieces as I can; and that is
  530. the strategy implemented in this game.  The most challenging part of this
  531. project, for me, was figuring out an efficient algorithm for determining which
  532. pieces in a given board configuration are permanent.  The answer was obvious
  533. (after several hours of intense thought :) ).
  534. This file contains the code which implements the algorithm.
  535.  
  536. To capture a piece (or line of pieces), P, the opponent must place 
  537. his pieces, O, on opposite sides of P.
  538. There are 4 axes through which this may be done:
  539.  
  540. horizontal   vertical   forward    backward
  541.                         diagonal   diagonal
  542.                O             O      O
  543.  O P O         P           P          P
  544.                O         O              O
  545.  
  546. If a piece is protected from being captured along all 4 axes, it cannot be
  547. captured at all, and is therefore permanent.
  548.  
  549. A piece is protected along an axis if one of these conditions is true:
  550.  
  551. 1)  The axis is full.
  552. 2)  One of the adjacent pieces along the axis is a friendly permanent piece.
  553. 3)  Both of the adjacent pieces along the axis are permanent.  (It doesn't
  554.     matter what colors they are.)
  555.  
  556. For these rules for protection along an axis to work, we have imaginary
  557. squares which lie off the edge of the board (that's why the boards are
  558. manipulated as 10x10 instead of 8x8).  These imaginary squares contain
  559. permanent pieces of a third color: "off-board".  Off-board is considered
  560. to be a friendly color, for both players.  It may seem weird to add all
  561. this imaginary stuff to the game, but it greatly simplifies handling the
  562. edge of the board.  Off-board pieces make the code simpler, smaller,
  563. and faster, at the expense of making the board data structure larger.
  564.  
  565. When to check protection and permanence:
  566.  
  567.    When a piece is played or its color is changed, all 4 of its axes must be
  568.    checked for protection (previous protection may be invalidated by color
  569.    change).
  570.  
  571.    When a protection bit that was clear is set, the piece must be checked
  572.    for permanence.
  573.  
  574.    When a piece becomes permanent, the pieces adjacent to it must be checked
  575.    for protection along the axis containing the newly permanent piece.
  576. */
  577.  
  578.  
  579. #include "othello.h"
  580.  
  581.  
  582. /* These definitions aren't used anywhere else.  They are part of a trick
  583.    for determining whether the protected axis rules are satisfied. (The
  584.    rules which deal with adjacent pieces being permanent, not the rule
  585.    about a full axis.)
  586.    Note that TRICK_PROTECTED == TRICK_ADJ1_PERM | TRICK_ADJ2_PERM.
  587. */
  588. #define TRICK_ADJ1_PERM    1 
  589. #define TRICK_ADJ2_PERM    2
  590. #define TRICK_PROTECTED    3
  591.  
  592. /*--------------------------------*/
  593. /*          Prototypes            */
  594. /*--------------------------------*/
  595.  
  596. void handle_changed_pieces(
  597.    struct board_struct *board_ptr,
  598.    int *affected_list,
  599.    int num_affected,
  600.    unsigned char new_color,
  601.    int prot_check_flag);
  602.  
  603. void new_piece_axis_fill_check(
  604.    struct board_struct *board_ptr,
  605.    int *affected_list);
  606.  
  607. void perform_all_protection_checks(struct board_struct *board_ptr);
  608.  
  609. unsigned char is_filled_axis(unsigned char *new_piece_ptr, int axis_num);
  610.  
  611. void request_prot_check(
  612.    struct board_struct *board_ptr, /* pointer to board structure */
  613.    unsigned char *cell_ptr,        /* pointer to cell */
  614.    unsigned char requested_axes);  /* requesting prot check for these axes */
  615.  
  616. int next_check(int *row_num_ptr, int *clm_num_ptr, int *axis_num_ptr);
  617.  
  618. /*--------------------------------*/
  619. /*             Variables          */
  620. /*--------------------------------*/
  621.  
  622. /* To convert axis flags to axis numbers, shift the axis flag right 4 bits;
  623.    use the result as an index into this table.
  624. */
  625. static const unsigned char bit_priority_encode[] = {
  626.    0, /* [0000] */ /* actually, no bit set */
  627.    0, /* [0001] */
  628.    1, /* [0010] */
  629.    1, /* [0011] */
  630.    2, /* [0100] */
  631.    2, /* [0101] */
  632.    2, /* [0110] */
  633.    2, /* [0111] */
  634.    3, /* [1000] */
  635.    3, /* [1001] */
  636.    3, /* [1010] */
  637.    3, /* [1011] */
  638.    3, /* [1100] */
  639.    3, /* [1101] */
  640.    3, /* [1110] */
  641.    3, /* [1111] */
  642. };
  643.  
  644. /*
  645.    For movement along an axis within a board, add or subtract
  646.    delta_array[axis_number] to a pointer to a cell within the board.
  647. */
  648. const int delta_array[4] = {11, 9, 1, 10};
  649.  
  650. static unsigned char schedule_map[10][10];
  651.  
  652.  
  653. /*------------------------------*/
  654. /*           Functions          */
  655. /*------------------------------*/
  656.  
  657.  
  658. /*
  659. Given a list of affected pieces, starting with the new piece,
  660. update the board, including the protection flags.
  661. */
  662. void
  663. update_protection_for_board(
  664.    struct board_struct *board_ptr,
  665.    int *affected_list, /* list of affected pieces, beginning with new piece */
  666.    int num_affected,   /* number of pieces in affected list */
  667.    unsigned char new_color)   /* new color for affected pieces */
  668. {
  669.    handle_changed_pieces(board_ptr, affected_list, num_affected, new_color, 1);
  670.    new_piece_axis_fill_check(board_ptr, affected_list);
  671.    perform_all_protection_checks(board_ptr);
  672. }
  673.  
  674. /*
  675. Update board according to list of pieces changed by this move (including
  676. new piece).
  677. */
  678. void
  679. handle_changed_pieces(
  680.    struct board_struct *board_ptr,
  681.    register int *affected_list, /* list of affected pieces, beginning with new piece */
  682.    int num_affected,            /* number of pieces in affected list */
  683.    unsigned char new_color,     /* new color for affected pieces */
  684.    int prot_check_flag)         /* flag: request protection checks iff set */
  685. {
  686.    register unsigned char *cell_ptr;
  687.  
  688.    /* for all pieces changed by the move, including the new piece */
  689.    while (num_affected--) {
  690.  
  691.       /* Clear all protection bits for this piece & set its new color. */
  692.       *(cell_ptr = &board_ptr->board[0][0] + *affected_list++) = new_color;
  693.  
  694.       /* Request that this piece be checked for protection along all 4 axes. */
  695.       if (prot_check_flag) {
  696.          request_prot_check(board_ptr, cell_ptr, BD_AX | FD_AX | H_AX | V_AX);
  697.       }
  698.    }
  699. }
  700.  
  701. /*
  702. Check each axis of new piece to see if we filled the axis.
  703. */
  704. void
  705. new_piece_axis_fill_check(
  706.    struct board_struct *board_ptr,
  707.    int *affected_list) /* list of affected pieces, beginning with new piece */
  708. {
  709.    unsigned char axis_flag;
  710.    unsigned char *new_piece_ptr;
  711.    register unsigned char *cell_ptr;
  712.    int axis_num;
  713.  
  714.    new_piece_ptr = &board_ptr->board[0][0] + *affected_list;
  715.  
  716.    /* for all 4 axes through the new piece */
  717.    for (axis_num = BD_NDX; axis_num <= V_NDX; axis_num++) {
  718.       if (is_filled_axis(new_piece_ptr, axis_num)) {
  719.  
  720.          /* Set full-axis bit for this axis */
  721.          SET_FA_BIT(board_ptr->fa_bits,
  722.           fa_tabl[*affected_list / 10 - 1][*affected_list % 10 - 1][axis_num]);
  723.  
  724.          /* Request protection check for each piece along this axis.
  725.             (The pieces are protected along this axis, of course.
  726.             But it's easier to keep the protection checking in one place,
  727.             so we go through the scheduler.)
  728.  
  729.             The loop which does this (below) never hits the new piece, but
  730.             that's OK because we already requested that it be checked for
  731.             protection (It's in the affected_list).
  732.          */
  733.  
  734.          {
  735.             register int delta;
  736.             int pass;
  737.  
  738.             axis_flag = (unsigned char)BD_AX << axis_num;
  739.  
  740.             delta = delta_array[axis_num];
  741.             for (pass = 0; pass < 2; pass++, delta = -delta) {
  742.                cell_ptr = new_piece_ptr;
  743.                while (!(*(cell_ptr += delta) & OFF_BOARD)) {
  744.                   request_prot_check(board_ptr, cell_ptr, axis_flag);
  745.                }
  746.             }
  747.          }
  748.       }
  749.    }
  750. }
  751.  
  752.  
  753. /*
  754.    Perform protection checks until they're all done.
  755.  
  756.    initialize row and column
  757.    while scheduler returns pieces to check {
  758.       check piece for protection along specified axis
  759.       if piece is protected {
  760.          set protection flag
  761.          if piece is permanent {
  762.             schedule adjacent pieces to be checked for permanence along
  763.             the axis containing this piece
  764.          }
  765.       }
  766.    }
  767. */
  768. void
  769. perform_all_protection_checks(struct board_struct *board_ptr)
  770. {
  771.    int row;
  772.    int clm;
  773.    int rule_trick;
  774.    register unsigned char *cell_ptr;
  775.    int axis_num;
  776.  
  777.    row = 1;
  778.    clm = 1;
  779.  
  780.    while (next_check(&row, &clm, &axis_num)) {
  781.  
  782.       cell_ptr = &board_ptr->board[row][clm];
  783.  
  784.       if (CHK_FA_BIT(board_ptr->fa_bits, fa_tabl[row-1][clm-1][axis_num])) {
  785.          /* axis is full, therefore piece is protected along it */
  786.          rule_trick = TRICK_PROTECTED;
  787.       }
  788.       else {
  789.          unsigned char adjac1;
  790.          unsigned char adjac2;
  791.          unsigned char friendly_colors;
  792.  
  793.          friendly_colors = *cell_ptr & (US_PIECE | THEM_PIECE) | OFF_BOARD;
  794.          adjac1 = *(cell_ptr + delta_array[axis_num]);
  795.          adjac2 = *(cell_ptr - delta_array[axis_num]);
  796.  
  797.          rule_trick =
  798.             IS_PERM(adjac1) ?
  799.             (BELONGS(adjac1, friendly_colors) ? TRICK_PROTECTED : TRICK_ADJ1_PERM)
  800.             :
  801.             0 ;
  802.  
  803.          if (IS_PERM(adjac2)) {
  804.             rule_trick |= BELONGS(adjac2, friendly_colors) ?
  805.                TRICK_PROTECTED : TRICK_ADJ2_PERM;
  806.          }
  807.       }
  808.  
  809.       if (rule_trick == TRICK_PROTECTED) {
  810.          /* the piece is protected along this axis */
  811.  
  812.          /* set the protection flag & check for permanence */
  813.  
  814.          if (IS_PERM(*cell_ptr |= BD_AX << axis_num)) {
  815.             int sched_ax_num;
  816.       
  817.             /* Piece is now permanent. */
  818.  
  819.             /* Schedule protection checks for all adjacent pieces
  820.                along the axis containing this piece.
  821.             */
  822.             for (sched_ax_num = BD_NDX;
  823.                sched_ax_num <= V_NDX;
  824.                sched_ax_num++)
  825.             {
  826.                request_prot_check(
  827.                   board_ptr,
  828.                   cell_ptr + delta_array[sched_ax_num],
  829.                   BD_AX << sched_ax_num
  830.                );
  831.                request_prot_check(
  832.                   board_ptr,
  833.                   cell_ptr - delta_array[sched_ax_num],
  834.                   BD_AX << sched_ax_num
  835.                );
  836.                   cell_ptr - delta_array[sched_ax_num];
  837.             }
  838.          }
  839.       }
  840.    }
  841. }
  842.  
  843.  
  844. /*
  845. Set bit(s) in the protection check scheduling map.
  846.  
  847. If the cell is unoccupied, the entire request will be ignored.
  848. Schedule bits corresponding to axes which are already protected
  849.    will not be set.
  850. */
  851. void
  852. request_prot_check(
  853.    struct board_struct *board_ptr, /* pointer to board structure */
  854.    unsigned char *cell_ptr,        /* pointer to cell */
  855.    unsigned char requested_axes)   /* requesting prot check for these axes */
  856. {
  857.    if (BELONGS(*cell_ptr, US_PIECE | THEM_PIECE)) {
  858.       /* Cell is occupied.
  859.          Set bits for requested axes, except those axes
  860.          which are already protected.
  861.       */
  862.  
  863.       *(&schedule_map[0][0] + (cell_ptr - &board_ptr->board[0][0]))
  864.          |= requested_axes & ~*cell_ptr;
  865.    }
  866.    /* else cell is unoccupied, so ignore request */
  867. }
  868.  
  869. /*
  870. Get next cell for protection check
  871.  
  872. Returns:
  873.    0: no more cells need to be checked
  874.    1: cell at *row_num_ptr, *clm_num_ptr needs to be checked along axis
  875.       number *axis_num_ptr
  876. */
  877. int
  878. next_check(int *row_num_ptr, int *clm_num_ptr, int *axis_num_ptr)
  879. {
  880.    register unsigned char *p;
  881.    register unsigned char *stop;
  882.    unsigned char *start;
  883.    int temp;
  884.    int pass;
  885.  
  886.    p = start = &schedule_map[*row_num_ptr][*clm_num_ptr];
  887.    stop = &schedule_map[8][9];
  888.    for (pass = 0; pass < 2; pass++) {
  889.       while (*p == 0 && ++p < stop) ;
  890.       if (p != stop) {
  891.          /* found one, perform calcs and return */
  892.          temp = p - &schedule_map[0][0];
  893.          *row_num_ptr = temp / 10;
  894.          *clm_num_ptr = temp % 10;
  895.          /* Determine which axis & clear schedule bit for that axis */
  896.          *p ^= BD_AX << (*axis_num_ptr = bit_priority_encode[*p >> 4]);
  897.          return (1); /* found one */
  898.       }
  899.       p = &schedule_map[1][1]; /* now check from 1st cell of the board... */
  900.       stop = start;            /* ...up to where we started checking */
  901.    }
  902.    return (0); /* they're all done */
  903. }
  904.  
  905.  
  906. /*
  907. Determine whether a specified axis has been filled by a new piece.
  908.  
  909. The cell occupied by the new piece is never checked; it is just assumed
  910. to be occupied.
  911.  
  912. Returns:
  913.    1 if axis is filled, 0 if axis is not filled
  914. */
  915. unsigned char
  916. is_filled_axis(unsigned char *new_piece_ptr, int axis_num)
  917. {
  918.    register unsigned char *ptr;
  919.    register int delta;
  920.    int pass;
  921.  
  922.    delta = delta_array[axis_num];
  923.    for (pass = 0; pass < 2; pass++, delta = -delta) {
  924.       ptr = new_piece_ptr;
  925.       while (*(ptr += delta) & (US_PIECE | THEM_PIECE)) ;
  926.       if (*ptr & NO_PIECE) {
  927.          return (0);    /* This axis is still unfilled. */
  928.       }  /* else we ran off the edge of the board */
  929.    }
  930.  
  931.    return (1);
  932. }
  933.