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