1 /* $OpenBSD: gomoku.h,v 1.11 2015/12/26 00:26:39 mestre Exp $ */ 2 /* 3 * Copyright (c) 1994 4 * The Regents of the University of California. All rights reserved. 5 * 6 * This code is derived from software contributed to Berkeley by 7 * Ralph Campbell. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 3. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 * 33 * @(#)gomoku.h 8.2 (Berkeley) 5/3/95 34 */ 35 36 #include <stdio.h> 37 #include <sys/types.h> 38 39 /* board dimensions */ 40 #define BSZ 19 41 #define BSZ1 (BSZ+1) 42 #define BSZ2 (BSZ+2) 43 #define BSZ3 (BSZ+3) 44 #define BSZ4 (BSZ+4) 45 #define BAREA (BSZ2*BSZ1+1) 46 47 /* interactive curses stuff */ 48 #define FF '\014' /* used as redraw command */ 49 #define BGOTO(y,x) move(BSZ - (y), 2 * (x) + 3) 50 51 /* frame dimensions (based on 5 in a row) */ 52 #define FSZ1 BSZ 53 #define FSZ2 (BSZ-4) 54 #define FAREA (FSZ1*FSZ2 + FSZ2*FSZ2 + FSZ1*FSZ2 + FSZ2*FSZ2) 55 56 #define MUP (BSZ1) 57 #define MDOWN (-BSZ1) 58 #define MLEFT (-1) 59 #define MRIGHT (1) 60 61 /* values for s_occ */ 62 #define BLACK 0 63 #define WHITE 1 64 #define EMPTY 2 65 #define BORDER 3 66 67 /* return values for makemove() */ 68 #define MOVEOK 0 69 #define RESIGN 1 70 #define ILLEGAL 2 71 #define WIN 3 72 #define TIE 4 73 #define SAVE 5 74 75 #define A 1 76 #define B 2 77 #define C 3 78 #define D 4 79 #define E 5 80 #define F 6 81 #define G 7 82 #define H 8 83 #define J 9 84 #define K 10 85 #define L 11 86 #define M 12 87 #define N 13 88 #define O 14 89 #define P 15 90 #define Q 16 91 #define R 17 92 #define S 18 93 #define T 19 94 95 #define PT(x,y) ((x) + BSZ1 * (y)) 96 97 /* 98 * A 'frame' is a group of five or six contiguous board locations. 99 * An open ended frame is one with spaces on both ends; otherwise, its closed. 100 * A 'combo' is a group of intersecting frames and consists of two numbers: 101 * 'A' is the number of moves to make the combo non-blockable. 102 * 'B' is the minimum number of moves needed to win once it can't be blocked. 103 * A 'force' is a combo that is one move away from being non-blockable 104 * 105 * Single frame combo values: 106 * <A,B> board values 107 * 5,0 . . . . . O 108 * 4,1 . . . . . . 109 * 4,0 . . . . X O 110 * 3,1 . . . . X . 111 * 3,0 . . . X X O 112 * 2,1 . . . X X . 113 * 2,0 . . X X X O 114 * 1,1 . . X X X . 115 * 1,0 . X X X X O 116 * 0,1 . X X X X . 117 * 0,0 X X X X X O 118 * 119 * The rule for combining two combos (<A1,B1> <A2,B2>) 120 * with V valid intersection points, is: 121 * A' = A1 + A2 - 2 - V 122 * B' = MIN(A1 + B1 - 1, A2 + B2 - 1) 123 * Each time a frame is added to the combo, the number of moves to complete 124 * the force is the number of moves needed to 'fill' the frame plus one at 125 * the intersection point. The number of moves to win is the number of moves 126 * to complete the best frame minus the last move to complete the force. 127 * Note that it doesn't make sense to combine a <1,x> with anything since 128 * it is already a force. Also, the frames have to be independent so a 129 * single move doesn't affect more than one frame making up the combo. 130 * 131 * Rules for comparing which of two combos (<A1,B1> <A2,B2>) is better: 132 * Both the same color: 133 * <A',B'> = (A1 < A2 || A1 == A2 && B1 <= B2) ? <A1,B1> : <A2,B2> 134 * We want to complete the force first, then the combo with the 135 * fewest moves to win. 136 * Different colors, <A1,B1> is the combo for the player with the next move: 137 * <A',B'> = A2 <= 1 && (A1 > 1 || A2 + B2 < A1 + B1) ? <A2,B2> : <A1,B1> 138 * We want to block only if we have to (i.e., if they are one move away 139 * from completing a force and we don't have a force that we can 140 * complete which takes fewer or the same number of moves to win). 141 */ 142 143 #define MAXA 6 144 #define MAXB 2 145 #define MAXCOMBO 0x600 146 147 union comboval { 148 struct { 149 #if BYTE_ORDER == BIG_ENDIAN 150 u_char a; /* # moves to complete force */ 151 u_char b; /* # moves to win */ 152 #endif 153 #if BYTE_ORDER == LITTLE_ENDIAN 154 u_char b; /* # moves to win */ 155 u_char a; /* # moves to complete force */ 156 #endif 157 } c; 158 u_short s; 159 }; 160 161 /* 162 * This structure is used to record information about single frames (F) and 163 * combinations of two more frames (C). 164 * For combinations of two or more frames, there is an additional 165 * array of pointers to the frames of the combination which is sorted 166 * by the index into the frames[] array. This is used to prevent duplication 167 * since frame A combined with B is the same as B with A. 168 * struct combostr *c_sort[size c_nframes]; 169 * The leaves of the tree (frames) are numbered 0 (bottom, leftmost) 170 * to c_nframes - 1 (top, right). This is stored in c_frameindex and 171 * c_dir if C_LOOP is set. 172 */ 173 struct combostr { 174 struct combostr *c_next; /* list of combos at the same level */ 175 struct combostr *c_prev; /* list of combos at the same level */ 176 struct combostr *c_link[2]; /* C:previous level or F:NULL */ 177 union comboval c_linkv[2]; /* C:combo value for link[0,1] */ 178 union comboval c_combo; /* C:combo value for this level */ 179 u_short c_vertex; /* C:intersection or F:frame head */ 180 u_char c_nframes; /* number of frames in the combo */ 181 u_char c_dir; /* C:loop frame or F:frame direction */ 182 u_char c_flg; /* C:combo flags */ 183 u_char c_frameindex; /* C:intersection frame index */ 184 u_char c_framecnt[2]; /* number of frames left to attach */ 185 u_char c_emask[2]; /* C:bit mask of completion spots for 186 * link[0] and link[1] */ 187 u_char c_voff[2]; /* C:vertex offset within frame */ 188 }; 189 190 /* flag values for c_flg */ 191 #define C_OPEN_0 0x01 /* link[0] is an open ended frame */ 192 #define C_OPEN_1 0x02 /* link[1] is an open ended frame */ 193 #define C_LOOP 0x04 /* link[1] intersects previous frame */ 194 #define C_MARK 0x08 /* indicates combo processed */ 195 196 /* 197 * This structure is used for recording the completion points of 198 * multi frame combos. 199 */ 200 struct elist { 201 struct elist *e_next; /* list of completion points */ 202 struct combostr *e_combo; /* the whole combo */ 203 u_char e_off; /* offset in frame of this empty spot */ 204 u_char e_frameindex; /* intersection frame index */ 205 u_char e_framecnt; /* number of frames left to attach */ 206 u_char e_emask; /* real value of the frame's emask */ 207 union comboval e_fval; /* frame combo value */ 208 }; 209 210 /* 211 * One spot structure for each location on the board. 212 * A frame consists of the combination for the current spot plus the five spots 213 * 0: right, 1: right & down, 2: down, 3: down & left. 214 */ 215 struct spotstr { 216 short s_occ; /* color of occupant */ 217 short s_wval; /* weighted value */ 218 int s_flg; /* flags for graph walks */ 219 struct combostr *s_frame[4]; /* level 1 combo for frame[dir] */ 220 union comboval s_fval[2][4]; /* combo value for [color][frame] */ 221 union comboval s_combo[2]; /* minimum combo value for BLK & WHT */ 222 u_char s_level[2]; /* number of frames in the min combo */ 223 u_char s_nforce[2]; /* number of <1,x> combos */ 224 struct elist *s_empty; /* level n combo completion spots */ 225 struct elist *s_nempty; /* level n+1 combo completion spots */ 226 int dummy[2]; /* XXX */ 227 }; 228 229 /* flag values for s_flg */ 230 #define CFLAG 0x000001 /* frame is part of a combo */ 231 #define CFLAGALL 0x00000F /* all frame directions marked */ 232 #define IFLAG 0x000010 /* legal intersection point */ 233 #define IFLAGALL 0x0000F0 /* any intersection points? */ 234 #define FFLAG 0x000100 /* frame is part of a <1,x> combo */ 235 #define FFLAGALL 0x000F00 /* all force frames */ 236 #define MFLAG 0x001000 /* frame has already been seen */ 237 #define MFLAGALL 0x00F000 /* all frames seen */ 238 #define BFLAG 0x010000 /* frame intersects border or dead */ 239 #define BFLAGALL 0x0F0000 /* all frames dead */ 240 241 /* 242 * This structure is used to store overlap information between frames. 243 */ 244 struct ovlp_info { 245 int o_intersect; /* intersection spot */ 246 struct combostr *o_fcombo; /* the connecting combo */ 247 u_char o_link; /* which link to update (0 or 1) */ 248 u_char o_off; /* offset in frame of intersection */ 249 u_char o_frameindex; /* intersection frame index */ 250 }; 251 252 extern char *letters; 253 extern char fmtbuf[128]; 254 extern char pdir[]; 255 256 extern int dd[4]; 257 extern struct spotstr board[BAREA]; /* info for board */ 258 extern struct combostr frames[FAREA]; /* storage for single frames */ 259 extern struct combostr *sortframes[2]; /* sorted, non-empty frames */ 260 extern u_char overlap[FAREA * FAREA]; /* frame [a][b] overlap */ 261 extern short intersect[FAREA * FAREA]; /* frame [a][b] intersection */ 262 extern int movelog[BSZ * BSZ]; /* history of moves */ 263 extern int movenum; 264 extern int debug; 265 266 void addframes(int); 267 void appendcombo(struct combostr *); 268 void ask(char *); 269 void bdinit(struct spotstr *); 270 void bdisp(void); 271 void bdisp_init(void); 272 #ifdef DEBUG 273 void bdump(FILE *); 274 #endif 275 void bdwho(int); 276 int better(struct spotstr *, struct spotstr *, int); 277 int checkframes(struct combostr *, struct combostr *, 278 struct spotstr *, int, struct ovlp_info *); 279 #ifdef DEBUG 280 void clearcombo(struct combostr *, int); 281 #endif 282 int ctos(char *); 283 void cursfini(void); 284 void cursinit(void); 285 void dislog(char *); 286 void dlog(char *); 287 int getcoord(void); 288 int get_line(char *, int); 289 void init_overlap(void); 290 #ifdef DEBUG 291 int list_eq(struct combostr **, struct combostr **, int); 292 #endif 293 void logit(char *); 294 int lton(int); 295 void makecombo(struct combostr *, struct spotstr *, int, int); 296 void makecombo2(struct combostr *, struct spotstr *, int, int); 297 void makeempty(struct combostr *); 298 int makemove(int, int); 299 #ifdef DEBUG 300 void markcombo(struct combostr *); 301 #endif 302 void panic(char *); 303 int pickmove(int); 304 void printcombo(struct combostr *, char *, size_t); 305 void qlog(char *); 306 __dead void quit(int); 307 int readinput(FILE *); 308 void scanframes(int); 309 int sortcombo(struct combostr **, struct combostr **, struct combostr *); 310 char *stoc(int); 311 void updatecombo(struct combostr *, int); 312 void update_overlap(struct spotstr *); 313 #ifdef DEBUG 314 void whatsup(int); 315 #endif 316 317 #define ASSERT(x) 318