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