1 /* 2 * Copyright (c) 1994 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Ralph Campbell. 7 * 8 * %sccs.include.redist.c% 9 * 10 * @(#)gomoku.h 8.2 (Berkeley) 05/03/95 11 */ 12 13 #include <sys/types.h> 14 15 /* board dimensions */ 16 #define BSZ 19 17 #define BSZ1 (BSZ+1) 18 #define BSZ2 (BSZ+2) 19 #define BAREA (BSZ2*BSZ1+1) 20 21 /* frame dimentions (based on 5 in a row) */ 22 #define FSZ1 BSZ 23 #define FSZ2 (BSZ-4) 24 #define FAREA (FSZ1*FSZ2 + FSZ2*FSZ2 + FSZ1*FSZ2 + FSZ2*FSZ2) 25 26 #define MUP (BSZ1) 27 #define MDOWN (-BSZ1) 28 #define MLEFT (-1) 29 #define MRIGHT (1) 30 31 /* values for s_occ */ 32 #define BLACK 0 33 #define WHITE 1 34 #define EMPTY 2 35 #define BORDER 3 36 37 /* return values for makemove() */ 38 #define MOVEOK 0 39 #define RESIGN 1 40 #define ILLEGAL 2 41 #define WIN 3 42 #define TIE 4 43 #define SAVE 5 44 45 #define A 1 46 #define B 2 47 #define C 3 48 #define D 4 49 #define E 5 50 #define F 6 51 #define G 7 52 #define H 8 53 #define J 9 54 #define K 10 55 #define L 11 56 #define M 12 57 #define N 13 58 #define O 14 59 #define P 15 60 #define Q 16 61 #define R 17 62 #define S 18 63 #define T 19 64 65 #define PT(x,y) ((x) + BSZ1 * (y)) 66 67 /* 68 * A 'frame' is a group of five or six contiguous board locations. 69 * An open ended frame is one with spaces on both ends; otherwise, its closed. 70 * A 'combo' is a group of intersecting frames and consists of two numbers: 71 * 'A' is the number of moves to make the combo non-blockable. 72 * 'B' is the minimum number of moves needed to win once it can't be blocked. 73 * A 'force' is a combo that is one move away from being non-blockable 74 * 75 * Single frame combo values: 76 * <A,B> board values 77 * 5,0 . . . . . O 78 * 4,1 . . . . . . 79 * 4,0 . . . . X O 80 * 3,1 . . . . X . 81 * 3,0 . . . X X O 82 * 2,1 . . . X X . 83 * 2,0 . . X X X O 84 * 1,1 . . X X X . 85 * 1,0 . X X X X O 86 * 0,1 . X X X X . 87 * 0,0 X X X X X O 88 * 89 * The rule for combining two combos (<A1,B1> <A2,B2>) 90 * with V valid intersection points, is: 91 * A' = A1 + A2 - 2 - V 92 * B' = MIN(A1 + B1 - 1, A2 + B2 - 1) 93 * Each time a frame is added to the combo, the number of moves to complete 94 * the force is the number of moves needed to 'fill' the frame plus one at 95 * the intersection point. The number of moves to win is the number of moves 96 * to complete the best frame minus the last move to complete the force. 97 * Note that it doesn't make sense to combine a <1,x> with anything since 98 * it is already a force. Also, the frames have to be independent so a 99 * single move doesn't affect more than one frame making up the combo. 100 * 101 * Rules for comparing which of two combos (<A1,B1> <A2,B2>) is better: 102 * Both the same color: 103 * <A',B'> = (A1 < A2 || A1 == A2 && B1 <= B2) ? <A1,B1> : <A2,B2> 104 * We want to complete the force first, then the combo with the 105 * fewest moves to win. 106 * Different colors, <A1,B1> is the combo for the player with the next move: 107 * <A',B'> = A2 <= 1 && (A1 > 1 || A2 + B2 < A1 + B1) ? <A2,B2> : <A1,B1> 108 * We want to block only if we have to (i.e., if they are one move away 109 * from completing a force and we don't have a force that we can 110 * complete which takes fewer or the same number of moves to win). 111 */ 112 113 #define MAXA 6 114 #define MAXB 2 115 #define MAXCOMBO 0x600 116 117 union comboval { 118 struct { 119 #if BYTE_ORDER == BIG_ENDIAN 120 u_char a; /* # moves to complete force */ 121 u_char b; /* # moves to win */ 122 #endif 123 #if BYTE_ORDER == LITTLE_ENDIAN 124 u_char b; /* # moves to win */ 125 u_char a; /* # moves to complete force */ 126 #endif 127 } c; 128 u_short s; 129 }; 130 131 /* 132 * This structure is used to record information about single frames (F) and 133 * combinations of two more frames (C). 134 * For combinations of two or more frames, there is an additional 135 * array of pointers to the frames of the combination which is sorted 136 * by the index into the frames[] array. This is used to prevent duplication 137 * since frame A combined with B is the same as B with A. 138 * struct combostr *c_sort[size c_nframes]; 139 * The leaves of the tree (frames) are numbered 0 (bottom, leftmost) 140 * to c_nframes - 1 (top, right). This is stored in c_frameindex and 141 * c_dir if C_LOOP is set. 142 */ 143 struct combostr { 144 struct combostr *c_next; /* list of combos at the same level */ 145 struct combostr *c_prev; /* list of combos at the same level */ 146 struct combostr *c_link[2]; /* C:previous level or F:NULL */ 147 union comboval c_linkv[2]; /* C:combo value for link[0,1] */ 148 union comboval c_combo; /* C:combo value for this level */ 149 u_short c_vertex; /* C:intersection or F:frame head */ 150 u_char c_nframes; /* number of frames in the combo */ 151 u_char c_dir; /* C:loop frame or F:frame direction */ 152 u_char c_flg; /* C:combo flags */ 153 u_char c_frameindex; /* C:intersection frame index */ 154 u_char c_framecnt[2]; /* number of frames left to attach */ 155 u_char c_emask[2]; /* C:bit mask of completion spots for 156 * link[0] and link[1] */ 157 u_char c_voff[2]; /* C:vertex offset within frame */ 158 }; 159 160 /* flag values for c_flg */ 161 #define C_OPEN_0 0x01 /* link[0] is an open ended frame */ 162 #define C_OPEN_1 0x02 /* link[1] is an open ended frame */ 163 #define C_LOOP 0x04 /* link[1] intersects previous frame */ 164 #define C_MARK 0x08 /* indicates combo processed */ 165 166 /* 167 * This structure is used for recording the completion points of 168 * multi frame combos. 169 */ 170 struct elist { 171 struct elist *e_next; /* list of completion points */ 172 struct combostr *e_combo; /* the whole combo */ 173 u_char e_off; /* offset in frame of this empty spot */ 174 u_char e_frameindex; /* intersection frame index */ 175 u_char e_framecnt; /* number of frames left to attach */ 176 u_char e_emask; /* real value of the frame's emask */ 177 union comboval e_fval; /* frame combo value */ 178 }; 179 180 /* 181 * One spot structure for each location on the board. 182 * A frame consists of the combination for the current spot plus the five spots 183 * 0: right, 1: right & down, 2: down, 3: down & left. 184 */ 185 struct spotstr { 186 short s_occ; /* color of occupant */ 187 short s_wval; /* weighted value */ 188 int s_flg; /* flags for graph walks */ 189 struct combostr *s_frame[4]; /* level 1 combo for frame[dir] */ 190 union comboval s_fval[2][4]; /* combo value for [color][frame] */ 191 union comboval s_combo[2]; /* minimum combo value for BLK & WHT */ 192 u_char s_level[2]; /* number of frames in the min combo */ 193 u_char s_nforce[2]; /* number of <1,x> combos */ 194 struct elist *s_empty; /* level n combo completion spots */ 195 struct elist *s_nempty; /* level n+1 combo completion spots */ 196 int dummy[2]; /* XXX */ 197 }; 198 199 /* flag values for s_flg */ 200 #define CFLAG 0x000001 /* frame is part of a combo */ 201 #define CFLAGALL 0x00000F /* all frame directions marked */ 202 #define IFLAG 0x000010 /* legal intersection point */ 203 #define IFLAGALL 0x0000F0 /* any intersection points? */ 204 #define FFLAG 0x000100 /* frame is part of a <1,x> combo */ 205 #define FFLAGALL 0x000F00 /* all force frames */ 206 #define MFLAG 0x001000 /* frame has already been seen */ 207 #define MFLAGALL 0x00F000 /* all frames seen */ 208 #define BFLAG 0x010000 /* frame intersects border or dead */ 209 #define BFLAGALL 0x0F0000 /* all frames dead */ 210 211 /* 212 * This structure is used to store overlap information between frames. 213 */ 214 struct ovlp_info { 215 int o_intersect; /* intersection spot */ 216 struct combostr *o_fcombo; /* the connecting combo */ 217 u_char o_link; /* which link to update (0 or 1) */ 218 u_char o_off; /* offset in frame of intersection */ 219 u_char o_frameindex; /* intersection frame index */ 220 }; 221 222 extern char *letters; 223 extern char fmtbuf[]; 224 extern char pdir[]; 225 226 extern int dd[4]; 227 extern struct spotstr board[BAREA]; /* info for board */ 228 extern struct combostr frames[FAREA]; /* storage for single frames */ 229 extern struct combostr *sortframes[2]; /* sorted, non-empty frames */ 230 extern u_char overlap[FAREA * FAREA]; /* frame [a][b] overlap */ 231 extern short intersect[FAREA * FAREA]; /* frame [a][b] intersection */ 232 extern int movelog[BSZ * BSZ]; /* history of moves */ 233 extern int movenum; 234 extern int debug; 235 236 extern char *copy(); 237 extern char *stoc(); 238 extern char *tail(); 239 240 #define ASSERT(x) 241