1 /* $NetBSD: gomoku.h,v 1.56 2022/06/19 10:23:48 rillig 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 <sys/endian.h> 39 #include <stdbool.h> 40 #include <stdio.h> 41 42 /* 43 * The gomoku 'board' mainly consists of the playing area of BSZ x BSZ spots. 44 * The playing area uses 1-based coordinates. Around the playing area is a 45 * rectangle of border spots, to avoid having to check the coordinates when 46 * calculating spot coordinates. The left and right border overlap, to save a 47 * few bytes. 48 */ 49 50 #define BSZ 19 51 #define BAREA ((1 + BSZ + 1) * (BSZ + 1) + 1) 52 53 /* 54 * A 'frame' is a group of five or six contiguous spots on the board. An 55 * open-ended frame is one with spaces on both ends; otherwise, it is closed. 56 */ 57 #define FAREA (2 * BSZ * (BSZ - 4) + 2 * (BSZ - 4) * (BSZ - 4)) 58 59 60 /* The content of a spot on the board; used in s_occ. */ 61 #define BLACK 0 62 #define WHITE 1 63 #define EMPTY 2 64 #define BORDER 3 65 66 /* Either BLACK or WHITE. */ 67 typedef unsigned char player_color; 68 69 /* A spot on the board, or one of the special values below. */ 70 typedef unsigned short spot_index; 71 #define PT(x, y) ((x) + (BSZ + 1) * (y)) 72 /* return values for makemove, readinput */ 73 #define MOVEOK 0 74 #define RESIGN 1 75 #define ILLEGAL 2 76 #define WIN 3 77 #define TIE 4 78 #define SAVE 5 79 #define END_OF_INPUT 6 80 81 /* 82 * A 'combo' is a group of intersecting or overlapping frames and consists of 83 * two numbers: 84 * 'F' is the number of moves still needed to make the combo non-blockable. 85 * 'W' is the minimum number of moves needed to win once it can't be blocked. 86 * 87 * A 'force' is a combo that is one move away from being non-blockable. 88 * 89 * Each time a frame is added to the combo, the number of moves to complete 90 * the force is the number of moves needed to 'fill' the frame plus one at 91 * the intersection point. The number of moves to win is the number of moves 92 * to complete the best frame minus the last move to complete the force. 93 * Note that it doesn't make sense to combine a <1,x> with anything since 94 * it is already a force. Also, the frames have to be independent so a 95 * single move doesn't affect more than one frame making up the combo. 96 * 97 * Rules for comparing which of two combos (<F1,W1> <F2,W2>) is better: 98 * Both the same color: 99 * <F',W'> = (F1 < F2 || F1 == F2 && W1 <= W2) ? <F1,W1> : <F2,W2> 100 * We want to complete the force first, then the combo with the 101 * fewest moves to win. 102 * Different colors, <F1,W1> is the combo for the player with the next move: 103 * <F',W'> = F2 <= 1 && (F1 > 1 || F2 + W2 < F1 + W1) ? <F2,W2> : <F1,W1> 104 * We want to block only if we have to (i.e., if they are one move away 105 * from completing a force, and we don't have a force that we can 106 * complete which takes fewer or the same number of moves to win). 107 */ 108 109 /* 110 * Single frame combo values: 111 * <F,W> board values 112 * 5,0 . . . . . O 113 * 4,1 . . . . . . 114 * 4,0 . . . . X O 115 * 3,1 . . . . X . 116 * 3,0 . . . X X O 117 * 2,1 . . . X X . 118 * 2,0 . . X X X O 119 * 1,1 . . X X X . 120 * 1,0 . X X X X O 121 * 0,1 . X X X X . 122 * 0,0 X X X X X O 123 * 124 * The rule for combining two combos (<F1,W1> <F2,W2>) with V valid 125 * intersection points is: 126 * F' = F1 + F2 - 2 - V 127 * W' = MIN(F1 + W1 - 1, F2 + W2 - 1) 128 */ 129 union comboval { 130 struct { 131 #if BYTE_ORDER == BIG_ENDIAN 132 u_char a; 133 u_char b; 134 #endif 135 #if BYTE_ORDER == LITTLE_ENDIAN 136 u_char b; 137 u_char a; 138 #endif 139 } c; 140 u_short s; 141 }; 142 #define cv_force c.a /* # moves to complete force */ 143 #define cv_win c.b /* # moves to win */ 144 145 /* 146 * This structure is used to record information about single frames (F) and 147 * combinations of two more frames (C). 148 * For combinations of two or more frames, there is an additional 149 * array of pointers to the frames of the combination which is sorted 150 * by the index into the frames[] array. This is used to prevent duplication 151 * since frame A combined with B is the same as B with A. 152 * struct combostr *c_sort[size c_nframes]; 153 * The leaves of the tree (frames) are numbered 0 (bottom, leftmost) 154 * to c_nframes - 1 (top, right). This is stored in c_frameindex and 155 * c_dir if C_LOOP is set. 156 */ 157 struct combostr { 158 struct combostr *c_next; /* list of combos at the same level */ 159 struct combostr *c_prev; /* list of combos at the same level */ 160 struct combostr *c_link[2]; /* F: NULL, 161 * C: previous level */ 162 union comboval c_linkv[2]; /* C: combo value for link[0, 1] */ 163 union comboval c_combo; /* F: initial combo value (read-only), 164 * C: combo value for this level */ 165 spot_index c_vertex; /* F: frame head, 166 * C: intersection */ 167 u_char c_nframes; /* F: 1, 168 * C: number of frames in the combo */ 169 u_char c_dir; /* F: frame direction, 170 * C: loop frame */ 171 u_char c_flags; /* C: combo flags */ 172 u_char c_frameindex; /* C: intersection frame index */ 173 u_char c_framecnt[2]; /* number of frames left to attach */ 174 u_char c_emask[2]; /* C: bit mask of completion spots for 175 * link[0] and link[1] */ 176 u_char c_voff[2]; /* C: vertex offset within frame */ 177 }; 178 179 /* flag values for c_flags */ 180 #define C_OPEN_0 0x01 /* link[0] is an open-ended frame */ 181 #define C_OPEN_1 0x02 /* link[1] is an open-ended frame */ 182 #define C_LOOP 0x04 /* link[1] intersects previous frame */ 183 184 /* 185 * This structure is used for recording the completion points of 186 * multi frame combos. 187 */ 188 struct elist { 189 struct elist *e_next; /* list of completion points */ 190 struct combostr *e_combo; /* the whole combo */ 191 u_char e_off; /* offset in frame of this empty spot */ 192 u_char e_frameindex; /* intersection frame index */ 193 u_char e_framecnt; /* number of frames left to attach */ 194 u_char e_emask; /* real value of the frame's emask */ 195 union comboval e_fval; /* frame combo value */ 196 }; 197 198 /* The index of a frame in the global 'frames'. */ 199 typedef unsigned short frame_index; 200 201 /* 0 = right, 1 = down right, 2 = down, 3 = down left. */ 202 typedef unsigned char direction; 203 #define DIR__R 0 /* right */ 204 #define DIR_DR 1 /* down right */ 205 #define DIR_D_ 2 /* down */ 206 #define DIR_DL 3 /* down left */ 207 208 /* 209 * One spot structure for each location on the board. 210 * A frame consists of the combination for the current spot plus the next 211 * five spots in the direction. 212 */ 213 struct spotstr { 214 short s_occ; /* color of occupant */ 215 short s_wval; /* weighted value */ 216 int s_flags; /* flags for graph walks */ 217 frame_index s_frame[4]; /* level 1 combo for [dir] */ 218 union comboval s_fval[2][4]; /* combo value for [color][dir] */ 219 union comboval s_combo[2]; /* minimum combo value for [color] */ 220 u_char s_level[2]; /* number of frames in the min combo */ 221 u_char s_nforce[2]; /* number of <1,x> combos */ 222 struct elist *s_empty; /* level n combo completion spots */ 223 struct elist *s_nempty; /* level n+1 combo completion spots */ 224 }; 225 226 /* flag values for s_flags */ 227 #define CFLAG 0x000001 /* frame is part of a combo */ 228 #define CFLAGALL 0x00000F /* all frame directions marked */ 229 #define IFLAG 0x000010 /* legal intersection point */ 230 #define IFLAGALL 0x0000F0 /* any intersection points? */ 231 #define FFLAG 0x000100 /* frame is part of a <1,x> combo */ 232 #define FFLAGALL 0x000F00 /* all force frames */ 233 #define MFLAG 0x001000 /* frame has already been seen */ 234 #define MFLAGALL 0x00F000 /* all frames seen */ 235 #define BFLAG 0x010000 /* frame intersects border or dead */ 236 #define BFLAGALL 0x0F0000 /* all frames dead */ 237 238 static inline bool 239 is_blocked(const struct spotstr *sp, direction r) 240 { 241 return (sp->s_flags & (BFLAG << r)) != 0; 242 } 243 244 static inline void 245 set_blocked(struct spotstr *sp, direction r) 246 { 247 sp->s_flags |= BFLAG << r; 248 } 249 250 struct game { 251 unsigned int nmoves; /* number of played moves */ 252 spot_index moves[BSZ * BSZ]; /* log of all played moves */ 253 spot_index win_spot; /* the winning move, or 0 */ 254 direction win_dir; 255 int user_x; 256 int user_y; 257 }; 258 259 extern const char letters[]; 260 extern const char pdir[]; 261 262 extern const int dd[4]; 263 extern struct spotstr board[BAREA]; /* info for board */ 264 extern struct combostr frames[FAREA]; /* storage for single frames */ 265 extern struct combostr *sortframes[2]; /* sorted, non-empty frames */ 266 extern u_char overlap[FAREA * FAREA]; 267 extern spot_index intersect[FAREA * FAREA]; /* frame [a][b] intersection */ 268 extern struct game game; 269 extern int debug; 270 271 extern bool interactive; 272 extern const char *plyr[]; 273 274 void init_board(void); 275 spot_index get_coord(void); 276 int get_key(const char *); 277 bool get_line(char *, int, void (*)(const char *)); 278 void ask(const char *); 279 void dislog(const char *); 280 void bdump(FILE *); 281 void bdisp(void); 282 void bdisp_init(void); 283 void cursfini(void); 284 void cursinit(void); 285 void bdwho(void); 286 void panic(const char *, ...) __printflike(1, 2) __dead; 287 void debuglog(const char *, ...) __printflike(1, 2); 288 void whatsup(int); 289 const char *stoc(spot_index); 290 spot_index ctos(const char *); 291 int makemove(player_color, spot_index); 292 void clearcombo(struct combostr *, int); 293 void markcombo(struct combostr *); 294 spot_index pickmove(player_color); 295 #if defined(DEBUG) 296 void printcombo(struct combostr *, char *, size_t); 297 #endif 298
Indexes created Sat Sep 20 22:09:52 GMT 2025