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