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. */ 67typedef unsigned char player_color; 68 69/* A spot on the board, or one of the special values below. */ 70typedef 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 */ 129union 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 */ 157struct 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 */ 188struct 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'. */ 199typedef unsigned short frame_index; 200 201/* 0 = right, 1 = down right, 2 = down, 3 = down left. */ 202typedef 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 */ 213struct 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 238static inline bool 239is_blocked(const struct spotstr *sp, direction r) 240{ 241 return (sp->s_flags & (BFLAG << r)) != 0; 242} 243 244static inline void 245set_blocked(struct spotstr *sp, direction r) 246{ 247 sp->s_flags |= BFLAG << r; 248} 249 250struct 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 259extern const char letters[]; 260extern const char pdir[]; 261 262extern const int dd[4]; 263extern struct spotstr board[BAREA]; /* info for board */ 264extern struct combostr frames[FAREA]; /* storage for single frames */ 265extern struct combostr *sortframes[2]; /* sorted, non-empty frames */ 266extern u_char overlap[FAREA * FAREA]; 267extern spot_index intersect[FAREA * FAREA]; /* frame [a][b] intersection */ 268extern struct game game; 269extern int debug; 270 271extern bool interactive; 272extern const char *plyr[]; 273 274void init_board(void); 275spot_index get_coord(void); 276int get_key(const char *); 277bool get_line(char *, int, void (*)(const char *)); 278void ask(const char *); 279void dislog(const char *); 280void bdump(FILE *); 281void bdisp(void); 282void bdisp_init(void); 283void cursfini(void); 284void cursinit(void); 285void bdwho(void); 286void panic(const char *, ...) __printflike(1, 2) __dead; 287void debuglog(const char *, ...) __printflike(1, 2); 288void whatsup(int); 289const char *stoc(spot_index); 290spot_index ctos(const char *); 291int makemove(player_color, spot_index); 292void clearcombo(struct combostr *, int); 293void markcombo(struct combostr *); 294spot_index pickmove(player_color); 295#if defined(DEBUG) 296void printcombo(struct combostr *, char *, size_t); 297#endif 298